Рис. 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 года.
Двоичный обратный отсчет
Недостатком базового протокола битовой карты, а также протокола с передачей маркера являются накладные расходы в один бит на станцию, из-за чего они плохо масштабируются на большие сети с тысячами станций. Используя двоичный адрес станции, можно улучшить эффективность канала. Станция, желающая занять канал, объявляет свой адрес в виде битовой строки, начиная со старшего бита. Предполагается, что все адреса станций имеют одинаковую длину. Будучи отправленными одновременно, биты адреса в каждой позиции логически складываются (логическое ИЛИ) средствами канала. Мы будем называть этот протокол протоколом с двоичным обратным отсчетом (binary countdown). Он использовался в сети Datakit (Fraser, 1987). Неявно предполагается, что задержки распространения сигнала пренебрежимо малы, поэтому станции слышат утверждаемые номера практически мгновенно.
Во избежание конфликтов следует применить правило арбитража: как только станция с 0 в старшем бите адреса видит, что в суммарном адресе этот 0 заменился единицей, она сдается и ждет следующего цикла. Например, если станции 0010, 0100, 1001 и 1010 конкурируют за канал, то в первом битовом интервале они передают биты 0, 0, 1 и 1 соответственно. В этом случае суммарный первый бит адреса будет равен 1. Следовательно, станции с номерами 0010 и 0100 считаются проигравшими, а станции 1001 и 1010 продолжают борьбу.
Следующий бит у обеих оставшихся станций равен 0 — таким образом, обе продолжают. Третий бит равен 1, поэтому станция 1001 сдается. Победителем оказывается станция 1010, так как ее адрес наибольший. Выиграв торги, она может начать передачу кадра, после чего начнется новый цикл торгов. Схема протокола показана на рис. 4.8. Данный метод предполагает, что приоритет станции напрямую зависит от ее номера. В некоторых случаях такое жесткое правило может играть положительную, в некоторых — отрицательную роль.
