Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 82
Текст из файла (страница 82)
Предположим, что й станций борются за доступ к каналу. Вероятность передачи каждой станции в каждый интервал времени равна р. Вероятность того, что какая-то станция успешно получит доступ к каналу на данный интервал времени, равна 4р(1 — р)' '. Чтобы найти оптимальное значение вероятности р, продифференцнруем данное выражение по р, приравняем результат к нулю и решим полученное уравнение относительно р.
В результате мы получим, что наилучшее значение р равно 1/Й. Заменяя в формуле р на 1/я, получаем вероятность успеха при оптимальном значении р; (я — 1) Р (успех при оптимальной вероятности р) = ~ — ~ (4.4) 308 Глава 4, Подуровень управления доступом к среде Зависимость этой вероятности от количества готовых станций графически показана на рнс. 4.8. Для небольшого числа станций значение вероятности успеха является неплохим, однако как только количество станций достигает хотя бы пяти, вероятность снижается почти до асимптотической величины, равной 1/е. 1,0 г.г го 0,2 0,0 з 10 16 20 26 Количество готовых станций Рио.
4.8. Вероятность получения доступа к каналу в симмвтричном протоколе Из рисунка очевидно, что вероятность получения доступа к каналу для какой-либо станции можно увеличить, только снизив конкуренцию за канал. Этим занимаются протоколы с ограниченной конкуренцией.
Они сначала делят все станции на группы (необязательно непересекаюшиеся). Состязаться за интервал О разрешается только членам группы О, Если кто-то из них выигрывает, он получает канал и передает по нему кадр. Если никто из них не хочет передавать или происходит столкновение, члены группы 1 состязаются за интервал 1, и т. д.
При соответствующем разбиении на группы конкуренция за каждый интервал времени уменьшается, что увеличивает вероятность его успешного использования (см. левую часть графика). Вопрос в том, как разбивать станции на группы. Прежде чем обсуждать обший случай, рассмотрим несколько частных случаев. В одном нз крайних случаев в каждой группе будет по одной станции. Такое разбиение гарантирует полное отсутствие конфликтов, так как на каждый интервал времени будет претендовать только одна станция. Подобные протоколы уже рассматривались ранее (например, протокол с двоичным обратным отсчетом).
Еще одним особым случаем является разбиение на группы, состоящие из двух станций. Вероятность того, что обе станции одновременно начнут передачу в течение одного интервала, равна р', и при малых значениях р этим значением можно пренебречь. По меРе увеличения количества станций в группах вероятность столкновений будет возрастать, однако длина бит-карты, необходимой чтобы перенумеровать все группы, будет уменьшаться.
Другим предельным случаем будет одна группа, в которую войдут все станции (то есть дискретная система АЕОНА). Нам требуется механизм динамического разбиения станций на группы с небольшим количеством крупных групп при слабой загруженности канала и большом количестве мелких групп (может быть, даже состояших из одной станции каждая), когда загруженность канала высока. Протоколы коллективного доступа 309 Протокол адаптивного прохода по дереву Одним из простых способов динамического разбиения на группы является алгоритм, разработанный во время Второй мировой войны в армии США для проверки солдат на сифилис (Пог6пап, 1943).
Брался анализ крови у Мсолдат. Часть каждого образца помещалась в одну общую пробирку. Этот смешанный образец проверялся на наличие антител. Если антитела не обнаруживались, все солдаты в данной группе объявлялись здоровыми. В противном же случае группа делилась пополам, и каждая половина группы проверялась отдельно. Подобный процесс продолжался до тех пор, пока размер группы не уменьшался до одного солдата. В компьютерной версии данного алгоритма (Саресапак1з, 1979) станции рассматриваются в виде листьев двоичного дерева, как показано на рис. 4.9.
В первом временном интервале состязания за право передачи участвуют все станции, Если кому-нибудь зто удается, то на этом работа,.алгоритма заканчивается. Если же происходит столкновение, то ко второму этапу состязаний допускается только половина станций, а именно станции, относящиеся к узлу 2 дерева. Если одна из станций успешно захватывает канал, то следующее состязание устраивается для второй половины станций (относящихся к узлу 3 дерева). Если снова происходит конфликт, то к следующему интервалу времени среди состязающнхся остается уже четверть станций, относящихся к узлу 4. « †Станц А В С С Е Е В Н Рис. 4.9.
Дерево из восьми станций Таким образом, если столкновение происходит во время интервала О, то все дерево сканируется на единичную глубину для поиска готовых станций. Каждый однобитовый слот ассоциируется с определенным узлом дерева. Если происходит столкновение, поиск продолжается для левого и правого дочерних узлов. Если количество станций, претендующих на передачу, равно нулю или единице, поиск в данном узле дерева прекращается. При сильной загруженности канала вряд ли стоит начинать поиск готовой станции с узла 1, поскольку шансов, что всего одна станция из всех будет претендовать на канал, мало. По той же причине могут быть пропущены также Узлы 2 и 3.
А на каком уровне дерева следует начинать опрос в общем случае? Очевидно, что чем сильнее загруженность канала, тем на более низком уровне 310 Глава 4. Подуровень управления доступом к среде дерева должен начинаться поиск готовых станций. Будем предполагать, что каждая станция довольно точно может оценить д (количество готовых на данный момент станций), отслеживая недавний трафик, Пронумеруем уровни дерева на рис. 4.9 — узел 1 на уровне О, узлы 2 и 3 на уровне 1 и т. д. Обратите внимание на то, что каждый узел на уровне 1 включает 2-' часть от всех станций. Если 7 готовых станций распределены равномерно, то ожидаемое их число ниже узла на уровне 1 равно 2-'д. Интуитивно ясно, что оптимальным уровнем для начала поиска будет тот, на котором среднее число конкурирующих в интервале станций равно 1, то есть уровень, на котором 2 ч) = 1.
Отсюда 1 = 1оду Были разработаны многочисленные усовершенствования базового алгоритма — в частности, некоторые детали обсуждаются у Бертсекаса (ВегЬеказ) и Галлагера (Оа!1аяег) в издании 1992 года. Например, рассмотрим случай, при котором передавать хотят только станции С и Н. На узле 1 произойдет конфликт, поэтому будет проверен узел 2. Он окажется пустым. Узел 3 проверять нет смысла, так как там гарантированно будет столкновение.
(Нам известно, что под узлом 1 находятся 2 нли более станций, а так как под узлом 2 нет ни одной станции, то все они должны быть под узлом 3.) Поэтому проверку узла 3 можно пропустить и сразу проверить узел 6. Поскольку под узлом 6 ничего не оказалось, то проверку узла 7 также можно пропустить и проверить узел С. Протоколы множественного доступа со спектральным разделением Еще один метод распределения канала заключается в его разбиении на подканалы с помощью частотного, временного или смешанного разделения н динамического распределения подканалов по мере необходимости.
Подобные схемы часто применяются в оптоволоконных локальных сетях, при этом возможна одновременная передача по каналу на разных длинах волн (то есть частотах). В данном разделе мы рассмотрим один такой протокол (НцшЫег н др., 1992). Проще всего построить целиком оптическую локальную сеть с помощью коммутатора «пассивная звездаь (см. рис. 2.8). Смысл состоит в том, что два оптических волокна от каждой станции вплавляются в стеклянный цилиндр, По одному волокну свет попадает в цилиндр, а по другому он из цилиндра попадает в другое волокно. Свет, выходящий в цилиндр из одного волокна, освещает весь цилиндр и попадает во все выходящие из него волокна. Пассивные звезды могут объединять до нескольких сотен станций.
Для реализации одновременной передачи спектр делится на каналы (диапазоны длин волн), как показано на рис. 2.27. В протоколе тч1ЭМА (Жаче1епйй П(ч(з(оп Мц1кр1е Ассезз — множественный доступ со спектральным разделением) каждой станции выделяется два канала. узкий канал обеспечивает получение станцией управляющей информации, а широкий канал — передачу данных станцией.
Каждый канал делится на группы временных интервалов, как показано на рис. 4.10. Пусть количество интервалов в управляющем канале равно т, а количество интервалов в канале данных — и+ 1, из которых и интервалов исполь- Протоколы коллективного доступа 311 дуются для данных, а последний интервал — для сообщения станцией о своем состоянии (главным образом о том, какие интервалы в обоих каналах свободны).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
