Оптимальность интервальной маршрутизации: специальные топологии. 5 глава

Так как u₁ Î S:

                               d^S(u₂, v) £ d^S (u₂, u₁) + d^S (u₁,v).             (2)

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

                               d^S(u₂, w) + d^S (w, v) < d^S (u₂, v).                  (3)

Применяя (2), и затем (1), и вычитая d^S(u₂, u₁), мы получим

                              d^S(u₁, w) + d^S (w, v) < d^S (u₁, v)                (4)

значит u₁ изменит D_u1 [v] в этом обходе.‰

 

В соответствии с этой леммой, Алгоритм 4.6 может быть модифицирован следующим образом. После получения таблицы D_w, (сообщение < dtab, w,D>) узел u вначале выполняет локальные w -централизованные операции, и затем рассылает таблицы своим сыновьям в T_w. Когда пересылка таблицы закончилась достаточно переслать те ссылки D[v] для которых D_u[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)

                 î    w_uw+d(w,v)       иначе

Два свойства этого равенства делают алгоритмы основанные на этом отличными от алгоритма Toueg.

(1) Локальность данных. Во время оценивания правой стороны равенством (4.1), узлу u необходима только информация доступная локально (именно, w_uw) или в соседях (именно, d(w, v)). Транспортирование данных между удаленными вершинами избегается.

(2) Независимость пункта назначения. Расстояния до v (именно, d(w, v) где w сосед u) только нуждаются в вычислении расстояния от u в v. Таким образом, вычисление всех расстояний до фиксированного пункта назначения v_o может происходить независимо от вычисления расстояния до других узлов, и также, может бать сделано обособленно.

 

В завершение этой части обсуждены два алгоритма основанные на равенстве, а именно алгоритмы Мерлина-Сигалла и Чанди-Мизра. Не смотря на преимущества от локальности данных, сложность соединений этих алгоритмов не лучше алгоритма Toueg. Это из-за независимости пункта назначения введенного равенством(4.1); очевидно, использование результатов для других пунктов назначения (как сделано в алгоритме Toueg) более выгодный прием чем локальность данных.

Если это не ведет к уменьшению сложности соединений, тогда каково значение локальности данных? Уверенность в удаленных данных требует повторных распространений если данные могли измениться из-за топологических изменений сети. Доведение до конца этих распространений (с возможными новыми топологическими изменениями в течение распространения) вызывает нетривиальные проблемы с дорогими решениями (см., на пример, [Gaf87]). Более того, алгоритмы основанные на равенстве 4.1 могут быть более легко адаптированы к топологическим изменениям. Оно служит примером в части 4.3, где подробно разобран такой алгоритм.

 

Алгоритм Мерлина-Сигалла. Алгоритм предложенный Мерлином и Сигаллом [MS79] вычисляет таблицы маршрутизации для каждого пункта назначения абсолютно обособленно; вычисления для различных пунктов назначения не оказывают влияния друг на друга. Для пункта назначения v, алгоритм начинает работу с дерева T_v с корнем в v, и повторно перевычисляет это дерево с тем чтобы оно стало оптимальным деревом стока для v.

Для пункта назначения v, каждый узел u содержит оценку расстояния до v (D_u[v]) и соседа через которого пакет для u пересылается (Nb_u[v]), который также является отцом u в T_v. В период перевычисления каждый узел u посылает свою оценку расстояния, D_u[v], к всем соседям исключая Nb_u[v] (в < mydist, v, D_u[v]> сообщении). Если узел u получает от соседа w сообщение <mydist, v, d > и если d+w_uv < D_u[v], u изменит Nb_u[v] на w и D_u[v] на d + w_uv. Период перевычисления контролируется узлом v и требует обмена двумя сообщениями в W бит на каждый канал.

