Предыдущая страница реферата | 19  20  21  22  23  24  25  26  27  28  29 | Следующая страница реферата

Определение 4.4. Пусть S - подмножество V. Путь < uo ..., uk> -S-путь если для любого i, 0 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:

{ через очередь Qwv} begin получить от 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 (посылая сообщения ). До тех пор пока 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 содержит сообщение ( последнее такое сообщение удовлетворят d = Du[v]
(2)

( up(u, w) ( Qwu не содержит сообщение ( 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)

ХPфэЭ0х~йхых‹у9хс' |Др· Pп?єн‰юм?уък5з?йъЫcкЦ?мыХЁнeЪZмИвўй_оРисунок
4.10 Инварианты P(u, w, v) и L(u, v).

Инварианты алгоритма Netchange. Мы докажем что утверждения являются инвариантами; утверждения даны на Рисунке 4.10. Утверждение P(u, w, v) констатирует что если u закончил обработку сообщения от w то оценка u расстояния d(w,v) эквивалентна оценке w расстояния d(w, v).
Пусть предикат up(u, w) истинен тогда и только тогда когда
(двунаправленный) канал между u и w существует и действует. Утверждение
L(u, v) констатирует что оценка u расстояния d(u, v) всегда согласована с локальными данными u, и Nbu[v] таким образом означен.
Выполнение алгоритма заканчивается когда нет больше сообщений в любом канале. Эти конфигурации не терминальны для всей системы так как вычисления в системе могут продолжится позже, начавшись отказом или восстановлением канала (на которые алгоритм должен среагировать). Мы пошлем сообщение конфигурационной стабильности, и определим предикат stable как stable = (u, w : up(u, w) ( Qwu не содержит сообщений
.

Это предполагает что переменные Neighu корректно отражают существующие рабочие коммуникационные каналы, т.е., что (1) существует изначально. Для доказательства инвариантности утверждений мы должны рассмотреть три типа переходов.
(1) Получение сообщения . Первое выполнение результирующего кодового фрагмента, как принято, выполняется автоматически и рассматривается отдельным переходом. Обратите внимание что в данном переходе принимается сообщение и возможно множество сообщений отправляется
(2) Отказ канала и обработка сообщения < fail. . > узлами на обоих концах канала.
(3) Восстановление канала и обработка сообщения двумя соединенными узлами.

Лемма 4.14 Для всех uo, wo, и vo, P(uo, wo, vo) –– инвариант.

Доказательство. Изначально, т.e., после выполнения инициализационной процедуры каждым узлом, (1) содержится предположением. Если изначально мы имеем (up(uo, wo), (2) и (3) тривиально содержатся. Если изначально мы имеем up(uo, wo), тогда ndisuo[wo, vo] = N. Если wo = vo то Dwo[wo] = 0 но сообщение < mydist, vo, 0> в Qw0u0, таким образом (2) и (3) истинны. Если wo ( vo то Dw0[vo]=N и нет сообщений в очереди, что также говорит что (2) и (3) содержаться. Мы рассмотрим три типа констатированных переходов упомянутых выше.

Тип (1). Предположим что u получает сообщение от w.
Следовательно нет топологических изменений и нет изменений в множестве
Neigh , следовательно (1) остается истинно. Если v(vo то это сообщение не меняет ничего в P(uo, wo, vo). Если v = vo, u =uo, и w=wo значение ndisu,[wo, vo] может изменится. Однако, если сообщение < mydist, vo, .> остается в канале значение этого сообщения продолжает удовлетворять (2), так как (2) в сохранности то и (3) также потому что посылка ложна. Если полученное сообщение было последним этого типа в канале то d = Dw0[vo] по
(2), которое подразумевает что заключение (3) становится истинным и (3) в сохранности. Посылка (2) становится ложной, таким образом (2) в сохранности. Если v = vo, u = wo (и uo сосед u) заключение (2) или (3) может быть ложно если значение Dw0[vo] изменилось в следствие выполнения
Recompute(v) в wo. В этом случае, однако, сообщение < mydist, vo, . > с новым значением посылается к uo, которое подразумевает что посылка (3) нарушена, и заключение (2) становится истинным, таким образом (2) и (3) сохранены. Это происходит и в случае когда сообщение < mydist, vo, . > добавляется в Qw0u0, и это всегда удовлетворяет d = Dw0[vo]. Если v = vo и u(uo, wo ничего не изменяет в P(uo, wo, vo).
Тип (2). Предположим что канал uw отказал. Если u = uo и w = wo этот отказ нарушил посылку (2) и (3) таким образом эти правила сохранены. (1) в безопасности потому что wo удалился из Neighu0 и обратно. Нечто произойдет если u = wo и w = uo. Если u = wo но w( uo заключение (2) или (3) может быть нарушено так как значение Dw0 [vo] изменилось. В этом случае пересылка сообщения < mydist, vo, . > узлом wo опять нарушит посылку (3) и сделает заключение (2) истинным, следовательно (2) и (3) в безопасности. Во всех других случаях нет изменений в P(uo, wo, vo).
Тип (3). Предположим добавление канала uw. Если u = uo и w = wo то up(vo,wo) истинно, но добавлением wo в Neighu0 (и обратно) это защищает(1).
Посылка < mydist, vo, Dw0 [vo]> узлом wo делает заключение (2) истинным и посылку (3) ложной, таким образом P(uo, wo, vo) обезопасен. Во всех других случаях нет изменений в P(uo, wo, vo).
(

Лемма 4.15 Для каждого uq и vo, L(uo, vo) –инвариант.

Доказательство. Изначально Du0[uo] = 0 и Nbu[uo] = local. Для vo (uo , изначально ndisu[w, vo] = N для всех w ( Neighu, и Du0[vo] = N и Nbu0[vo] = udef.
Тип (1). Положим что u получил сообщение < mydist, v,d> от w. Если u( uo или v( vo нет переменных упомянутых изменениях L(uo, vo) . Если u = uo и v
= vo значение ndisu[w, vo] меняется, но Du0 [vo] и Nbu0[vo] перевычисляется точно так как удовлетворяется L(vo, vo).
Тип (2). Положим что канал uw отказал. Если u = uo или w = uo то Neighu0 изменился, но опять Du0[vo] и Nbu0[vo] перевычисляются точно так как удовлетворяется L(uo, vo).
Тип (3). Положим что добавлен канал uw . Если u = uo то изменилсяNeighu0 добавлением w, но так как u устанавливает ndisu0[w, vo] в N это сохраняет
L(uo, vo).
4.3.2 Корректность алгоритма Netchange

Должны быть доказаны два требования корректности.

Теорема 4.16 Когда достигнута стабильная конфигурация, таблицы Nbu[v] удовлетворяют :
(1) если u = v то Nbu[v] = local;
(2) если путь от u до v( u существует то Nbu[v] = w, где w первый сосед u на кратчайшем пути от u до v;
(3) если нет путь от u до v не существует то Nbu[v] = udef.

Доказательство. Когда алгоритм прекращает работу, предикат stable добавляется к P(u,w,v) для всех u, v, и w, и это подразумевает что для всех u, v, и w up(u, w) ( ndisu[w, v] = Dw[v].

(4.2)

Применив также L(u, v) для всех u и v мы получим

(0 если u ( v
Du [v] = ( 1+ min Dw[v] если u( v ((w ( Neighu : Dw[v] < N -1

(N w (Neigh u если u(v ((w ( Neighu :
Dw[v]( N -1

(4.3)

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.





Предыдущая страница реферата | 19  20  21  22  23  24  25  26  27  28  29 | Следующая страница реферата