Время оборота и распознавание коллизий

СЕТИ ЭВМ и ТЕЛЕКОММУНИКАЦИИ

Методические указания к лабораторной работе

«Исследование характеристик метода доступа в сетях Ethernet»

 

Составил А.А.Логинов

 

Рязань 2011

Лабораторная работа

«Исследование характеристик метода доступа в сетях Ethernet»

Цель работы

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

 

1 Метод доступом CSMA/CD в сети Ethernet

 

Метод доступа к разделяемой среде – моноканалу (МК) является одним из главных факторов, определяющих эффективность совместного использования этого общего ресурса сетевыми узлами (СУ) локальной сети. Метод доступа формирует «облик» технологии, позволяет отличать данную технологию от других. В технологии Ethernet применяется очень простой алгоритм доступа, позволяющий СУ передавать данные в те моменты времени, когда он считает, что МК свободен. Простота метода доступа определила простоту и низкую стоимость оборудования Ethernet. Негативным атрибутом метода доступа технологии Ethernet являются коллизии, то есть ситуации, когда кадры, передаваемые разными СУ, сталкиваются друг с другом в МК. Коллизии снижают пропускную способность сети и придают её работе непредсказуемый характер.

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

Используемый метод доступа к МК – CSMA/CD (Carrier-Sense Multiple Access with Collision Detection - множественный доступ с контролем несущей и обнаружением коллизий) относится к децентрализованным случайным методам. Он используется как в обычных сетях типа Ethernet, так и в высокоскоростных сетях (FastEthernet, GigaEthernet). Характеристики и области применения этих популярных на практике сетей связаны именно с особенностями используемого метода доступа CSMA/CD.

Передача кадра

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

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

 

Рис. 1. Метод случайного доступа CSMA/CD

 

остальные станции на этом прием кадра прекращают. Станция назначения обрабатывает полученные данные и передает их вверх по своему стеку протоколов.

Узел 2 во время передачи кадра узлом 1 также пытался начать передачу своего кадра, однако обнаруживает, что среда занята — на ней присутствует несущая частота, — поэтому узел 2 вынужден ждать, пока узел 1 не прекратит передачу кадра.

После окончания передачи кадра все узлы сети обязаны выдержать технологическую паузу, равную межпакетному интервалу (Inter Packet. Gap, IPG) в 9,6 мкс. Эта пауза нужна для приведения сетевых адаптеров в исходное состояние, а также для предотвращения монопольного захвата среды одной станцией. После окончания технологической паузы узлы имеют право начать передачу своего кадра, так как среда свободна. В приведенном примере узел 2 дождался окончания передачи кадра узлом 1, сделал паузу в 9,6 мкс и начал передачу своего кадра.

 

Возникновение коллизии

Механизм прослушивания среды и пауза между кадрами не гарантируют исключения ситуации,когда две или более станции одновременно решают, что среда свободна, и начинают передавать свои кадры. Говорят, что при этом происходит коллизия, так как содержимое обоих кадров сталкивается на общем кабеле и происходит искажение информации.

Коллизия — это нормальная ситуация в работе сетей Ethernet. В примере на рис. 1 и рис. 2 коллизию породила одновременная передача данных узлами 3 и 1. Для возникновения коллизии не обязательно, чтобы несколько станций начали передачу абсолютно одновременно, такая ситуация маловероятна. Более вероятна ситуация, когда один узел начинает передачу, а через некоторое (короткое) время другой узел, проверив среду и не обнаружив несущую (сигналы первого узла еще не успели до него дойти), начинает передачу своего кадра. Таким образом, возникновение коллизии является следствием распределения узлов сети в пространстве.

 

 

Рис. 2. Схема возникновения и распространения коллизии

 

Чтобы корректно обработать коллизию, все СУ одновременно прослушивают МК. Если передаваемые и принимаемые сигналы отличаются, то фиксируется факт обнаружения коллизии (Collision Detection, CD). Для повышения вероятности обнаружения коллизии всеми СУ сети тот СУ, который обнаружил коллизию, прерывает передачу своего кадра в произвольном месте, и усугубляет коллизию посылкой в сеть специальной последовательности из 32 бит, называемой jam-последовательностью (глушение). После этого обнаружившая коллизию передающий СУ обязана прекратить передачу и сделать паузу в течение случайного интервала времени τ. Затем СУ может снова предпринять попытку захвата МК и передачи кадра. Случайная пауза выбирается по следующему алгоритму:

τ = L х (интервал отсрочки).

В технологии Ethernet интервал отсрочкивыбран равным значению 512 битовых интервалов (BT – Bit Time). BT соответствует времени между появлением двух последовательных битов данных на кабеле; для скорости 10 Мбит/с величина BT равна 0,1 мкс, или 100 нс. Величина Lпредставляет собой целое число, выбранное с равной вероятностью из диапазона [0, 2min(10, N}],где N —номер повторной попытки передачи данного кадра: 1, 2, ..., 16. После 10-й попытки интервал, из которого выбирается пауза, не увеличивается.

Таким образом, максимально пауза τ может равновероятно принимать значения от 0 до 52,4 мс с дискретностью Δτ = 512 х BT = 0,0512 мс.

Если 16 последовательных попыток передачи кадра вызывают коллизию, то передатчик должен прекратить попытки и отбросить этот кадр. Описанный алгоритм носит название усеченного экспоненциального двоичного алгоритма отсрочки (Truncated binary exponential back off).

Число коллизий тем больше, чем больше диаметр (размер) МК и чем дальше расположены друг от друга СУ с интенсивным трафиком.

Поведение сети Ethernet при значительной нагрузке, когда коэффициент использования МК растет и начинает приближаться к 1, характеризуется большими задержками в передаче кадров из-за высокой вероятности коллизий и как следствие роста N и среднего значения паузы τ.

Администраторы сетей Ethernet на разделяемой среде руководствуются простым эмпирическим правилом — коэффициент использования среды не должен превышать 30-40 %. То есть для поддержки чувствительных к задержкам приложений в сети Ethernet можно применять только один подход — обеспечивать недогруженный режим работы.

 

Время оборота и распознавание коллизий

Надежное распознавание коллизий всеми СУ сети является необходимым условием корректной работы сети Ethernet. Если какая-либо передающая станция не распознает коллизию и решит, что кадр данных передан ею верно, этот кадр будет утерян. Из-за наложения сигналов при коллизии информация кадра исказится, и он будет отбракован принимающей станцией. Скорее всего, недошедшие до получателя данные будут повторно переданы каким-либо протоколом верхнего уровня, например транспортным или прикладным, работающим с установлением соединения, либо протоколом канального подуровня LLC. Однако повторная передача сообщения протоколами верхних уровней произойдет гораздо позже (иногда по прошествии нескольких секунд), чем повторная передача средствами сети Ethernet (первая попытка повторной передачи при N = 0 произойдет не более чем через τmax = 0,1024 мс). Поэтому если коллизии не будут надежно распознаваться узлами сети Ethernet, то это приведет к заметному снижению полезной пропускной способности сети.

Для надежного распознавания коллизий должно выполняться следующее соотношение:

Tmin > RTT,

где Tmin — время передачи кадра минимальной длины, a RTT — время оборота,то есть время, за которое сигнал коллизии успевает распространиться до самого дальнего узла сети. В худшем случае сигнал должен пройти дважды между наиболее удаленными друг от друга станциями сети (в одну сторону проходит неискаженный сигнал, а в обратном направлении — сигнал, уже искаженный коллизией). При выполнении этого условия передающая станция должна успеть обнаружить коллизию, которую вызвал переданный её кадр, еще до того, как она закончит передачу этого кадра.

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

Так, стандарт Ethernet определяет минимальную длину поля данных кадра в 46 байт, что вместе со служебными полями дает минимальную длину кадра 64 байт, а вместе с преамбулой — 72 байт, или 576 бит. Отсюда может быть вычислено ограничение на расстоянии между станциями. Таким образом, время передачи кадра минимальной длины равно Tmin = 576 BT, следовательно для стандарта Ethernet 10 Мбит/c, время оборота RTT должно быть меньше Tmin = 57,6 мкс.

Расстояние, которое проходит сигнал за время Tmin равно

L = VTmin,

где V - скорость распространения сигнала зависит от типа кабеля, но обычно не менее V = 230 м/мкс. В этом случае L = 13248 м.

Учитывая, что за время Tmin сигнал должен пройти по линии связи дважды, расстояние между двумя узлами (диаметр сети) не должно быть больше L/2 = 6624 м. В стандарте величина этого расстояния выбрана равной 2500 м, что существенно меньше. Это объясняется тем, что повторители, которые нужны для соединения пяти сегментов кабеля, вносят задержки в распространение сигнала.

