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

Когда механизм пересылки имеет эту форму, и никакие (дальнейшие) изменения топологии не происходят, корректность таблиц маршрутизации может быть удостоверена, используя следующий результат. Таблицы маршрутизации, как говорят, содержат цикл (для адресата d), если существуют узлы u 1,..., u k такие, что для всех i, u i ¹ d, для всех i < k, table_lookup u(d) = u i+1, и table_lookup u(d) = u j+1.. Таблицы, как говорят, являются свободным от циклов, если они не содержат циклов для любого d.

(* Пакет с адресатом d был получен или сгенерирован в узле u *)

if d=u

     then доставить «местный» пакет

     else послать пакет к table_lookup u (d)

Алгоритм 4.2 Адресат-основанная пересылка (для узла u).

Лемма 4.3 Механизм пересылки доставляет каждый пакет адресату, тогда и только тогда когда таблицы маршрутизации цикл-свободны.

Доказательство. Если таблицы содержат цикл для некоторого адресата d, пакет для d никогда не будет доставлен, если источник - узел в цикле.

Примем, что таблицы цикл-свободны и позволяют пакету с адресатом d (и источник u o) быть посланным через u o, u 1, u 2,... если один встречается дважды в этой последовательности, скажем u i = u j, тогда таблицы содержат цикл, а именно < u i..., u j> противореча предположению, что таблицы являются цикл-свободными. Таким образом, каждый узел входит единожды, что подразумевает, что эта последовательность конечна, заканчивающаяся, скажем, в узле Великобританию u k (k < N). Согласно процедуре пересылки последовательность может заканчиваться только в d, то есть, u k = d, и пакет достиг адресата за не больше чем N — 1 шагов 

В некоторых алгоритмах маршрутизации случается, что таблицы не цикл-свободны в течение их вычисления. Когда такой алгоритм используется, пакет может пересекать цикл в течение вычисления таблиц, но достигает адресата не больше чем N — 1 шагов после завершения вычисления таблицы, если изменения топологии прекращаются. Если изменения топологии не прекращаются, то есть, сеть подчинена бесконечной последовательности изменений топологии, пакеты не обязательно достигают своего адресата, даже если таблицы цикл-свободны во время модификаций;

Ветвящаяся маршрутизация с минимальной задержкой. При маршрутизации через пути с минимальной задержкой требуется, и задержка канала зависит от использования (таким образом, предположение (1) в начале этого раздела не имеет силу), стоимость использования пути не может просто быть оценена как функция этого единственного пути. Кроме того, трафик на канал должен быть принят во внимание. Избегать скопления пакетов (и возникающую в результате этого задержку) на пути, обычно необходимо посылать пакеты, имеющие ту же самую пару исходный-адресат через различные пути; трафик для этой пары "распределяется" в один или большее количество узлов промежуточного звена как изображено в Рисунке 4.3. Методы маршрутизации, которые используют различные пути к одному адресату, называются много-путевыми или ветвящимися методами маршрутизации. Потому что ветвящиеся методы маршрутизация являются, обычно, очень запутанными, они не будет рассматриваться в этой главе

 

Рисунок 4.3 Пример буферизованной маршрутизации.

4.2 Проблема кротчайших путей всех пар

Этот раздел обсуждает алгоритм Toueg [Tou80a] одновременного вычисления таблицы маршрутизации для всех узлов в сети. Алгоритм вычисляет для каждой пары (u, v) узлов длину самый короткий пути от u до v и сохраняет первый канал такого пути в u. Проблема вычисления самого короткого пути между любыми двумя узлами графа известна как проблема кротчайшего пути всех пар. Распределенный алгоритм Toueg для этой проблемы основан на централизованном алгоритме Флойда-Уошалла [CLR90, Раздел 26.4]. Мы обсудим алгоритм Флойда-Уошалла в Подразделе 4.2.1, и впоследствии алгоритм Toueg в Подразделе 4.2.2. Краткое обсуждение некоторых других алгоритмов для проблемы кротчайших путей всех пар следует в Подразделе 4.2.3..                                

4.2.1 Алгоритм Флойда-Уошала

 