В [MS79] показано что после i периодов перевычислений все кротчайшие пути в более чем i шагов будут корректно вычислены, так что после N раундов все кротчайшие пути будут вычислены. Кротчайшие пути в каждый пункт назначения вычисляются выполнением алгоритма независимо для каждого пункта назначения.

Теорема 4.11 Алгоритм Мерлина и Сигалла вычисляет таблицы маршрутизации кротчайших путей с обменом 0(N²) сообщениями на канал, 0(N² W) битами на канал, 0(N² |E|) сообщениями всего, и 0(N²|E|W) битами всего.

 

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

Алгоритм Чанди—Мизра. Алгоритм предложенный Чанди и Мизра [CM82] вычисляет все кротчайшие вычисляет до одного пункта назначения используя парадигму диффузивных вычислений (распределенные вычисления которые инициируются одним узлом, и другие узлы присоединяются только после получения сообщения).

Вычисление, для всех узлов, расстояния до узла v_o (и привилегированного исходящего канала), каждый узел u начинает с D_u[v_o] = ¥ и ждет получения сообщений. Узел v_o посылает <mydist, v_o,0> сообщение всем соседям. Когда же узел u получает сообщение < maydist ,v_o,d> от соседа w, где d + w_uw < D_u[v_o], u заносит значение d+w_uv в D_u[v_o] и посылает сообщение < mydist, v_o, D D_u[v_o]> всем соседям; смотри Алгоритм 4.7.

 

var D_u[v_o]: вес    init ¥;

  Nb_u[v_o]: узел init udef;

 

Только для узла v_o:

begin D_u[v_o]:= 0;

           forall w Î Neigh_vo do послать < maydist, v_o, 0> к w

  end

 

Обработка сообщения < maydist, v_o, d> от соседа w узлом u:

   { <mydist, v_o, d > Î M_wv }

   begin получить <mydist, v_o, d > от w;

                if   d + w_uw < D_u[v_o] then

                     begin D_u[v_o]:= d+w_uw;  Nb_u[v_o]:= w;

                              f orall x Î Neigh_u do послать < maydist, v_o, D_u[v_o]> к x

                     end

     end

Алгоритм 4.7 Алгоритм Чанди-Мизра (для узла u).

Не трудно показать что D_u[v_o] всегда верхняя граница для d(u, vo), т.е ., d(u,vq) £ D_u[v_o] инвариант алгоритма; см. упражнение 4.3. Чтобы продемонстрировать чти алгоритм вычисляет расстояния верно, нужно показать что в конечном счете достигнется конфигурация в которой D_u[v_o] £ d(u, v_o) для каждого u. Мы дадим доказательство этого свойства используя предположение допущения слабой справедливости, а именно, что каждое сообщение которое посылается в конечном счете получено в каждом вычислении.

 

Теорема 4.12 В каждом вычислении Алгоритма 4.7 достигнется конфигурация в которой для каждого узла u, D_u[v_o] £ d(u, v_o).

Доказательство. Зафиксируем оптимальное дерево стока T для v_o и обозначим остальные узлы v₁ … v_N-1 таким образом что если v _i, отец узла v_j, тогда i < j. Пусть C вычисление; можно показано индукцией по j что для каждого j £ N— 1  достигнется конфигурация в которой, для каждого i £ j, D_vi[v_o] £ d(v_i, v_o). Заметим что  D_vi[v_o] никогда не увеличивается в алгоритме; таким образом если D_vi[v_o] £ d(v_i, v_o) содержится в некоторой конфигурации то она лучшая конфигурация из всех.

Случай j = 0: d(v_o, v_o) = 0, и D_vo[v_o] = 0 после выполнения инициализационной части узлом v_o,, таким образом D_vo[v_o] £ d(v_o, v_o) содержится после этого выполнения.

