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

4.2. Протоколы коллективного доступа

Существует множество алгоритмов коллективного доступа. В следующих разделах будут рассмотрены наиболее интересные из них и даны примеры их применения на практике.

4.2.1. Система ALOHA

История первого протокола подуровня MAC начинается на нетронутых цивилизацией Гавайях в 1970-х годах. В данном случае «нетронутые цивилизацией» означает «не имеющие рабочей телефонной системы». Это не упрощало жизнь Нормана Абрамсона (Norman Abramson) и его коллег из Гавайского университета, которые пытались подключить пользователей на удаленных островах к главному компьютеру в Гонолулу. Идея протянуть кабели на громадное расстояние по дну Тихого океана даже не рассматривалась, так что исследователи искали другой способ.

Решение было основано на использовании радиосистемы ближнего радиуса действия. Терминал каждого пользователя передавал фреймы на центральный компьютер в пределах общей полосы частот. Также был найден простой и элегантный метод решения проблемы распределения каналов. Результаты работы этой группы ученых впоследствии стали основой многих исследований (Шварц и Абрамсон; Schwartz and Abramson, 2009). Несмотря на то что в разработанной Абрамсоном сети ALOHA использовалась широковещательная радиосвязь со стационарными передатчиками, ее общий принцип применим к любой системе, в которой независимые пользователи соревнуются за право использования одного общего канала.

В данном разделе мы рассмотрим две версии системы ALOHA: чистую и дискретную. Различие между ними состоит в том, что в чистой версии время является непрерывным, а в дискретной делится на дискретные интервалы, в которые должны помещаться все фреймы.

Чистая система ALOHA

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

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

На илл. 4.1 показан пример формирования фреймов в ALOHA. Все они имеют единый фиксированный размер, так как за счет этого пропускная способность системы становится максимальной.

Когда два фрейма одновременно пытаются занять канал, происходит коллизия (как видно на илл. 4.1). Оба фрейма искажаются. Даже если только один первый бит второго фрейма перекроет последний бит первого, оба фрейма полностью теряются (то есть их контрольные суммы не совпадут с правильными значениями). Позже они должны быть переданы повторно. В контрольной сумме нет (и не должно быть) различия между полным и частичным искажением информации. Потеря есть потеря.

Илл. 4.1. В чистой системе ALOHA фреймы передаются в абсолютно произвольное время

Интересно, какова эффективность канала ALOHA? Другими словами, какая часть передаваемых фреймов избежит коллизии при таком беспорядке? Представьте бесконечное множество пользователей, сидящих за своими компьютерами (станциями). Пользователь всегда находится в одном из двух состояний: ввод с клавиатуры или ожидание. Вначале все находятся в состоянии ввода. Закончив набор строки, пользователь перестает вводить текст, ожидая ответа. В это время станция передает фрейм, содержащий набранную строку, по общему каналу на центральный компьютер и опрашивает канал, проверяя успешность передачи. Если фрейм передан успешно, пользователь видит ответ и продолжает набор. В противном случае он ждет повторной передачи, которая происходит раз за разом, пока данные не будут успешно отправлены.

Пусть «время фрейма» означает интервал, требуемый для отправки стандартного фрейма фиксированной длины (это длина фрейма, деленная на скорость передачи). Допустим, новые фреймы, порождаемые станциями, хорошо распределены по Пуассону со средним значением N фреймов за интервал. (Допущение о бесконечном количестве пользователей необходимо для того, чтобы гарантировать, что N не станет уменьшаться по мере их блокирования.) Если N > 1, это означает, что сообщество пользователей формирует фреймы с большей скоростью, чем может быть передано по каналу, и почти каждый фрейм будет искажаться. Разум­нее предположить, что 0 < N < 1.

Помимо новых, станции повторно отправляют старые фреймы, пострадавшие от столкновений. Предположим, что старые и новые фреймы хорошо распределены по Пуассону со средним значением G фреймов за интервал. Очевидно, что 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 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.

На илл. 4.4 показана расчетная зависимость производительности канала от предлагаемого потока фреймов для всех трех протоколов, а также для чистой и дискретной систем ALOHA.

Илл. 4.4. Сравнение использования канала в зависимости от его загрузки для различных протоколов коллективного доступа

Протокол CSMA с обнаружением коллизий

Настойчивый и ненастойчивый протоколы CSMA, несомненно, более эффективны по сравнению с системой ALOHA, поскольку гарантируют, что ни одна станция не начнет передачу, если канал уже занят. Однако если две станции, обнаружив, что канал свободен, одновременно начали передачу, коллизия все равно произойдет. Еще одно улучшение — станции способны быстро распознать коллизию и немедленно прекратить передачу (а не доводить ее до конца), так как данные все равно искажены. Эта стратегия обеспечивает более экономное использование времени и пропускной способности канала.

Протокол CSMA с обнаружением коллизий (CSMA/CD) лежит в основе классических локальных сетей Ethernet и потому заслуживает подробного рассмотрения. Важно понимать, что распознавание коллизий представляет собой аналоговый процесс. Оборудование станции должно прослушивать канал во время передачи. Если считываемый сигнал отличается от пересылаемого, становится понятно, что произошла коллизия. Полученный сигнал не обязательно должен идеально совпадать с отправленным. Это затруднительно для беспроводных сетей, в которых принятый сигнал нередко в 1 000 000 раз слабее отправленного. Необходимо выбрать такую модуляцию, которая позволит распознавать коллизии (например, коллизию двух 0-вольтовых сигналов распознать практически невозможно).

В протоколе CSMA/CD, как и во многих других протоколах LAN, применяется концептуальная модель, показанная на илл. 4.5. В момент времени t0 одна из станций заканчивает передачу фрейма. Все остальные станции, готовые к передаче, теперь могут попытаться отправить свои фреймы. Если две или несколько станций одновременно начнут передачу, то произойдет коллизия. Обнаружив ее, станция прекращает передачу, ждет в течение случайного периода времени, после чего пытается снова, при условии, что к этому моменту не начала передачу другая станция. Таким образом, простая модель протокола CSMA/CD состоит из чередующихся периодов конкуренции и передачи, а также периодов простоя (когда все станции молчат).

Илл. 4.5. Протокол CSMA/CD может находиться в одном из трех состояний: передачи, конкуренции и простоя

Рассмотрим более подробно алгоритм борьбы за право использования канала. Предположим, две станции одновременно начали передачу в момент t0. Сколько понадобится времени на то, чтобы они поняли, что произошла коллизия? От ответа на этот вопрос зависит длина периода конкуренции, а следовательно, величина задержки и производительность канала.

Минимальное время обнаружения коллизии равно времени распространения сигнала от одной станции до другой. Исходя из этого, можно предположить, что станция, которая не фиксирует коллизию за время, требуемое для прохождения сигнала по всему кабелю, может быть уверена, что ей удалось захватить канал. «Захват» означает, что все остальные станции знают, что она осуществляет передачу, и не мешают ей. Однако такое заключение неверно.

Рассмотрим наихудший сценарий. Пусть время, необходимое для прохождения сигнала между двумя самыми дальними станциями, равно τ. В момент времени t0 одна из станций отправляет сигнал. В момент времени 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. Фреймы передаются в том же направлении, что и маркер. Они передаются по кольцу, проходя по всем станциям, которые оказываются на их пути. Но чтобы фрейм не циркулировал вечно (как маркер), какая-то станция должна извлечь его из кольца. Это может быть либо

Илл. 4.7. Маркерное кольцо

первоначальный отправитель (если фрейм прошел полный цикл), либо станция-получатель.

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

В этом случае каждая станция передает маркер по шине соседям в предопределенном порядке. Получив маркер, станция может использовать шину для отправки одного фрейма. Такой протокол называется маркерной шиной (token bus). Он описан в стандарте IEEE 802.4, который оказался настолько неудачным, что был отменен институтом IEEE. Стандарты не вечны.

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

Протоколы MAC на базе маркерных колец появляются с определенной периодичностью. Один из ранних протоколов такого рода — Token Ring, то есть «Маркерное кольцо», — описан в стандарте IEEE 802.5. В 1980-х он был популярен в качестве альтернативы классическому Ethernet. В 1990-е годы намного более быстрое маркерное кольцо, интерфейс передачи распределенных данных по волоконно-оптическим каналам (Fiber Distributed Data Interface, FDDI), потерпело поражение от коммутируемого Ethernet. В 2000-х отказоустойчивое пакетное кольцо (Resilient Packet Ring, RPR) было описано в IEEE 802.17, чтобы стандартизировать множество вариантов кольцевых сетей, используемых провайдерами в городских условиях. Интересно, какие протоколы появятся после 2020 года.

