Э. Таненбаум - Компьютерные сети. (4-е издание) (PDF) (1130118), страница 78
Текст из файла (страница 78)
4.8. Для небольшого числа станций значение вероятности успеха является неплохим, однако как только количество станций достигает хотя быпяти, вероятность снижается почти до асимптотической величины, равной 1/е.1,00,80,60,40,20,051015Количество готовых станций2025Рис. 4.8. Вероятность получения доступа к каналу в симметричном протоколеИз рисунка очевидно, что вероятность получения доступа к каналу для какой-либо станции можно увеличить, только снизив конкуренцию за канал.
Этимзанимаются протоколы с ограниченной конкуренцией. Они сначала делят всестанции на группы (необязательно непересекающиеся). Состязаться за интервал 0 разрешается только членам группы 0. Если кто-то из них выигрывает, онполучает канал и передает по нему кадр. Если никто из них не хочет передаватьили происходит столкновение, члены группы 1 состязаются за интервал 1, и т. д.При соответствующем разбиении на группы конкуренция за каждый интервалвремени уменьшается, что увеличивает вероятность его успешного использования (см.
левую часть графика).Вопрос в том, как разбивать станции на группы. Прежде чем обсуждать общий случай, рассмотрим несколько частных случаев. В одном из крайних случаев в каждой группе будет по одной станции. Такое разбиение гарантируетполное отсутствие конфликтов, так как на каждый интервал времени будет претендовать только одна станция. Подобные протоколы уже рассматривались ранее (например, протокол с двоичным обратным отсчетом). Еще одним особымслучаем является разбиение на группы, состоящие из двух станций. Вероятностьтого, что обе станции одновременно начнут передачу в течение одного интервала, равна р2, и при малых значениях р этим значением можно пренебречь.
По мере увеличения количества станций в группах вероятность столкновений будетвозрастать, однако длина бит-карты, необходимой чтобы перенумеровать всегруппы, будет уменьшаться. Другим предельным случаем будет одна группа,в которую войдут все станции (то есть дискретная система ALOHA). Нам требуется механизм динамического разбиения станций на группы с небольшим количеством крупных групп при слабой загруженности канала и большом количествемелких групп (может быть, даже состоящих из одной станции каждая), когда загруженность канала высока.309Протокол адаптивного прохода по деревуОдним из простых способов динамического разбиения на группы является алгоритм, разработанный во время Второй мировой войны в армии США для проверки солдат на сифилис (Dorfman, 1943). Брался анализ крови у Nсолдат.
Часть каждого образца помещалась в одну общую пробирку. Этот смешанный образецпроверялся на наличие антител. Если антитела не обнаруживались, все солдаты вданной группе объявлялись здоровыми. В противном же случае группа делиласьпополам, и каждая половина группы проверялась отдельно. Подобный процесспродолжался до тех пор, пока размер группы не уменьшался до одного солдата.В компьютерной версии данного алгоритма (Capetanakis, 1979) станции рассматриваются в виде листьев двоичного дерева, как показано на рис. 4.9. В первом временном интервале состязания за право передачи участвуют все станции.Если кому-нибудь это удается, то на этом работа4алгоритма заканчивается. Еслиже происходит столкновение, то ко второму этапу состязаний допускается только половина станций, а именно станции, относящиеся к узлу 2 дерева.
Если однаиз станций успешно захватывает канал, то следующее состязание устраиваетсядля второй половины станций (относящихся к узлу 3 дерева). Если снова происходит конфликт, то к следующему интервалу времени среди состязающихся остается уже четверть станций, относящихся к узлу 4.CDEFGНРис. 4.9. Дерево из восьми станцийСтанцииТаким образом, если столкновение происходит во время интервала 0, то вседерево сканируется на единичную глубину для поиска готовых станций. Каждыйоднобитовый слот ассоциируется с определенным узлом дерева. Если происходит столкновение, поиск продолжается для левого и правого дочерних узлов.
Если количество станций, претендующих на передачу, равно нулю или единице,поиск в данном узле дерева прекращается.При сильной загруженности канала вряд ли стоит начинать поиск готовойстанции с узла 1, поскольку шансов, что всего одна станция из всех будет претендовать на канал, мало. По той же причине могут быть пропущены такжеузлы 2 и 3.
А на каком уровне дерева следует начинать опрос в общем случае?Очевидно, что чем сильнее загруженность канала, тем на более низком уровне310Глава 4. Подуровень управления доступом к средедерева должен начинаться поиск готовых станций. Будем предполагать, что каждая станция довольно точно может оценить q (количество готовых на данныймомент станций), отслеживая недавний трафик.Пронумеруем уровни дерева на рис. 4.9 - узел 1 на уровне 0, узлы 2 и 3 науровне 1 и т. д. Обратите внимание на то, что каждый узел на уровне i включает2"' часть от всех станций. Если q готовых станций распределены равномерно, тоожидаемое их число ниже узла на уровне i равно 2-'q. Интуитивно ясно, что оптимальным уровнем для начала поиска будет тот, на котором среднее число конкурирующих в интервале станций равно 1, то есть уровень, на котором 2-'q - 1.Отсюда i = \og2q.Были разработаны многочисленные усовершенствования базового алгоритма—в частности, некоторые детали обсуждаются у Бертсекаса (Bertsekas) и Галлагера (Gallager) в издании 1992 года.
Например, рассмотрим случай, при котором передавать хотят только станции G и Я. На узле 1 произойдет конфликт,поэтому будет проверен узел 2. Он окажется пустым. Узел 3 проверять нет смысла, так как там гарантированно будет столкновение. (Нам известно, что под узлом 1 находятся 2 или более станций, а так как под узлом 2 нет ни одной станции, то все они должны быть под узлом 3.) Поэтому проверку узла 3 можнопропустить и сразу проверить узел 6. Поскольку под узлом 6 ничего не оказалось, то проверку узла 7 также можно пропустить и проверить узел G.Протоколы множественного доступасо спектральным разделениемЕще один метод распределения канала заключается в его разбиении на подканалы с помощью частотного, временного или смешанного разделения и динамического распределения подканалов по мере необходимости.
Подобные схемы частоприменяются в оптоволоконных локальных сетях, при этом возможна одновременная передача по каналу на разных длинах волн (то есть частотах). В данномразделе мы рассмотрим один такой протокол (Humblet и др., 1992).Проще всего построить целиком оптическую локальную сеть с помощью коммутатора «пассивная звезда» (см. рис. 2.8). Смысл состоит в том, что два оптических волокна от каждой станции вплавляются в стеклянный цилиндр. По одному волокну свет попадает в цилиндр, а по другому он из цилиндра попадает вдругое волокно. Свет, выходящий в цилиндр из одного волокна, освещает весьцилиндр и попадает во все выходящие из него волокна.
Пассивные звезды могутобъединять до нескольких сотен станций.Для реализации одновременной передачи спектр делится на каналы (диапазоны длин волн), как показано на рис. 2.27. В протоколе WDMA (WavelengthDivision Multiple Access — множественный доступ со спектральным разделением) каждой станции выделяется два канала. Узкий канал обеспечивает получение станцией управляющей информации, а широкий канал — передачу данныхстанцией.Каждый канал делится на группы временных интервалов, как показано нарис.
4.10. Пусть количество интервалов в управляющем канале равно т, а количество интервалов в канале данных — п+ 1, из которых п интервалов исполь-Протоколы коллективного доступа311зуются для данных, а последний интервал — для сообщения станцией о своем состоянии (главным образом о том, какие интервалы в обоих каналах свободны).В обоих каналах последовательность интервалов повторяется бесконечно, приэтом интервал 0 помечается специальным образом, чтобы все могли его распознать. Все каналы синхронизируются одними глобальными часами.т временных интерваловдля управленияСтанцияУправляющий канал Аиспользуется другимистанциями дляобщения с Ат и i IX i шжпя 11Жп + 1 временных интервалов для данныхУправляющий канал ВКанал данных ВУправляющий канал СИспользуетсястанцией Вдля передачиданныхКанал данных СУправляющий канал ОКанал данных ОВремя•Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
