Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 41
Текст из файла (страница 41)
А вот доказательство того,что алгоритм рано или поздно достигает заключительной конфигурации, требуетвведения более сложной нормирующей функции.Можно даже провести такое обобщение этого алгоритма, чтобы он мог работать с каналами связи, имеющими переменный вес; реакцией узла u на изменение весового коэффициента канала должно быть перевычисление значений4.4. Маршрутизация с использованием компактных таблицPPBBBw4 B vw1 PPvu vw2PPPPvw3 vадр.v1кан.w2u-vjw3vNw1каналыw1w2w3w4147адресаты..., vNv1 , ......, vj , ...Рис.
4.11. Сокращение размера таблиц маршрутизациипеременных Du [v] для всех вершин v. Однако такой алгоритм мог бы иметь практическое применение только в тех случаях, когда средний период времени междуизменениями весовых коэффициентов каналов связи значительно превосходитвремя сходимости алгоритма. К сожалению, это совершенно нереальное допущение. В данной ситуации предпочтение отдается таким алгоритмам, которыегарантирует ацикличность таблиц маршрутизации на протяжении всего периодасходимости; к их числу относится, например, алгоритм Мерлина —Сигалла.4.4. Маршрутизация с использованием компактных таблицДо сих пор мы имели дело с алгоритмами маршрутизации, которые в каждом узле сети создают и поддерживают таблицы маршрутизации с отдельнымвходом для каждой вершины-адресата.
Когда пакет продвигается по сети, обращение к таблицам происходит в каждом узле пройденного пути (за исключениемвершины-адресата). В этом параграфе мы займемся изучением такого устройстватаблиц маршрутизации, которое позволяет сократить объем памяти и издержки,связанные с просмотром таблиц. Мы не будем здесь касаться вопросов о том, каквычислять такие таблицы при помощи распределенных алгоритмов. Для простотыописания алгоритмов на протяжении всего этого параграфа мы будем предполагать, что все рассматриваемые сети являются связными.Общая стратегия получения таблиц меньшего размера, которая используетсяв каждом из трех алгоритмов, рассматриваемых в этом параграфе, очень проста.Если для каждой вершины-адресата в таблице того или иного узла отдельно указывается соответствующий исходящий канал связи, то таблица маршрутизациибудет неизбежно иметь длину N; таким образом, для хранения таблицы требуется Ω (N) битов памяти независимо от того, насколько компактно закодированы вней имена вершин-адресатов.
Теперь попробуем организовать устройство таблицпо-другому: для каждого канала связи, примыкающего к узлу, построим списоквершин-адресатов, маршруты к которым начинаются с прохождения этого канала(см. рис. 4.11). Если к узлу примыкают deg каналов связи, то и «длина» таблицыбудет равна deg; реальная экономия памяти будет зависеть от того, насколькокомпактно мы сможем представить множество всех вершин-адресатов, соответствующих каждому каналу связи. Чтобы эффективно проводить поиск в таб-148Гл. 4. Алгоритмы маршрутизациилицах, они должны быть устроены так, чтобы для заданной вершины-адресатана основе таблиц можно было быстро выбрать соответствующий ей исходящийканал связи.4.4.1. Схема древесной разметкиПервый компактный метод маршрутизации был предложен Санторо и Хатибом в работе [169] .
Этот метод помечает каждую вершину целым числом от 0до N − 1 таким образом, чтобы для каждого канала связи множество вершинадресатов, сообщение с которыми осуществляется через этот канал, представляло собой интервал. Обозначим символом ZN множество целых чисел {0, 1, . . . , N−1}.Арифметические операции в этом множестве будут проводиться по модулю N, т. е.(N − 1) + 1 ≡ 0, но при этом в множестве Z будет действовать такой же порядокрасположения элементов, как в натуральном ряде.Определение 4.19.
Циклическим интервалом [a, b) на множестве ZN будем называть всякое множество целых чисел, удовлетворяющее следующему соотношению:(если a < b,{a, a + 1, . . . , b − 1},[a, b) ={0, . . . , b − 1, a, . . . , N − 1}, если a > b.Следует помнить о том, что [a, a) = ZN и для любой пары a 6= b дополнением интервала [a, b) является интервал [b, a). Циклический интервал [a, b)называется линейным, если a < b.v0v@v l v0 = 0@0 v lw0 = lw + |T [w] |w vlw w@AA A T [w] AAAAvlx = lw + |T [w] | − 1xРис. 4.12.
Обход дерева по порядкуТеорема 4.20. Вершины дерева T можно занумеровать таким образом, чтобы для всякой вершины и каждого исходящего из этой вершиныканала множество узлов, путь в которые проходит через этот канал,образовывало циклический интервал.4.4. Маршрутизация с использованием компактных таблиц149Д о к а з а т е л ь с т в о. Выберем произвольную вершину v 0 в качестве корня дерева, и для каждого узла w обозначим символом T [w] поддерево дерева T,имеющее вершину w в качестве корня.
Оказывается, можно так занумероватьвершины дерева, что для каждого узла w номера всех вершин в поддереве T [w]будут образовывать линейный интервал; для этого достаточно совершить обходдерева по некоторому порядку, как показано на рис. 4.12. При таком порядкеобхода первой вершиной поддерева T [w] , которая будет пройдена, является вершина w; после прохождения вершины w все остальные вершины поддерева T [w]посещаются прежде, чем обход перейдет к остальным вершинам дерева.
Такимобразом, вершины дерева T [w] получают порядковые номера, которые образуютлинейный интервал [lw , lw + |T [w] |), где lw — номер вершины w.Пусть [aw , bw) — это интервал целых чисел, которыми помечены вершиныподдерева T [w] . Соседом вершины w может являться либо сыновняя, либо родительская вершина узла w. Узел w переправляет сыновней вершине u те пакеты, адресаты которых располагаются в дереве T [u] , т. е.
имеют номера, лежащиев интервале [au , bu). Узел w переправляет своей родительской вершине все тепакеты, адресаты которых располагаются вне дерева T [w] , т. е. имеют номера,лежащие в множестве ZN \ [aw , bw) = [bw , aw).(* Пакет с адресом d был получен или создан в узле u *)if d = luthen пакет доставлен по адресуelse begin выбрать такое число i , что d ∈ [ i , i+1) ;отправить пакет по каналу, помеченному iendАлгоритм 4.13.
Продвижение пакетов на основе интервалов (для узла u).Для задания одного циклического интервала можно обойтись 2 log N битами, указывая только границы интервала. Поскольку в нашем случае приходитсяиметь дело с совокупностью непересекающихся интервалов, объединением которых является все множество ZN , для задания одного интервала будет достаточноlog N битов памяти. Для каждого канала в память заносится только левая граница соответствующего интервала; правая граница равна следующей по порядкулевой границе одного из интервалов той же самой вершины.
Левая граница интервала, соответствующего каналу uw, примыкающему к вершине u, определяетсяследующим соотношением:(lw ,если w является сыновней вершиной для u,uw =lu + |T [u] |, если w является родительской вершиной для u.Предположим, что degu каналов, примыкающих к вершине u, помечены числами1 , . . . , degu и при этом 1 < . . . < degu . Тогда для продвижения сообщенийиспользуется алгоритм 4.13. Пометки каналов разбивают множество Z N на deguинтервалов, каждый из которых соответствует одному каналу (см. рис. 4.14).150Гл. 4.
Алгоритмы маршрутизацииЗаметим, что самое большее один из этих интервалов может быть нелинейным.Если все пометки каналов упорядочены, то правильную пометку можно найти заO(log degu) шагов при помощи дихотомического поиска. Индекс i вычисляетсяпо модулю degu , т. е. degu +1 = 1 .Схема древесной разметки строит оптимальные маршруты в деревьях, таккак в дереве между любыми двумя вершинами есть только один простой путь.Этой схемой можно воспользоваться и тогда, когда сеть не является деревом.В сети выбирается остовное дерево, и указанная схема применяется к этомудереву.
Каналы, не принадлежащие остовному дереву, не принимаются в расчет;в таблицах маршрутизации каждый из них помечается специальным символомдля обозначения того, что по этим каналам никакие пакеты не продвигаются.Чтобы сравнить длины путей, которые выбираются схемой древесной разметки, с длинами оптимальных путей, рассмотрим расстояние d T (u, v) между вершинами u и v в дереве T и расстояние dG (u, v) между вершинами u и v в графе G.
Обозначим символом DG диаметр графа G, т. е. максимальное расстояниеdG (u, v) по всем парам вершин u и v.Лемма 4.21. Не существует конечной верхней оценки для отношениявеличин dT (u, v) и dG (u, v). Это справедливо даже в том случае, когда длина пути полагается равной числу звеньев.Д о к а з а т е л ь с т в о. Рассмотрим кольцо G, состоящее из N вершин. Тогда остовное дерево получается путем удаления из графа G одного канала, например xy. В этом случае dG (x, y) = 1 и dT (x, y) = N − 1, и поэтому отношениерассматриваемых величин равно N − 1.
Это отношение может быть произвольнобольшим для больших колец.Следующая лемма опирается на симметричность стоимостей каналов связи,т. е. в ней предполагает, что uw = wu . Отсюда следует, что dG (u, v) = dG (v, u)для всех пар вершин u и v.Лемма 4.22. Дерево T может быть выбрано так, чтобы для любойпары вершин u и v выполнялось неравенство dT (u, v) 6 2DG .Д о к а з а т е л ь с т в о. Пусть T — оптимальное входное дерево для узла w0(так же как в теореме 4.2).
ТогдаdT (u, v) 6 dT (u, w0) + dT (w0 , v) == dT (u, w0) + dT (v, w0) == dG (u, w0) + dG (v, w0) 66 DG + DG(согласно симметричности )(согласно выбору T)(по определению DG).Подводя итоги, заметим, что путь, который выбирается схемой древесной разметки, может быть сколь угодно хуже оптимального пути между той же паройвершин (лемма 4.21), но если выбрать подходящее остовное дерево, то он неболее чем в два раза хуже пути между двумя другими вершинами коммуникационной системы (лемма 4.22). Отсюда следует, что схема вполне пригодна, еслив большинстве случаев коммуникация проводится между узлами, отстоящимидруг от друга на расстояние Θ (DG), но не годится, если в большинстве случаев4.4. Маршрутизация с использованием компактных таблицdegi+1151..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
