Компьютерные сети. 6-е изд. - Эндрю Таненбаум

первоначальный отправитель (если фрейм прошел полный цикл), либо станция-получатель.

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

В этом случае каждая станция передает маркер по шине соседям в предопределенном порядке. Получив маркер, станция может использовать шину для отправки одного фрейма. Такой протокол называется маркерной шиной (token bus). Он описан в стандарте IEEE 802.4, который оказался настолько неудачным, что был отменен институтом IEEE. Стандарты не вечны.

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

Протоколы MAC на базе маркерных колец появляются с определенной периодичностью. Один из ранних протоколов такого рода — Token Ring, то есть «Маркерное кольцо», — описан в стандарте IEEE 802.5. В 1980-х он был популярен в качестве альтернативы классическому Ethernet. В 1990-е годы намного более быстрое маркерное кольцо, интерфейс передачи распределенных данных по волоконно-оптическим каналам (Fiber Distributed Data Interface, FDDI), потерпело поражение от коммутируемого Ethernet. В 2000-х отказоустойчивое пакетное кольцо (Resilient Packet Ring, RPR) было описано в IEEE 802.17, чтобы стандартизировать множество вариантов кольцевых сетей, используемых провайдерами в городских условиях. Интересно, какие протоколы появятся после 2020 года.

Двоичный обратный отсчет

Недостатком двух представленных выше протоколов являются накладные расходы в один бит на станцию. Из-за этого они плохо масштабируются на большие сети с сотнями или даже тысячами станций. Можно добиться лучших результатов, используя двоичные адреса станций и канал, способный определенным образом комбинировать передаваемые данные. Станция, желающая занять канал, объявляет свой адрес в виде битовой строки, начиная со старшего бита. Предполагается, что все адреса станций содержат одинаковое количество битов. Будучи отправленными одновременно, биты адреса в каждой позиции логически складываются (логическое ИЛИ) средствами канала. Мы будем называть этот метод протоколом с двоичным обратным отсчетом (binary countdown). Он использовался в сети Datakit (Фрейзер; Fraser, 1983). Подразумевается, что задержки распространения сигнала пренебрежимо малы, поэтому станции слышат утверждаемые номера практически мгновенно.

Во избежание конфликтов следует применить правило арбитража: как только станция с 0 в старшем бите адреса видит, что в суммарном адресе этот 0 заменился единицей, она сдается и ждет следующего цикла. Например, если станции 0010, 0100, 1001 и 1010 конкурируют за канал, то в первом битовом интервале они передают биты 0, 0, 1 и 1 соответственно. В этом случае суммарный первый бит адреса будет равен 1. Следовательно, станции с номерами 0010 и 0100 считаются проигравшими, а станции 1001 и 1010 продолжают борьбу.

Следующий бит у обеих оставшихся станций равен 0 — таким образом, обе продолжают. Третий бит равен 1, поэтому станция 1001 сдается. Победителем оказывается станция 1010, так как ее адрес наибольший. Выиграв торги, она может начать передачу фрейма, после чего начнется новый цикл торгов. Схема протокола показана на илл. 4.8. Данный метод предполагает, что приоритет станции напрямую зависит от ее номера. В некоторых случаях такое жесткое правило может играть положительную, а порой — отрицательную роль.

Илл. 4.8. Протокол с двоичным обратным отсчетом. Прочерк означает молчание

Эффективность использования канала при этом методе составляет d/(d + + log2 N). Однако можно так хитро выбрать формат фрейма, что его первое поле будет содержать адрес отправителя. Тогда даже эти log2 N бит не пропадут зря и эффективность составит 100 %.

Двоичный обратный отсчет является примером простого, элегантного и эффективного протокола. Разработчикам будущих сетей еще предстоит заново его открыть. Хочется надеяться, что когда-нибудь он займет свою нишу в сетевых технологиях.

4.2.4. Протоколы с ограниченной конкуренцией

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

Очевидно, что было бы неплохо объединить лучшие свойства обеих стратегий и получить протокол, использующий разные стратегии в зависимости от загруженности канала. Такие протоколы мы будем называть протоколами с ограниченной конкуренцией (limited-contention protocols) — они на самом деле существуют. На них мы завершим изучение сетей с контролем несущей.

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

Прежде чем приступить к асимметричным протоколам, давайте кратко рассмотрим производительность в симметричном случае. Предположим, что k станций конкурируют за доступ к каналу. Вероятность передачи каждой станции в каждый интервал времени равна p. Шанс получения станцией доступа к каналу в данном слоте включает вероятность того, что любая станция передает данные (с вероятностью p), а остальные k – 1 станций воздерживаются от передачи (каждая с вероятностью 1 – p). Итоговое значение равно kp(1 – p)k – 1. Чтобы найти оптимальное значение p, продифференцируем данное выражение по p, приравняем результат к нулю и решим полученное уравнение относительно p. В результате наилучшее значение p равно 1/k. Заменив в формуле p на 1/k, мы получим вероятность успеха при оптимальном значении p:

Pr [успех при оптимальной вероятности p] =

Зависимость этой вероятности от количества