Двоичный обратный отсчет

Недостатком двух представленных выше протоколов являются накладные расходы в один бит на станцию. Из-за этого они плохо масштабируются на большие сети с сотнями или даже тысячами станций. Можно добиться лучших результатов, используя двоичные адреса станций и канал, способный определенным образом комбинировать передаваемые данные. Станция, желающая занять канал, объявляет свой адрес в виде битовой строки, начиная со старшего бита. Предполагается, что все адреса станций содержат одинаковое количество битов. Будучи отправленными одновременно, биты адреса в каждой позиции логически складываются (логическое ИЛИ) средствами канала. Мы будем называть этот метод протоколом с двоичным обратным отсчетом (binary countdown). Он использовался в сети Datakit (Фрейзер; Fraser, 1983). Подразумевается, что задержки распространения сигнала пренебрежимо малы, поэтому станции слышат утверждаемые номера практически мгновенно.

Во избежание конфликтов следует применить правило арбитража: как только станция с 0 в старшем бите адреса видит, что в суммарном адресе этот 0 заменился единицей, она сдается и ждет следующего цикла. Например, если станции 0010, 0100, 1001 и 1010 конкурируют за канал, то в первом битовом интервале они передают биты 0, 0, 1 и 1 соответственно. В этом случае суммарный первый бит адреса будет равен 1. Следовательно, станции с номерами 0010 и 0100 считаются проигравшими, а станции 1001 и 1010 продолжают борьбу.

Следующий бит у обеих оставшихся станций равен 0 — таким образом, обе продолжают. Третий бит равен 1, поэтому станция 1001 сдается. Победителем оказывается станция 1010, так как ее адрес наибольший. Выиграв торги, она может начать передачу фрейма, после чего начнется новый цикл торгов. Схема протокола показана на илл. 4.8. Данный метод предполагает, что приоритет станции напрямую зависит от ее номера. В некоторых случаях такое жесткое правило может играть положительную, а порой — отрицательную роль.

Илл. 4.8. Протокол с двоичным обратным отсчетом. Прочерк означает молчание

Эффективность использования канала при этом методе составляет d/(d + + log2 N). Однако можно так хитро выбрать формат фрейма, что его первое поле будет содержать адрес отправителя. Тогда даже эти log2 N бит не пропадут зря и эффективность составит 100 %.

Двоичный обратный отсчет является примером простого, элегантного и эффективного протокола. Разработчикам будущих сетей еще предстоит заново его открыть. Хочется надеяться, что когда-нибудь он займет свою нишу в сетевых технологиях.

4.2.4. Протоколы с ограниченной конкуренцией

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

Очевидно, что было бы неплохо объединить лучшие свойства обеих стратегий и получить протокол, использующий разные стратегии в зависимости от загруженности канала. Такие протоколы мы будем называть протоколами с ограниченной конкуренцией (limited-contention protocols) — они на самом деле существуют. На них мы завершим изучение сетей с контролем несущей.

До сих пор мы рассматривали только симметричные протоколы коллективного доступа, в которых каждая станция пытается получить доступ к каналу с равной вероятностью p. Интересно, что производительность всей системы может быть увеличена при использовании асимметричного протокола, в котором станциям назначаются различные вероятности.

Прежде чем приступить к асимметричным протоколам, давайте кратко рассмотрим производительность в симметричном случае. Предположим, что k станций конкурируют за доступ к каналу. Вероятность передачи каждой станции в каждый интервал времени равна p. Шанс получения станцией доступа к каналу в данном слоте включает вероятность того, что любая станция передает данные (с вероятностью p), а остальные k – 1 станций воздерживаются от передачи (каждая с вероятностью 1 – p). Итоговое значение равно kp(1 – p)k – 1. Чтобы найти оптимальное значение p, продифференцируем данное выражение по p, приравняем результат к нулю и решим полученное уравнение относительно p. В результате наилучшее значение p равно 1/k. Заменив в формуле p на 1/k, мы получим вероятность успеха при оптимальном значении p:

Pr [успех при оптимальной вероятности p] = .

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

