Во избежание конфликтов следует применить правило арбитража: как только станция с 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.