Введение
Лидирующее положение среди технологий, используемых при создании локальных сетей, принадлежит технологии Ethernet. Данная технология предусматривает использование метода доступа к единой среде передачи данных CSMA/CD : [2, с. 21]. Метод носит вероятностный характер, который не гарантирует успешность передачи сообщения в случае высокой интенсивности сетевого трафика. Здесь нет возможности приоритетного доступа и по этой причине сети, использующие данный метод доступа, плохо приспособлены для решения задач управления в реальном масштабе времени. Доступ по схеме CSMA/CD (из-за столкновений) предполагает ограничение на минимальную длину пакета. По существу, этот метод доступа предполагает широковещательную передачу пакетов. Все рабочие станции логического сетевого сегмента воспринимают эти пакеты хотя бы частично, чтобы прочесть адресную часть. Логика поведения субъектов в сети с доступом CSMA/CD может варьироваться. Здесь существенную роль играет то, синхронизовано ли время доступа у этих субъектов. В случае сети Ethernet такой синхронизации нет. Некоторые видоизменения алгоритма доступа CSMA/CD позволяют устранить такие недостатки сетей Ethernet, как:
- возможность коллизий;
- ограничение на минимальную длину пакета;
- невозможность приоритетного обслуживания абонентов;
- невозможность использования таких сетей для решения задач управления в реальном масштабе времени.
В статье приведены результаты исследований зависимости вероятности возникновения коллизии от выбора момента начала передачи сообщения, рассмотрены возможности коррекции протоколов Ethernet с целью повышения эффективности работы сети в условиях высокой интенсивности передаваемого трафика.
Математическая модель сети Ethernet
Локальная сеть на основе повторителя, построенная с использованием топологии «пассивная звезда», представляется как одноканальная система массового обслуживания с ожиданием [1, с. 326]при неограниченном числе мест в очереди (Рис. 1). В табл. 1 приведены характеристики состояний системы, где ρ=λ/μ.
Рисунок 1. Сеть Ethernet, как система массового обслуживания
Таблица 1
Характеристика состояний системы на основе повторителя
Сеть Ethernet на основе коммутатора может быть представлена как одноканальная система массового обслуживания с ожиданием при ограниченном числе мест m в очереди (Рис. 2). Число мест в очереди ограничивается размерами буферной памяти коммутатора. В табл. 2 приведены характеристики состояний системы.
Так как потоки событий (поступления заявок и выполнения заявок) в случае локальной сети Ethernet являются стационарными, то есть вероятность появления n событий на интервале времени (t, t+x) не зависит от времени t, а зависит только от длины этого участка, интенсивности λ и μ могут быть подсчитаны как среднее число событий в единицу времени. То есть λ(t) = λ = const и μ (t) = μ = const.
Матрица вероятностей
Основной топологией локальной сети, построенной по технологии Fast Ethernet, является топология «пассивная звезда». На рис. 3 приведён пример структуры такой сети, объединяющей десять компьютеров. Отдельные физические сегменты сети, объединённые при помощи концентратора, представляют собой общую среду передачи данных, разделяемую конечными узлами сети. Метод CSMA/CD предполагает прослушивание станциями канала связи на предмет наличия в нём несущей, что является признаком его занятости. Вследствие распределённого характера сети передаваемое сообщение не одновременно достигает всех узлов сети. Поэтому возможна ситуация, когда станция начинает передачу своего сообщения в то время, когда среда передачи уже занята. В результате происходит столкновение передаваемых кадров и их искажение. Это явление получило название коллизии. Вероятности возникновения явления коллизии в сетях Fast Ethernet в зависимости от расстояния между конфликтующими станциями, а также в зависимости от интервала времени между моментами начала передачи сообщений этими станциями могут быть представлены в виде матрицы вероятностей (рис. 4). Оцениваемый интервал времени разбит на n битовых интервалов. Ширина W области битовых интервалов с ненулевой вероятностью зависит от расстояния между конфликтующими станциями и тем больше, чем больше это расстояние.
Вероятность коллизии будет нулевой, если выполняется условие:
где 
(1)
i— номер битового интервала — начала передачи кадра станцией a (PCi);
j— номер битового интервала — начала передачи кадра станцией b(PCj);
La — длина физического сегмента станции a;
Рисунок 4. Матрица вероятностей
Lb — длина физического сегмента станции b;
V — скорость распространения сигнала по каналу связи.
Если предположить, что вероятность передачи кадра каждой станцией на оцениваемом интервале времени равна 0.5, то вероятность начала передачи кадра на i ( j ) битовом интервале равна 0.5/ n. Вероятность коллизии в клетке матрицы, принадлежащей области ненулевых коллизий, определяется по формуле:
Каждой возможной паре конфликтующих станций соответствует своя матрица вероятностей. Очевидно, что количество матриц Z может быть подсчитано по формуле:
где m— количество станций в сети.
Полная вероятность коллизии с учётом вероятностей для всех возможных пар конфликтующих станций будет определяться по формуле:
Pij=∑pijk , (4)
где pijk— вероятность возникновения коллизии для k— той пары станций.
Механизм включения временного разделения канала связи
В случае повышения интенсивности сетевого трафика, когда процент потерянных пакетов превысит установленный порог, время использования канала связи начинает делиться между узлами сети. Механизм включения (выключения) временного разделения основан на использовании статистического метода последовательного анализа [1, с. 29]. Это метод статистического исследования при проверке гипотез, при котором после каждого наблюдения производится анализ всех предыдущих наблюдений случайной величины x. В нашем случае применения этого статистического метода проверяются две конкурирующие гипотезы: H0— «Временное разделение канала необходимо»; H1— «Необходимости временного разделения канала нет». В роли случайной величины x выступает количество потерянных пакетов на m-м испытании. Метод последовательной проверки гипотезы H0 относительно гипотезы H1 основан на применении на каждой стадии эксперимента (m-м испытании) некоторого правила принятия одного из трёх возможных решений. Правило определяет три попарно-непересекающиеся области Rm0, Rm1 и Rm множества всех возможных выборок (x1, … , xm) объёма m, таких, что если наблюдённая выборка, начиная с m=1, попала в область Rm0, то принимается 1-е решение (гипотеза H0), если в область Rm, то эксперимент продолжается и проводится очередное m+1— е испытание.
Область Rm1 называется критической областью W и однозначно определяется ошибками двух родов. Ошибка 1-го рода, если отклоняется гипотеза H0, в то время как она истинна. Ошибка 2-го рода— если гипотеза H0 принимается, в то время как истинна конкурирующая гипотеза H1. Вероятность ошибки 1-го рода α равна вероятности попадания наблюдённой выборки в критическую область W, вычисленной при гипотезе H0, а вероятность ошибки 2-го рода β- вероятности непопадания выборки в область W, вычисленной при гипотезе H1.
Процесс последовательной проверки характеризуется допускаемым риском, связанным с принятием неверных решений. Допускаемый риск определяется выбором четырёх чисел: ошибками 1-го рода (α) и 2-го рода (β), а также верхней (Q0) и нижней (Q1) границами областей принятия и отклонения проверяемой гипотезы.
Ошибки α и β и значения Q0 и Q1 выбираются на основе оценки последствий, к которым приводит неправильное решение, так чтобы вероятность принятия гипотезы H0 не превышала величины α, когда истинное значение неизвестного параметра Q<=Q0 и вероятность не принятия гипотезы H0 не превышала β, когда Q>=Q1.
Методика проведения последовательного анализа.
3)На m-м испытании вычисляется число потерянных кадров
m
dm = ∑xi (12)
i=1
и проверяется условие am <dm< rm .
Если am <dm< rm— может быть принята любая гипотеза,
если dm ≥ rm— принимается гипотеза H0, а
если dm ≤ am — принимается гипотеза H1.
Пример. Путём моделирования варианта сеанса связи проверить целесообразность принятия гипотезы H0. Приём гипотезы H0 («Временное разделение канала необходимо»), будем считать целесообразным, если ему соответствует вероятность успешной передачи пакета W >= 0,8. Пусть с вероятностью α ≤ 0,02 допустимо принятие решения о том, что приём гипотезы H0 целесообразен, хотя W < 0,7, и пусть с вероятностью β ≤ 0,03 также допустимо принятие альтернативной гипотезы H1 ( «Необходимости временного разделения канала нет»), хотя W >0,9. Таким образом, требуется проверить целесообразность приёма гипотезы H0 при допускаемом риске:
Q0 = 1 – 0.9 = 0.1; Q1 = 1- 0.7 = 0.3;. α = 0.02; β = 0.03
Решение. 1. Проверка целесообразности приёма гипотезы H0.
а) По формулам (10, 11) рассчитываются am и rm и заносятся в табл. 3.
Таблица 3
Результаты проверки целесообразности принятия гипотезы H0
| m | am | dm | rm | m | am | dm | rm | |
| 1 | -2 | 0 | 3 | 12 | 0 | 2 | 5 | |
| 2 | -2 | 0 | 3 | 13 | 0 | 3 | 5 | |
| 3 | -2 | 1 | 3 | 14 | 0 | 3 | 5 | |
| 4 | -2 | 1 | 4 | 15 | 0 | 4 | 6 | |
| 5 | -2 | 1 | 4 | 16 | 0 | 5 | 6 | |
| 6 | -1 | 1 | 4 | 17 | 1 | 6 | 6 | |
| 7 | -1 | 1 | 4 | 18 | 1 | 6 | ||
| 8 | -1 | 1 | 4 | 19 | 1 | 6 | ||
| 9 | -1 | 2 | 5 | 20 | 1 | 7 | ||
| 10 | -1 | 2 | 5 | 21 | 1 | 7 | ||
| 11 | -1 | 2 | 5 | 22 | 2 | 7 |
б) Проводится моделирование. После каждого m = 1, 2, … вычисляется dm, заносится в табл. 3 и сравнивается с am и rm.
в) При m = 17 dm = rm. Проверка закончилась. Гипотеза H0 принимается.
Алгоритм приоритетного доступа к каналу передачи данных
Предлагаемый алгоритм приоритетного доступа основывается на статистическом законе больших чисел. Предположим, что в составе ЛВС находятся станции S1, S2,…Sz. Начальные вероятности поступления заявок на передачу сообщений станциями сети на i-том битовом интервале соответственно равны P1, P2,…Pz. Начальные вероятности могут быть подсчитаны на основе статистики, собранной за N битовых интервалов, по формуле:
Pi = Mi / N, где
Mi — число заявок поступивших от i – той станции.
При этом должно выполняться условие:
∑ Pi =1
В течении следующих K битовых интервалов собирается статистика по числу поступивших заявок по каждой станции ЛВС. По закону больших чисел вероятность поступления заявки от станции Si на передачу сообщения на (K+1) битовом интервале может быть подсчитана по формуле:
PK+1 i =(Mi – Li ) / (N – K),
где Mi – предполагаемое число заявок, которые поступят от i – той станции в течении N битовых интервалов при начальной вероятности Pi; Li – число заявок, поступивших в течении К битовых интервалов.
При этом должно выполняться условие:
∑ PK+1 i =1
Начиная с (К + 1) – го битового интервала среда передачи предоставляется станциям в порядке убывания вероятностей PK+1 i .
Заключение
Недостатки, присущие сетям, использующим метод доступа CSMA/CD, частично устраняются при реализации сети на основе коммутатора. Однако по причине ограниченности ёмкости буферного ЗУ коммутатора при высокой интенсивности потока заявок процент потерянных пакетов остаётся недопустимо высоким. Когда передача данных сталкивается с проблемой «бутылочного горлышка» для приёма и отправки пакетов на коммутаторах обычно используется метод FIFO: первый пришел — первый ушёл (First In — First Out). При интенсивном трафике это создаёт заторы, которые разрешаются крайне простым образом: все пакеты, не вошедшие в буфер очереди FIFO (на вход или на выход), игнорируются коммутатором и, соответственно, теряются безвозвратно. Использование рассмотренного способа коррекции метода доступа позволяет увеличить пропускную способность сети Ethernet на основе коммутатора. В отличие от метода приоритетного доступа QoS предлагаемая организация доступа предполагает определение порядка станций в очереди на обслуживание, имеющих пакеты для передачи с одинаковыми метками типа сервиса.
Список литературы:
- Абчук В.А. Справочник по исследованию операций. — М.: Воениздат, 1975. – 157 с.
- Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. — СПб.: Питер, 2004. – 863 с.[schema type=»book» name=»КОРРЕКЦИЯ МЕТОДА ДОСТУПА В СЕТЯХ ETHERNET» description=»Предлагается использование математического аппарата теории массового обслуживания для моделирования процессов в локальной вычислительной сети. Рассматривается возможный вариант схемы временного разделения канала связи. Механизм включения (выключения) временного разделения основан на использовании статистического метода последовательного анализа.» author=»Сторожок Евгений Анатольевич, Сторожок Олег Евгеньевич» publisher=»БАСАРАНОВИЧ ЕКАТЕРИНА» pubdate=»2017-01-25″ edition=»ЕВРАЗИЙСКИЙ СОЮЗ УЧЕНЫХ_31.10.15_10(19)» ebook=»yes» ]