Из илл. 4.9 очевидно, что вероятность получения доступа к каналу для какой-либо станции можно увеличить, только снизив конкуренцию за канал. Этим занимаются протоколы с ограниченной конкуренцией. Сначала они делят все станции на группы (необязательно непересекающиеся). Состязаться за интервал 0 разрешается только членам группы 0. Если кто-то из них выигрывает, он получает канал и передает по нему фрейм. Если никто из них не хочет передавать или происходит коллизия, члены группы 1 состязаются за интервал 1, и т.д. При соответствующем разбиении на группы конкуренция за каждый слот уменьшается, что повышает вероятность его успешного использования (см. левую часть графика).

Илл. 4.9. Вероятность получения доступа к каналу в симметричном протоколе

Вопрос в том, как разбивать станции на группы. Прежде чем обсуждать общий случай, рассмотрим несколько частных. Для начала возьмем крайний случай, когда каждая группа включает только одну станцию. Такое разбиение гарантирует полное отсутствие коллизий, так как на каждый интервал времени будет претендовать только один участник. Подобные протоколы уже рассматривались ранее (например, протокол с двоичным обратным отсчетом). Еще одним особым случаем является разбиение на группы, состоящие из двух станций. Вероятность того, что обе станции одновременно начнут передачу в течение одного интервала, равна p2, и при малых значениях p этим значением можно пренебречь. По мере увеличения количества станций в группах вероятность столкновений будет возрастать, однако длина битовой карты, необходимой, чтобы перенумеровать все группы, будет уменьшаться. Другим предельным случаем будет одна группа, в которую войдут все станции (то есть дискретная система ALOHA). Нам требуется механизм динамического разбиения станций, с небольшим количеством крупных групп при слабой загруженности канала и большом количестве мелких групп (может быть, даже из одной станции), когда нагрузка на канал высока.

Протокол адаптивного прохода по дереву

Одним из простых способов динамического разбиения на группы является алгоритм, разработанный во время Второй мировой войны в армии США для проверки солдат на сифилис (Дорфман; Dorfman, 1943). У N солдат брался анализ крови. Часть каждого образца помещалась в одну общую пробирку. Этот смешанный образец проверялся на наличие антител. Если антитела не обнаруживались, все солдаты в данной группе объявлялись здоровыми. В противном же случае группа делилась пополам, и каждая половина группы проверялась отдельно. Подобный процесс продолжался до тех пор, пока размер группы не уменьшался до одного солдата.

В компьютерной версии данного алгоритма (Капетанакис; Capetanakis, 1979) станции рассматриваются в виде листьев двоичного дерева, как показано на илл. 4.10. В первом после успешной передачи периоде конкуренции (слот 0) могут участвовать все станции. Если одной из них удается получить канал, то на этом работа алгоритма заканчивается. В случае коллизии ко второму этапу (слот 1) допускается только половина станций, те, которые относятся к узлу 2 дерева. Если одна из этих станций успешно захватывает канал, то следующее состязание устраивается для второй половины станций (относящихся к узлу 3 дерева). Если же две или более станции узла 2 конфликтуют в слоте 1, то в конкуренции в слоте 2 участвуют станции узла 4.

Илл. 4.10. Дерево из восьми станций

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

При сильной загруженности канала вряд ли стоит начинать поиск с узла 1 — маловероятно, что из всех станций претендовать на канал будет всего одна. По той же причине могут быть пропущены узлы 2 и 3. На каком уровне дерева следует запускать алгоритм в общем случае? Очевидно, что чем сильнее загруженность канала, тем более низкий уровень выбирается для начала поиска готовых станций. Мы будем предполагать, что каждая станция может точно оценить q (количество готовых на данный момент станций), например, отслеживая недавний трафик.

Пронумеруем уровни дерева на илл. 4.10 — узел 1 на уровне 0, узлы 2 и 3 на уровне 1 и т.д. Обратите внимание, что каждый узел на уровне i включает в себя 2–i часть от всех нижележащих станций. Если q распределяется равномерно, то ожидаемое число готовых станций ниже узла на уровне i равно 2–iq. Вполне очевидно, что оптимальным уровнем для начала поиска будет тот, на котором среднее число конкурирующих в интервале станций равно 1, то есть уровень, на котором 2–iq = 1. Отсюда получаем i = log2 q.

