Дискретная ALOHA Робертса отличается от чистой ALOHA Абрамсона тем, что станция не может начинать передачу сразу после ввода пользователем строки. Вместо этого она должна дождаться начала нового слота. Таким образом, система ALOHA с непрерывным временем превращается в дискретную. Уязвимый временной интервал теперь в два раза короче. Чтобы понять это, взгляните на илл. 4.3 и представьте, какие теперь возможны коллизии. Вероятность отсутствия трафика в течение того же интервала, в котором передается тестовый фрейм, равна e–G. В результате получаем:

Как видно из илл. 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, как только обнаружит, что канал свободен.

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

Если копнуть чуть глубже, можно увидеть, что на число коллизий значительное влияние оказывает задержка распространения сигнала. Существует небольшая вероятность того, что как только одна станция начнет передачу, другая также придет в состояние готовности и опросит канал. Если сигнал от первой станции еще не успел достичь второй, она решит, что канал свободен, и также начнет передачу, в результате произойдет коллизия. Эта вероятность зависит от числа фреймов, помещающихся в канал, то есть от показателя «полоса пропускания, умноженная на задержку» (bandwidth-delay product) для данного канала. Если канал вмещает лишь небольшую часть фрейма, как бывает в большинстве LAN, где задержка распространения невелика, то и шанс коллизии мал. Чем больше время распространения сигнала, тем выше вероятность коллизий и ниже производительность протокола. Однако даже такая система значительно лучше чистой ALOHA, так как обе станции воздерживаются от передачи, пока передает третья станция, в результате чего ее фрейм остается неповрежденным. То же самое можно сказать о дискретной системе ALOHA.

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

Третий протокол с контролем несущей — CSMA с настойчивостью p. Он применяется в дискретных каналах и работает следующим образом. Когда станция готова передавать, она опрашивает канал. Если канал свободен, она с вероятностью p начинает передачу. С вероятностью q = 1 – p она отказывается от передачи и ждет начала следующего слота. Этот процесс повторяется до тех пор, пока фрейм не будет передан или какая-либо другая станция не начнет передачу. В последнем случае станция ведет себя так же, как в случае коллизии. Она ждет в течение случайного интервала времени, после чего начинает все заново. Если при первом прослушивании канала выясняется, что он занят, станция ждет следующий слот, а затем применяет тот же алгоритм IEEE 802.1 с использованием более совершенного протокола CSMA с настойчивостью p, который мы обсудим далее в разделе 4.4.