6.4. Множественный доступ с прослушиванием несущей и обнаружении столкновений. МДПН/ОС.

Этот метод является развитием метода чистой Алохи и позволяет улучшить ее характеристики. Метод МДПН/ОС (в оригинале CSMA/CD) входит в протокол сети Ethernet и является одним из стандартных методов в ЛВС (стандарт IEEE 802.3).

Рассмотрим основную идею метода CSMA/CD.

Все станции прослушивают передачу по линии.  Станция, желающая передать сообщение, выходит на связь только после обнаружения свободного состояния канала. Эта процедура называется проверкой несущей (ПН), а соответствующая стратегия доступа - МДПН.

Очевидно, столкновение все же может возникнуть из-за того, что станции физически разнесены одна от другой, а время распространения сигнала t - конечно. Если столкновение все же происходит и станции его обнаруживают (ОС), то они передают сигнал о помехе, и отменяют свои передачи.

Был предложен и проанализирован ряд методов МДПН, они различаются тем, как происходит управление передачей, если канал окажется занятым.

Например, в схеме с р-настойчивостью станция, обнаружившая занятым канал, осуществляет передачу после того, как канал освободится с вероятностью р, и с вероятностью 1-р, отказывается от передачи на промежутке t , где t  - время распространения сигнала в линии.

При схеме с 1-настойчивостью станция осуществляет передачу сразу, как только канал окажется свободным.

При ненастойчивой схеме станция переносит передачу на другое случайное время (в соответствии с некоторым распределением задержек передачи).             

Все эти схемы рассчитаны на то, что станция сможет обнаружить конец передачи вскоре после ее завершения. Т.е. они требуют, чтобы        t<<m. Это условие обычно описывается параметром

a = t /m << 1.

Протокол МДПН/ОС (CSMA/CD), работающий по схеме с не настойчивостью, был принят в качестве стандартного протокола в ЛВС Ethernet. Если обнаруживается столкновение, и передача прекращается, то попытка повторной передачи предпринимается через случайный промежуток времени. как в схемах Алохи. Этот случайный промежуток удваивается каждый раз после обнаружения нового столкновения до некоторой максимальной величины, при которой станция выходит из строя и извещает вышестоящие условия о нарушении связи.

Расчет характеристик метода CSMA/CD.

Рассмотрим структуру с общей шиной  и пусть А и В - 2 наиболее удаленные станции (рис. 6.14). Рассчитаем среднее время для успешной передачи сообщения.

Рис. 6.14.

Сохраняя прежние обозначения назовем время до успешного завершения передачи сообщения - виртуальным временем tV. Оно включает время передачи кадра m, время t - необходимое для проверки завершения передачи и время кратное 2t для разрешения столкновений, если они возникнут.

Итак, пусть возникло столкновение между сигналами, передаваемыми станциями А и В. В худшем случае обнаружение столкновения займет на станциях А и В время 2t сек, после чего передача будет выключена.

Рис. 6.15. Расчет величины tV в методе CSMA/CD.

Если произошло столкновение, то предположим, что нам требуется еще 2tI ед. времени для его разрешения, где I - среднее число повторных передач, после того как столкновение произошло. Оно сопоставимо с параметром n = G/S - 1, который был введен для чистой Алохи. Тогда

tV=m+t+2t*I=m[1+a(1+2I)],                                                                               (6.19)

где aºt/m.

Теперь необходимо найти величину I. Она зависит от  стратегии повторных передач.

Предположим, что длительность интервала столкновений описывается геометрическим распределением единиц, кратных 2t, с параметром n. В частности, этот интервал равен 2t с вероятностью n, 4t с вероятностью n(1-n), 6t с вероятностью n(1-n)2. Т.о. n является вероятностью успеха, а (1-n) - вероятностью неуспеха, т.е. столкновения.

Тогда среднее число повторных попыток передач

                                                                                                        (6.20)