Были разработаны многочисленные усовершенствования базового алгоритма, — в частности, некоторые детали обсуждаются в работе Бертсекаса и Галлагера (Bertsekas and Gallager, 1992). Идея оказалась настолько удачной, что исследователи продолжают ее оптимизировать до сих пор (см. работу Де Марко и Ковальски; De Marco and Kowalski, 2017). Например, рассмотрим случай, при котором передавать хотят только станции G и H. На узле 1 произойдет коллизия, поэтому будет проверен узел 2. Он окажется пустым. Узел 3 проверять нет смысла, так как там гарантированно будет коллизия. (Нам известно, что под узлом 1 находятся две или более станции, а так как под узлом 2 нет ни одной станции, то все они должны быть под узлом 3.) Поэтому проверку узла 3 можно пропустить и сразу проверить узел 6. Поскольку под узлом 6 ничего не оказалось, то проверку узла 7 также можно пропустить и проверить узел G.

4.2.5. Протоколы беспроводных локальных сетей

Систему, состоящую из ноутбуков, взаимодействующих по радио, можно рассматривать как беспроводную локальную сеть — мы уже обсуждали это в разделе 1.4.3. Такая LAN — пример сети на базе широковещательного канала. Она имеет другие характеристики, нежели проводная LAN, поэтому здесь требуются специальные протоколы управления доступом к среде (MAC). В данном разделе мы познакомимся с некоторыми из них. Далее в разделе 4.4 мы подробно рассмотрим стандарт 802.11 (Wi-Fi).

Распространенная конфигурация беспроводных LAN подразумевает наличие офисного здания с заранее размещенными в нем точками доступа. Все точки соединены друг с другом медным проводом или оптоволоконным кабелем; они рассылают данные на пользовательские станции. Если мощность передатчиков точек доступа и ноутбуков настроена так, что диапазон приема составляет около десятка метров, то соседние комнаты становятся единой сотой. Тогда все здание превращается в большую сотовую систему, подобную мобильной телефонии, описанной в главе 2. В отличие от обычной сотовой системы, у каждой соты в данном случае всего один канал, работающий со всеми станциями, находящимися в нем, включая точку доступа. Обычно пропускная способность такого канала измеряется мегабитами или даже гигабитами в секунду. Теоретически стандарт IEEE 802.11ac обеспечивает пропускную способность до 7 Гбит/с, однако в реальности она гораздо ниже.

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

Есть еще одно очень важное различие между проводными и беспроводными LAN. В беспроводной сети у станций иногда нет возможности передавать или получать фреймы с других станций из-за ограниченного диапазона радиопередачи. В проводных сетях, если одна станция отправляет фрейм, все остальные его получают. Эта особенность приводит к различным сложностям.

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

В беспроводных LAN можно просто попытаться применить протокол CSMA — прослушивать эфир и осуществлять передачу только тогда, когда он никем не занят. Но проблема в том, что в действительности имеет значение интерференция на приемнике, а не на передатчике, поэтому этот протокол не слишком подходит для беспроводных сетей. Чтобы наглядно увидеть суть проблемы, рассмотрим илл. 4.11, где показаны четыре беспроводные станции. В нашем случае не имеет значения, какая из них является точкой доступа, а какая — портативным компьютером. Мощность передатчиков такова, что взаимодействовать могут только соседние станции, то есть A может слышать B, C — B и D (но не A).

Илл. 4.11. Беспроводная локальная сеть. (а) A и C — скрытые станции во время пересылки данных на B. (б) B и C — засвеченные станции во время пересылки данных на A и D

Сначала рассмотрим, что происходит, когда станции A и C передают данные станции B, как изображено на илл. 4.11 (а). Если A отправляет данные, а C сразу же опрашивает канал, то она не будет слышать A, поскольку та расположена слишком далеко, и может прийти к неверному выводу о том, что канал свободен и можно посылать данные на станцию B. Если станция C начнет передачу, она будет конфликтовать со станцией B и исказит фрейм, передаваемый станцией A. (Мы предполагаем, что никакая схема по типу CDMA не используется для предоставления нескольких каналов, поэтому из-за коллизий сигналы искажаются и оба фрейма разрушаются.) Нам необходим MAC-протокол, который предотвратит коллизии такого рода, ведь это лишняя трата полосы пропускания. Проблема, при которой одна станция не слышит возможного конкурента, поскольку он расположен слишком далеко от нее, называется проблемой скрытой станции (hidden terminal problem).

