Протокол CSMA/CD

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

Передача кадра (рис. 7.4 а):

1. Станция, собравшаяся передавать, прослушивает среду, и передает, если среда свободна. В противном случае (т.е. если среда занята), переходит к шагу 2. При передаче нескольких кадров подряд станция выдерживает определенную паузу между посылками кадров — межкадровый интервал, причем после каждой такой паузы перед отправкой следующего кадра станция вновь прослушивает среду (возвращение на начало шага 1);
2. Если среда занята, станция продолжает прослушивать среду до тех пор, пока-среда не станет свободной, и затем сразу же начинает передачу;
3. Каждая станция, ведущая передачу, прослушивает среду, и, в случае обнаружения коллизии, не прекращает сразу же передачу, а сначала передает короткий специальный сигнал коллизии — jam-сигнал, информируя другие станции о коллизии, и прекращает передачу;
4. После передачи jam-сигнала станция замолкает и ждет некоторое произвольное время в соответствии с правилом бинарной экспоненциальной задержки, а затем возвращается к шагу 1.

Межкадровый интервал IFG (mterframe gap) составляет 9,6 мкм (12 байт). С одной стороны, он необходим для того, чтобы принимающая станция могла корректно завершить прием кадра. Кроме этого, если бы станция передавала кадры непрерывно, она бы полностью захватила канал и, тем самым, лишила другие станции возможности передачи.

Jam-сигнал (jamming — дословно глушение). Передача jam-сигнала гарантирует, что ни один кадр не будет потерян, так как все узлы, которые передавали кадры до возникновения коллизии, приняв jam-сигнал, прервут свои передачи и замолкнут в ожидании новой попытки передать кадры. Jam-сигнал должен быть достаточной длины, чтобы он дошел до самых удаленных станций коллизионного домена с учетом дополнительной задержки SF (safety margin) на возможных повторителях. Содержание jam-сигнала не принципиально за исключением того, что оно не должно соответствовать значению поля CRC частично переданного кадра (802.3), и первые 62 бита должны представлять чередование 1 и 0 со стартовым битом 1.

Рис. 7.4. Структурная схема алгоритма CSMA/CD (уровень MAC):
а) при передаче кадра станцией; б) при приеме кадра станцией

