ref (664672), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Toueg дал дальнейшую оптимизацию алгоритма, полагаясь на следующий результат. (Узел u₂ потомок u₁ если u₂ принадлежит поддереву u₁)

Лемма 4.10 Пусть u₁ w, и пусть u₂ потомок u₁ в T_w, в начале w-централизованного обхода, если u₂ изменит своё расстояние до v во время w-централизованного обхода, тогда и u₁ изменит своё расстояние до v в этом же обходе.

Доказательство. Так как u₂ потомок u₁ в T_w :

d^S(u₂, w) = d^S (u₂, u₁) + d^S (u₁, w). (1)

Так как u₁  S:

d^S(u₂, v)  d^S (u₂, u₁) + d^S (u₁,v). (2)

Узел u₂ изменит D_u2 [v] в данном обходе тогда и только тогда когда

d^S(u₂, w) + d^S (w, v) < d^S (u₂, v). (3)

Применяя (2), и затем (1), и вычитая d^S(u₂, u₁), мы получим

d^S(u₁, w) + d^S (w, v) < d^S (u₁, v) (4)

значит u₁ изменит D_u1 [v] в этом обходе.

В соответствии с этой леммой, Алгоритм 4.6 может быть модифицирован следующим образом. После получения таблицы D_w, (сообщение <dtab, w,D>) узел u вначале выполняет локальные w-централизованные операции, и затем рассылает таблицы своим сыновьям в T_w. Когда пересылка таблицы закончилась достаточно переслать те ссылки D[v] для которых D_u[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) может использоваться в алгоритмах для проблем кротчайших путей:

 0 если u=v

d(u,v)=  (4.1)

 w_uw+d(w,v) иначе

Два свойства этого равенства делают алгоритмы основанные на этом отличными от алгоритма Toueg.

(1) Локальность данных. Во время оценивания правой стороны равенством (4.1), узлу u необходима только информация доступная локально (именно, w_uw) или в соседях (именно, d(w, v)). Транспортирование данных между удаленными вершинами избегается.

(2) Независимость пункта назначения. Расстояния до v (именно, d(w, v) где w сосед u) только нуждаются в вычислении расстояния от u в v. Таким образом, вычисление всех расстояний до фиксированного пункта назначения v_o может происходить независимо от вычисления расстояния до других узлов, и также, может бать сделано обособленно.

В завершение этой части обсуждены два алгоритма основанные на равенстве, а именно алгоритмы Мерлина-Сигалла и Чанди-Мизра. Не смотря на преимущества от локальности данных, сложность соединений этих алгоритмов не лучше алгоритма Toueg. Это из-за независимости пункта назначения введенного равенством(4.1); очевидно, использование результатов для других пунктов назначения (как сделано в алгоритме Toueg) более выгодный прием чем локальность данных.

Если это не ведет к уменьшению сложности соединений, тогда каково значение локальности данных? Уверенность в удаленных данных требует повторных распространений если данные могли измениться из-за топологических изменений сети. Доведение до конца этих распространений (с возможными новыми топологическими изменениями в течение распространения) вызывает нетривиальные проблемы с дорогими решениями (см., на пример, [Gaf87]). Более того, алгоритмы основанные на равенстве 4.1 могут быть более легко адаптированы к топологическим изменениям. Оно служит примером в части 4.3, где подробно разобран такой алгоритм.

Алгоритм Мерлина-Сигалла. Алгоритм предложенный Мерлином и Сигаллом [MS79] вычисляет таблицы маршрутизации для каждого пункта назначения абсолютно обособленно; вычисления для различных пунктов назначения не оказывают влияния друг на друга. Для пункта назначения v, алгоритм начинает работу с дерева T_v с корнем в v, и повторно перевычисляет это дерево с тем чтобы оно стало оптимальным деревом стока для v.

Для пункта назначения v, каждый узел u содержит оценку расстояния до v (D_u[v]) и соседа через которого пакет для u пересылается (Nb_u[v]), который также является отцом u в T_v. В период перевычисления каждый узел u посылает свою оценку расстояния, D_u[v], к всем соседям исключая Nb_u[v] (в < mydist, v, D_u[v]> сообщении). Если узел u получает от соседа w сообщение v,d> и если d+w_uv < D_u[v], u изменит Nb_u[v] на w и D_u[v] на d + w_uv. Период перевычисления контролируется узлом v и требует обмена двумя сообщениями в W бит на каждый канал.

В [MS79] показано что после i периодов перевычислений все кротчайшие пути в более чем i шагов будут корректно вычислены, так что после N раундов все кротчайшие пути будут вычислены. Кротчайшие пути в каждый пункт назначения вычисляются выполнением алгоритма независимо для каждого пункта назначения.

Теорема 4.11 Алгоритм Мерлина и Сигалла вычисляет таблицы маршрутизации кротчайших путей с обменом 0(N²) сообщениями на канал, 0(N² W) битами на канал, 0(N² |E|) сообщениями всего, и 0(N²|E|W) битами всего.

Алгоритм может также адаптироваться к изменениям топологии и весов каналов. Важное свойство алгоритма в том что в течение периода перевычислений таблицы маршрутизации не содержат циклов.