Теперь необходимо найти n. Пусть в передаче может участвовать n станций (n>>1). Пусть вероятность того, что 1 станция намеревается передавать в промежутке 2t равна р. Тогда вероятность, что передает точно 1 станция и эта передача успешна (столкновения нет), равна

n=np(1-p)n-1.                                                                                                                                      (6.21)

Будем искать maxp n(p). Легко проверить, что величина р0=1/n максимизирует n(p). Учитывая, что n>>1, в пределе получим

.                                                                                                            (6.22)

Т.о. величина  и I=1/n=e.

В результате найдем время успешной передачи

tV=m[1+a(1+2e)],                                                                                                                               (6.23)

где a=t/m.

Тогда максимальная производительность протокола

lmax=1/tV , a rmax=lmax×m=                                                                                 (6.24)

Обозначим через l среднюю общую интенсивность передачи по каналу сообщений от всех станций, найдем нормированную пропускную способность (ПС) протокола CMSA/CD

  r=m< .

Пример.

Пусть а=0,1. Для этого значения имеем 0,6, что существенно лучше, чем для чистой Алохи (r=0,184) и синхронной Алохи (r=0,368).

Стандарты IEEE на ЛВС.

Стандарты на ЛВС 802 комиссией института IEEE. Эти стандарты рассматривают физический уровень и частично уровень канала, и согласуются с эталонной моделью ВОС/МОС.

В настоящее время наиболее известны следующие стандарты на ЛВС:

n   IEEE 802.3 на ЛВС с общей шиной и методом доступа CSMA/CD,

n   IEEE 802.4 на ЛВС с общей шиной и передачей маркера,

n   IEEE 802.5 на ЛВС кольцевой структуры с передачей маркера.

Стандарт IEEE 802.3.

Первая работа по созданию метода случайного доступа CSMA/CD была выполнена компанией XEROX, которая создала сеть Ethernet. Она в дальнейшем получила развитие, и совместными усилиями компаний DEC, Intel и XEROX была разработана подробная спецификация, которая в дальнейшем была утверждена как стандарт IEEE 802.3.

Стандарт IEEE 802.5 на кольцо с передачей маркера основан на разработках Цюрихской ХИЛ фирмы IBM. Стандарты методов доступа, входящие в семейство IEEE 802. были разработаны в соответствии с эталонной моделью ВОС. Они охватывают физический и часть уровня канала этой модели.

Эти стандарты описывают форматы и протоколы, применяемые на подуровне управления доступом к передающей среде уровня канала, а также на физическом уровне. В свою очередь все стандарты доступа связаны с вышестоящим уровнем. ВОС/МОС через стандарты логического управления каналом IEEE 802.2, который составляет верхнюю часть уровня канала.

Взаимосвязь между эталонной моделью ВОС/МОС и стандартами IEEE 802. для ЛВС приводятся на рис. 6.16.

Рис. 6.16.

Дадим краткую характеристику стандартов IEEE 802. Канальный уровень ВЛВС делится на 2 подуровня: подуровень управления логическим звеном (УЛЗ) и подуровень управления доступом к передающей среде (УДС).

Подуровень УЛЗ с точки зрения стандартной модели ВОС пользуется услугами подуровня управления доступом к передающей среде (УДС) для предоставления услуг сетевому и другим вышестоящим уровням. УЛЗ выполняет также функции канала передачи данных, которые не зависят от типа передающей среды и методы доступа описаны 2 типа процедур управления ЛЗ.

Первый тип, называемый услугами соединения, выполняет функции восстановления сбоев, основанные на асинхронном балансном режиме (LAPB).

Второй тип, называемый услугой без соединения, не предоставляет возможности восстановления сбоев. Эта возможность для распределенных сетей предоставляет транспортный протокол 4 класса - ТП-4.

Одним из применений услуги без соединения подуровня УЛЗ может быть соединение ЛВС с широкополосной передающей средой, например по оптоволоконному каналу.