Пусть дан взвешенный граф G = (V, E), где вес ребра uv дан w uv. Не обязательно допускать что w uv = w vu, но допустим, что граф не содержит циклов с общим отрицательным весом. Вес пути < u o,..., u k> определяется как  . Дистанция от u до v, обозначенная d(u, v), наименьший вес любого пути от u к v (¥ если нет такого пути). Проблема кротчайших путей всех пар - вычисление d(u, v) для каждых u и v.

Для вычисления всех расстояний, алгоритм Флойда-Уошала использует понятие S -путей; это пути, в которых все промежуточные вершины принадлежат к подмножеству S из V.

Определение 4.4.   Пусть S - подмножество V. Путь < u o..., u k> -S-путь если для любого i, 0 <i < k, u j Î S. S-расстояние от u до v, обозначенное d^S(u. v), наименьший вес любого S-пути от u до v (¥ если такого пути нет).

 

Алгоритм стартует рассмотрением всех Æ-путей, и увеличивая вычисления S -путей для больших подмножеств S, до тех пор пока V -пути будут рассмотрены. Могут быть сделаны следующие наблюдения.

Утверждение 4.5 Для всех u и S, d^S(u, u) = 0. Более того, S-пути удовлетворяют следующим правилам для u ¹ v.

(1) Существует Æ -путь от u к v тогда и только тогда когда uv Î E.

(2) Если uv Î E тогда d^S(u, v) = w_uv   иначе d^S(u, v) = ¥.

(3) Если S'=S È {w} тогда простой S'-путь от и к v - S-путь от u к v или S-путь от u к w соединенные S-путем от w к v.

(4) Если S' = S È {w} тогда d^S’ (u, v)=min(d^S (u, v), d^S (u, w)+ d^S (w, v)).

(5) Путь от u до v существует тогда и только тогда когда V-путь от u к v существует

(6) d(u, v)= d^V (u, v),

Доказательство. Для всех u и S d^S (u, u) £.0 по причине того, что пустой путь (состоящий из 0 ребер) это S -путь от u к u с весом 0. Нет путей, имеющих меньший вес, потому что G не содержит циклов отрицательного веса, таким образом, d^S (u, u) = 0.

Для (1): Æ -путь не содержит промежуточных узлов, так Æ - путь от u к v

состоит только из канала uv.

Для (2): следует непосредственно из (1).

Для (3): простой S ’-путь от u к v содержит узел w единожды, или 0 раз как промежуточный. Если он не содержит w как промежуточную вершину он S-путь, иначе он - конкатенация двух S-путей, один к w и один из w.

Для (4): Это можно доказать применив Лемму 4.1. Получим что (если S’-путь от u в v существует) это простой S' -путь длиной d^S’(u, v) от u к v, такой, что d^S’(u, v) = min(d^S (u, v), d^S (u, w) + d^S (w, v)) по (3).

Для (5): каждый S-путь - путь, и обратно.

Для (6): каждый S-путь - путь, и обратно, следовательно, оптимальный V-путь также оптимальный путь.

_____________________________________________________________________

begin (* Инициализация S = Æ и D = Æ-дистанция *)

  S:=0;

forall u,v do

if u = v then D[u, v]:= 0

                      else

if uv Î E then D[u, v]:= w _uv

                                                          else D[u. v]:= ¥;

(* Расширим S «центральными точками» *)