Случай j + 1: Допустим что достигнется конфигурация в которой для каждого i £ j, D_vi[v_o] £d(v_i, v_o), и рассмотрим узел v_j+1. Имеется кротчайший путь v_j+1, v_i,..., v_o длины d(v_j+1, v_o) от v_j+1 до v_o, где v_i отец v_j+1 в T, отсюда i £ j. Следовательно, по индукции, достигается конфигурация в которой D_vi[v_o] £ d(v_i, v_o). Всякий раз когда D_vi[v_o] уменьшится, v_i посылает сообщение < mydist, v_o, D_vi[v_o]> своим соседям, отсюда сообщение < mydist, v_o,d> посылается к v_j+1 по крайней мере однажды с d £ d(v_i,v_o).

По предположению, это сообщение принимается в C узлом v_j+1. Алгоритм подразумевает что после получения этого сообщения хранится D_vi[v_o] £ d +  , и выбор i подразумевает что  d +   £ d(v_j+1, v_o). 

 

Полный алгоритм также включает механизм с помощью которого узлы могут определить окончание вычисления.; сравним с замечанием об алгоритме Netchange в начале части 4.3.3. Механизм для определения завершения является вариацией алгоритма Дейкстры-Шолтена обсужденного в 8.2.1.

Алгоритм отличается от алгоритма Мерлина-Сигалла двумя вещами. Во-первых, нет "отца" узла u которому не посылаются сообщения типа < mydist,.,.>. Эта особенность алгоритма Мерлина и Сигалла гарантирует что таблицы всегда не содержат циклов, даже в течение вычислений и при наличии топологических изменений. Во-вторых, обмен сообщениями < mydist,.,. > не координируется в раундах, но существует отслеживание завершения, который влияет на сложность не лучшим образом.

Алгоритм может потребовать экспоненциальное количество сообщений для вычисления путей до одного пункта назначения v_o. Если стоимости всех каналов равны (т.е., рассматривается маршрутизация с минимальным количеством переходов) все кротчайшие пути к v_о вычисляются используя O (N |E|) сообщений (O(W) бит каждое), руководствуясь следующим результатом.

Теорема 4.13 Алгоритм Чанди и Мизра вычисляет таблицы маршрутизации с минимальным количеством шагов с помощью обменов 0(N²) сообщениями (N²W) бит на канал, и 0(N²|E|) сообщений и 0(N² |E| W) бит всего.

 

Преимущество алгоритма Чанди и Мизра над алгоритмом Мерлина и Сигалла в его простоте, его меньшей пространственной сложности, и его меньшей временной сложности.

4.3 Алгоритм Netchange

 

Алгоритм Таджибнаписа Netchange [Taj77] вычисляет таблицы маршрутизации которые удовлетворяют мере "минимальное количество шагов". Алгоритм подобен алгоритму Чанди-Мизра, но содержит дополнительную информацию которая позволяет таблицам только частично перевычисляться после отказа или восстановления канала. Представление алгоритма в этой части придерживается Лампорта [Lam82]. Алгоритм основан на следующих предположениях.

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

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

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

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

Алгоритм может управлять отказами и восстановлениями или добавлениями каналов, но положим что узел уведомляет когда смежный с ним канал отказывает или восстанавливается. Отказ и восстановление узлов не рассматривается: на самом деле отказ узла можно рассматриваться его соседями как отказ соединяющего канала. Алгоритм содержит в каждом узле u таблицу Nb_u [v], дающую для каждого пункт назначения v соседа u через которого u пересылает пакеты для v. Требования алгоритмов следующие:

 

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

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

(a) если v = u то Nb_u[v] = local;

(b) если путь из u в v ¹ u существует то Nb_u[v] = w, где w первый сосед u в кротчайшем пути из u в v,

(c)  если нет пути из u в v тогда Nb_u[v] = udef.

4.3.1 Описание алгоритма

 

Алгоритм Таджибнаписа Netchange дан как алгоритмы 4.8 и 4.9. Шаги алгоритма будут сначала объяснены неформально, и, впоследствии правильность алгоритма будет доказана формально. Ради ясности моделирование топологических изменений упрощено по сравнению с [Lam82], примем, что уведомление об изменении обрабатывается одновременно двумя узлами задействованными изменениями. Это обозначено в Подразделе 4.3.3, как асинхронная обработка.

