Компьютерные сети. 6-е изд.

Как видно из илл. 4.3, дискретная ALOHA имеет пик при G = 1. Производительность канала составляет S = 1/e, что приблизительно равно 0,368, то есть в два раза больше, чем в чистой ALOHA. Если система работает при G = 1, вероятность появления пустого слота равна 0,368 (согласно уравнению 4.1). Для дискретной системы ALOHA в оптимальной ситуации 37 % интервалов будут пустыми, 37 % — с успешно переданными фреймами и 26 % — с коллизией. При более высоких значениях G количество пустых интервалов уменьшается, но коллизий становится значительно больше. Чтобы увидеть, как быстро растет их число, рассмотрим передачу тестового фрейма. Вероятность того, что он избежит коллизии, равна e–G. Фактически это означает, что все остальные станции будут молчать в этом слоте. Таким образом, шанс возникновения коллизии равен 1 – e–G. Вероятность передачи фрейма ровно за k попыток (то есть после k – 1 коллизий, за которыми следует успешная отправка) равна

.

Ожидаемое число попыток передачи E для одной строки, введенной на терминале, равно

.

Поскольку E экспоненциально зависит от G, небольшое увеличение нагрузки в канале может серьезно снизить его производительность.

Дискретная система ALOHA заслуживает внимания по причине, которая на первый взгляд не кажется очевидной. Она появилась в 1970-е годы, применялась в некоторых экспериментальных системах и затем была практически забыта (если не считать упоминаний в работах чудаковатых авторов, считающих ее интересной). С появлением кабельного интернет-доступа вновь возникла проблема распределения общего канала между большим числом конкурирующих пользователей. Тогда дискретная ALOHA была вновь извлечена на белый свет и в сочетании с рядом новых идей обеспечила решение проблемы. Часто вполне работоспособные протоколы оказывались невостребованными по политическим причинам (например, если какая-нибудь корпорация требовала, чтобы все использовали исключительно ее продукцию) или из-за постоянно меняющихся технологий. Однако по прошествии многих лет какой-нибудь мудрый человек вспоминал о существовании древнего метода, способного решить современную проблему. Именно поэтому в данной главе мы изучим ряд элегантных, но непопулярных протоколов, которые вполне могут оказаться востребованными в будущем при условии, что о них будет знать достаточное количество разработчиков сетей. Разумеется, мы также обсудим множество актуальных протоколов.

4.2.2. Протоколы множественного доступа с контролем несущей

В дискретной системе ALOHA максимальный коэффициент использования канала равен 1/e. Такой скромный показатель неудивителен, поскольку станции передают данные, когда хотят, не считаясь с тем, что делают остальные. В такой системе неизбежно возникает большое количество коллизий. Однако в локальных сетях можно организовать процесс так, что станции будут учитывать поведение друг друга. За счет этого можно достичь намного большего значения, чем 1/e. В данном разделе представлены некоторые протоколы, позволяющие улучшить производительность канала.

Протоколы, в которых станции прослушивают среду передачи данных и действуют в соответствии с этим, называются протоколами с контролем (опросом) несущей (carrier sense protocols). Было разработано множество таких протоколов, и они давно подробно проанализированы, например, в работе Клейнрока и Тобаги (Kleinrock and Tobagi, 1975). Ниже мы рассмотрим несколько версий протоколов с контролем несущей.

Настойчивый и ненастойчивый CSMA

Мы начнем с протокола CSMA с настойчивостью 1 (Carrier-Sense Multiple Access — множественный доступ с контролем несущей). Длинноватое название для простейшей схемы CSMA. Когда у станции появляются данные для передачи, она сначала прослушивает канал, проверяя, свободен ли он. Когда канал простаивает, станция сразу отправляет данные. Если же он занят — она ждет освобождения линии, а затем передает фрейм. В случае коллизии станция ждет в течение случайного интервала времени, затем снова прослушивает канал, и если он свободен, повторяет передачу. Такой протокол называется CSMA с настойчивостью 1, поскольку станция передает фрейм с вероятностью 1, как только обнаружит, что канал свободен.

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