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 Î Neighu do послать < 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
else begin Du[v] := N ; Nbu[v] := udef end
end;
if Du[v] изменилась then
forall x Î Neighu do послать < mydist, v, Du[v]> к x
Алгоритм 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)
Произошел отказ канала uw:
begin получить < fail, w> ; Neighu := Neighu \ {w} ,
forall v Î V do Recompute (v)
Произошло восстановление канала uw:
begin получить < repair, w> , Neighu := Neighu È {w} ;
begin ndisu[w, v] := N;
послать < mydist, v, Du{[v]> to w
Алгоритм 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)
Страницы: 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