Описанные соображения объясняют выбор минимальной длины поля данных кадра в 46 байт. Уменьшение этого значения до 0 привело бы к значительному сокращению максимальной длины сети.

Требование Tmin > RTT имеет одно интересное следствие: чем выше скорость протокола, тем меньше должна быть максимальная длина сети. Поэтому для FastEthernet на разделяемой среде при скорости в 100 Мбит/с максимальная длина сети пропорционально уменьшается до 250 м, а для GigaEthernet при скорости в 1 Гбит/с — до 25 м. Эта зависимость, наряду с резким ростом задержек при повышении загрузки сети, говорит о еще одном коренном недостатке методе доступа CSMA/CD.

 

2 Имитационное моделирование CSMA/CD в среде GPSS

Описание программы

Ниже перечислим основные моменты, которые учитывались при разработке программы моделирования метода доступа CSMA/CD для сети Ethernet на GPSS.

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

Каждый СУ может быть занят одним кадром (сообщением) до тех пор, пока он не будет отправлен или пока его не удаётся отправить из‑за некоторого числа коллизий с кадрами других СУ, после чего СУ освобождается. Если число коллизий превышает определённый предел, то объявляется ошибка и СУ также освобождается.

Подразумевается, что отдельные СУ отстоят друг от друга на небольшое расстояние (при моделировании — 2,5 м). При расчете окна коллизии для определения разделяющего расстояния используется идентификационный номер (ID) СУ. Идентификационный номер (ID) СУ используется для определения расстояния при вычислении «Окна коллизии».

Межкадровый IPG интервал моделируется путем приостановки функционирования сети на некоторое дополнительное время после передачи СУ кадра.

Коллизия возникает из-за одновременных попыток передачи кадров двумя или более СУ. Задержка распространения сигнала препятствует определять данному СУ одновременность начала передачи кадра другим СУ, тем самым приводя к возможности коллизии. Интервал времени, в течение которого сигнал из другого СУ не может быть обнаружен, называется «окном коллизии».

Алгоритм работы программы приведен на рис. 4.

Текст программы на GPSS представлен на рис. 5.

Кадры представлены GPSS транзактами. СУ представлены GPSS устройствами (Facilities).

При моделировании коллизия инициирует лишение передаваемого транзакта права занимать Ethernet путем отправки его в подпрограмму backoff задержки на некоторый интервал времени. При возникновении коллизии генерируется jam-последовательность, которая на небольшой промежуток времени блокирует Ethernet, после чего каждый кадр, попавший в коллизию, ждёт еще некоторый случайный временной интервал Backoff_Delay до попытки повторной передачи. При отправке кадра транзакт занимает устройство Ethernet с приоритетом 0 и может быть вытеснен только транзактом с приоритетом 1. Транзакт с приоритетом, равным 1, никогда не отдаст занятую им среду передачи (устройство Ethernet).

Если бы все СУ попытались повторно передать кадр сразу после коллизии, то это закончилось бы другой коллизией. Поэтому протокол обязан гарантировать низкую вероятность одновременной повторной передачи. Принятая схема Ethernet использует случайный период, где каждый узел выбирает случайное число, умножает его на время передачи минимального кадра (этот период равен 51,2 мкс - время передачи короткого кадра длиной 512 бит) и ждет в течение этого случайного периода перед попыткой повторной передачи. Также добавляется технологическая пауза IPG - межкадровый интервал, равный 9,6 мкс.

В загруженной сети повторная передача одного узла может возникать одновременно с повторной передачей другого узла. Протокол подсчитывает число попыток повторной передачи Retries(переменная N в вышеупомянутой схеме) и пытается повторно передавать тот же самый кадр до 15 раз.

 

Рис. 4. Алгоритм моделирующей программы

 

Для уменьшения вероятности возникновения повторных коллизий используется процедура регулирования задержки повторной передачи:

Backoff_Delay = Slot_time х Backrandom = 512 х BT х Backrandom

где Backrandom - целое число, которое выбирается случайным образом из диапазона 1 ÷ 2min(10, N).

 

 

* 10 Mbps Модель ЛВС на основе метода доступа CSMA/CD

* Время измеряется в мс.

