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

A1. Каждый цикл в сети имеет положительный вес.

A2. Каждый узел в сети знает обо всех узлах (множество V).

A3. Каждый узел знает какой из  узлов его сосед  (хранится в  Neighu для узла u) и веса своих выходящих каналов.

Корректность алгоритма  Toueg (Алгоритма4.6) будет более просто понять если мы сперва обсудим предварительную версию  алгоритма , "простой алгоритм" (Алгоритм 4.5).

Простой алгоритм. Для достижения распределенного алгоритма переменные и операции алгоритма Флойда-Уошала распределены по узлам сети. D[u, v] - переменная принадлежащая узлу  u; по соглашению, это будет выражено описанием  Du[v] .Операция, означивающая  Du[v], должна быть выполнена узлам u, и когда необходимо значение переменной узла w, это значение должно быть послано u. В алгоритме Флойда-Уошала все узлы должны использовать информацию из «центрального» узла (w в теле цикла), который посылает эту информацию к всем узлам одновременно операцией "распространения". В заключение, алгоритм будет расширен операцией  для поддержки не только длины кратчайших S-путей (как в переменной Du[v]), но также первый канал такого пути (в переменной Nbu[v]).

Утверждение что циклы сети имеет положительный вес может использоваться чтобы показать  что не существует циклов в таблицах маршрутизации.

Лемма 4.7 Пусть даны  S и w и выполняется:

(1) для всех  u :Du[w] = dS(u, w) и

(2) если dS(u, w) < ¥  и  u ¹ w, то Nbu[w]- первый канал кратчайшего  S-пути к w.

Тогда  направленный граф Tw = (Vw, Ew), где (u Î Vw Û Du[w]<¥ ) и (ux ÎEw Û (v¹wÙNbu[w]=x)) -  дерево с дугами направленными к  w.

Доказательство. Во-первых, заметим, что если Du[w] < ¥  для u ¹ w, то Nbu[w] ¹ udef и .  Таким образом для каждого узла u Î Vw, u ¹ w существует узел x для которого Nbu[w] = x, и  x Î Vw.

Для каждого узла u¹ w в Vw существует единственное ребро в Ew, такое что число узлов в Tw превышает количество ребер на единицу и  достаточно показать что  Tw не содержит циклов. Так  ux ÎEw подразумевает что dS(u, w) =wux+ dS(x, w), существование цикла <uo, u1, .. ., uk> в Tw подразумевает что

                        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  получить <dtab,w,D> от 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

Алгоритм 4.6 Алгоритм Тoueg (для узла u).

_____________________________________________________________________

В начале w-централизованного раунда узел u с Du[w] < ¥  знает кто его отец (в Tw) , но не знает кто его сыновья. Поэтому каждый узел v должен послать сообщение к каждому своему соседу u, спрашивая  u является ли v сыном  u в Tw. Полный  алгоритм дан как Алгоритм 4.6. Узел может участвовать в пересылке таблицы w когда известно что  его соседи являются его сыновьями в Tw. Алгоритм использует три типа сообщений:

(1) <ys,w> сообщение  <ys обозначение для "your son">  u посылает к x; в начале  w-централизованного обхода если x отец u в Tw.

(2) <nys, w> сообщение <nys обозначение для "not your son"> u посылает x в начале w-централизованного обхода если x не отец u в Tw

(3) <dtab, w, D> сообщение посылается в течение w-централизованного обхода через каждое ребро Tw чтобы переслать значение Dw  к каждому узлу который должен использовать это значение.

Полагая сто вес (ребра или пути) вместе с именем узла можно представить W битами, сложность алгоритма показана следующей теоремой.

Теорема 4.9 Алгоритм 4.6 вычисляет для каждых  u и v дистанцию от u к v, и, если эта дистанция конечная, первый канал. Алгоритм обменивается 0(N) сообщениями на канал,, 0(N*|E|) сообщений всего, O(N2W) бит на канал, O(N 3W) бит всего, и требуется  0(NW) бит хранения на узел.

Доказательство. Алгоритм 4.6 выведен от Алгоритма 4.5, который корректен.

Каждый канал переносит два ( < ys, w> или < nys, w> ) сообщений (одно в каждом направлении) и не более одного <dtab, w, D > сообщения в w-централизованном обходе, который включает не более 3N сообщений на канал.  < ys, w > или < nys, w > сообщение содержит O(W) бит и <dtab, w, D > сообщение содержит O(NW) бит, что и является границей для числа бит на канал. Не более N2 < dtab, w,D> сообщений и 2N - |E| (<ys,w> и <nys,w> ) сообщений обмена, и того всего O(N2 - NW +2N-|E|-W) = O(N3W) бит. Таблицы Du и Nbu хранящиеся в узле u требуют 0(NW) бит.‰

                                                            

