ì 0 если u=v
d(u,v)= í (4.1)
î wuw+d(w,v) иначе
Два свойства этого равенства делают алгоритмы основанные на этом отличными от алгоритма Toueg.
(1) Локальность данных. Во время оценивания правой стороны равенством (4.1), узлу u необходима только информация доступная локально (именно, wuw) или в соседях (именно, d(w, v)). Транспортирование данных между удаленными вершинами избегается.
(2) Независимость пункта назначения. Расстояния до v (именно, d(w, v) где w сосед u) только нуждаются в вычислении расстояния от u в v. Таким образом, вычисление всех расстояний до фиксированного пункта назначения vo может происходить независимо от вычисления расстояния до других узлов, и также, может бать сделано обособленно.
В завершение этой части обсуждены два алгоритма основанные на равенстве, а именно алгоритмы Мерлина-Сигалла и Чанди-Мизра. Не смотря на преимущества от локальности данных, сложность соединений этих алгоритмов не лучше алгоритма Toueg. Это из-за независимости пункта назначения введенного равенством(4.1); очевидно, использование результатов для других пунктов назначения (как сделано в алгоритме Toueg) более выгодный прием чем локальность данных.
Если это не ведет к уменьшению сложности соединений, тогда каково значение локальности данных? Уверенность в удаленных данных требует повторных распространений если данные могли измениться из-за топологических изменений сети. Доведение до конца этих распространений (с возможными новыми топологическими изменениями в течение распространения) вызывает нетривиальные проблемы с дорогими решениями (см., на пример, [Gaf87]). Более того, алгоритмы основанные на равенстве 4.1 могут быть более легко адаптированы к топологическим изменениям. Оно служит примером в части 4.3, где подробно разобран такой алгоритм.
Алгоритм Мерлина-Сигалла. Алгоритм предложенный Мерлином и Сигаллом [MS79] вычисляет таблицы маршрутизации для каждого пункта назначения абсолютно обособленно; вычисления для различных пунктов назначения не оказывают влияния друг на друга. Для пункта назначения v, алгоритм начинает работу с дерева Tv с корнем в v, и повторно перевычисляет это дерево с тем чтобы оно стало оптимальным деревом стока для v.
Для пункта назначения v, каждый узел u содержит оценку расстояния до v (Du[v]) и соседа через которого пакет для u пересылается (Nbu[v]), который также является отцом u в Tv. В период перевычисления каждый узел u посылает свою оценку расстояния, Du[v], к всем соседям исключая Nbu[v] (в < mydist, v, Du[v]> сообщении). Если узел u получает от соседа w сообщение <mydist,v,d> и если d+wuv < Du[v], u изменит Nbu[v] на w и Du[v] на d + wuv. Период перевычисления контролируется узлом v и требует обмена двумя сообщениями в W бит на каждый канал.
В [MS79] показано что после i периодов перевычислений все кротчайшие пути в более чем i шагов будут корректно вычислены, так что после N раундов все кротчайшие пути будут вычислены. Кротчайшие пути в каждый пункт назначения вычисляются выполнением алгоритма независимо для каждого пункта назначения.
Теорема 4.11 Алгоритм Мерлина и Сигалла вычисляет таблицы маршрутизации кротчайших путей с обменом 0(N2) сообщениями на канал, 0(N2 W) битами на канал, 0(N2 |E|) сообщениями всего, и 0(N2|E|W) битами всего.
Алгоритм может также адаптироваться к изменениям топологии и весов каналов. Важное свойство алгоритма в том что в течение периода перевычислений таблицы маршрутизации не содержат циклов.
Алгоритм Чанди—Мизра. Алгоритм предложенный Чанди и Мизра [CM82] вычисляет все кротчайшие вычисляет до одного пункта назначения используя парадигму диффузивных вычислений (распределенные вычисления которые инициируются одним узлом, и другие узлы присоединяются только после получения сообщения).
Вычисление, для всех узлов, расстояния до узла vo (и привилегированного исходящего канала), каждый узел u начинает с Du[vo] = ¥ и ждет получения сообщений. Узел vo посылает <mydist,vo,0> сообщение всем соседям. Когда же узел u получает сообщение <maydist,vo,d> от соседа w, где d + wuw < Du[vo], u заносит значение d+wuv в Du[vo] и посылает сообщение < mydist, vo, D Du[vo]> всем соседям; смотри Алгоритм 4.7.
var Du[vo] : вес init ¥ ;
Nbu[vo] : узел init udef ;
Только для узла vo :
begin Du[vo] := 0 ;
forall w Î Neighvo do послать < maydist, vo, 0> к w
end
Обработка сообщения < maydist, vo, d> от соседа w узлом u:
{ <mydist, vo,d> Î Mwv }
begin получить <mydist,vo,d> от w ;
if d + wuw < Du[vo] then
begin Du[vo] := d+wuw ; Nbu[vo] := w ;
forall x Î Neighu do послать < maydist, vo, Du[vo]> к x
Алгоритм 4.7 Алгоритм Чанди-Мизра (для узла u).
Не трудно показать что Du[vo] всегда верхняя граница для d(u, vo), т.е., d(u,vq) £ Du[vo] инвариант алгоритма; см. упражнение 4.3. Чтобы продемонстрировать чти алгоритм вычисляет расстояния верно, нужно показать что в конечном счете достигнется конфигурация в которой Du[vo] £ d(u, vo) для каждого u. Мы дадим доказательство этого свойства используя предположение допущения слабой справедливости, а именно, что каждое сообщение которое посылается в конечном счете получено в каждом вычислении.
Теорема 4.12 В каждом вычислении Алгоритма 4.7 достигнется конфигурация в которой для каждого узла u, Du[vo] £ d(u, vo).
Доказательство. Зафиксируем оптимальное дерево стока T для vo и обозначим остальные узлы v1 … vN-1 таким образом что если vi, отец узла vj, тогда i < j. Пусть C вычисление; можно показано индукцией по j что для каждого j £ N— 1 достигнется конфигурация в которой, для каждого i £ j, Dvi[vo] £ d(vi, vo). Заметим что Dvi[vo] никогда не увеличивается в алгоритме; таким образом если Dvi[vo] £ d(vi, vo) содержится в некоторой конфигурации то она лучшая конфигурация из всех.
Случай j = 0: d(vo, vo) = 0, и Dvo[vo] = 0 после выполнения инициализационной части узлом vo, , таким образом Dvo[vo]£ d(vo, vo) содержится после этого выполнения.
Случай j + 1: Допустим что достигнется конфигурация в которой для каждого i £ j, Dvi[vo]£d(vi, vo), и рассмотрим узел vj+1. Имеется кротчайший путь vj+1, vi, ..., vo длины d(vj+1, vo) от vj+1 до vo, где vi отец vj+1 в T, отсюда i £ j. Следовательно, по индукции, достигается конфигурация в которой Dvi[vo]£ d(vi, vo). Всякий раз когда Dvi[vo] уменьшится, vi посылает сообщение < mydist, vo, Dvi[vo]> своим соседям, отсюда сообщение < mydist, vo,d>посылается к vj+1 по крайней мере однажды с d £ d(vi,vo).
По предположению, это сообщение принимается в C узлом vj+1. Алгоритм подразумевает что после получения этого сообщения хранится Dvi[vo] £ d + , и выбор i подразумевает что d + £ d(vj+1, vo).
Полный алгоритм также включает механизм с помощью которого узлы могут определить окончание вычисления.; сравним с замечанием об алгоритме Netchange в начале части 4.3.3. Механизм для определения завершения является вариацией алгоритма Дейкстры-Шолтена обсужденного в 8.2.1.
Алгоритм отличается от алгоритма Мерлина-Сигалла двумя вещами. Во-первых, нет "отца" узла u которому не посылаются сообщения типа <mydist,.,.>. Эта особенность алгоритма Мерлина и Сигалла гарантирует что таблицы всегда не содержат циклов, даже в течение вычислений и при наличии топологических изменений. Во-вторых, обмен сообщениями < mydist,.,. > не координируется в раундах, но существует отслеживание завершения, который влияет на сложность не лучшим образом.
Алгоритм может потребовать экспоненциальное количество сообщений для вычисления путей до одного пункта назначения vo. Если стоимости всех каналов равны (т.е., рассматривается маршрутизация с минимальным количеством переходов) все кротчайшие пути к vо вычисляются используя O(N |E|) сообщений ( O(W) бит каждое), руководствуясь следующим результатом.
Теорема 4.13 Алгоритм Чанди и Мизра вычисляет таблицы маршрутизации с минимальным количеством шагов с помощью обменов 0(N2) сообщениями (N2W) бит на канал, и 0(N2|E|) сообщений и 0(N2 |E| W) бит всего.
Преимущество алгоритма Чанди и Мизра над алгоритмом Мерлина и Сигалла в его простоте, его меньшей пространственной сложности, и его меньшей временной сложности.
4.3 Алгоритм Netchange
Алгоритм Таджибнаписа Netchange [Taj77] вычисляет таблицы маршрутизации которые удовлетворяют мере "минимальное количество шагов". Алгоритм подобен алгоритму Чанди-Мизра , но содержит дополнительную информацию которая позволяет таблицам только частично перевычисляться после отказа или восстановления канала. Представление алгоритма в этой части придерживается Лампорта [Lam82]. Алгоритм основан на следующих предположениях.
Страницы: 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
