Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 41

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 41)

. , b - 1, а, . . . , N - 1},если а < Ь,если а > 6 .Следует помнить о том, что [а, а) = Z a/ и для любой пары а Ф b допол­нением интервала [а, Ь) является интервал [Ь, а). Циклический интервал [а, b)называется линейным, если а < Ь.VoI» 0—ОРис. 4.12. Обход дерева по порядкуТеорема 4.20. Вершины дерева Т можно занумеровать таким обра­зом, чтобы для всякой вершины и каждого исходящего из этой вершиныканала множество узлов, путь в которые проходит через этот канал,образовывало циклический интервал.4.4.

Маршрутизация с использованием компактных таблиц149Д о к а з а т е л ь с т в о . Выберем произвольную вершину vo в качестве кор­ня дерева, и для каждого узла да обозначим символом T [ w ] поддерево дерева Т,имеющее вершину да в качестве корня. Оказывается, можно так занумероватьвершины дерева, что для каждого узла да номера всех вершин в поддереве T [ w ]будут образовывать линейный интервал; для этого достаточно совершить обходдерева по некоторому порядку, как показано на рис. 4.12. При таком порядкеобхода первой вершиной поддерева T [ w ] , которая будет пройдена, является вер­шина да; после прохождения вершины да все остальные вершины поддерева T [ w ]посещаются прежде, чем обход перейдет к остальным вершинам дерева.

Такимобразом, вершины дерева T[w] получают порядковые номера, которые образуютлинейный интервал [lw, lw + |7’[да]|), где lw — номер вершины да.Пусть [aw, bw) — это интервал целых чисел, которыми помечены вершиныподдерева Г[да]. Соседом вершины да может являться либо сыновняя, либо ро­дительская вершина узла да. Узел да переправляет сыновней вершине и те паке­ты, адресаты которых располагаются в дереве Т[и\, т. е. имеют номера, лежащиев интервале [аи, Ьа). Узел да переправляет своей родительской вершине все тепакеты, адресаты которых располагаются вне дерева T[w], т. е.

имеют номера,лежащие в множестве Ъ,у \ [aw, bw) = [bw, aw).□(* Пакет с адресом d был получен или создан в узле и *)if d = luthen пакет доставлен по адресуelse begin выбрать такое число щ, что d, € [a;, oti+ i) ;отправить пакет по каналу, помеченному а;endАлгоритм 4.13. Продвижение пакетов на основе интервалов (для узла и).Для задания одного циклического интервала можно обойтись 2 log TV бита­ми, указывая только границы интервала. Поскольку в нашем случае приходитсяиметь дело с совокупностью непересекающихся интервалов, объединением кото­рых является все множество 2 дг, для задания одного интервала будет достаточноlog N битов памяти.

Для каждого канала в память заносится только левая гра­ница соответствующего интервала; правая граница равна следующей по порядкулевой границе одного из интервалов той же самой вершины. Левая граница интер­вала, соответствующего каналу uw, примыкающему к вершине и, определяетсяследующим соотношением:I lw,\1а + | Т[и\ |,если да является сыновней вершиной для и,если да является родительской вершиной для и.Предположим, что degu каналов, примыкающих к вершине и , помечены числамиai, .

. . , a degu и при этом а; < .. . < o-degR- Тогда для продвижения сообщенийиспользуется алгоритм 4.13. Пометки каналов разбивают множество Z/y на deguинтервалов, каждый из которых соответствует одному каналу (см. рис. 4.14).150Гл. 4. Алгоритмы маршрутизацииЗаметим, что самое большее один из этих интервалов может быть нелинейным.Если все пометки каналов упорядочены, то правильную пометку можно найти за0(\ogdega) шагов при помощи дихотомического поиска.

Индекс i вычисляетсяпо модулю dega, т. е. adega+i = осьСхема древесной разметки строит оптимальные маршруты в деревьях, таккак в дереве между любыми двумя вершинами есть только один простой путь.Этой схемой можно воспользоваться и тогда, когда сеть не является деревом.В сети выбирается остовное дерево, и указанная схема применяется к этомудереву.

Каналы, не принадлежащие остовному дереву, не принимаются в расчет;в таблицах маршрутизации каждый из них помечается специальным символомдля обозначения того, что по этим каналам никакие пакеты не продвигаются.Чтобы сравнить длины путей, которые выбираются схемой древесной размет­ки, с длинами оптимальных путей, рассмотрим расстояние d p ( u , v) между вер­шинами и н и в дереве Т и расстояние d a ( u , v) между вершинами и и о в гра­фе G. Обозначим символом D q диаметр графа G, т.

е. максимальное расстояниеdo(u, v) по всем парам вершин и и о.Лемма 4.21. Не существует конечной верхней оценки для отношениявеличин drill, v) и d a { u , v). Это справедливо даже в том случае, когда дли­на пути полагается равной числу звеньев.Д о к а з а т е л ь с т в о . Рассмотрим кольцо G, состоящее из N вершин. То­гда остовное дерево получается путем удаления из графа G одного канала, на­пример ху. В этом случае do(x, у) = 1 и dj{x, у) = N — 1, и поэтому отношениерассматриваемых величин равно N — 1. Это отношение может быть произвольнобольшим для больших колец.□Следующая лемма опирается на симметричность стоимостей каналов связи,т. е.

в ней предполагает, что ыии) = a wu. Отсюда следует, что d d u , и) = do{v, и)для всех пар вершин и и и.Лемма 4.22. Дерево Т может быть выбрано так , чтобы для любойпары вершин и и v выполнялось неравенство dr(u, v ) < 2 DoД о к а з а т е л ь с т в о . Пусть Т — оптимальное входное дерево для узла дао(так же как в теореме 4.2). Тогдаdr{u, v) ^ dr{u, wo) + driwo, и) == dr(u, wo) + dr{i), дао) == doiu, wo) + d d v , дао) <^ Dq + D q(согласно симметричности со)(согласно выбору 7")( п о определению D q).□Подводя итоги, заметим, что путь, который выбирается схемой древесной раз­метки, может быть сколь угодно хуже оптимального пути между той же паройвершин (лемма 4.21), но если выбрать подходящее остовное дерево, то он неболее чем в два раза хуже пути между двумя другими вершинами коммуникаци­онной системы (лемма 4.22).

Отсюда следует, что схема вполне пригодна, еслив большинстве случаев коммуникация проводится между узлами, отстоящимидруг от друга на расстояние 0 )Dg), н о не годится, если в большинстве случаев4.4. Маршрутизация с использованием компактных таблиц151Узлы, маршруты к которымпроходят по каналу оцРис.

