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

сигнал. В момент времени t0 + τ – ε, за мгновение до того, как сигнал достигнет самой дальней станции, та станция также начинает передачу. Конечно, почти мгновенно она обнаруживает коллизию и останавливается. Однако всплеск шума, вызванный коллизией, достигает передающей станции только к моменту 2τ – ε. То есть станция не может быть уверена в том, что захватила канал, пока не пройдет 2τ с момента начала передачи.

С учетом этого конкуренцию CSMA/CD можно рассматривать как дискретную систему ALOHA с шириной интервала 2τ. В коаксиальном кабеле длиной 1 км τ ≈ 5 мкс. Различие между CSMA/CD и дискретной ALOHA состоит в том, что в первом случае за слотом, в котором передачу осуществляет только одна станция (то есть когда канал захвачен), следует передача оставшейся части фрейма. Это позволяет значительно улучшить производительность, если время фрейма намного больше времени распространения сигнала по каналу.

4.2.3. Протоколы без коллизий

Хотя в протоколе CSMA/CD коллизии не могут происходить после того, как станция захватывает канал, они могут случаться в период конкуренции. Это снижает производительность системы, особенно когда произведение полосы пропускания на значение задержки велико, то есть при большой длине кабеля (и больших τ) и коротких фреймах. Коллизии не только уменьшают пропускную способность, но и делают время пересылки фрейма непостоянным, что очень плохо для трафика, передаваемого в режиме реального времени (например, голосовых данных по IP). Метод CSMA/CD не является универсальным.

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

В описанных ниже протоколах предполагается наличие N станций. Для каждой из них запрограммирован постоянный уникальный адрес в пределах от 0 до N – 1. Некоторые станции могут часть времени оставаться пассивными, но это не имеет значения. Мы будем исходить из того, что задержка распространения сигнала пренебрежимо мала. Главный вопрос остается неизменным: какой станции будет предоставлен канал после успешной передачи? Мы будем по-прежнему использовать модель, изображенную на илл. 4.5, с ее дискретными интервалами конкуренции.

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

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

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

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

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

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

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

Если канал слабо загружен, его производительность легко вычислить. Накладные расходы на фрейм составляют N бит, и при длине фрейма в d бит производительность равна d/(d + N).

При сильной загруженности канала, когда все станции хотят что-то передать, период подачи заявок из N бит чередуется с N фреймами. При этом накладные расходы на передачу одного фрейма составляют всего один бит, а производительность равна d/(d + 1). Среднее время задержки для фрейма равно сумме времени ожидания в очереди на станции и дополнительных (N – 1)d + N однобитовых интервалов, когда он попадет в начало своей внутренней очереди. Этот интервал указывает, как долго станции приходится ожидать завершения передачи всеми остальными станциями и очередного получения битовой карты.

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

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

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