while S ¹ V do

           (* Цикл инвариантен: " u, v: D[u, v] = d^S (u, v) *)

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

                     (* Выполнить глобальную w -центровку *)

forall u Î V do

                            (* Выполнить локальную w -центровку u *)

forall v Î V do

                                     D[u. v]:= min (D[u, v], D[u, w] + D[w, v]);

                                    S:=S È {w}

           end (*" u, v: D[u, v] = d^S (u, v)*)

  end

Алгоритм 4.4 Алгоритм Флойда-Уошалла.

 

Используя Утверждение 4.5 не сложно разработать алгоритм "динамического программирования" для решения проблемы кротчайших путей всех пар; смотри см. Алгоритм 4.4. Алгоритм вначале считает 0-пути, и, увеличивая, вычисляет S-пути для больших множеств S (увеличивая S "центральными" кругами), до тех пор, пока все пути не будут обсуждены.

Теорема 4.6 Алгоритм 4.4 вычисляет расстояние между всеми парами узлов за Q(N³) шагов.

Доказательство. Алгоритм начинает с D[u, v] = 0,  если u = v, D[u, v] = w_uv, если uv Î E и D[u, v] = ¥ в другом случае, и S = 0. Следуя из Утверждения 4.5, частей (1) и (2), " u, v имеет силу  D[u, v] = d^S (u, v). В центральной окружности с центральной вершиной w множество S расширено узлом w, и означивание D[u, v] гарантирует (по частям (3) и (4) утверждения) что утверждение " u, v: D[u, v] = d^S(u, v) сохранено как инвариант цикла. Программа заканчивает работу, когда S = V, т.е., (по частям (5) и (6) утверждения и инварианту цикла) S -расстояние эквивалентно расстоянию.

Главный цикл выполняется N раз, и содержит N² операций (которые могут быть выполнены параллельно или последовательно), откуда и следует временная граница данная теоремой.ˆ

_____________________________________________________________________                                                   

var S_u    : множество вершин;

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

  Nb_u: массив вершин;

begin S_u:= Æ;

forall v Î V do

       if v = u

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

       else if v Î Neigh_u

             then begin D_u[v]:= w_uv; Nb_u[v]:= v end

       else begin Du[v]:= ¥; Nb_u[v]:= udef end;

while S_u ¹ V do

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

                (* Все вершины должны побывать вершиной w *)

                 if u == w

                        then "распространить таблицу D_w"

                         else "принять таблицу D_w"

                  forall v Î V do

                        if D_u[w] + D_w[v] < D_u[v] then

                             begin D_u[v]:= D_u[w] + D_w[v];

                                        Nb_u[v]:= Nb[w]

                             end;

                             Su:= Su U {w}

                  end

     end;

Алгоритм 4.5 Простой алгоритм (Для узла u).

4.2.2 Алгоритм кротчайшего пути.(Toueg)

 

Распределенный алгоритм вычисления таблиц маршрутизации бал дан Toueg [TouSOa], основанный на алгоритме Флойда-Уошалла описанном в предыдущей части. Можно проверить что алгоритм Флойда-Уошалла подходит для этих целей, т.е., что его ограничения реалистичны для распределенных систем. Наиболее важное ограничение алгоритма что граф не содержит циклов отрицательного веса. Это ограничение действительно реально для распределенных систем, где обычно каждый отдельный канал означен положительной оценкой. Даже можно дать более строгое ограничение; смотри A1 ниже. В этой части даны следующие ограничения.

 

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

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

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

 

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

 

 

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

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

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

(1) для всех u:D_u[w] = d^S(u, w) и

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

Тогда направленный граф T_w = (V_w, E_w), где (u Î V_w Û D_u[w]< ¥) и (ux Î E_w Û (v ¹w Ù Nb_u[w]=x)) - дерево с дугами направленными к w.

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

Для каждого узла u ¹ w в V_w существует единственное ребро в E_w, такое что число узлов в T_w превышает количество ребер на единицу и достаточно показать что T_w не содержит циклов. Так ux Î E_w подразумевает что d^S(u, w) =w_ux+ d^S(x, w), существование цикла < u_o, u₁,..., u_k > в T_w подразумевает что

                   d^S (u_o, w) = w_{uo u1} + w_{u1 u2} + … + w_{uk-1 uo}u+ d^S(u_o, w),

  т.е.,    0 = w_{uo u1} + w_{u1 u2} + … + w_{uk-1 uo}u

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

 

Алгоритм Флойда-Уошала теперь может быть просто преобразован в Алгоритм 4.5. Каждый узел инициализирует свои собственные переменные и исполняет N итераций основного цикла. Этот алгоритм не является окончательным решением, и он не дан полностью, потому что мы не описали, как может бать произведено (эффективно) распространение таблиц центрального узла. Пока это можно использовать как гарантированное, поскольку операция "распространить таблицу D_w" выполняется узлом w, а операция "принять таблицу D_w" выполняется другими узлами, и каждый узел имеет доступ к таблице D_w.

Некоторое внимание должно быть уделено операции "выбрать w из V \ S", чтобы узлы выбирали центры в однообразном порядке. Так как все узлы знают V заранее, мы можем запросто предположить, что узлы выбираются в некотором предписанном порядке (на пример, алфавитный порядок имен узлов).

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

 

 

Теорема 4.8 Алгоритм 4.5 завершит свою работу в каждом узле после N итераций основного цикла. Когда алгоритм завершит свою работу в узле u D_u[v] = d(u, v), и если путь из u в v существует то Nb_u[v] первый канал кротчайшего пути из u в v, иначе Nb_u[v] = udef.

Доказательство. Завершение и корректность D_u[v] по завершении работы следует из корректности алгоритма Флойда-Уошала (теорема 4.6). Утверждение о значении Nb_u[v] справедливо потому что Nb_u[v] перевычисляется каждый раз когда означивается D_u[v]. ‰

 

 Усовершенствованный алгоритм. Чтобы сделать распространение в Алгоритме 4.5 эффективным, Toueg заметил, что узел u для каждого D_u[w] = ¥ на старте w -централизованного обхода не меняет свои таблицы в течение всего w -централизованного обхода. Если D_u[w] = ¥, то D_u[w] + D_w[v] < D_u[v] не выполняется для каждого узда v. Следовательно, только узлы, принадлежащие T_w (в начале w -централизованного обхода) нуждаются в получении таблиц w, и операция распространения может стать более эффективной рассылая D_w только через каналы, принадлежащие дереву T_w. Таким образом, w рассылает D_w своим сыновьям в T_w и каждый узел в T_w который принимает таблицу (от своего отца в T_w) пересылает её к своим сыновьям в T_w.

____________________________________________________________________

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

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

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

Begin

Su:= Æ;

f orall v Î V do

        if v = u

             then begin D_u[v]:= O; Nb_u[v]:= udef end

        else if v Î Neigh_u

             then begin D_u[v]:= w_uv; Nb_u[v]:= v end

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

  while S_u ¹ V do

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

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

                  f orall x Î Neigh_u do

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

                                              else send < nys, w > to x;

                       num_rec_u:= O; (* u должен получить | Neigh_u | сообщений *)

                      while num_rec_u < | Neigh_u| do

                                begin получить < ys, w > или < nys, w > сообщение;

                                           num_rec_u:= num_rec_u + 1

                                end;

                       if D_u[w] < ¥  then (* участвует в центр. обходе*)

                                begin if u ¹ w

                                                     then получить <dtab ,w,D> от Nb_u[w];

                                          f orall x Î Neigh_u do

                                                   if < ys, w > было послано от x

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

                                         f orall v Î V do (* локальный w -центр *)

                                                    if D_u[w] + D[v] < D_u[v] then

                                                             begin D_u[v]:= D_u[w] + D[v]:

                                                                       Nb_u[v]:= Nb_u[w]

                                                             end

                                 end;

                        S_u:= S_u È {w}

          end

end

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

_____________________________________________________________________

 

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

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

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

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

 

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

 

Теорема 4.9 Алгоритм 4.6 вычисляет для каждых u и v дистанцию от u к v, и, если эта дистанция конечная, первый канал. Алгоритм обменивается 0(N) сообщениями на канал,, 0(N*|E|) сообщений всего, O(N²W) бит на канал, O(N ³W) бит всего, и требуется 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) бит, что и является границей для числа бит на канал. Не более N² < dtab, w,D> сообщений и 2N - |E| (< ys ,w> и <nys ,w>) сообщений обмена, и того всего O (N² - NW +2N-|E|-W) = O (N³W) бит. Таблицы D_u и Nb_u хранящиеся в узле u требуют 0(NW) бит.‰

                                                           

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

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

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

Доказательство. Так как u₂ потомок u₁ в T_w :

                               d^S(u₂, w) = d^S (u₂, u₁) + d^S (u₁, w).         (1)

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

Поделиться:

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