Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 37
Текст из файла (страница 37)
Поэтому вычисление и анализ всех расстояний до заданной вершины-адресата v0 можно проводить независимо от вычислений расстояний до других вершин сети.В оставшейся части этого параграфа мы обсудим два алгоритма, в основукоторых положено уравнение (4.1), а именно алгоритм Мерлина —Сигалла и алгоритм Чанди—Мисры. Несмотря на те преимущества, которые открываютсяв связи с локальностью данных, коммуникационная сложность этих алгоритмов ничуть не лучше, чем сложность алгоритма Туэга.
Это объясняется свойством независимости от вершины-адресата, которым обладает уравнение (4.1);на самом деле использование результатов, которые были получены для другихвершин-адресатов (как это осуществляется в алгоритме Туэга), представляетсяболее выгодным методом, нежели введение локальности данных.Но если уменьшения коммуникационной сложности не происходит, то почему же столь важна локальность данных? Зависимость вычисления от удаленныхданных приводит к тому, что эти данные приходится широковещательно распространять много раз, если они становятся другими вследствие изменений топологической структуры сети из-за отказов и возобновления работы каналов и узлов.А проведение широковещательной рассылки сообщений (если иметь при этомв виду, что в ходе самой рассылки могут происходить и другие топологическиеизменения) — это очень непростая задача, решение которой требует большихзатрат (см., например, [95]).
Поэтому алгоритмы, в основу которых положеноуравнение (4.1), можно проще адаптировать для учета топологических изменений. Примером тому может служить алгоритм, который мы подробно рассмотримв § 4.6.3.Алгоритм Мерлина—Сигалла. Алгоритм, предложенный Мерлином и Сигаллом в работе [147] , вычисляет таблицы маршрутизации по отдельности длякаждой вершины-адресата; вычисления таблиц для разных вершин-адресатов неоказывают совершенно никакого влияния друг на друга. Для каждой вершиныадресата v алгоритм строит дерево Tv с корнем в вершине v и проводит итеративное преобразование этого дерева, с тем чтобы в конце концов получитьоптимальное входное дерево для вершины-адресата v.134Гл.
4. Алгоритмы маршрутизацииВ каждом узле u хранится оценка расстояния Du [v] до вершины v, а такжеимя того соседа, которому нужно передать пакет, адресованный узлу v, и этот сосед является родительской вершиной для узла u в дереве T v . При каждой итерации всякий узел u отправляет известную ему оценку расстояния D u [v] всем своимсоседям, кроме вершины Nbu [v] (для этого используется сообщение hmydist, v, D u [v] i).Как только узел u получает от своего соседа w сообщение hmydist, v, di и обнаруживает, что d + uw < Du [v] , в узле u значение переменной Nbu [v] полагаетсяравным w, а значение переменной Du [v] полагается равным d + uw .
Управляющим параметром этого преобразования служит вершина v, и для его проведениянужно провести обмен двумя сообщениями, состоящими из W битов, по каждомуканалу связи.В работе [147] установлено, что после проведения i итераций все кратчайшиепути, состоящие не более чем из i звеньев, будут правильно вычислены, и поэтому для вычисления всх кратчайших путей нужно совершить не более N итераций.Кратчайшие пути ко всем вершинам-адресатам вычисляются за счет независимого применения предложенного алгоритма ко всем вершинам-адресатам.Теорема 4.11. Алгоритм Мерлина—Сигалла вычисляет таблицы маршрутизации по кратчайшим путям, совершая при этом обмен O(N 2) сообщениями и передавая O(N2 · W) битов информации по каждому каналусвязи, имея, таким образом, коммуникационную сложность O(N 2 ·|E|) и битовую сложность O(N2 · |E|W).Этот алгоритм можно приспособить к изменениям топологии сети и весовыххарактеристик каналов.
Важная особенность этого алгоритма состоит в том, чтопо ходу проведения итераций таблицы маршрутизации остаются ациклическими.Алгоритм Чанди—Мисры. Алгоритм, предложенный Чанди и Мисрой в работе [44] , вычисляет все кратчайшие пути к заданной вершине-адресату на основепринципа диффузных вычислений. Суть его такова: распределенное вычисление начинается в одной-единственной вершине, и другие узлы сети поочередноприсоединяются к вычислению только после получения сообщения.Чтобы вычислить расстояние от каждой вершины до заданного узла v 0 (а также предпочтительный исходящий канал связи), каждый узел u устанавливает начальное значение Du [v0 ] = ∞ и ожидает получения сообщений. Узел v0 отправляет сообщение hmydist, v0 , 0i всем своим соседям.
Как только вершина u получает сообщение hmydist, v0 , di от соседа w и убеждается в том, что выполняетсянеравенство d + uw < Du [v0 ] , значением переменной Du [v0 ] становится суммаd + uw , и всем соседям вершины u отправляется сообщение hmydist, v 0 , Du [v0 ] i(см. алгоритм 4.7).Легко показать, что значение Du [v0 ] всегда является верхней оценкой величины d(u, v0), т. е. неравенство d(u, v0) 6 Du [v0 ] следует из инварианта алгоритма;см.
упражнение 4.3. Чтобы убедиться в том, что алгоритм правильно вычисляет расстояния, необходимо показать, что рано или поздно будет достигнута такая конфигурация, для которой в каждом узле будет выполняться неравенствоDu [v0 ] 6 d(u, v0). Мы приведем доказательство этого утверждения, в котором4.2. Задача построения кратчайших путей для всех пар вершин135var Du [v0 ] : весinit ∞ ;Nbu [v0 ] : вершина init udef ;Только для вершины v0 :begin Dv0 [v0 ] := 0 ;forall w ∈ Neighv0 do send hmydist, v0 , 0i to wendОбработка сообщения hmydist, v0 , di, полученного вершиной u от соседа w:{ hmydist, v0 , di ∈ Mwu }begin receive hmydist, v0 , di from w ;if d + uw < Du [v0 ] thenbegin Du [v0 ] := d + uw ; Nbu [v0 ] := w ;forall x ∈ Neighu do send hmydist, v0 , Du [v0 ] i to xendendАлгоритм 4.7.
Алгоритм Чанди—Мисры (для узла u).подразумевается соблюдение допущения слабой справедливости, гласящего, чтов любом вычислении каждое отправленное сообщение рано или поздно будетполучено. Существует и такое доказательство, которое никак не опирается науказанное допущение, но оно гораздо сложнее.Теорема 4.12. В любом вычислении алгоритма 4.7 достигается такаяконфигурация, что в каждом узле u выполняется неравенство Du [v0 ] 6 d(u, v0).Д о к а з а т е л ь с т в о. Рассмотрим некоторое оптимальное входное дерево T для вершины v0 и занумеруем 2) все вершины, отличные от v0 , натуральнымичислами от 1 до N − 1 так, чтобы всякий раз, когда v i является родительской вершиной для vj , выполнялось неравенство i < j. Рассмотрим произвольное вычисление C и покажем, воспользовавшись индукцией по j, что для каждого номераj, j 6 N − 1, достигается такая конфигурация, в которой для всех номеров i,i 6 j, выполняется неравенство Dvi [v0 ] 6 d(vi , v0). Заметим, что значение переменной Dvi [v0 ] никогда не увеличивается по ходу работы алгоритма, и поэтому,как только соотношение Dvi [v0 ] 6 d(vi , v0) оказывается верным в какой-либоконфигурации, оно будет также оставаться верным и во всех последующих конфигурациях.2) Здесь в доказательстве допущена принципиальная ошибка.
Для заданной вершины v в сети0может существовать несколько различных оптимальных входных деревьев, и разные выполненияалгоритма могут строить разные деревья. Правильнее было бы рассмотреть произвольное выполнениеC рассматриваемого алгоритма и показать, что C обязательно завершается. После этого вершинысети нумеруются так, чтобы всякий раз, когда последнее изменение значения переменной D vi [v0 ]в вычислении C предшествует последнему изменению переменной Dvj [v0 ] в том же вычислении C,выполнялось неравенство i < j.
— Прим. перев.136Гл. 4. Алгоритмы маршрутизацииБазис (j = 0). После выполнения блока инициализации v 0 имеем d(v0 , v0) == 0, и Dv0 [v0 ] = 0, поэтому неравенство Dv0 [v0 ] 6 d(v0 , v0) соблюдается и послевыполнения всего процесса.Индуктивный переход j → j + 1. Предположим, что была достигнута такая конфигурация, в которой для всех узлов с номерами i 6 j выполняется неравенство Dvi [v0 ] 6 d(vi , v0). Рассмотрим вершину vj+1 . Из нее в вершину v0 существует кратчайший путь vj+1 , vi , .
. . , v0 длины d(vj+1 , v0), в котором vi являетсяродительской вершиной для vj+1 в дереве T, и поэтому i 6 j. Следовательно,по индуктивному предположению может быть достигнута такая конфигурация,в которой Dvi [v0 ] 6 d(vi , v0). Всякий раз, когда значение Dvi [v0 ] уменьшается,процесс vi отправляет сообщение hmydist, v0 , Dvi [v0 ] i своим соседям, и, следовательно, сообщение hmydist, v0 , di, в котором d 6 d(vi , v0), хотя бы один разотправляется процессу vj+1 .По предположению это сообщение будет получено процессом v j+1 в некоторой конфигурации C. Согласно описанию алгоритма после получения этогосообщения будет выполняться неравенство D vj+1 [v0 ] 6 d + vj+1 vi ; как следует извыбора номера i, это влечет за собой неравенство d + vj+1 vi 6 d(vj+1 , v0).Полное описание алгоритма также включает в себя процедуру, посредствомкоторой узлы могут обнаружить, что вычисление завершилось (обратите внимание на замечание в начале § 4.3.3, относящееся к алгоритму Netchange).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
