Распределенные алгоритмы (стр. 29 из 85)

Во-первых, как ранее говорилось, однообразный выбор всеми узлами следующего центрального узла (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 сообщение <mydist,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 посылает <mydist,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:

{ <mydist, v_o,d> Î M_wv }

begin получить <mydist,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,.,.>. Эта особенность алгоритма Мерлина и Сигалла гарантирует что таблицы всегда не содержат циклов, даже в течение вычислений и при наличии топологических изменений. Во-вторых, обмен сообщениями < mydist,.,. > не координируется в раундах, но существует отслеживание завершения, который влияет на сложность не лучшим образом.