Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 42
Текст из файла (страница 42)
0L .. L ..ZN1 iPP Узлы, маршруты к которымУзлы, маршруты к которым 1P Lпроходят по каналу iпроходят по каналу 1Li2Рис. 4.14. Разбиение множества ZN в узлекоммуникация проводится между узлами, удаленными друг от друга на короткоерасстояние в графе G.Помимо неудобства, связанного с протяженностью выбираемых путей, схемадревесной разметки имеет следующие недостатки.1. Каналы, не принадлежащие дереву T, не используются, а это означает, чторесурсы сети расходуются неэкономно.2. Весь трафик сосредоточен в дереве, а это приводит к перегрузкам в сети.3. Всякая неисправность в одном канале дерева T приводит к разрыву сети.4.4.2.
Интервальная маршрутизацияВан Ливен и Тан в работе [128] предложили такое обобщение схемы древесной разметки, которое позволило применять эту схему к произвольным сетямтаким образом, что почти каждый канал оказывается задействованным в продвижении пакетов.Определение 4.23. Схемой интервальной разметки (ILS) называется такая разметка узлов и каналов коммуникационной сети, при которой1) узлы сети помечаются различными числами из множества Z N ,2) для каждого узла примыкающие к нему каналы помечаются различнымичислами из множества ZN .Для заданной ILS интервальный алгоритм маршрутизации продвигает пакетыточно так же, как это делает алгоритм 4.13.Определение 4.24. Схема интервальной разметки называется правильной,если всякий пакет, который продвигается в сети в соответствии с этой схемой,рано или поздно достигает своего адресата.Как будет показано в теореме 4.25, для каждой связной сети G существуетправильная схема интервальной разметки однако для произвольной связной сетиэта схема обычно не очень эффективна.
После того как мы докажем теоремуо существовании правильной схемы интервальной разметки, мы изучим вопрособ оптимальности путей, которые выбираются такой схемой.Теорема 4.25. Для каждой связной сети G существует правильная схема интервальной разметки.152Гл. 4. Алгоритмы маршрутизацииД о к а з а т е л ь с т в о. Правильная схема интервальной разметки строитсяпутем расширения схемы древесной разметки Санторо и Хатиба, примененнойк остовному дереву T рассматриваемой сети. Для заданного остовного деревавсякое ребро, не принадлежащее этому дереву, мы будем называть стягивающим ребром.
Кроме того, вершину v будем называть предком вершины u, еслиu ∈ T [v] . Так как при построении схемы главная трудность состоит в проведенииразметки стгивающих ребер (все ребра, принадлежащие дереву, будут помеченытак, как того требует схема древесной разметки), остовное дерево выбираетсятаким образом, чтобы все стягивающие ребра имели особое расположение. Дляэтого рассмотрим следующее утверждение.Лемма 4.26. Существует такое остовное дерево, в котором все стягивающие ребра соединяют вершину и ее предка.Д о к а з а т е л ь с т в о. Этим свойством обладает всякое остовное дерево,которое строится методом обхода сети в глубину (см. [184] и § 6.6.4).В дальнейшем мы будем полагать, что дерево T построено методом обходасети G в глубину.Определение 4.27.
Схемой интервальной разметки в глубину для сетиG (относительно дерева T) называется такая схема разметки, которая удовлетворяет следующим правилам.1. Вершины сети помечаются по порядку в соответствии с обходом дерева T,т. е. вершины поддерева T [w] помечаются числами из интервала [l w , lw + |T [w] |).Будем полагать kw = lw + |T [w] |.2. Пометка uw ребра uw, примыкающего к узлу u, определяется так:а) если uw — это стягивающее ребро, то uw = lw ;б) если w — это сыновняя вершина для u (в дереве T), то uw = lw ;в) если w — это родительская вершина для u, то uw = ku за исключениетого случая, когда ku = N и вершина u имеет стягивающее ребро, соединяющее эту вершину с корнем;(в последнем случае данное стягивающее ребро в узле u помечается числом 0 согласно правилу (a), и поэтому пометка этого ребра числом k u нарушала бы принцип однозначности, требующий, чтобы все пометки реберв узле u были разными; пометки расставляются по модулю N, и поэтомуN ≡ 0);г) Если w — это родительская вершина для u, вершина u имеет стягивающееребро, соединяющее эту вершину с корнем, и ku = N, то uw = lw .Пример схемы интервальной разметки в глубину приведен на рис.
4.15. Следует обратить внимание на то, что все стягивающие ребра помечены согласноправилу (2a), ребра, ведущие в родительские вершины 4, 8 и 10, помечены согласно правилу (2c), а ребро, ведущее в родительскую вершину 9, помечено согласноправилу (2d).Покажем теперь, что схема интервальной разметки в глубину является правильной схемой. Заметим, что v ∈ T [u] ⇐⇒ lv ∈ [lu , ku). В трех леммах, которыеприведены ниже, рассматривается одна и та же ситуация, когда пакет из узла u4.4.
Маршрутизация с использованием компактных таблиц.0.1 . . 810 . Q.9. . .Q0. . Q. . Q. ..81..2 .4 5...9.. @......@5@8. 0. 8...592... 10 11364 ..7. C C C ..CC80 . 11 CC04 5CC .17361047118153Древесные ребра. . . . . . . . Стягивающие ребраРис. 4.15. Схема интервальной разметки в глубинупродвигается согласно алгоритму 4.13 по направлению к вершине v через узел w,являющийся соседом вершины u. Это подразумевает, что в узле u для некоторойпометки выполняется соотношение lv ∈ [ uw , ) и нет такой пометки 0 6= uw ,для которой в узле u выполняется включение 0 ∈ [ uw , lv).Лемма 4.28.
Если lu > lv , то lw < lu .Д о к а з а т е л ь с т в о. Вначале рассмотрим случай, когда uw 6 lv . Вершина w не является сыновней вершиной для u, поскольку в этом случае мыимели бы uw = lw > lu > lv . Если uw — стягивающее ребро, то lw = uw 6 lv << lu . Если w — родительская вершина для u, то в любом случае выполняетсянеравенство lw < lu .Далее рассмотрим случай, когда uw — это наибольшее число, помечающееребро, примыкающее к узлу u, и не существует пометки 0 6 lv (т. е. lv лежитв нижней части нелинейного интервала). В этом случае ребро, соединяющее u сродительской вершиной, помечено не 0, а числом k u (поскольку 0 6 lv и нет пометки 0 6 lv). Тогда число ku является максимальной пометкой; ребро (древесноеили стягивающее), ведущее в вершину-потомок w0 , имеет пометку uw0 = lw0 << ku , а ребро, ведущее в вершину-предок w0 , имеет пометку uw0 = lw0 < lu .Значит, w — родительская вершина для u, и отсюда следует неравенство l w << lu .В двух других леммах рассматривается случай, когда l u < lv .
Мы докажем,что тогда либо v ∈ T [u] , либо lv > ku , и при этом в последнем случае выполняетсянеравенство ku < N, благодаря чему ребро, ведущее в родительскую вершину дляu, помечено числом ku .Лемма 4.29. Если lu < lv , то lw 6 lv .Д о к а з а т е л ь с т в о.
Вначале рассмотрим случай, когда v ∈ T [u] . Рассмотрим ту сыновнюю вершину w0 для u, для которой выполняется включениеv ∈ T [w0 ] . Тогда имеем соотношения uw0 = lw0 6 lv , из которых следует, чтоuw0 6 uw 6 lv < kw0 . Мы заключили, что w не является родительской вершиной для u, и поэтому lw = uw , откуда следует, что lw 6 lv .154Гл. 4. Алгоритмы маршрутизацииДалее рассмотрим случай, когда lv > ku . Убедимся, что в этом случае wявляется родительской вершиной для u. Ребро, ведущее к родительской вершине,помечено числом ku , и при этом ku 6 lv .
Ребро, ведущее в сыновнюю вершину w0для узла u, помечено числом lw0 < ku , стягивающее ребро, ведущее в вершинупотомок w0 , помечено числом lw0 < ku , а стягивающее ребро, ведущее в вершинупредок w0 , помечено числом lw0 < lu . Так как w — это родительская вершина дляu, выполняется неравенство lw < lu < lv .Нормирующую функцию, позволяющую отслеживать доставку сообщений ввершину v, можно определить следующим образом. Наименьшим общим предком двух узлов u и v называется наиболее удаленная от корня вершина, котораяявляется предком обеих вершин u и v. Условимся, что запись lca(u, v) будет обозначать пометку наименьшего общего потомка вершин u и v, и будем полагатьfv (u) = (−lca(u, v), lu).Лемма 4.30. Если lu < lv , то fv (w) < fv (u).Д о к а з а т е л ь с т в о. Начнем с того случая, когда v ∈ T [u] (отсюда следует, что lca(u, v) = lu).
Если w0 — это та сыновняя вершина для u, для которойимеет место включение v ∈ T [w0 ] , то (так же как и в предшествующей лемме) выполняются неравенства lw0 6 lw < kw0 , и поэтому верно включение w ∈ T [w0 ] , изкоторого следуют неравенства lca(w, v) > lw0 > lu . Таким образом, fv (w) < fv (u).Далее рассмотрим случай, когда lv > ku . Так же как и в предыдущей лемме,w является родительской вершиной для u, и, коль скоро v 6 ∈T [u] , выполняется равенство lca(w, v) = lca(u, v). Но теперь lw < lu , вследствие чего вернонеравенство fv (w) < fv (u).Корень: l = 0u@u @..@.@.. .uПредок: l < lv. .?AI..@ .
?@.u@. . . . . .A@...@ ..u... ..I@ @. v. . . @..@I@.@. . T [v]@ @. . ./l < lvl > lv @l > lv @@@Рис. 4.16. Продвижение пакета по направлению к вершине v в схеме интервальнойразметки в глубинуТеперь мы можем убедиться в том, что каждый пакет достигает своего адресата. Поток пакетов, направленных в вершину v, изображен на рис. 4.16. Допустим,что пакет, адресованный узлу v, был сформирован в вершине u. Согласно лемме 4.28, при прохождении каждого звена маршрута метка вершины убывает, дотех пор пока спустя конечное число продвижений пакет не достигнет такой вершины w, для которой выполняется неравенство l w 6 lv . Согласно лемме 4.294.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
