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

фреймов за интервал. Очевидно, что G ≥ N. При малой загрузке канала (то есть при N ≈ 0) коллизий возникает мало, как и повторных передач, то есть G ≈ N. При большой загрузке коллизий много, а следовательно, G > N. Какая бы ни была загрузка, производительность канала S будет равна предлагаемой загрузке G, умноженной на вероятность успешной передачи P0, то есть S = GP0, где P0 — вероятность того, что фрейм не повредится в результате коллизии.

Фрейм не пострадает, если в течение интервала времени его передачи больше ничего не отправлять, как показано на илл. 4.2. При каких условиях фрейм, затененный на рисунке, будет передан без повреждений? Пусть t — это время, требуемое для передачи фрейма. Если пользователь сформирует фрейм в интервале времени между t0 и t0 + t, то его конец столкнется с началом затененного фрейма. При этом судьба затененного фрейма предрешена еще до того, как будет послан его первый бит. Но в чистой ALOHA станции не прослушивают линию до начала передачи и у них нет способа узнать, что канал занят и по нему уже передается фрейм. Аналогичным образом, любой другой фрейм, передача которого начнется в интервале от t0 + t до t0 + 2t, столкнется с концом затененного фрейма.

Илл. 4.2. Уязвимый период времени для затененного фрейма

Вероятность того, что за время фрейма вместо G будет сформировано k фреймов, можно вычислить по формуле распределения Пуассона:

(4.1)

Таким образом, вероятность генерации нуля фреймов в течение этого интервала равна e–G. Среднее количество фреймов, сформированных за интервал длиной в два фрейма, равно 2G. Вероятность того, что никто не начнет передачу в течение всего уязвимого периода, равна P0 = e–2G. Учитывая, что S = GP0, получаем:

.

Соотношение между предоставляемым трафиком и пропускной способностью показано на илл. 4.3. Максимальная производительность достигает значения S = 1/(2e), что приблизительно равно 0,184 при G = 0,5. Другими словами, лучшее, на что мы можем надеяться, — это использовать канал на 18 %. Этот результат несколько разочаровывает, но если каждый передает данные тогда, когда хочет, трудно ожидать стопроцентного успеха.

Илл. 4.3. Зависимость производительности канала от предоставляемого трафика для систем ALOHA

Дискретная система ALOHA

Вскоре после появления системы ALOHA Робертс (Roberts, 1972) опубликовал метод, позволяющий удвоить ее производительность. Он предложил разделять время на дискретные интервалы, соответствующие одному фрейму. Их называют слотами (slots). При таком подходе пользователи должны согласиться с определенными временными ограничениями. Одним из способов достижения синхронизации является установка специальной станции, которая генерирует синхронизирующий сигнал в начале каждого интервала.

Дискретная 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