Локальная сеть Ethernet с методом CSMA/CD. Функции физического уровня сети Ethernet (стандарт IEEE 802.3) показаны на  рис. 6.17.

Рис. 6.17.

         Физический уровень осуществляет проверку наличия передачи в передающей среде, путем прослушивания канала и передает сигнал проверки несущей подуровню управления доступом к передающей среде.

Этот же уровень сравнивает сигнал в среде с сигналом, генерированным при передаче и выдает сигнал об обнаружении столкновения, если оно возникло. Эти функции выполняют блок доступа к каналу передачи. Для генерирования сигнала проверки несущей служат блоки доступа к каналу передачи и канала приема.   Эти сигналы генерируются подуровнем УДС канального уровня.

Кроме проверки двух сигналов блоки доступа к каналу передают символы в кабель и принимают их из кабеля. Блок кодирования передаваемых символов кодирует передаваемую информацию в двоичные сигналы с помощью так называемого <эманчестерского кода>. (см. рис. 6.18).

Рис. 6.18.Манчестерский код.

Функции подуровня УДС.

Структура подуровня УДС приведена на рис. 6.19.

Рис. 6.19.

Блоки управления каналом предотвращают столкновение, используя сигналы проверки несущей, и разрешают столкновения, используя сигналы обнаружения столкновений (ОС).

Формирование кадров, адресование и обнаружение ошибок выполняется блоками компоновки и декомпоновки кадров.

Информация по каналу передается в виде кадров. Формат кадра передается в виде кадров. Формат кадра сети Ethernet представлен на рис. 6.20.

Рис. 6.20.

Преамбула (7 октет) используются для целей синхронизации. Эти же функции выполняет начальный ограничитель (1 октет). Поле типа резервируется для вышестоящих уровней. В поле Данные приводится информация пользователя, размер его изменяется от 46 до 1500 октет.

В случае, если объем передаваемых данных меньше минимального размера (46 октет), то используется вспомогательное поле ЗАП (запас), для дополнения информационной части до 46 октет.

Поле ППК - проверочная последовательность кадра используется для контроля достоверности передаваемой информации и обнаружения ошибок.

Таким образом, размер кадра колеблется от 72 до 1526 октет.  

Спецификация сети Ethernet.

Спецификации сети Ethernet предусматривают физический канал в виде коаксиального кабеля со скоростью передачи 10 Мбит/с и             100 Мбит/с.

При такой скорости (10Мбит/с) общая длина коаксиального кабеля между двумя любыми приемопередатчиками (ПП) не превышает l£1500м. Скорость распространения сигнала в кабеле 4,33 мкс/км. При этой скорости время распространения сигнала 6,5 мкс. При самой короткой длине кадра 72 октет нижний предел время передачи кадра m=57,6 мкс, это дает величину a=t/m>0. И, что достаточно велико. Если поле данных увеличивается до 200 октет, то параметр а уменьшается до величины а=6,5/180=0,036, что гораздо лучше.

Кроме того, для обеспечения надлежащего времени восстановления управляющих устройств и физического канала принимается минимальное межкадровое время 9,6 мкс. При этом условии станция, желающая передать сообщение, должна задержать передачу по крайней мере на 9,6 мкс, после обнаружения конца кадра в канале, что снижает вероятность столкновений.

Станция сети Ethernet не обязательно должны быть подключены к одному и тому же кабелю. Отрезки кабеля могут быть соединены через т.н. регенераторы (или репитеры).

Типичные примеры конфигураций приведены на рис. 21. Отдельный сегмент кабеля не должен превышать l=500 м. В тракте между двумя РС не может быть более 3х регенераторов.

Максимальное число РС в любой части сети Ethernet равно 1024, причем в одном сегменте не может быть более 100 РС. Соединительный канал между регенераторами от одного конца до другого не может превышать 1000 м.