Алгоритм Чанди—Мизра. Алгоритм предложенный Чанди и Мизра [CM82] вычисляет все кротчайшие вычисляет до одного пункта назначения используя парадигму диффузивных вычислений (распределенные вычисления которые инициируются одним узлом, и другие узлы присоединяются только после получения сообщения).

Вычисление, для всех узлов, расстояния до узла v_o (и привилегированного исходящего канала), каждый узел u начинает с D_u[v_o] =  и ждет получения сообщений. Узел v_o посылает v_o,0> сообщение всем соседям. Когда же узел u получает сообщение <maydist,v_o,d> от соседа w, где d + w_uw < D_u[v_o], u заносит значение d+w_uv в D_u[v_o] и посылает сообщение < mydist, v_o, D D_u[v_o]> всем соседям; смотри Алгоритм 4.7.

var D_u[v_o] : вес init  ;

Nb_u[v_o] : узел init udef ;

Только для узла v_o :

begin D_u[v_o] := 0 ;

forall w  Neigh_vo do послать < maydist, v_o, 0> к w

end

Обработка сообщения < maydist, v_o, d> от соседа w узлом u:

{ v_o,d>  M_wv }

begin получить v_o,d> от w ;

if d + w_uw < D_u[v_o] then

begin D_u[v_o] := d+w_uw ; Nb_u[v_o] := w ;

forall x  Neigh_u do послать < maydist, v_o, D_u[v_o]> к x

end

end

Алгоритм 4.7 Алгоритм Чанди-Мизра (для узла u).

Не трудно показать что D_u[v_o] всегда верхняя граница для d(u, vo), т.е., d(u,vq)  D_u[v_o] инвариант алгоритма; см. упражнение 4.3. Чтобы продемонстрировать чти алгоритм вычисляет расстояния верно, нужно показать что в конечном счете достигнется конфигурация в которой D_u[v_o]  d(u, v_o) для каждого u. Мы дадим доказательство этого свойства используя предположение допущения слабой справедливости, а именно, что каждое сообщение которое посылается в конечном счете получено в каждом вычислении.

Теорема 4.12 В каждом вычислении Алгоритма 4.7 достигнется конфигурация в которой для каждого узла u, D_u[v_o]  d(u, v_o).

Доказательство. Зафиксируем оптимальное дерево стока T для v_o и обозначим остальные узлы v₁ … v_N-1 таким образом что если v_i, отец узла v_j, тогда i < j. Пусть C вычисление; можно показано индукцией по j что для каждого j  N— 1 достигнется конфигурация в которой, для каждого i  j, D_vi[v_o]  d(v_i, v_o). Заметим что D_vi[v_o] никогда не увеличивается в алгоритме; таким образом если D_vi[v_o]  d(v_i, v_o) содержится в некоторой конфигурации то она лучшая конфигурация из всех.

Случай j = 0: d(v_o, v_o) = 0, и D_vo[v_o] = 0 после выполнения инициализационной части узлом v_o, , таким образом D_vo[v_o] d(v_o, v_o) содержится после этого выполнения.

Случай j + 1: Допустим что достигнется конфигурация в которой для каждого i  j, D_vi[v_o]d(v_i, v_o), и рассмотрим узел v_j+1. Имеется кротчайший путь v_j+1, v_i, ..., v_o длины d(v_j+1, v_o) от v_j+1 до v_o, где v_i отец v_j+1 в T, отсюда i  j. Следовательно, по индукции, достигается конфигурация в которой D_vi[v_o] d(v_i, v_o). Всякий раз когда D_vi[v_o] уменьшится, v_i посылает сообщение < mydist, v_o, D_vi[v_o]> своим соседям, отсюда сообщение < mydist, v_o,d>посылается к v_j+1 по крайней мере однажды с d  d(v_i,v_o).

По предположению, это сообщение принимается в C узлом v_j+1. Алгоритм подразумевает что после получения этого сообщения хранится D_vi[v_o]  d + , и выбор i подразумевает что d +  d(v_j+1, v_o).

Полный алгоритм также включает механизм с помощью которого узлы могут определить окончание вычисления.; сравним с замечанием об алгоритме Netchange в начале части 4.3.3. Механизм для определения завершения является вариацией алгоритма Дейкстры-Шолтена обсужденного в 8.2.1.

Алгоритм отличается от алгоритма Мерлина-Сигалла двумя вещами. Во-первых, нет "отца" узла u которому не посылаются сообщения типа <mydist,.,.>. Эта особенность алгоритма Мерлина и Сигалла гарантирует что таблицы всегда не содержат циклов, даже в течение вычислений и при наличии топологических изменений. Во-вторых, обмен сообщениями не координируется в раундах, но существует отслеживание завершения, который влияет на сложность не лучшим образом.

Алгоритм может потребовать экспоненциальное количество сообщений для вычисления путей до одного пункта назначения v_o. Если стоимости всех каналов равны (т.е., рассматривается маршрутизация с минимальным количеством переходов) все кротчайшие пути к v_о вычисляются используя O(N |E|) сообщений ( O(W) бит каждое), руководствуясь следующим результатом.

Характеристики

Список файлов реферата