*********************************************************

* Параметры константы

*********************************************************

Node_Count EQU 100 ;Число СУ в моноканале (МК) Nсу

Node_Period EQU 105.2 ;Средний интервал между кадрами

;одного (каждого) СУ

Min_Frame EQU 512 ;Длина короткого кадра в битах

Max_Frame EQU 12144 ;Длина длинного кадра в битах

Fraction_Short_Frame EQU 600 ;Доля коротких кадров на тысячу

Bit_Time EQU 0.0001 ;Врямя передачи одного бита

Slot_Time EQU Min_Frame#Bit_Time ;Интервал отсрочки - время 512 бит

Jam_Time EQU 32#Bit_Time ;Длительность Jam-последовательности

;- время 32 бит

InterFrame_Time EQU 96#Bit_Time ;Межкадровый интервал - время 96 бит

Backoff_Limit EQU 15 ;Max число повторных попыток

Signal_Speed EQU 250000 ;Скорость сигнала в кабеле V[м/мс]

Net_Length EQU 250 ;Максимальная удалённость СУ - длина МК L[м]

* Задержка распространения сигнала в кабеле между смежными СУ: L/(Nсу*V)

InterNode_Time EQU Net_Length/(Node_Count#Signal_Speed)

*********************************************************

* Переменные параметры

*********************************************************

Net_Period VARIABLE Node_Period/Node_Count ;Средний интервал между кадрами

;в сети

Backoff_Delay VARIABLE Slot_Time#V$Backrandom ;Задержка повторной попытки

;зависит от числа попыток N

Backrandom VARIABLE 1+(RN4@((2^V$Backmin)-1)) ;как RAND(0,2min(10,N)) х 512 х ВТ

Backmin VARIABLE (10#(10'L'P$Retries))+(P$Retries#(10'GE'P$Retries))

Node_Select VARIABLE 1+(RN3@Node_Count) ;Выбор СУ

* Проверка на попадание в окно коллизии (collision window)

Collide VARIABLE ABS((X$Xmit_Node-P$Node_ID)#InterNode_Time)'GE'(AC1-X$Xmit_Begin)

FrameTime VARIABLE Bit_Time#V$FrameRand ;Время на передачу кадра = BT х длину

FrameRand VARIABLE Min_Frame+(RN1'G'Fraction_Short_Frame)#(Max_Frame-Min_Frame)

********************************************************

* Гистограмма числа попыток N

********************************************************

N_retries TABLE P$Retries,0,1,17

********************************************************

* Гистограмма задержки кадров

********************************************************

Frame_Delays QTABLE Global_Delays,1,1,20

********************************************************

* Главная часть модели

********************************************************

********************************************************

* Порождение кадров

********************************************************

GENERATE (Exponential(1,0,V$Net_Period)) ;Генерация кадра

ASSIGN Node_ID,V$Node_Select ;Формирование ID СУ

ASSIGN Frame_Time,V$FrameTime ;Формирование длины кадра

ASSIGN Retries,0 ;Обнул.счётчика повт.передач

********************************************************

* Ждать пока СУ не закончить любую предыдущую работу

********************************************************

QUEUE Global_Delays ;Запуск счётчика гистограммы

SEIZE P$Node_ID ;Занятие СУ с номером ID

Try_ToSend PRIORITY 1 ;Попытка и повторная попытка

TEST E F$Ethernet,1,Start_Xmit ;Если МК свободен, то к передаче кадра

********************************************************

* МК занят.

* Проверка, находится ли СУ при передаче в "Окне коллизий".

* Если да, то этот СУ должен начать передачу, так так он ещё не знает, что другой

* СУ уже начал передачу (ещё нет сигнала от другого СУ и коллизия не началась).

* В этом случае необходимо инициировать коллизию.

********************************************************

TEST E V$Collide,1,Start_Xmit ;Проверка на наличие коллизии, если не

;началась, то занять МК (начать перед.)

************** Коллизия ********************************

Collision PREEMPT Ethernet,PR,Backoff,,RE ;Удалить кадр, который был в МК

SEIZE Jam ;Отправка Jam-последовательности

ADVANCE Jam_Time ;Задержка на время Jam-последоват.

RELEASE Jam ;Конец Jam-последовательности

RELEASE Ethernet ;Освободить МК

PRIORITY 0 ;Восстановить нормальный приоритет

Backoff ASSIGN Retries+,1 ;Увеличить число повторных попыток

TEST LE P$Retries,Backoff_Limit,Xmit_Error ;Предел попыток

ADVANCE V$Backoff_Delay ;Тайм-аут повторной попытки

TRANSFER ,Try_ToSend ;К повторной попытке

*********************************************************

* МК свободен. Начало передачи кадра

*********************************************************

Start_Xmit SEIZE Ethernet ;Получение МК

SAVEVALUE Xmit_Node,P$Node_ID ;Идентификация СУ отправителя

SAVEVALUE Xmit_Begin,AC1 ;Фиксация начала xmit времени

PRIORITY 0 ;Гарантия, что можно прервать

ADVANCE P$Frame_Time ;Ожидание времени передачи кадра

ADVANCE InterFrame_Time ;Межкадровое время

RELEASE Ethernet ;Освобождение МК

Free_Node RELEASE P$Node_ID ;Освобождение СУ с номером ID

DEPART Global_Delays ;Остановка счетчика для гистограммы

TABULATE N_retries ;Счёчик гистограммы повт.попыток

TERMINATE ;Удаление переданного кадра

**********************************************************

Xmit_Error SAVEVALUE Error_Count+,1 ;Подсчёт ошибок

TRANSFER ,Free_Node ;и освобождение СУ

**********************************************************

* Сегмент таймера

**********************************************************

**********************************************************

GENERATE 10000 ;Время моделирования 10000 мс = 10 с

SAVEVALUE USE_ETHERNET,(FR$Ethernet/1000) ;Коэффициент использования

;сети

TERMINATE 1

 

Рис. 5. Текст моделирующей программы на GPSS

 

При описании программы под кадрами/сообщениями следует понимать транзакты, поскольку именно ими оперирует GPSS.

Создание кадра и выбор СУ. С помощью блока GENERATE генерируются сообщения (транзакты), интервалы между которыми распределены по экспоненциальному закону. В блоке ASSING переменной Node_ID присваивается номер узла Node_Select, тем самым выбирается СУ, отправляющий кадр. В блоке ASSING переменной Frame_Time присваивается значение FrameTime, тем самым выбирается длина передаваемого кадра.

Занятие СУ и Ethernet. При помощи блока SEIZE занимается выбранный узел, после чего идет проверка занятости среды. Это делается в блоке TEST, где проверяется, свободна среда Ethernet или нет. Если да, то с помощью блока SEIZE она занимается. Если среда занята, то с помощью блока TEST ее проверяют на наличие коллизии. При наличии коллизии сообщение поступает в часть программы, занимающуюся обработкой коллизий. Если коллизии нет, то сообщение продвигается по программе дальше и устройство Ethernet занимается.

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

Освобождение Ethernet и СУ. После окончания прохождения сообщения через Ethernet с помощью блока RELEASE происходит освобождение сети. При этом происходит освобождение узла с номером Node_ID, что свидетельствует о том, что сообщение полностью передано. Затем оно уничтожается в блоке TERMINATE.

Обработка коллизий.Если в сети возникла коллизия, то сообщение после второго блока TEST, который отвечает за распознавание коллизий, поступает в блок PREEMPT. Если приоритет сообщения кадра «захватчика» выше, чем приоритет обслуживаемого, то с помощью этого блока происходит захват Ethernet. Прерванное сообщение будет направлено на метку Backoff, и оно теряет право на восстановление. Затем с помощью блока SEIZE занимается устройство Jam, и транзакт в этом устройстве удерживается блоком ADVANCE на время передачи jam-последовательности. После прохождения времени задержки устройство Jam освобождается при помощи блока RELEASE, а после этого блоком RELEASE освобождается устройство Ethernet. При каждом попадании кадра/транзакта на метку Backoff в блоке ASSING происходит суммирование попыток повторной передачи сообщения. Дальше происходит сравнение блоком TEST количества попыток повторной передачи сообщения с предельным количеством попыток. Если число попыток не достигло предельного значения, то происходит задержка на время случайной паузы блоком ADVANCE. По истечении случайной паузы сообщение направляется на повторную передачу. Если же число попыток достигло предельного значения, то инициируется ошибка в сети и пакет отбрасывается, при этом узел и Ethernet освобождаются, а сообщение удаляется в блоке TERMINATE.