Выбор соседа через которого пакеты для v будут посылаться основан на оценке расстояния от каждого узла до v. Предпочитаемый сосед всегда сосед с минимальной оценкой расстояния. Узел u содержит оценку d(u, v) в D_u[v] и оценки d(w, v) в ndis_u[w, v] для каждого соседа u. Оценка D_u[v] вычисляется из оценок ndis_u[w, v], и оценки ndis_u[w,v] получены посредством коммуникаций с соседями.

Вычисление оценок D_u[v] происходит следующим образом. Если u = v тогда d(u, v) = 0 таким образом D_u[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), найденным в таблицах ndis_u[w, v]. Так как всего N узлов, путь с минимальным количеством шагов имеет длину не более чем N—1. Узел может подозревать что такой путь не существует если оцененное расстояние равно N или больше; значение N используется для этой цели.

 

var   Neigh_u  : множество узлов; (* Соседи u *)

             D_u: массив 0.. N;   (* D_u[v] - оценки d(u, v) *)

            Nb_u: массив узлов;  (* Nb_u[v]- предпочтительный сосед для v *)

             ndis_u: массив 0.. N;    (* ndis_u[w, v] - оценки d (w. v) *)

 

Инициализация:

  begin forall w Î Neigh_u , v Î V do ndis_u[w, v]:= N,

             forall v Î V do

                        begin D_u[v]:= N;

                                   Nb_u[v]:= udef

                         end;

              D_u[u]:= 0; Nb_u[u]:= local;

               forall w Î Neigh_u do послать < mydist, u, 0> к w

    end

 

процедура Recompute (v):

    begin if v = u

            then begin D_u[v]:= 0; Nb_u[v]:= local end

            else begin (* оценка расстояния до v *)

                      d:= 1 + min{ ndis_u[w, v]: w Î Neigh_u};

                   if d < N then

                           begin D_u[v]:= d;

                                     Nb_u[v]:= w with 1 + ndis_u[w, v] = d

                           end

                   else begin D_u[v]:= N; Nb_u[v]:= udef end

            end;

            if D_u[v] изменилась then

                   forall x Î Neigh_u do послать < mydist, v, D_u[v]> к x

     end

Алгоритм 4.8 Алгоритм Netchange (часть I, для узла u).

 

Алгоритм требует чтобы узел имел оценки расстояний до v своих соседей. Их они получают от этих узлов послав им сообщение <mydist,.,.> следующим образом. Если узел u вычисляет значение d как оценку своего расстояния до v (D_u[v] = d), то эта информация посылается всем соседям в сообщении < mydist, v, d >. На получение сообщения <mydist, v, d> от соседа w, u означивает ndis_u[w, v] значением d. В результате изменения ndis_u[w, v] оценка  u расстояния d(u, v) может измениться и следовательно оценка перевычисляется каждый раз при изменении таблицы ndis_u. Если оценка на самом деле изменилась то, на d' например, происходит соединение с соседями используя сообщение < mydist, v, d'>.

 

Алгоритм реагирует на отказы и восстановления каналов изменением локальных таблиц, и посылая сообщение <mydist,.,.> если оценка расстояния изменилась. Мы предположим что уведомление которое узлы получают о падении или подъеме канала (предположение N3) представлено в виде сообщений < fail,. > и < repair,. >. Канал между узлами u₁ и u₂ смоделирован двумя очередями, Q u₁ u₂  для сообщений от u₁ к u₁ и Q u₂ u₁ для сообщений из u₂ в u₁. Когда канал отказывает эти очереди удаляются из конфигурации (фактически вызывается потеря всех сообщений в обоих очередях) и узлы на обоих концах канала получают сообщение < fail,. >. Если канал между u₁ и u₁ отказывает, u₁ получает сообщение < fail, u₂ > и u₂ получает сообщение < fail, u₁ >. Когда канал восстанавливается (или добавляется новый канал в сети) две пустые очереди добавляются в конфигурацию и два узлы соединяются через канал получая сообщение < repair,. >. Если канал между u₁ и u₂ поднялся u₁ получает сообщение< repair, u₂ > и u₂ получает сообщение < repair, u₁ >.

 

