Эндрю Уэзеролл - Компьютерные сети. 5-е издание

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

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

В компьютерной версии данного алгоритма (Capetanakis, 1979) станции рассматриваются в виде листьев двоичного дерева, как показано на рис. 4.10. В первом временном интервале состязания за право передачи участвуют все станции. Если кому-нибудь это удается, то на этом работа алгоритма заканчивается. Если же происходит столкновение, то ко второму этапу состязаний допускается только половина станций, а именно станции, относящиеся к узлу 2 дерева. Если одна из станций успешно захватывает канал, то следующее состязание устраивается для второй половины станций (относящихся к узлу 3 дерева). Если снова происходит конфликт, то к следующему интервалу времени среди состязающихся остается уже четверть станций, относящихся к узлу 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 = log 2q.

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

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

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

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

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

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

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

Можно наивно попытаться применить в локальных беспроводных сетях протокол CSMA( Carrier-Sense Multiple Access — множественный доступ с опросом несущей) — просто прослушивать эфир и осуществлять передачу только тогда, когда он никем не занят. Однако проблема заключается в том, что в действительности имеет значение интерференция на приемнике, а не на передатчике, поэтому этот протокол для беспроводных сетей подходит не очень хорошо. Чтобы наглядно увидеть суть проблемы, рассмотрим рис. 4.11, где показаны четыре беспроводные станции. Для нашей