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