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

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