____________________________________________________________________
var Su : множество узлов ;
Du : массив весов;
Nbu : массив узлов ;
begin
Su := Æ ;
forall v Î V do
if v = u
then begin Du[v] := O ; Nbu[v] := udef end
else if v Î Neighu
then begin Du[v] := wuv ; Nbu[v] := v end
else begin Du[v] := ¥ ; Nbu[v] := udef end ;
while Su ¹ V do
begin выбрать w из V \ Su ;
(* Построение дерева Tw *)
forall x Î Neighu do
if Nbu[w] = x then send < ys, w> to x
else send < nys, w > to x ;
num_recu := O ; (* u должен получить |Neighu| сообщений *)
while num_recu < |Neighu| do
begin получить < ys, w > или < nys, w > сообщение ;
num_recu := num_recu + 1
end;
if Du[w] < ¥ then (* участвует в центр. обходе*)
begin if u¹ w
then получить <dtab,w,D> от Nbu[w] ;
if < ys, w > было послано от x
then послать < dtab, w, D>) к x; ;
forall v Î V do (* локальный w-центр *)
if Du[w] + D[v] < Du[v] then
begin Du[v] := Du[w] + D[v] :
Nbu[v] := Nbu[w]
end
Su := Su È {w}
Алгоритм 4.6 Алгоритм Тoueg (для узла u).
_____________________________________________________________________
В начале w-централизованного раунда узел u с Du[w] < ¥ знает кто его отец (в Tw) , но не знает кто его сыновья. Поэтому каждый узел v должен послать сообщение к каждому своему соседу u, спрашивая u является ли v сыном u в Tw. Полный алгоритм дан как Алгоритм 4.6. Узел может участвовать в пересылке таблицы w когда известно что его соседи являются его сыновьями в Tw. Алгоритм использует три типа сообщений:
(1) <ys,w> сообщение <ys обозначение для "your son"> u посылает к x; в начале w-централизованного обхода если x отец u в Tw.
(2) <nys, w> сообщение <nys обозначение для "not your son"> u посылает x в начале w-централизованного обхода если x не отец u в Tw
(3) <dtab, w, D> сообщение посылается в течение w-централизованного обхода через каждое ребро Tw чтобы переслать значение Dw к каждому узлу который должен использовать это значение.
Полагая сто вес (ребра или пути) вместе с именем узла можно представить W битами, сложность алгоритма показана следующей теоремой.
Теорема 4.9 Алгоритм 4.6 вычисляет для каждых u и v дистанцию от u к v, и, если эта дистанция конечная, первый канал. Алгоритм обменивается 0(N) сообщениями на канал,, 0(N*|E|) сообщений всего, O(N2W) бит на канал, O(N 3W) бит всего, и требуется 0(NW) бит хранения на узел.
Доказательство. Алгоритм 4.6 выведен от Алгоритма 4.5, который корректен.
Каждый канал переносит два ( < ys, w> или < nys, w> ) сообщений (одно в каждом направлении) и не более одного <dtab, w, D > сообщения в w-централизованном обходе, который включает не более 3N сообщений на канал. < ys, w > или < nys, w > сообщение содержит O(W) бит и <dtab, w, D > сообщение содержит O(NW) бит, что и является границей для числа бит на канал. Не более N2 < dtab, w,D> сообщений и 2N - |E| (<ys,w> и <nys,w> ) сообщений обмена, и того всего O(N2 - NW +2N-|E|-W) = O(N3W) бит. Таблицы Du и Nbu хранящиеся в узле u требуют 0(NW) бит.‰
В течение w-центализованного обхода узлу разрешено принимать и обрабатывать сообщения только данного обхода, т.е., те которые переносят параметр w. Если каналы удовлетворяют дисциплине FIFO тогда сообщения <ys,w> и <nys, w> прибывают первыми, по одному через каждый канал, и затем сообщение < dtab, w, D > от Nbu[ w] (если узел в Vw). Таким образом возможно, аккуратно программируя, опустить параметр w во всех сообщениях если каналы удовлетворяют дисциплине FIFO. Если каналы не удовлетворяют дисциплине FIFO возможно что сообщение с параметром w' придет пока узел ожидает сообщения для обхода w, тогда как w' становится центром после w. В этом случае параметр используется чтобы различить сообщения для каждого централизованного обхода, и локальная буферизация ( в канале и узле) должна использоваться для отсрочки выполнения w'-сообщения.
Toueg дал дальнейшую оптимизацию алгоритма, полагаясь на следующий результат. (Узел u2 потомок u1 если u2 принадлежит поддереву u1)
Лемма 4.10 Пусть u1¹ w, и пусть u2 потомок u1 в Tw, в начале w-централизованного обхода, если u2 изменит своё расстояние до v во время w-централизованного обхода, тогда и u1 изменит своё расстояние до v в этом же обходе.
Доказательство. Так как u2 потомок u1 в Tw :
dS(u2, w) = dS (u2, u1) + dS (u1, w). (1)
Так как u1 Î S:
dS(u2, v) £ dS (u2, u1) + dS (u1,v). (2)
Узел u2 изменит Du2 [v] в данном обходе тогда и только тогда когда
dS(u2, w) + dS (w, v) < dS (u2, v). (3)
Применяя (2), и затем (1), и вычитая dS(u2, u1), мы получим
dS(u1, w) + dS (w, v) < dS (u1, v) (4)
значит u1 изменит Du1 [v] в этом обходе.‰
В соответствии с этой леммой, Алгоритм 4.6 может быть модифицирован следующим образом. После получения таблицы Dw, (сообщение <dtab, w,D>) узел u вначале выполняет локальные w-централизованные операции, и затем рассылает таблицы своим сыновьям в Tw. Когда пересылка таблицы закончилась достаточно переслать те ссылки D[v] для которых Du[v] изменилась в течение локальной w-централизованной операции. С этой модификацией таблицы маршрутизации не содержат циклов не только между централизованными обходами (как сказано в Лемме 4.7), но также в течение централизованных обходов.
4.2.3 Обсуждение и Дополнительные Алгоритмы
Представление алгоритм Toueg предоставило пример как распределенный алгоритм может быть получен непосредственным образом из последовательного алгоритма. Переменные последовательного алгоритма распределены по процессам, и любое означивание переменной x (в последовательном алгоритме) выполняется процессом владеющим x. Всякий раз когда ознaчивающее выражение содержит ссылки на переменные из других процессов, связь между процессами потребуется для передачи значения и синхронизации процессов. Специфические свойства последовательного алгоритма могут быть использованы для минимизации числа соединений.
Алгоритм Toueg прост для понимания, имеет низкую сложность, и маршрутизирует через оптимальные пути; его главный недостаток в его плохая живучесть. Когда топология сети изменилась все вычисления должны произвестись заново.
Во-первых, как ранее говорилось, однообразный выбор всеми узлами следующего центрального узла (w) требует чтобы множество участвующих узлов было известно заранее. Так как это в основном не известно априори, исполнение расширенного распределенного алгоритма вычисления этого множества (на пример алгоритм Финна, Алгоритм 6.9) должно предшествовать исполнению алгоритма Toueg.
Во-вторых, алгоритм Toueg основан на повторяющимися применениями уникальности треугольника d(u, v) £ d(u, w) + d(w, v). Оценивание правой стороны ( u) требует информацию о d(w, v), и эта информация в часто удалена, т.е., не доступна ни в u ни в любой из его соседей. Зависимость от удаленных данных делает необходимым транспортирование информации к удаленным узлам, которые могут быть исследованы в алгоритме Toueg (часть распространения).
Как альтернатива, определенное ниже равенство для d(u, v) может использоваться в алгоритмах для проблем кротчайших путей:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
