Алгоритм может потребовать экспоненциальное количество сообщений для вычисления путей до одного пункта назначения vo. Если стоимости всех каналов равны (т.е., рассматривается маршрутизация с минимальным количеством переходов) все кротчайшие пути к vо вычисляются используя O(N |E|) сообщений ( O(W) бит каждое), руководствуясь следующим результатом.
Теорема 4.13 Алгоритм Чанди и Мизра вычисляет таблицы маршрутизации с минимальным количеством шагов с помощью обменов 0(N2) сообщениями (N2W) бит на канал, и 0(N2|E|) сообщений и 0(N2 |E| W) бит всего.
Преимущество алгоритма Чанди и Мизра над алгоритмом Мерлина и Сигалла в его простоте, его меньшей пространственной сложности, и его меньшей временной сложности.
Алгоритм Таджибнаписа Netchange [Taj77] вычисляет таблицы маршрутизации которые удовлетворяют мере "минимальное количество шагов". Алгоритм подобен алгоритму Чанди-Мизра , но содержит дополнительную информацию которая позволяет таблицам только частично перевычисляться после отказа или восстановления канала. Представление алгоритма в этой части придерживается Лампорта [Lam82]. Алгоритм основан на следующих предположениях.
Nl. Узлы знают размер сети (N).
N2. Каналы удовлетворяют дисциплине FIFO.
N3. Узлы уведомляют об отказах и восстановлениях смежных к ним каналов.
N4. Цена пути – количество каналов в пути.
Алгоритм может управлять отказами и восстановлениями или добавлениями каналов, но положим что узел уведомляет когда смежный с ним канал отказывает или восстанавливается. Отказ и восстановление узлов не рассматривается: на самом деле отказ узла можно рассматриваться его соседями как отказ соединяющего канала. Алгоритм содержит в каждом узле u таблицу Nbu [v], дающую для каждого пункт назначения v соседа u через которого u пересылает пакеты для v. Требования алгоритмов следующие:
Rl. Если топология сети остается постоянной после конечного числа топологических изменений , тогда алгоритм завершается после конечного числа шагов.
R2. Когда алгоритм завершает свою работу таблицы Nbu[v] удовлетворяют
(a) если v = u то Nbu[v] = local ;
(b) если путь из u в v ¹ u существует то Nbu[v] = w, где w первый сосед u в кротчайшем пути из u в v,
(c) если нет пути из u в v тогда Nbu[v] = udef.
4.3.1 Описание алгоритма
Алгоритм Таджибнаписа Netchange дан как алгоритмы 4.8 и 4.9. Шаги алгоритма будут сначала объяснены неформально, и, впоследствии правильность алгоритма будет доказана формально. Ради ясности моделирование топологических изменений упрощено по сравнению с [Lam82], примем, что уведомление об изменении обрабатывается одновременно двумя узлами задействованными изменениями. Это обозначено в Подразделе 4.3.3, как асинхронная обработка.
Выбор соседа через которого пакеты для v будут посылаться основан на оценке расстояния от каждого узла до v. Предпочитаемый сосед всегда сосед с минимальной оценкой расстояния. Узел u содержит оценку d(u, v) в Du[v] и оценки d(w, v) в ndisu[w, v] для каждого соседа u. Оценка Du[v] вычисляется из оценок ndisu[w, v], и оценки ndisu[w,v] получены посредством коммуникаций с соседями.
Вычисление оценок Du[v] происходит следующим образом. Если u = v тогда d(u, v) = 0 таким образом Du[v] становится 0 в этом случае. Если u¹ v, кротчайший путь от u в v (если такой путь существует) состоит из канала из u до сосед, присоединенного к кратчайшему пути из сосед до v, и следовательно d(u, v) = 1 + min d(w, v).
wÎ Neigh u
Исходя из этого равенства, узел u ¹v оценивает d(u, v) применением этой формулы к оценочным значениям d(w, v), найденным в таблицах ndisu[w, v]. Так как всего N узлов, путь с минимальным количеством шагов имеет длину не более чем N—1 . Узел может подозревать что такой путь не существует если оцененное расстояние равно N или больше; значение N используется для этой цели.
var Neighu : множество узлов ; (* Соседи u *)
Du: массив 0.. N ; (* Du[v] - оценки d(u, v) *)
Nbu: массив узлов ; (* Nbu[v]- предпочтительный сосед для v *)
ndisu: массив 0.. N ; (*ndisu[w, v] - оценки d(w. v) *)
Инициализация:
begin forall w Î Neighu , v Î V do ndisu[w, v] := N ,
forall v Î V do
begin Du[v] := N ;
Nbu[v] := udef
end ;
Du[u]:= 0 ; Nbu[u] := local ;
forall w Î Neighudo послать < mydist, u, 0> к w
end
процедура Recompute (v):
begin if v = u
then begin Du[v]:= 0 ; Nbu[v] := local end
else begin (* оценка расстояния до v *)
d := 1 + min{ ndisu[w, v] : w Î Neighu} ;
if d < N then
begin Du[v] := d ;
Nbu[v] := w with 1 + ndisu[w, v] = d
end
else begin Du[v] := N ; Nbu[v] := udef end
end;
if Du[v] изменилась then
forall x Î Neighu do послать < mydist, v, Du[v]> к x
end
Алгоритм 4.8 Алгоритм Netchange (часть I, для узла u).
Алгоритм требует чтобы узел имел оценки расстояний до v своих соседей. Их они получают от этих узлов послав им сообщение <mydist,.,.> следующим образом. Если узел u вычисляет значение d как оценку своего расстояния до v (Du[v] = d), то эта информация посылается всем соседям в сообщении < mydist ,v,d>. На получение сообщения <mydist, v, d> от соседа w, u означивает ndisu[w, v] значением d. В результате изменения ndisu[w, v] оценка u расстояния d(u, v) может измениться и следовательно оценка перевычисляется каждый раз при изменении таблицы ndisu . Если оценка на самом деле изменилась то, на d' например, происходит соединение с соседями используя сообщение <mydist, v, d'>.
Алгоритм реагирует на отказы и восстановления каналов изменением локальных таблиц, и посылая сообщение <mydist, ., .> если оценка расстояния изменилась. Мы предположим что уведомление которое узлы получают о падении или подъеме канала (предположение N3) представлено в виде сообщений < fail,. > и <repair, . >. Канал между узлами u1 и u2 смоделирован двумя очередями, Q u1 u2 для сообщений от u1 к u1 и Q u2 u1 для сообщений из u2 в u1. Когда канал отказывает эти очереди удаляются из конфигурации (фактически вызывается потеря всех сообщений в обоих очередях) и узлы на обоих концах канала получают сообщение < fail, . > . Если канал между u1 и u1 отказывает, u1 получает сообщение < fail, u2 > и u2 получает сообщение < fail, u1 > . Когда канал восстанавливается (или добавляется новый канал в сети) две пустые очереди добавляются в конфигурацию и два узлы соединяются через канал получая сообщение < repair, . > . Если канал между u1 и u2 поднялся u1 получает сообщение< repair, u2 > и u2получает сообщение < repair, u1 > .
Обработка сообщения <mydist,v,d> от соседа w:
{ <mydist,v,d> через очередь Qwv}
begin получить <mydist,v,d> от w;
ndisu[w,v] := d ; Recompute (v)
end
Произошел отказ канала uw:
begin получить < fail, w> ; Neighu := Neighu\ {w} ,
forall v Î V do Recompute (v)
end
Произошло восстановление канала uw:
begin получить < repair, w> , Neighu := Neighu È {w} ;
forall v Î V do
begin ndisu[w, v] := N;
послать < mydist, v, Du{[v]> to w
end
end
Алгоритм 4.9 АЛГОРИТМ NETCHANGE (часть 2, для узла и).
Реакция алгоритма на отказы и восстановления выглядит следующим образом. Когда канал между u и w отказывает, w удаляется из Neighu и наоборот. Оценка расстояния перевычисляется для каждого пункта назначения и, конечно, рассылается всем существующим соседям если оно изменилось. Это случай если лучший маршрут был через отказавший канал и нет другого соседа w' с ndisu[w', v]= ndisu[w, v]. Когда канал восстановлен(или добавлен новый канал) то w добавляется в Neighu, но u имеет теперь неоцененное расстояние d(w, v) (и наоборот). Новый сосед w немедленно информирует относительно Du[v] для всех пунктов назначения v (посылая сообщения<mydist,v, Du[v]> ). До тех пор пока u получает подобное сообщения от w, u использует N как оценку для d(w,v), т.е., он устанавливает ndisu[w, v] в N.
P(u, w, V)º
up(u, w) Û w Î Neighu (1)
Ù up(u, w) Ù Qwu содержит сообщение <mydist,v,d> Þ
последнее такое сообщение удовлетворят d = Du[v] (2)
Ù up(u, w) Ù Qwu не содержит сообщение <mydist,v,d> Þ
ndisu[w, v] =Dw [v] (3)
L(u, v) º
u = v Þ (Du[v] = 0 Ù Nbu[v] = local) (4)
Ù (u ¹ v)Ù $w Î Neighu: ndisu[w, v] < N - 1)Þ
( Du[v] = 1 + min ndisu[w, v] = 1 + ndisu[Nbu[v], v]) (5)
w Î Neigh u
Ù (u ¹ v Ù "w Î Neighu: ndisu[w, v]³ N—1) Þ
(Du[v] = N Ù Nbu[v] = udef) (6)
Рисунок 4.10 Инварианты P(u, w, v) и L(u, v).
Инварианты алгоритма Netchange. Мы докажем что утверждения являются инвариантами; утверждения даны на Рисунке 4.10. Утверждение P(u, w, v) констатирует что если u закончил обработку сообщения <mydist, v, .> от w то оценка u расстояния d(w,v) эквивалентна оценке w расстояния d(w, v). Пусть предикат up(u, w) истинен тогда и только тогда когда (двунаправленный) канал между u и w существует и действует. Утверждение L(u, v) констатирует что оценка u расстояния d(u, v) всегда согласована с локальными данными u, и Nbu[v] таким образом означен.