В сети Ethernet для управления повторными передачами применяется усеченный алгоритм двоичного замедления. После обнаружения столкновений задержка перед повторной передачей определяется как случайное число e канальных интервалов (по 512 разрядов), равномерно распределенных в диапазоне от 1 до 2n, где n - номер повторной попытки (n£10). В случае, когда число k повторных попыток превышает 10, то интервал задержки фиксируется на уровне 210 до достижения 15 попытки.

После этого событие столкновения интерпретируется как сбой, станция отключается от сети, и эта ситуация разрешается на вышестоящем уровне.

ЛВС с передачей маркера.

Рассмотрим организацию работы ЛВС с передачей маркера. В настоящее время наиболее известными являются следующие стандарты IEEE 802.4 - на шину с передачей маркера и IEEE 802.5 - на кольцо с передачей маркера (Token Ring).

Архитектуры этих ЛВС приведены на рис. 6.21 и 6.22.

Рис. 6.21 Шина с                                  Рис. 6.22 Кольцо с

передачей маркера                            передачей маркера

Все станции работают в децентрализованном режиме. Все сообщения (кадры) передаются по кольцу и активно повторяются каждой станцией, через которую они проходят. Станция, на которой в качестве адреса получателя считывается ее собственный адрес, копирует этот кадр во время его поразрядной передачи на следующую станцию кольца. Затем информация, содержащаяся в кадре, передается в терминалы или контроллеры, включенные на этой станции.

Циркулирующий кадр удаляется из кольца станцией, которая его передала, после его прохождения по кольцу и поступлению в источник. Время, требуемое для организации повторения кадра на станции, т.е. его задержки на данной станции называется латентным временем станции.        

Латентный период кольца - это величина, эквивалентна L, она равна сумме задержек t распространения сигнала по кольцу и латентного времени b/с станций

L=t+Nb/c.

Рассмотрим теперь технологию передачи маркера.

Пусть по кольцу циркулирует свободный маркер (специальный кадр).

Первая станция, имеющая данные для передачи, захватывает маркер и переходит к передаче, а по ее окончании передает маркер дальше.

Существует ряд стратегий выполнения этой операции.

Одна стратегия (подобная передаче управления) состоит в выдаче маркера в составе передаваемого кадра, т. о. следующая станция получает разрешение на передачу как только на рассматриваемой станции завершится передача последнего разряда кадра.

Другая стратегия состоит в передаче маркера только после того, как передающая станция получит обратно свое сообщение, прошедшее по кольцу.

Здесь возможны 2 версии:

1) ожидание того момента, пока не будет принято (и стерто) все сообщение;

2) выдача нового маркера, как только будет принят предыдущий.

В обоих случаях в кольце допускается в любой момент времени только 1 маркер. Определим среднее время tf необходимое для передачи данных от станции-источника до станции-назначения в кольце.

Оно в точности равно ранее приведенной формуле для циклического опроса с добавлением времени передачи кадра m и величины L/2 для учета задержки при распространении сигнала до получателя на пути, который в среднем равен половине длины кольца:

,                                                                   (6.25)

где r=Nl`m, m - длительность передачи кадра,

L=t+Nb/c b/c - латентное время станции.

Сравнение характеристик методов доступа CSMA/CD и кольца с передачей маркера. На рис.6.24 и 6.25 приводятся зависимости среднего времени задержки в доставке tf/m для методов доступа CSMA/CD и маркерного метода доступа в зависимости от загрузки r=lm, для различных скоростей передачи Vпер=1 Мбит/с и Vпер=10 Мбит/с.  Число станций N=50. Латентное время станции - 1 бит/ст.

Длина пакета распределена показательно со средней lср=1000 бит, заголовок - 24 разряда.

На рис. 6.26 приводится зависимость нормированной средней задержки для метода доступа CSMA/CD в зависимости от значений a=t/m для различных значений r=lm. В пределе при аR0

.

Рис. 6.24. Зависимость задержки передачи от производительности.

Рис.6.25.

Рис.6.26. Зависимость нормированной средней задержки от a=t/m.