В течение w-центализованного обхода узлу разрешено принимать и обрабатывать сообщения только данного обхода, т.е., те которые переносят параметр w. Если каналы удовлетворяют дисциплине FIFO тогда сообщения <ys,w> и <nys, w> прибывают первыми, по одному через каждый канал, и затем сообщение < dtab, w, D > от Nbu[ w] (если узел в Vw). Таким образом возможно, аккуратно программируя, опустить параметр w во всех сообщениях если каналы удовлетворяют дисциплине FIFO. Если каналы не удовлетворяют дисциплине FIFO возможно что сообщение с параметром w' придет пока узел ожидает сообщения для обхода w, тогда как w' становится центром после  w.  В этом случае параметр используется  чтобы различить сообщения  для каждого централизованного обхода, и локальная буферизация ( в канале и узле) должна  использоваться для отсрочки выполнения w'-сообщения.

Toueg дал дальнейшую оптимизацию алгоритма, полагаясь на следующий результат. (Узел u2 потомок  u1 если u2 принадлежит поддереву  u1)

Лемма 4.10 Пусть u1¹ w, и пусть u2  потомок   u1 в Tw, в начале w-централизованного обхода, если u2  изменит своё расстояние до  v во время w-централизованного обхода, тогда и  u1 изменит своё расстояние до v в этом же обходе.

Доказательство. Так как  u2 потомок u1 в Tw :

                                    dS(u2, w) = dS (u2, u1) + dS (u1, w).             (1)

  Так как  u1 Π S:

                                    dS(u2, v) £ dS (u2, u1) + dS (u1,v).                 (2)

   Узел  u2 изменит Du2 [v] в данном обходе тогда и только тогда когда

                                    dS(u2, w) + dS (w, v) < dS (u2, v).                  (3)

   Применяя (2), и затем (1), и вычитая dS(u2, u1), мы получим

                                   dS(u1, w) + dS (w, v) < dS (u1, v)                    (4)

значит  u1 изменит Du1 [v] в этом обходе.‰

В соответствии с этой леммой, Алгоритм 4.6 может быть модифицирован следующим образом. После получения таблицы Dw, (сообщение <dtab, w,D>) узел u вначале выполняет локальные w-централизованные операции, и затем рассылает таблицы своим сыновьям в Tw. Когда пересылка таблицы закончилась достаточно переслать те ссылки  D[v] для которых Du[v] изменилась в течение локальной w-централизованной операции. С этой модификацией таблицы маршрутизации не содержат циклов не только между централизованными обходами (как сказано в Лемме 4.7), но также в течение централизованных обходов.

 

4.2.3 Обсуждение и Дополнительные Алгоритмы

Представление алгоритм Toueg  предоставило пример как распределенный алгоритм может быть получен непосредственным образом из последовательного алгоритма. Переменные последовательного алгоритма распределены по процессам, и любое означивание переменной x (в последовательном алгоритме) выполняется процессом владеющим x. Всякий раз когда  ознaчивающее выражение содержит ссылки на переменные  из других процессов, связь между процессами потребуется для  передачи значения и синхронизации процессов. Специфические свойства последовательного алгоритма могут быть использованы для минимизации числа соединений.

Алгоритм Toueg прост для понимания, имеет низкую сложность, и маршрутизирует через оптимальные пути; его главный недостаток в его  плохая живучесть. Когда топология сети изменилась все вычисления должны произвестись заново.

Во-первых, как ранее говорилось, однообразный выбор всеми узлами следующего центрального узла (w) требует чтобы множество участвующих узлов было известно заранее. Так как это в основном не известно априори, исполнение расширенного распределенного алгоритма вычисления этого множества (на пример  алгоритм Финна, Алгоритм 6.9) должно предшествовать исполнению алгоритма Toueg.

Во-вторых, алгоритм Toueg основан на повторяющимися применениями уникальности треугольника d(u, v) £ d(u, w) + d(w, v). Оценивание правой стороны ( u) требует информацию о d(w, v), и эта информация  в часто удалена, т.е., не доступна ни в u ни в любой из его соседей. Зависимость от удаленных данных делает необходимым транспортирование информации к удаленным узлам, которые могут быть исследованы в алгоритме Toueg (часть распространения).

Как альтернатива, определенное ниже равенство для d(u, v) может использоваться в алгоритмах для проблем кротчайших путей:

                      ì        0                             если u=v

    d(u,v)=      í                                                                            (4.1)

                      î         wuw+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