Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 86
Текст из файла (страница 86)
В 2000-е маркерное кольцо RPR (Resilient Packet Ring,отказоустойчивое пакетное кольцо), определенное в стандарте IEEE 802.17, стандартизирует множество вариантов кольцевых сетей, применяемых в городских условияхпоставщиками услуг Интернета. Интересно, что появится после 2010 года.Двоичный обратный отсчетНедостатком базового протокола битовой карты, а также протокола с передачей маркера являются накладные расходы в один бит на станцию, из-за чего они плохо масштабируются на большие сети с тысячами станций.
Используя двоичный адрес станции,можно улучшить эффективность канала. Станция, желающая занять канал, объявляетсвой адрес в виде битовой строки, начиная со старшего бита. Предполагается, что всеадреса станций имеют одинаковую длину. Будучи отправленными одновременно, битыадреса в каждой позиции логически складываются (логическое ИЛИ) средствамиканала.
Мы будем называть этот протокол протоколом с двоичным обратным отсчетом (binary countdown). Он использовался в сети Datakit (Fraser, 1987). Неявнопредполагается, что задержки распространения сигнала пренебрежимо малы, поэтомустанции слышат утверждаемые номера практически мгновенно.Во избежание конфликтов следует применить правило арбитража: как толькостанция с 0 в старшем бите адреса видит, что в суммарном адресе этот 0 заменилсяединицей, она сдается и ждет следующего цикла.
Например, если станции 0010, 0100,1001 и 1010 конкурируют за канал, то в первом битовом интервале они передают биты0, 0, 1 и 1 соответственно. В этом случае суммарный первый бит адреса будет равен 1.Следовательно, станции с номерами 0010 и 0100 считаются проигравшими, а станции1001 и 1010 продолжают борьбу.298 Глава 4. Подуровень управления доступом к средеСледующий бит у обеих оставшихся станций равен 0 — таким образом, обе продолжают.
Третий бит равен 1, поэтому станция 1001 сдается. Победителем оказываетсястанция 1010, так как ее адрес наибольший. Выиграв торги, она может начать передачукадра, после чего начнется новый цикл торгов. Схема протокола показана на рис. 4.8.Данный метод предполагает, что приоритет станции напрямую зависит от ее номера.В некоторых случаях такое жесткое правило может играть положительную, в некоторых — отрицательную роль.Рис. 4.8. Протокол с двоичным обратным отсчетом. Прочерк означает молчаниеЭффективность использования канала при этом методе составляет d/(d + log2N ). Однако можно так хитро выбрать формат кадра, что его первое поле будет содержать адресотправителя, тогда даже эти log2N бит не пропадут зря и эффективность составит 100 %.Двоичный обратный отсчет является примером простого, элегантного и эффективного протокола, который еще предстоит открыть заново разработчикам будущих сетей.Хочется надеяться, что когда-нибудь он займет свою нишу в сетевых технологиях.4.2.4.
Протоколы с ограниченной конкуренциейИтак, мы рассмотрели две основные стратегии предоставления доступа к каналу в широковещательных сетях: соревнование, как в CSMA, и бесконфликтные протоколы.Каждую стратегию можно оценить по двум важным параметрам: времени задержкипри низкой загрузке канала и эффективность канала при большой загрузке. В условиях низкой загрузки конфликты (то есть чистая или дискретная системы ALOHA)предпочтительнее, так как время задержки в таких системах меньше (коллизий меньше). По мере роста загруженности канала системы со столкновениями становятсявсе менее привлекательными, поскольку возрастают накладные расходы, связанныес конфликтами.
Для бесконфликтных протоколов справедливо обратное. При низкойнагрузке у них относительно высокое время задержки, но по мере увеличения нагрузкиэффективность использования канала не уменьшается, как у конфликтных протоколов, а наоборот, возрастает (накладные расходы фиксированные).4.2. Протоколы коллективного доступа 299Очевидно, было бы неплохо объединить лучшие свойства обеих стратегий и получить протокол, использующий разные стратегии при разной загруженности канала.Такие протоколы мы будем называть протоколами с ограниченной конкуренцией(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:k !1" k ! 1%P [успех при оптимальной вероятности p] = $. # k '&(4.4)Зависимость этой вероятности от количества готовых станций графически показана на рис. 4.9. Для небольшого числа станций значение вероятности успеха являетсянеплохим, однако как только количество станций достигает хотя бы пяти, вероятностьснижается почти до асимптотической величины, равной 1/e.Рис. 4.9. Вероятность получения доступа к каналу в симметричном протоколе300 Глава 4. Подуровень управления доступом к средеИз рисунка очевидно, что вероятность получения доступа к каналу для какой-либостанции можно увеличить, только снизив конкуренцию за канал. Этим занимаютсяпротоколы с ограниченной конкуренцией. Они сначала делят все станции на группы(необязательно непересекающиеся). Состязаться за интервал 0 разрешается толькочленам группы 0.
Если кто-то из них выигрывает, он получает канал и передает понему кадр. Если никто из них не хочет передавать или происходит столкновение,члены группы 1 состязаются за интервал 1 и т. д. При соответствующем разбиениина группы конкуренция за каждый интервал времени уменьшается, что увеличиваетвероятность его успешного использования (см. левую часть графика).Вопрос в том, как разбивать станции на группы.
Прежде чем обсуждать общийслучай, рассмотрим несколько частных случаев. В одном из крайних случаев в каждой группе будет по одной станции. Такое разбиение гарантирует полное отсутствиеконфликтов, так как на каждый интервал времени будет претендовать только однастанция. Подобные протоколы уже рассматривались ранее (например, протоколс двоичным обратным отсчетом). Еще одним особым случаем является разбиение нагруппы, состоящие из двух станций. Вероятность того, что обе станции одновременноначнут передачу в течение одного интервала, равна p2, и при малых значениях p этимзначением можно пренебречь. По мере увеличения количества станций в группах,вероятность столкновений будет возрастать, однако длина битовой карты, необходимой, чтобы перенумеровать все группы, будет уменьшаться.
Другим предельнымслучаем будет одна группа, в которую войдут все станции (то есть дискретная системаALOHA). Нам требуется механизм динамического разбиения станций на группы, с небольшим количеством крупных групп при слабой загруженности канала и большомколичестве мелких групп (может быть, даже состоящих из одной станции каждая),когда загруженность канала высока.Протокол адаптивного прохода по деревуОдним из простых способов динамического разбиения на группы является алгоритм,разработанный во время Второй мировой войны в армии США для проверки солдатна сифилис (Dorfman, 1943).
Брался анализ крови у N солдат. Часть каждого образцапомещалась в одну общую пробирку. Этот смешанный образец проверялся на наличиеантител. Если антитела не обнаруживались, все солдаты в данной группе объявлялисьздоровыми. В противном же случае группа делилась пополам, и каждая половинагруппы проверялась отдельно. Подобный процесс продолжался до тех пор, пока размер группы не уменьшался до одного солдата.В компьютерной версии данного алгоритма (Capetanakis, 1979) станции рассматриваются в виде листьев двоичного дерева, как показано на рис. 4.10. В первом временно´минтервале состязания за право передачи участвуют все станции.
Если кому-нибудь этоудается, то на этом работа алгоритма заканчивается. Если же происходит столкновение, то ко второму этапу состязаний допускается только половина станций, а именностанции, относящиеся к узлу 2 дерева. Если одна из станций успешно захватываетканал, то следующее состязание устраивается для второй половины станций (относящихся к узлу 3 дерева). Если снова происходит конфликт, то к следующему интервалувремени среди состязающихся остается уже четверть станций, относящихся к узлу 4.4.2. Протоколы коллективного доступа 301Рис. 4.10. Дерево из восьми станцийТаким образом, если столкновение происходит во время интервала 0, то все деревосканируется на единичную глубину для поиска готовых станций. Каждый однобитовый слот ассоциируется с определенным узлом дерева.
Если происходит столкновение,поиск продолжается для левого и правого дочерних узлов. Если количество станций,претендующих на передачу, равно нулю или единице, поиск в данном узле дерева прекращается, поскольку все готовые станции уже обнаружены.При сильной загруженности канала вряд ли стоит начинать поиск готовой станции с узла 1, поскольку шансов, что всего одна станция из всех будет претендовать наканал, мало. По той же причине могут быть пропущены также узлы 2 и 3.
А на какомуровне дерева следует начинать опрос в общем случае? Очевидно, что чем сильнеезагруженность канала, тем на более низком уровне дерева должен начинаться поискготовых станций. Будем предполагать, что каждая станция довольно точно можетоценить q (количество готовых на данный момент станций), например, отслеживаянедавний трафик.Пронумеруем уровни дерева на рис. 4.10 — узел 1 на уровне 0, узлы 2 и 3 на уровне 1 и т. д. Обратите внимание на то, что каждый узел на уровне i включает 2–i частьот всех станций. Если q готовых станций распределены равномерно, то ожидаемое ихчисло ниже узла на уровне i равно 2–iq.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