Обработка сообщения < mydist, v,d>  от соседа w:

        { < mydist, v,d> через очередь Q wv }

        begin  получить < mydist, v,d> от w;

                    ndis_u[w,v]:= d; Recompute (v)

          end

 

Произошел отказ канала uw:

        begin получить < fail, w>; Neigh_u:= Neigh_u \ {w},

                   forall v Î V do Recompute (v)

         end

Произошло восстановление канала uw:

       begin получить < repair, w>, Neigh_u:= Neigh_u È {w};

                      forall v Î V do

                              begin ndis_u[w, v]:= N;

                                        послать < mydist, v, D_u{[v]> to w

                              end

         end

Алгоритм 4.9 АЛГОРИТМ NETCHANGE (часть 2, для узла и).

Реакция алгоритма на отказы и восстановления выглядит следующим образом. Когда канал между u и w отказывает, w удаляется из Neigh_u и наоборот. Оценка расстояния перевычисляется для каждого пункта назначения и, конечно, рассылается всем существующим соседям если оно изменилось. Это случай если лучший маршрут был через отказавший канал и нет другого соседа w' с ndis_u[w', v]= ndis_u[w, v]. Когда канал восстановлен(или добавлен новый канал) то w добавляется в Neigh_u, но u имеет теперь неоцененное расстояние d(w, v) (и наоборот). Новый сосед w немедленно информирует относительно D_u[v] для всех пунктов назначения v (посылая сообщения< mydist, v, D_u[v] >). До тех пор пока u получает подобное сообщения от w, u использует N как оценку для d(w,v), т.е., он устанавливает ndis_u[w, v] в N.

P(u, w, V) º

             up(u, w) Û w Î Neigh_u                              (1)

         Ù up(u, w) Ù Q_wu содержит сообщение < mydis t,v,d> Þ

                последнее такое сообщение удовлетворят d = D_u[v] (2)

        Ù up(u, w) Ù Q_wu не содержит сообщение < mydis t,v,d> Þ

               ndis_u[w, v] = D_w [v]                                  (3)

   L(u, v) º

                u = v Þ (D_u[v] = 0 Ù Nb_u[v] = local)        (4)

           Ù (u ¹ v) Ù $ w Î Neigh_u: ndis_u[w, v] < N - 1) Þ

                (D_u[v] = 1 + min ndis_u[w, v] = 1 + ndis_u[Nb_u[v], v]) (5)

                                      ^{w Î Neigh u}

           Ù (u ¹ v Ù " w Î Neigh_u: ndis_u[w, v] ³ N—1) Þ

                      (D_u[v] = N Ù Nb_u[v] = udef)                         (6)

Рисунок 4.10 Инварианты P(u, w, v) и L(u, v).

Инварианты алгоритма Netchange. Мы докажем что утверждения являются инвариантами; утверждения даны на Рисунке 4.10. Утверждение P(u, w, v) констатирует что если u закончил обработку сообщения <mydist, v,.>  от w то оценка u расстояния d(w,v) эквивалентна оценке w расстояния d(w, v). Пусть предикат up(u, w) истинен тогда и только тогда когда (двунаправленный) канал между u и w существует и действует. Утверждение L(u, v) констатирует что оценка u расстояния d(u, v) всегда согласована с локальными данными u, и Nb_u[v] таким образом означен.

Предыдущая12345678910111213141516Следующая

Поделиться:

Воспользуйтесь поиском по сайту: