Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 35
Текст из файла (страница 35)
Принимая во внимание правила 5) и 6) утверждения 4.5, а такжеследовательное соединение двух S-путей, один из которых ведет в вершину w, аинвариантцикла, заключаем, что S-расстояния между всеми вершинами равныдругой исходит из вершины w.расстояниям.Правило (4). Применяя лемму 4.1, можно показать, что в том случае, если0Основной цикл выполняется N раз, и в каждой его итерации выполняетсяв графе есть S0 -путь из u в v, существует и простой S0 -путь длины dS (u, v) из u02SSSSNв v. Согласно правилу (3) отсюда следует равенство d (u, v) = min (d (u, v), d (u, w) +d (w, v) ).
операций (их можно выполнять последовательно или параллельно). Отсюдаполучается верхняя оценка сложности алгоритма.Правило (5). Каждый V -путь является путем и наоборот.126Гл. 4. Алгоритмы маршрутизации4.2.2. Алгоритм Туэга построения кратчайших путейvar SuDuNbu: set of nodes ;: array of weights ;: array of nodes ;begin Su := ∅ ;forall v ∈ V doif v = uthen begin Du [v] := 0 ; Nbu [v] := udef endelse if v ∈ Neighuthen begin Du [v] := uv ; Nbu [v] := v endelse begin Du [v] := ∞ ; Nbu [v] := udef end;while Su 6= V dobegin pick w from V \ Su ;(* Здесь все процессы должны выбрать одну и ту же вершину w *)if u = wthen «broadcast the table Dw »else «receive the table Dw » ;forall v ∈ V doif Du [w] + Dw [v] < Du [v] thenbegin Du [v] := Du [w] + Dw [v] ;Nbu [v] := Nbu [w]end;Su := Su ∪ {w}endendАлгоритм 4.5.
Упрощенный вариант алгоритма (для узла u).Распределенный алгоритм вычисления таблиц маршрутизации был разработан Туэгом в работе [194] на основе алгоритма Флойда —Уоршалла, которыйбыл описан в предыдущем параграфе. Мы должны убедиться в том, что алгоритм Флойда—Уоршалла подходит для этой цели, т. е. те допущения, на которыхбазируется этот алгоритм, верны для распределенных систем. Наиболее важным из этих допущений является предположение о том, что в графе нет цикловотрицательного веса. Распределенные системы и в самом деле обладают этимсвойством, так как каждому отдельному каналу связи приписывается положительная стоимость. Можно принять даже более строгое предположение (см. A1ниже).В этом параграфе мы будем действовать в рамках следующих допущений.A1.
Каждый цикл в сети имеет положительный вес.A2. Каждый процесс сети располагает информацией об отличительных признаках всех узлов системы (множества вершин V).4.2. Задача построения кратчайших путей для всех пар вершин127A3. Каждый процесс располагает информацией о том, какие узлы являютсяего соседями (для каждой вершины u эти сведения содержатся в массиве Neigh u)и какой вес имеют каналы, соединяющие процесс с его соседями.Нам будет проще разобраться с корректностью алгоритма Туэга (алгоритм 4.6),если вначале мы рассмотрим его упрощенный вариант, так называемый «простойалгоритм» (алгоритм 4.5).Упрощенный алгоритм. Чтобы получить распределенный алгоритм, переменные и операции алгоритма Флойда—Уоршалла разносятся по разным узлам сети. Переменная D [u, v] отдается процессу u; для удобства обозначениямы будем записывать u на месте индекса следующим образом D u [v] .
Операции,которые присваивают значения переменной Du [v] , должны выполняться в узлеu, и, когда значение некоторой переменной, относящейся к узлу w, необходимодля этой операции, это значение должно быть послано процессу u. В алгоритмеФлойда—Уоршалла все вершины должны использовать информацию от опорной вершины (она обозначена символом w в теле цикла), которая отправляет этуинформацию одновременно всем вершинам посредством «широковещательной»операции.
Наконец, в этом алгоритме нужно ввести специальную операцию, длятого чтобы не только вычислять длины кратчайших S-путей (для этого используются переменные Du [v]), но также и первый канал в каждом таком пути (дляэтого мы будем использовать переменные Nbu [v]).Допущение о том, что всякий цикл в сети имеет положительный вес, можно использовать для того, чтобы показать, что после каждого этапа обработкиопорной вершины в таблицах маршрутизации не образуются циклы.Лемма 4.7. Пусть заданы множество вершин S и вершина w. Предположим также, что1) для всех вершин u верно равенство Du [w] = dS (u, w);2) если dS (u, w) < ∞ и u 6= w, то значением переменной Nbu [w] является имя соседа вершины u на кратчайшем S-пути, ведущем к вершине w.Тогда ориентированный граф Tw = (Vw , Ew), где(u ∈ Vw ⇐⇒ Du [w] < ∞)и(ux ∈ Ew ⇐⇒ (u 6= w ∧ Nbu [w] = x)),является деревом, в корне которого расположена вершина w.Д о к а з а т е л ь с т в о.
Прежде всего заметим, что в том случае, если длявершины u 6= w выполняется неравенство Du [w] < ∞, то Nbu [w] 6= udef иDNbu [w] [w] < ∞. Значит, для каждой вершины u ∈ Vw , u 6= w, существует вершинаx, x ∈ Vw , для которой верно равенство Nbu [w] = x.Для каждой вершины u ∈ Vw , u 6= w, в множестве Ew есть одно ребро, и поэтому число вершин в графе Tw превосходит количество ребер на единицу. Осталосьпоказать, что граф Tw не содержит циклов.
Коль скоро для ребра ux ∈ E w имеет место равенство dS (u, w) = ux + dS (x, w), наличие цикла hu0 , u1 , . . . , uk iв графе Tw повлекло бы за собой следующее соотношение:dS (u0 , w) =u0 u1+u1 u2+ ... +uk−1 u0+ dS (u0 , w),128Гл. 4. Алгоритмы маршрутизациииз которого вытекает то, что0=u0 u1+u1 u2+ ... +uk−1 u0 ,а это противоречит допущению о том, что каждый цикл имеет положительныйвес.Теперь алгоритм Флойда—Уоршалла может быть непосредственно преобразован в алгоритм 4.5. Каждая вершина-процесс устанавливает начальные значения приписанным ей переменным и выполняет N итераций основного цикла. Этоталгоритм еще не дает нам окончательного решения, потому что мы не описали,как провести эффективное широковещательное распространение таблицы маршрутизации опорной вершины. Пока мы можем лишь поверить, что в том случае,когда операция «broadcast the table Dw » выполняется процессом w, а операция«receive the table Dw » выполняется другими процессами, каждый узел получитдоступ к таблице Dw .Нужно обратить особое внимание на операцию «pick w from V \ S» и организовать ее выполнение так, чтобы все процессы выбирали опорные вершиныв одном и том же порядке.
Коль скоро предполагается, что всем процессам заранее известно множество V, мы можем считать, что вершины из этого множествавыбираются в каком-либо заранее заданном порядке (например, имена вершинвыбираются в алфавитном порядке).Корректность упрощенного алгоритма устанавливается в следующей теореме.Теорема 4.8.
Алгоритм 4.5 завершает свое выполнение в каждом узлесети после N итераций основного цикла. Когда алгоритм завершаетсяв узле u, для каждой вершины v выполняется равенство Du [v] = d(u, v),и в том случае, если в сети есть путь из u в v, то значением переменнойNbu [v] является наименование первого канала в кратчайшем пути из uв v; в противном случае Nbu [v] = udef.Д о к а з а т е л ь с т в о. Завершаемость и частичная корректность нашегоалгоритма следуют из корректности алгоритма Флойда —Уоршалла (теорема 4.6).Отсюда следует и справедливость утверждения о значении переменной Nb u [v] ,поскольку значение Nbu [v] изменяется всякий раз, когда переменной D u [v] присваивается новое значение.4.2.
Задача построения кратчайших путей для всех пар вершин129var Su : set of nodes ;Du : array of weights ;Nbu : array of nodes ;begin Su := ∅ ;forall v ∈ V doif v = uthen begin Du [v] := 0 ; Nbu [v] := udef endelse if v ∈ Neighuthen begin Du [v] := uv ; Nbu [v] := v endelse begin Du [v] := ∞ ; Nbu [v] := udef end;while Su 6= V dobegin pick w from V \ Su ;(* Построить дерево Tw *)forall x ∈ Neighu doif Nbu [w] = x then send hys, wi to x else send hnys, wi to x ;recu := 0 ; (* u должен получить |Neighu | сообщений *)while recu < |Neighu | dobegin receive hys, wi or hnys, wi message ; recu := recu + 1 end;if Du [w] < ∞ then (* принять участие в обработке опорной вершины *)begin if u 6= w then receive hdtab, w, Di from Nbu [w] ;forall x ∈ Neighu doif hys, wi was received from x then send hdtab, w, Di to x ;forall v ∈ V do(* local w-pivot *)if Du [w] + D [v] < Du [v] thenbegin Du [v] := Du [w] + D [v] ; Nbu [v] := Nbu [w] endend;Su := Su ∪ {w}endendАлгоритм 4.6.
Алгоритм Туэга (для узла u).Улучшенный алгоритм. Чтобы эффективно провести широковещательнуюрассылку в алгоритме 4.5, Туэг обратил внимание на то, что если узел u удовлетворяет условию Du [w] = ∞ в начале этапа обработки опорной вершины, то поокончании обработки этой вершины таблица маршрутизации этого узла остаетсянеизменной. Если Du [w] = ∞, то неравенство Du [w] + Dw [v] < Du [v] неверно для каждой вершины v.
Следовательно, таблицу маршрутизации вершины wнужно доставить только в те узлы, которые принадлежат дереву T w (в том виде,в котором оно было сформировано к началу этапа обработки опорной вершины),и операцию широковещательной рассылки можно провести эффективно, отправляя таблицу Dw только по тем каналам, которые входят в состав дерева T w . Такимобразом, узел w отправляет таблицу Dw своим сыновним вершинам в дереве Tw ,и каждый узел в дереве Tw , получивший эту таблицу от родительской вершиныв дереве Tw , переправляет ее своим сыновним вершинам в дереве T w .130Гл. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
