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

В компьютерной версии данного алгоритма (Капетанакис; 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 Гбит/с, однако в реальности она гораздо ниже.

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