Быстрый поиск

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

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

end

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

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,

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) *)

Страницы: 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, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105