Теперь рассмотрим другую ситуацию: B передает данные A в то же время, когда С хочет начать передачу D, как показано на илл. 4.11 (б). Станция С при опросе канала слышит выполняемую передачу и может ошибочно предположить, что она не может передавать данные станции D (пунктирная стрелка на рисунке). В действительности такая передача создала бы помехи только в зоне от станции B до станции C, где в данный момент не ведется прием. Нам необходим MAC-протокол, который предотвратит такой тип задержек, ведь это лишняя трата полосы пропускания. Такая ситуация называется проблемой засвеченной станции (exposed terminal problem).

Сложность в том, что перед тем, как начать передачу, станции необходимо знать, есть ли какая-нибудь активность в радиодиапазоне вблизи приемника. Протокол CSMA может лишь сообщить об активности вокруг передатчика путем опрашивания несущей. В случае проводной передачи все сигналы достигают всех станций, поэтому такой проблемы нет. При этом во всей системе одновременно только одна станция может вести передачу. В системе на основе радиосвязи ближнего действия несколько станций могут передавать данные одновременно, если принимающие станции находятся достаточно далеко. Нам нужно, чтобы даже в растущей соте одновременная передача не прекращалась. Так, гости на вечеринке не ждут, пока все замолчат, чтобы начать говорить, — в большом помещении может происходить несколько разговоров одновременно (если только все гости не пытаются пообщаться с одним и тем же собеседником).

Одним из первых значительных протоколов, разработанных для беспроводных LAN и умеющих справляться с этими проблемами, является протокол MACA (Multiple Access with Collision Avoidance — множественный доступ с предотвращением коллизий) (Карн; Karn, 1990; Гарсиа-Луна-Асевес; Garcia-Luna-Aceves, 2017). Идея, лежащая в основе этого протокола, заключается в том, что отправитель заставляет получателя передать короткий фрейм. Соседние станции слышат эту передачу и воздерживаются от действий на время, требуемое для приема большого фрейма данных. Этот метод заменяет контроль несущей.

Протокол MACA проиллюстрирован на илл. 4.12. Рассмотрим ситуацию, в которой станция A передает станции B. Станция A начинает с того, что посылает станции B фрейм RTS (Request To Send — запрос на передачу), как показано на илл. 4.12 (а). Этот короткий фрейм (30 байт) содержит длину фрейма данных, который последует за ним. Затем B отвечает фреймом CTS (Clear To Send — разрешение передачи), см. илл. 4.12 (б). Он также содержит длину фрейма данных (скопированную из фрейма RTS). Приняв фрейм CTS, A начинает передачу.

Теперь выясним, как реагируют станции, фиксирующие передачу одного из этих фреймов. Любая станция, которая фиксирует RTS, находится близко к станции A и поэтому должна молчать, пока та не примет CTS. Станции, слышащие CTS, находятся рядом с B, следовательно, должны воздержаться от передачи, пока станция B не получит фрейм данных (его длину они могут узнать из CTS).

На илл. 4.12 станция C находится в зоне станции A, но не входит в зону станции B. Поэтому она фиксирует RTS от A (но не CTS от B). Поскольку она не интерферирует с CTS, она не обязана воздерживаться от передачи в то время, пока пересылается фрейм с данными. D, напротив, находится близко от B, но далеко от A. Она не слышит RTS, но фиксирует CTS, а это означает, что она находится вблизи станции, собирающейся принять фрейм с данными. Поэтому ей нельзя вести передачу, пока этот фрейм не будет получен. E слышит оба управляющих сообщения и так же, как и D, должна хранить молчание, пока не будет завершена передача фрейма данных.

Илл. 4.12. Протокол MACA. (а) Станция A посылает фрейм RTS станции B. (б) станция B отвечает фреймом CTS станции A

Несмотря на все меры предосторожности, коллизии все равно могут произойти. Например, станции B и C могут одновременно послать RTS станции A. Возникнет коллизия, и фреймы не будут приняты. В этом случае передатчики, не услышав CTS в установленный срок, ждут случайное время и повторяют попытку.