Протокол подуровня управления доступом к среде в Ethernet. Алгоритм двоичного экспоненциального отката.

 

Каждый кадр начинается с поля Preamble (преамбула, заго­ловок) длиной 8 байт которое содержит последовательность 10101010. Манче­стерское кодирование такой последовательности битов дает в результате меандр с частотой 10 МГц и длительностью 6,4 мкс, что позволяет получателю синхрони­зировать свои часы с часами отправителя. Далее до конца кадра они должны со­хранять синхронизированное состояние за счет манчестерского кода, хранящего отметки границ битов.

Кадр содержит два адреса: получателя и отправителя. По стандарту разреша­ются 2-байтовые и 6-байтовые адреса, однако параметры немодулированной пе­редачи со скоростью 10 Мбит/с предусматривают только 6-байтовые адреса. Старший бит адреса получателя содержит 0 для обычных адресов и 1 для груп­повых получателей. Групповые адреса позволяют нескольким станциям прини­мать информацию от одного отправителя. Кадр, отправляемый групповому адре­сату, может быть получен всеми станциями, входящими в эту группу. Такой механизм называется групповой рассылкой. Если адрес состоит только из еди­ниц, то кадр могут принять абсолютно все станции сети. Таким способом осуще­ствляется широковещание. Разница между групповой рассылкой и широкове­щанием весьма существенна, поэтому еще раз повторим: кадр, предназначенный для групповой рассылки, посылается некоторой группе станций Ethernet; широ­ковещательный же кадр получают абсолютно все станции сети. Групповая рас­сылка более избирательна, но требует некоторых усилий при управлении груп­пами. Широковещание — это более грубая технология, но зато не требует никакой настройки групп.

Затем следует поле Туре, которое показывает приемнику, что делать с кадром. Дело в том, что одновременно на одной и той же машине могут работать не­сколько протоколов сетевого уровня, поэтому когда приходит кадр Ethernet, яд­ро должно понимать, какому протоколу его передать. Поле Туре определяет про­цесс, который должен взять себе кадр.

Наконец, за полем Туре следует поле данных, размер которого ограничен 1500 байтами. Такое ограничение было выбрано, в общем-то, произвольно в те времена, когда официально был закреплен стандарт DIX. При выборе ссылались на то, что приемопередатчику нужно довольно много оперативной памяти для того, чтобы хранить весь кадр. А память в том далеком 1978 году была еще очень дорогой. Соответственно, увеличение верхней границы размера поля данных при­вело бы к необходимости установки большего объема памяти, а значит, к удоро­жанию всего приемопередатчика.

Между тем, кроме верхней границы размера поля данных очень важна и нижняя граница. Поле данных, содержащее 0 байт, вызывает определенные проблемы. Дело в том, что когда приемопередатчик обнаруживает столкновение, он об­резает текущий кадр, а это означает, что отдельные куски кадров постоянно блуждают по кабелю. Чтобы было легче отличить нормальные кадры от мусора, сети Ethernet требуется кадр размером не менее 64 байт (от поля адреса получа­теля до поля контрольной суммы включительно). Если в кадре содержится меньше 46 байт данных, в него вставляется специальное поле Pad, с помощью которого размер кадра доводится до необходимого минимума.

Последнее поле кадра стандарта Ethernet содержит контрольную сумму. По сути дела, это 32-битный хэш-код данных. Если какие-либо биты приняты неправильно (в результате шума в канале), контрольная сумма практически наверняка будет неправильной, и ошибка, таким образом, будет замечена.

Алгоритм двоичного экспоненциального отката

Рассмотрим, как осуществляется рандомизация периода ожидания после столк­новения. Модель представлена на рис. 4.5. После возникновения коллизии время делится на дискретные интервалы, длительность которых равна максимальному времени кругового обращения сигнала (то есть его прохождения по кабелю в пря­мом и обратном направлениях), 2т. Для удовлетворения потребностей Ethernet при максимальном размере сети необходимо, чтобы один интервал составлял 512 битовых интервалов, или 51,2 мкс.

После первого столкновения каждая станция ждет или 0 или 1 интервал, пре­жде чем попытаться передавать опять. Если две станции столкнутся и выберут одно и то же псевдослучайное число, то они столкнутся снова. После второго столкновения каждая станция выбирает случайным образом 0, 1, 2 или 3 интер­вала из набора и ждет опять. При третьем столкновении (вероятность такого со­бытия после двойного столкновения равна '/₄) интервалы будут выбираться в диапазоне от 0 до 2³ - 1.

В общем случае после i столкновений случайный номер выбирается в диапа­зоне от 0 до 2' - 1, и это количество интервалов станция пропускает. Однако по­сле 10 столкновений подряд интервал рандомизации фиксируется на отметке 1023. После 16 столкновений подряд контроллер признает свое поражение и воз­вращает компьютеру ошибку. Дальнейшим восстановлением занимаются более высокие уровни.

Этот алгоритм, называемый двоичным экспоненциальным алгоритмом отка­та, был выбран для динамического учета количества станций, пытающихся осу­ществить передачу. Если выбрать интервал рандомизации равным 1023, то веро­ятность повторного столкновения будет пренебрежимо мала, однако среднее время ожидания составит сотни тактов, в результате чего среднее время задерж­ки будет слишком велико. С другой стороны, если каждая станция будет выби­рать время ожидания всего из двух вариантов, 0 и 1, то в случае столкновения сотни станций они будут продолжать сталкиваться снова и снова до тех пор, по­ка 99 из них не выберут 1, а одна станция — 0. Такого события можно будет ждать годами. Экспоненциально увеличивая интервал рандомизации по мере возникновения повторных столкновений, алгоритм обеспечивает небольшое вре­мя задержки при столкновении небольшого количества станций и одновременно гарантирует, что при столкновении большого числа станций конфликт будет разрешен за разумное время.

 

Вопросы проектирования сетевого уровня. Метод коммутации пакетов с ожиданием.

 

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

 

⇐ Предыдущая15161718192021222324Следующая ⇒

Поделиться: