Лекция №3. Метод доступа CSMA/CD

В сетях Ethernet используется метод доступа к среде передачи данных, называемый методом коллективного доступа с опознаванием несущей и обнаружением коллизий (carrier-sense-multiply-access with collision detection, CSMA/CD).

Этот метод используется исключительно в сетях с общей шиной (к которым относятся и радиосети, породившие этот метод). Все компьютеры такой сети имеют непосредственный доступ к общей шине, поэтому она может быть использована для передачи данных между любыми двумя узлами сети. Простота схемы подключения - это один из факторов, определивших успех стандарта Ethernet. Говорят, что кабель, к которому подключены все станции, работает в режиме коллективного доступа (multiply-access,MA).

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

При описанном подходе возможна ситуация, когда две станции одновременно пытаются передать кадр данных по общему кабелю (рис. 3). Для уменьшения вероятности этой ситуации непосредственно перед отправкой кадра передающая станция слушает кабель (то есть принимает и анализирует возникающие на нем электрические сигналы), чтобы обнаружить, не передается ли уже по кабелю кадр данных от другой станции. Если опознается несущая (carrier-sense, CS), то станция откладывает передачу своего кадра до окончания чужой передачи, и только потом пытается вновь его передать. Но даже при таком алгоритме две станции одновременно могут решить, что по шине в данный момент времени нет передачи, и начать одновременно передавать свои кадры. Говорят, что при этом происходит коллизия, так как содержимое обоих кадров сталкивается на общем кабеле, что приводит к искажению информации.

Чтобы корректно обработать коллизию, все станции одновременно наблюдают за возникающими на кабеле сигналами. Если передаваемые и наблюдаемые сигналы отличаются, то фиксируется обнаружение коллизии (collision detection, CD). Для увеличения вероятности немедленного обнаружения коллизии всеми станциями сети, ситуация коллизии усиливается посылкой в сеть станциями, начавшими передачу своих кадров, специальной последовательности битов, называемой jam-последовательностью.

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

Из описания метода доступа видно, что он носит вероятностный характер, и вероятность успешного получения в свое распоряжение общей среды зависит от загруженности сети, то есть от интенсивности возникновения в станциях потребности передачи кадров. При разработке этого метода предполагалось, что скорость передачи данных в 10 Мб/с очень высока по сравнению с потребностями компьютеров во взаимном обмене данными, поэтому загрузка сети будет всегда небольшой. Это предположение остается часто справедливым и по сей день, однако уже появились приложения, работающие в реальном масштабе времени с мультимедийной информацией, для которых требуются гораздо более высокие скорости передачи данных. Поэтому наряду с классическим Ethernet'ом растет потребность и в новых высокоскоростных технологиях.

Метод CSMA/CD определяет основные временные и логические соотношения, гарантирующие корректную работу всех станций в сети:

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

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

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

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

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

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

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

LÎ[0, 2^N], выбирается случайным образом (называется усеченной бинарной экспоненциальной задержкой).

NÎ[1,10]. Таким образом. Случайная пауза – от 51,2мкс до 52,4 мс.

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

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

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

По стандарту IEEE 802.3 узел не может предавать очень короткие кадры, или иными словами вести очень короткие передачи. Как говорилось при описании формата кадра, даже если поле данных не заполнено до конца, то появляется специальное дополнительное поле, удлиняющее кадр до минимальной длины 64 байта без учета преамбулы. Время канала ST (slot time)- это минимальное время, в течении которого узел обязан вести передачу, занимать канал. Это время соответствует передаче кадра минимального допустимого размера, принятого стандартом. Время канала связано с максимальным допустимым расстоянием между узлами сети - диаметром коллизионного домена. Допустим, что в приведенном выше примере реализуется наихудший сценарий, когда станции A и B удалены друг от друга на максимальное расстояние. Время, распространения сигнала от A до B обозначим через . Узел A начинает передавать в нулевой момент времени. Узел B начинает передавать в момент времени и обнаруживает коллизию спустя интервал после начала своей передачи. Узел A обнаруживает коллизию в момент времени . Для того, чтобы кадр, испущенный A, не был потерян, необходимо, чтобы узел A не прекращал вести передачу к этому моменту, так как тогда, обнаружив коллизию, узел A будет знать, что его кадр не дошел, и попытается передавать его повторно. В противном случае кадр будет потерян. Максимальное время, спустя которое с момента начала передачи узел A еще может обнаружить коллизию равно - это время называется задержкой на двойном пробеге RTD (round-trip delay). В более общем случае RTD определяет суммарную задержку, связанную как с задержкой из-за конечной длины сегментов, так и с задержкой, возникающей при обработке кадров на физическим уровнем промежуточных повторителей и оконечных узлов сети. Для дальнейшего удобно использовать также другую единицу измерения времени: битовое время BT (bit time). Время в 1 BT соответствует времени, необходимому для передачи одного бита, т.е. 0,1 мкс при скорости 10 Мбит/с.

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

1. Узел A должен обнаружить коллизию до того, как передаст свой 512-й бит, включая биты преамбулы;

2. Узел A должен прекратить передачу раньше, чем будет передан кадр минимальной длины - передано 576 бит (512 бит, начиная отсчет после ограничителя начала кадра SFD);

3. Перекрытие между передачами узлов A и B - битовый интервал начиная с момента передачи первого бита преамбулы узлом A и заканчивая приемом узлом A последнего бита испущенного узлом B - должно быть меньше чем 575 BT.

Последнее условие для сети Ethernet является наиболее важным, поскольку его выполнение автоматически влечет выполнение и первых двух. Это третье условие задает ограничение на диаметр сети. Применительно к задержке на двойном пробеге RTD третье условие можно сформулировать в виде: T.

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

,

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

Усеченная бинарная экспоненциальная задержка (truncated binary exponential backoff). При возникновении коллизии в алгоритме CSMA/CD стация подсчитывает, сколько раз подряд при отправке пакета возникает коллизия. Поскольку повторяющиеся коллизии свидетельствуют о высокой загруженности среды, MAC-узел пытается увеличивать задержку между повторными попытками передачи кадра. Соответствующая процедура увеличения интервалов времени подчиняется правилу усеченной бинарной экспоненциальной задержки и работает следующим образом.

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

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

Прием кадра (рис.3б)

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

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

Значения основных параметров процедуры передачи кадра стандарта 802.3 приведено в таблице 1.

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

Так как размер пакета минимальной длины вместе с преамбулой составляет 64+8 = 72 байта или 576 битов, то на его передачу затрачивается 57.6 мкс. Прибавив межкадровый интервал в 9.6 мкс, получаем, что период следования минимальных пакетов равен 67.2 мкс. Это соответствует максимально возможной пропускной способности сегмента Ethernet в 14880 п/с.