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