4.14. Разбиение множествав узлекоммуникация проводится между узлами, удаленными друг от друга на короткоерасстояние в графе G.Помимо неудобства, связанного с протяженностью выбираемых путей, схемадревесной разметки имеет следующие недостатки.1. Каналы, не принадлежащие дереву Т, не используются, а это означает, чторесурсы сети расходуются неэкономно.2. Весь трафик сосредоточен в дереве, а это приводит к перегрузкам в сети.3. Всякая неисправность в одном канале дерева Т приводит к разрыву сети.4.4.2. Интервальная маршрутизацияВан Ливен и Тан в работе [128] предложили такое обобщение схемы дре­весной разметки, которое позволило применять эту схему к произвольным сетямтаким образом, что почти каждый канал оказывается задействованным в продви­жении пакетов.Определение 4.23.

Схемой интервальной разметки (ILS ) называется та­кая разметка узлов и каналов коммуникационной сети, при которой1 ) узлы сети помечаются различными числами из множества Zyy,2 ) для каждого узла примыкающие к нему каналы помечаются различнымичислами из множества Zyy.Для заданной ILS интервальный алгоритм маршрутизации продвигает пакетыточно так же, как это делает алгоритм 4.13.Определение 4.24. Схема интервальной разметки называется правильной,если всякий пакет, который продвигается в сети в соответствии с этой схемой,рано или поздно достигает своего адресата.Как будет показано в теореме 4.25, для каждой связной сети G существуетправильная схема интервальной разметки однако для произвольной связной сетиэта схема обычно не очень эффективна.

После того как мы докажем теоремуо существовании правильной схемы интервальной разметки, мы изучим вопрособ оптимальности путей, которые выбираются такой схемой.Теорема 4.25. Для каждой связной сети G существует правильная схе­ма интервальной разметки.152Гл. 4. Алгоритмы маршрутизацииД о к а з а т е л ь с т в о . Правильная схема интервальной разметки строитсяпутем расширения схемы древесной разметки Санторо и Хатиба, примененнойк остовному дереву Т рассматриваемой сети. Для заданного остовного деревавсякое ребро, не принадлежащее этому дереву, мы будем называть стягиваю­щим ребром. Кроме того, вершину v будем называть предком вершины и, еслии € T[v\.

Так как при построении схемы главная трудность состоит в проведенииразметки стгивающих ребер (все ребра, принадлежащие дереву, будут помеченытак, как того требует схема древесной разметки), остовное дерево выбираетсятаким образом, чтобы все стягивающие ребра имели особое расположение. Дляэтого рассмотрим следующее утверждение.Лемма 4.26. Существует такое остовное дерево, в котором все стя­гивающие ребра соединяют вершину и ее предка.Д о к а з а т е л ь с т в о . Этим свойством обладает всякое остовное дерево,которое строится методом обхода сети в глубину (см. [184] и §6.6.4).□В дальнейшем мы будем полагать, что дерево Т построено методом обходасети G в глубину.Определение 4.27. Схемой интервальной разметки в глубину для сетиG (относительно дерева Т) называется такая схема разметки, которая удовлетво­ряет следующим правилам.1.

Вершины сети помечаются по порядку в соответствии с обходом дерева Т,т. е. вершины поддерева T[w] помечаются числами из интервала [lw, lw + \T[w]\).Будем полагать kw = lw + |7’[да]|.2. Пометка auw ребра uw, примыкающего к узлу и, определяется так:а) если uw — это стягивающее ребро, то auw = lw\б) если w — это сыновняя вершина для и (в дереве Т), то auw = lw;в) если w — это родительская вершина для и, то <xuw = ku за исключениетого случая, когда k a = N и вершина и имеет стягивающее ребро, соеди­няющее эту вершину с корнем;(в последнем случае данное стягивающее ребро в узле и помечается чис­лом 0 согласно правилу (а), и поэтому пометка этого ребра числом k u на­рушала бы принцип однозначности, требующий, чтобы все пометки реберв узле и были разными; пометки расставляются по модулю N, и поэтомуN = 0);г) Если w — это родительская вершина для и, вершина и имеет стягивающееребро, соединяющее эту вершину с корнем, и k u = N, то auw = lw.Пример схемы интервальной разметки в глубину приведен на рис.

4.15. Сле­дует обратить внимание на то, что все стягивающие ребра помечены согласноправилу (2а), ребра, ведущие в родительские вершины 4, 8 и 10, помечены соглас­но правилу (2с), а ребро, ведущее в родительскую вершину 9, помечено согласноправилу (2 d).Покажем теперь, что схема интервальной разметки в глубину является пра­вильной схемой. Заметим, что v e Т[и]lv € [/„, ka).

Характеристики

Список файлов книги