Распределенные алгоритмы

что

dS(uo, w) = wuo u1 + wu1 u2 + … + wuk-1 uou+ dS(uo,

w),

т.е., 0 = wuo u1 + wu1 u2 + … + wuk-1 uou

что противоречит предположению, что каждый цикл имеет положительный вес.

(

Алгоритм Флойда-Уошала теперь может быть просто преобразован в Алгоритм

4.5. Каждый узел инициализирует свои собственные переменные и исполняет N

итераций основного цикла. Этот алгоритм не является окончательным решением,

и он не дан полностью, потому что мы не описали, как может бать произведено

(эффективно) распространение таблиц центрального узла. Пока это можно

использовать как гарантированное, поскольку операция "распространить

таблицу Dw" выполняется узлом w, а операция "принять таблицу Dw"

выполняется другими узлами, и каждый узел имеет доступ к таблице Dw.

Некоторое внимание должно быть уделено операции "выбрать w из V \ S", чтобы

узлы выбирали центры в однообразном порядке. Так как все узлы знают V

заранее, мы можем запросто предположить, что узлы выбираются в некотором

предписанном порядке (на пример, алфавитный порядок имен узлов).

Корректность простого алгоритма доказана в следующей теореме.

Теорема 4.8 Алгоритм 4.5 завершит свою работу в каждом узле после N

итераций основного цикла. Когда алгоритм завершит свою работу в узле u

Du[v] = d(u, v), и если путь из u в v существует то Nbu[v] первый канал

кротчайшего пути из u в v, иначе Nbu[v] = udef.

Доказательство. Завершение и корректность Du[v] по завершении работы

следует из корректности алгоритма Флойда-Уошала (теорема 4.6). Утверждение

о значении Nbu[v] справедливо потому что Nbu[v] перевычисляется каждый раз

когда означивается Du[v] .(

Усовершенствованный алгоритм. Чтобы сделать распространение в Алгоритме

4.5 эффективным, Toueg заметил, что узел u для каждого Du[w] = ( на старте

w-централизованного обхода не меняет свои таблицы в течение всего w-

централизованного обхода. Если Du[w] = ( , то Du[w] + Dw[v] < Du[v] не

выполняется для каждого узда v. Следовательно, только узлы, принадлежащие

Tw (в начале w-централизованного обхода) нуждаются в получении таблиц w, и

операция распространения может стать более эффективной рассылая Dw только

через каналы, принадлежащие дереву Tw. Таким образом, w рассылает Dw своим

сыновьям в Tw и каждый узел в Tw который принимает таблицу (от своего отца

в Tw) пересылает её к своим сыновьям в Tw.

____________________________________________________________________

var Su : множество узлов ;

Du : массив весов;

Nbu : массив узлов ;

begin

Su := ( ;

forall v ( V do

if v = u

then begin Du[v] := O ; Nbu[v] := udef end

else if v ( Neighu

then begin Du[v] := wuv ; Nbu[v] := v end

else begin Du[v] := ( ; Nbu[v] := udef end ;

while Su ( V do

begin выбрать w из V \ Su ;

(* Построение дерева Tw *)

forall x ( Neighu do

if Nbu[w] = x then send < ys, w> to x

else send < nys, w > to

x ;

num_recu := O ; (* u должен получить |Neighu|

сообщений *)

while num_recu < |Neighu| do

begin получить < ys, w > или < nys, w

> сообщение ;

num_recu := num_recu + 1

end;

if Du[w] < ( then (* участвует в центр.

обходе*)

begin if u( w

then получить

от Nbu[w] ;

forall x ( Neighu do

if < ys, w > было

послано от x

then

послать < dtab, w, D>) к x; ;

forall v ( V do (* локальный

w-центр *)

if Du[w] + D[v] <

Du[v] then

begin

Du[v] := Du[w] + D[v] :

Nbu[v] := Nbu[w]

end

end;

Su := Su ( {w}

end

end

вD7&0?8biD;nGАаC[2]Ъ;,v4-Н-#Г!?$К#¬!”-9{[pic] , и выбор i подразумевает

что d + [pic] ( d(vj+1, vo).(

Полный алгоритм также включает механизм с помощью которого узлы могут

определить окончание вычисления.; сравним с замечанием об алгоритме

Netchange в начале части 4.3.3. Механизм для определения завершения

является вариацией алгоритма Дейкстры-Шолтена обсужденного в 8.2.1.

Алгоритм отличается от алгоритма Мерлина-Сигалла двумя вещами. Во-первых,

нет "отца" узла u которому не посылаются сообщения типа . Эта

особенность алгоритма Мерлина и Сигалла гарантирует что таблицы всегда не

содержат циклов, даже в течение вычислений и при наличии топологических

изменений. Во-вторых, обмен сообщениями < 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]. Алгоритм основан на следующих предположениях.

Nl. Узлы знают размер сети (N).

N2. Каналы удовлетворяют дисциплине FIFO.

N3. Узлы уведомляют об отказах и восстановлениях смежных к ним каналов.

N4. Цена пути – количество каналов в пути.

Алгоритм может управлять отказами и восстановлениями или добавлениями

каналов, но положим что узел уведомляет когда смежный с ним канал

отказывает или восстанавливается. Отказ и восстановление узлов не

рассматривается: на самом деле отказ узла можно рассматриваться его

соседями как отказ соединяющего канала. Алгоритм содержит в каждом узле u

таблицу Nbu [v], дающую для каждого пункт назначения v соседа u через

которого u пересылает пакеты для v. Требования алгоритмов следующие:

Rl. Если топология сети остается постоянной после конечного числа

топологических изменений , тогда алгоритм завершается после конечного числа

шагов.

R2. Когда алгоритм завершает свою работу таблицы Nbu[v] удовлетворяют

если v = u то Nbu[v] = local ;

если путь из u в v ( u существует то Nbu[v] = w, где w первый сосед u в

кротчайшем пути из u в v,

если нет пути из 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

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 своих соседей. Их

они получают от этих узлов послав им сообщение следующим

образом. Если узел u вычисляет значение d как оценку своего расстояния до

v (Du[v] = d), то эта информация посылается всем соседям в сообщении <

mydist ,v,d>. На получение сообщения от соседа w, u

означивает ndisu[w, v] значением d. В результате изменения ndisu[w, v]

оценка u расстояния d(u, v) может измениться и следовательно оценка

перевычисляется каждый раз при изменении таблицы ndisu . Если оценка на

самом деле изменилась то, на d' например, происходит соединение с соседями

используя сообщение .

Алгоритм реагирует на отказы и восстановления каналов изменением локальных

таблиц, и посылая сообщение если оценка расстояния

изменилась. Мы предположим что уведомление которое узлы получают о

падении или подъеме канала (предположение N3) представлено в виде

сообщений < fail,. > и . Канал между узлами 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 > .

Обработка сообщения от соседа w:

Страницы: 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