На рис. 7.5 проиллюстрирован процесс обнаружения коллизии применительно к топологии «шина» (на основе тонкого или толстого коаксиального кабеля (стандарты 10Base5 и 10Base2 соответственно).

В момент времени t0 узел A (DTE А) начинает передачу, естественно прослушивая свой же передаваемый сигнал. В момент времени t1 когда кадр почти дошел до узла В (DTE В), этот узел, не зная о том, что уже идет передача, сам начинает передавать. В момент времени t2 = t1 + А , узел В обнаруживает коллизию (увеличивается постоянная составляющей электрического сигнала в прослушиваемой линии). После этого узел В передает jam-сигнал и прекращает передачу. В момент времени t3 сигнал коллизии доходит до узла А, после чего А также передает jam-сигнал и прекращает передачу.

Рис. 7.5. Обнаружение коллизии в шине при использовании схемы CSMA/CD стандарта Ethernet

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

Время канала ST (slot time) — это минимальное время, в течение которого узел обязан вести передачу, занимать канал. Это время соответствует передаче кадра минимального допустимого размера, принятого стандартом Ethernet IEEE 802.3. Время канала связано с максимальным допустимым расстоянием между узлами сети — диаметром коллизионного домена. Допустим, что в приведенном выше примере реализуется наихудший сценарий, когда станции А и В удалены друг от друга на максимальное расстояние. Время распространения сигнала от А до В обозначим через tP . Узел А начинает передавать в нулевой момент времени. Узел В начинает передавать в момент времени t1=tP — А и обнаруживает коллизию спустя интервал Д после начала своей передачи. Узел А обнаруживает коллизию в момент времени t3 = 2tP — А . Для того, чтобы кадр, испущенный А, не был потерян, необходимо, чтобы узел А не прекращал вести передачу к этому моменту, так как тогда, обнаружив коллизию, узел А будет знать, что его кадр не дошел, и попытается передавать его повторно. В противном случае, кадр будет потерян. Максимальное время, спустя которое с момента начала передачи узел А еще может обнаружить коллизию, равно 2tP — это время называется задержкой на двойном пробеге RTD (round-trip delay). В более общем случае, RTD определяет суммарную задержку, связанную как с задержкой из-за конечной длины сегментов, так и с задержкой, возникающей при обработке кадров на физическим уровне промежуточных повторителей и оконечных узлов сети. Далее удобно использовать также другую единицу измерения времени: битовое время ВТ (bit time). Время в 1 ВТ соответствует времени, необходимому для передачи одного бита, т.е. 0,1 мкс при скорости 10 Мбит/с.

Стандартом Ethernet регламентированы следующие правила обнаружения коллизии конечным узлом сети:

1. Узел А должен обнаружить коллизию до того, как передаст свой 512-й бит, включая биты преамбулы;
2. Узел А должен прекратить передачу раньше, чем будет передан кадр минимальной длины — передано 576 бит (512 бит после ограничителя начала кадра SFD);
3. Перекрытие между передачами узлов А и В ~ битовый интервал, начиная с момента передачи первого бита преамбулы узлом А и заканчивая приемом узлом А последнего бита, испущенного узлом В, — должно быть меньше, чем 575 ВТ.

Последнее условие для сети Ethernet является наиболее важным, поскольку его выполнение автоматически влечет выполнение и первых двух. Это третье условие задает ограничение на диаметр сети. Применительно к задержке на двойном пробеге RTD третье условие можно сформулировать в виде; RTD < 575 ВТ. При передаче больших кадров, например 1500 байт, коллизия, если она вообще возникнет, обнаруживается практически в самом начале передачи, не позднее первых 64 переданных байт (если коллизия не возникла в это время, то позже она уже не возникнет, поскольку все станции прослушивают линию и, "слыша" передачу, будут молчать). Так как jam-сигнал значительно короче полного размера кадра, то при использовании алгоритма CSMA/CD количество в холостую израсходованной емкости канала сокращается до времени, требуемого на обнаружение коллизии. Раннее обнаружение коллизий приводит к более эф­фективному использованию канала. Позднее обнаружение коллизий, свойственное более протяженным сетям, когда диаметр коллизионного домена составляет несколько километров, снижает эффективность работы сети. На основании упрощенной теоретической модели поведения загруженной сети (в предположении большого числа одновременно передающих станций и фиксированной минимальной длины передаваемых кадров у всех станций) можно выразить производительность сети U через отношение RTD/ST:

где е — основание натурального логарифма. На производительность сети влияет размер транслируемых кадров и диаметр сети. Производительность в наихудшем случае (когда RDT = ST) составляет около 37%, а в наилучшем случае (когда RTD много меньше, чем ST) стремится к 1. Хотя формула и выведена в пределе большого числа станций, пытающихся передавать одновременно, она не учитывает особенностей алгоритма усеченной бинарной экспоненциальной задержки, рассмотренного ниже, и не справедлива для сильно перегруженной коллизиями сети, например, когда станций, желающих передавать, становится больше 15.
Усеченная бинарная экспоненциальная задержка. Алгоритм, принятый в стандарте IEEE 802.3 CSMA/CD, наиболее близок к 1-постоянному алгоритму, но отличается дополнительным элементом — усеченной бинарной экспоненциальной задержкой. При возникновении коллизии станция подсчитывает, сколько раз подряд при отправке пакета возникает коллизия.

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

Количество слотовых времен (интервалов по 51,2 мкс), которое станция ждет перед тем, как совершить N-ую попытку передачи (N — 1 попыток потерпели фиаско из-за возникновения коллизий во время передачи), представляет случайное целое число R с однородной функцией распределения в интервале 0K, где К = min(N,BL), и BL (backoff limit) — установленная стандартом предельная задержка, равная 10. Если число последовательных безуспешных попыток отправить кадр доходит до 16, то есть коллизия возникает 16 раз подряд, то кадр сбрасывается.

Алгоритм CSMA/CD с использованием усеченной бинарной экспоненциальной задержки признан лучшим среди множества алгоритмов случайного доступа и обеспечивает эффективную работу сети как при малых, так и при средних загрузках. При больших загрузках следует отметить два недостатка. Во-первых, при большом числе коллизий станция 1, которая впервые собирается отправить кадр (до этого не пыталась передавать кадры), имеет преимущество перед станцией 2, которая уже несколько раз безуспешно пыталась передать кадр, натыкаясь на коллизии, поскольку станция 2 ожидает значительное время перед последующими попытками в соответствии с правилом бинарной экспоненциальной задержки. Таким образом, может наблюдаться нерегулярность передачи кадров, что нежелательно для зависящих от времени приложений. Во-вторых, при большой загруженности снижается эффективность работы сети в целом. Оценки показывают, что при одновременной передаче 25 станциями об­щая полоса пропускания снижается примерно в 2 раза . Но число станций в коллизионном домене может быть больше, поскольку далеко не все они одновременно будут обращаться к среде.

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

На уровне MAC оставшиеся биты преамбулы сбрасываются, а станция читает адрес назначения и сравнивает его со своим собственным. Если адреса совпадают, то поля кадра, за исключением преамбулы, SDF и FCS помещаются в буфер и вычисляется контрольная сумма, которая сравнивается с полем контрольной последовательности кадра FCS (используется метод циклического суммирования CRC-32). Если они равны, то содержимое буфера передается протоколу более высокого уровня. В противном случае кадр сбрасывается. Возникновение коллизии при приеме кадра обнаруживается либо по изменению электрического потенциала (если используется коаксиальный сегмент), либо по факту приема дефектного кадра (неверная контрольная сумма), если используется витая пара или оптическое волокно. В обоих случаях принятая информация сбрасывается.

Основные функциональные параметры стандарта Ethernet приведены в табл. 7.1.

Таблица 7.1. Основные функциональные параметры Ethernet IEEE 802.3