Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Протокол битовой карты

В первом протоколе без столкновений, который мы рассмотрим, называющемся основным методом битовой карты( basic bit-map method), каждый период конкуренции состоит ровно из N временных интервалов. Если у станции 0 есть кадр для передачи, она передает единичный бит во время 0-го интервала. Другим станциям не разрешается передача в это время. Во время интервала 1 станция 1 также сообщает, есть ли у нее кадр для передачи, передавая бит 1 или 0. В результате к окончанию интервала N все N станций знают, кто хочет передавать. В этот момент они начинают передачу в соответствии со своим порядком номеров (на рис. 4.6 приведен пример для N = 8).

Рис. 4.6.Базовый протокол битовой карты

Поскольку все знают, чья очередь передавать, столкновений нет. После того как последняя станция передает свой кадр, что все станции отслеживают, прослушивая линию, начинается новый период подачи заявок из N интервалов. Если станция переходит в состояние готовности (получает кадр для передачи) сразу после того, как она отказалась от передачи, это значит, что ей не повезло и она должна ждать следующего цикла.

Протоколы, в которых намерение передавать объявляется всем перед самой передачей, называются протоколами с резервированием( reservation protocols), так как

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

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

Перспективы станций с большими номерами более радужны. В среднем время ожидания передачи составит половину цикла (N/2 однобитовых интервалов). Станциям

с большими номерами редко приходится ждать следующего цикла. Поскольку станциям с небольшими номерами приходится ждать в среднем 1,5N интервала, а станциям с большими номерами — N/2 интервалов, среднее время ожидания для всех станций составляет N интервалов.

При низкой загрузке канала его производительность легко сосчитать. Накладные расходы на кадр составляют N бит, и при длине кадра в d бит эффективность равна

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

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

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

Смысл протокола битовой карты в том, что он позволяет каждой станции передавать данные по очереди в заранее определенном порядке. Другой способ, аналогичный этому, основан на передаче небольшого сообщения, называемого маркером (token), от одной станции к следующей в том же самом заранее определенном порядке. Маркер представляет собой разрешение на отправку. Если на станции в очереди находится кадр, готовый к пересылке, и станция получает маркер, она имеет право отправить кадр, прежде чем передавать маркер следующей станции. Если кадров для отправки нет, то она просто передает маркер.

В протоколе маркерного кольца (token ring) для определения порядка, в котором станции отправляют данные, используется топология сети. Станции подключены одна к другой, образуя простое кольцо. Таким образом, передача маркера заключается в получении его с одного направления и пересылке в противоположном, как видно на рис. 4.7. Кадры передаются в том же направлении, что и маркер. Они путешествуют по кольцу, проходя по всем станциям, которые оказываются на их пути. Однако для того чтобы кадр не циркулировал вечно (как маркер), какая-то станция должна извлечь его из кольца. Это может быть либо первоначальный отправитель (если кадр прошел полный цикл), либо станция-получатель.

Рис. 4.7. Маркерное кольцо

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

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

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