Рис. 4.8. Протокол с двоичным обратным отсчетом. Прочерк означает молчание
Эффективность использования канала при этом методе составляет d/(d + log2W). Однако можно так хитро выбрать формат кадра, что его первое поле будет содержать адрес отправителя, тогда даже эти log2W бит не пропадут зря и эффективность составит 100 %.
Двоичный обратный отсчет является примером простого, элегантного и эффективного протокола, который еще предстоит открыть заново разработчикам будущих сетей. Хочется надеяться, что когда-нибудь он займет свою нишу в сетевых технологиях.
4.2.4. Протоколы с ограниченной конкуренцией
Итак, мы рассмотрели две основные стратегии предоставления доступа к каналу в широковещательных сетях: соревнование, как в CSMA, и бесконфликтные протоколы. Каждую стратегию можно оценить по двум важным параметрам: времени задержки при низкой загрузке канала и эффективность канала при большой загрузке. В условиях низкой загрузки конфликты (то есть чистая или дискретная системы ALOHA) предпочтительнее, так как время задержки в таких системах меньше (коллизий меньше). По мере роста загруженности канала системы со столкновениями становятся все менее привлекательными, поскольку возрастают накладные расходы, связанные с конфликтами. Для бесконфликтных протоколов справедливо обратное. При низкой нагрузке у них относительно высокое время задержки, но по мере увеличения нагрузки эффективность использования канала не уменьшается, как у конфликтных протоколов, а наоборот, возрастает (накладные расходы фиксированные).
Очевидно, было бы неплохо объединить лучшие свойства обеих стратегий и получить протокол, использующий разные стратегии при разной загруженности канала. Такие протоколы мы будем называть протоколами с ограниченной конкуренцией (limited-contention protocols). Они в самом деле существуют, и их рассмотрением мы завершим изучение сетей с опросом носителя.
До сих пор мы рассматривали только симметричные протоколы коллективного доступа, в которых каждая станция пытается получить доступ к каналу с равной вероятностью р. Интересно, что производительность всей системы может быть улучшена при использовании асимметричного протокола, в котором станциям назначаются различные вероятности.
Прежде чем приступить к рассмотрению асимметричных протоколов, давайте кратко рассмотрим производительность в симметричном случае. Предположим, что k станций борются за доступ к каналу. Вероятность передачи каждой станции в каждый интервал времени равна р. Вероятность того, что какая-то станция успешно получит доступ к каналу на данный интервал времени, составляется из вероятности того, что любая станция передает данные с вероятностьюр, а все остальные k - 1 станций воздерживаются от передачи, каждая с вероятностью 1 - р. Итоговое значение равно kp(1 - p)k-1. Чтобы найти оптимальное значение вероятности р, продифференцируем данное выражение по р, приравняем результат нулю и решим полученное уравнение относительно р. В результате мы получим, что наилучшее значение р равно 1/k. Заменяя в формуле р на 1/k, получаем вероятность успеха при оптимальном значении р:
Зависимость этой вероятности от количества готовых станций графически показана на рис. 4.9. Для небольшого числа станций значение вероятности успеха является неплохим, однако как только количество станций достигает хотя бы пяти, вероятность снижается почти до асимптотической величины, равной 1/e.
Рис. 4.9. Вероятность получения доступа к каналу в симметричном протоколе
Из рисунка очевидно, что вероятность получения доступа к каналу для какой-либо станции можно увеличить, только снизив конкуренцию за канал. Этим занимаются протоколы с ограниченной конкуренцией. Они сначала делят все станции на группы (необязательно непересекающиеся). Состязаться за интервал 0 разрешается только членам группы 0. Если кто-то из них выигрывает, он получает канал и передает по нему кадр. Если никто из них не хочет передавать или происходит столкновение, члены группы 1 состязаются за интервал 1 и т. д. При соответствующем разбиении на группы конкуренция за каждый интервал времени уменьшается, что увеличивает вероятность его успешного использования (см. левую часть графика).
Вопрос в том, как разбивать станции на группы. Прежде чем обсуждать общий случай, рассмотрим несколько частных случаев. В одном из крайних случаев в каждой группе будет по одной станции. Такое разбиение гарантирует полное отсутствие конфликтов, так как на каждый интервал времени будет претендовать только одна станция. Подобные протоколы уже рассматривались ранее (например, протокол с двоичным обратным отсчетом). Еще одним особым случаем является разбиение на группы, состоящие из двух станций. Вероятность того, что обе станции одновременно начнут передачу в течение одного интервала, равна p2, и при малых значениях p этим значением можно пренебречь. По мере увеличения количества станций в группах, вероятность столкновений будет возрастать, однако длина битовой карты, необходимой, чтобы перенумеровать все группы, будет уменьшаться. Другим предельным случаем будет одна группа, в которую войдут все станции (то есть дискретная система ALOHA). Нам требуется механизм динамического разбиения станций на группы, с небольшим количеством крупных групп при слабой загруженности канала и большом количестве мелких групп (может быть, даже состоящих из одной станции каждая), когда загруженность канала высока.
Протокол адаптивного прохода по дереву
Одним из простых способов динамического разбиения на группы является алгоритм, разработанный во время Второй мировой войны в армии США для проверки солдат на сифилис (Dorfman, 1943). Брался анализ крови у N солдат. Часть каждого образца помещалась в одну общую пробирку. Этот смешанный образец проверялся на наличие антител. Если антитела не обнаруживались, все солдаты в данной группе объявлялись здоровыми. В противном же случае группа делилась пополам, и каждая половина группы проверялась отдельно. Подобный процесс продолжался до тех пор, пока размер группы не уменьшался до одного солдата.
В компьютерной версии данного алгоритма (Capetanakis, 1979) станции рассматриваются в виде листьев двоичного дерева, как показано на рис. 4.10. В первом временном интервале состязания за право передачи участвуют все станции. Если кому-нибудь это удается, то на этом работа алгоритма заканчивается. Если же происходит столкновение, то ко второму этапу состязаний допускается только половина станций, а именно станции, относящиеся к узлу 2 дерева. Если одна из станций успешно захватывает канал, то следующее состязание устраивается для второй половины станций (относящихся к узлу 3 дерева). Если снова происходит конфликт, то к следующему интервалу времени среди состязающихся остается уже четверть станций, относящихся к узлу 4.
Рис. 4.10. Дерево из восьми станций
Таким образом, если столкновение происходит во время интервала 0, то все дерево сканируется на единичную глубину для поиска готовых станций. Каждый однобитовый слот ассоциируется с определенным узлом дерева. Если происходит столкновение, поиск продолжается для левого и правого дочерних узлов. Если количество станций, претендующих на передачу, равно нулю или единице, поиск в данном узле дерева прекращается, поскольку все готовые станции уже обнаружены.
При сильной загруженности канала вряд ли стоит начинать поиск готовой станции с узла 1, поскольку шансов, что всего одна станция из всех будет претендовать на канал, мало. По той же причине могут быть пропущены также узлы 2 и 3. А на каком уровне дерева следует начинать опрос в общем случае? Очевидно, что чем сильнее загруженность канала, тем на более низком уровне дерева должен начинаться поиск готовых станций. Будем предполагать, что каждая станция довольно точно может оценить q (количество готовых на данный момент станций), например, отслеживая недавний трафик.
