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

Тип (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)

которого достаточно для доказательства что Du[v] = d(u, v) если u и v в некотором связном компоненте сети, и Du[v] = N  если u и v в различных связных компонентах.

Во-первых покажем индукцией по d{u, v) что если u и v в некотором связном компоненте то Du[v]£ d(u, v).

Случай d(u, v) = 0: подразумевает  u = v и следовательно Du[v] = 0.

Случай d(u, v) = k +1: это подразумевает что существует узел w Î Neighu с d(w, v) = k.      По индукции Du[v] £ k,  которое по (4.3) подразумевает что Du[v] £ k + 1.

Теперь покажем индуктивно по Du[v] что если Du[v] < N то существует путь между u и v и d(u, v) £ Du[v].

Случай Du[v] = 0: Формула (4.3) подразумевает что Du[v] = 0 только для u = v, что дает пустой путь между u и v, и d(u, v) = 0.

Случай Du[v] = k +1 < N : Формула (4.3) подразумевает что существует  узел w Î Neighu с Dw[v] = k. По индукции существует путь между  w и v и d(w, v) £ k, что подразумевает существование пути между u и v и d(u, v) < k+ 1.

Следовательно что если u и v в некотором связном компоненте то Du[v] = d(u, v), иначе Du[v] = N. Это, Формула (4.2), и "u,v : L(u, v)  и доказывает теорему о Nbu[v].                         []

Докажем что стабильная ситуация в конечном счете достигается если топологические изменения прекращаются, норм-функция в отношении stable определена. Определим, для конфигурации алгоритма g,

                   ti =   (число сообщений <mydist, .,i>) +

                            (число упорядоченных пар u, v таких что Du[v] = i)

и функцию f 

                        f(g) = (to, t1,..., tN)

f(g)   кортеж из  (N + l) натуральных чисел, в некотором лексиграфическом порядке (обозначенном £l) . напомним что  (N, £l) хорошо-обоснованное множество (Упражнение 2.5).

Лемма 4.17 Обработка сообщения  < mydist,.,. > уменьшает f.

Доказательство. Пусть узел u с Du[v] = d1  получил сообщение < mydist, v, d2> , и после перевычислил новое значение Du[v]  – d. Алгоритм подразумевает что d < di + 1.

Случай d < d1: Пусть d = d1 + 1 что подразумевает что td2 уменьшилось на 1 (и td1 следовательно), и только td с d > d1 увеличилось. Это подразумевает что значение f  уменьшилось.

Случай d = d1: Не новое сообщение < mydist, ., .> посланное  u, и влияет только на f  так что  td2 уменьшилось на 1, т.о. значение  f  уменьшилось.

Случай d > d1: Пусть td1  уменьшилось на 1 (и td2 следовательно), и только td с d > d1 увеличилось. Это подразумевает что значение f уменьшилось.

[]

Теорема 4.18 Если  топология  сети остается неизменной после конечного числа топологических изменений, то  алгоритм достигнет стабильной конфигурации за конечное число шагов.

Доказательство. Если  сетевая топология остается постоянной  только обрабатывая  сообщения  <mydist,.,.>которые имеют место, и, по предыдущей лемме, значение f уменьшается с каждым таким переходом. Это следует из хорошей обоснованности области  f  в которой может быть только конечное число таких переходов; следовательно алгоритм достигает стабильной конфигурации после конечного числа шагов. []

4.3.3 Обсуждение алгоритма

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

Асинхронная обработка уведомлений. Было  этой части предположили что уведомления о топологических изменениях  обрабатываются автоматически вместе с именением в единой транзакции. Обработка происходит на обоих сторонах удаленного или добавленного канал одновременно. Лампорт [Lam82] выполнил анализ мелких деталей и учел задержки  в обработке этих уведомлений. Коммуникационный  канал от w до u  смоделирован объединением трех очередей.

(1) OQwu ,  выходная очередь  w,

(2) TQwu ,  очередь сообщений  (и пакетов данных)  передаваемая

(3) IQwu ,   входная очередь u.

При нормальном функционировании  канала, w посылает сообщение к u добавлением его в OQwu, сообщения двигаются от OQwu к TQwu и от TQwu к IQwu, и u получает их удаляя из IQwu. Когда  канал отказывает  сообщения в TQwu  выбрасываются и сообщения в OQwu соответственно выбрасываются  раньше чем добавились к TQwu. Сообщение < fail, w>  становится в конец IQwu, и когда нормальное функционирование восстановилось  сообщение <repair,w>  также становится в конец IQwu. предикаты P(u, w, v)  принимают слегка более  сложную форму но алгоритм остается тот же самый.

Маршрутизация по кротчайшему пути. Возможно означить вес каждого канала и модифицировать алгоритм так чтобы  вычислять кратчайший путь вместо пути с  минимальным количеством шагов. Процедура Recompute алгоритма Netchange использовать вес  канала uw в  вычислении оценки длины кратчайший путь через w если константу 1 заменить на wuw. Константа N  в алгоритме должна быть заменена верхней границей диаметра  сети.

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

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

4.4 Маршрутизация с Компактными Таблицами маршрутизации

Обсужденные алгоритмы маршрутизации требуют что бы каждый  узел содержал таблицу маршрутизации  с отдельной ссылкой для каждого возможного пункта назначения. Когда пакет передается через сеть эти таблицы используются  каждом узле пути (исключая пункта назначения). В этой части рассматриваются некоторые организации таблиц маршрутизации которые хранение и поиск механизмов маршрутизации. Как эти таблицы маршрутизации могут быть вычислены распределенными алгоритмами здесь не рассматриваются. Для простоты представления положим что сеть связная.

Стратегию уменьшения таблицы в каждом из трех механизмов маршрутизации, обсуждаемых в этой части, просто объяснить следующим образом. Если  таблицы маршрутизации узла хранят выходящий канал для  каждого пункта назначения отдельно, таблица маршрутизации имеет длину N; следовательно  таблицы требуют W(N) бит, не важно как  компактно выходящий канал закодирован для каждого пункта назначения. Теперь рассмотрим перестройку таблицы: таблица содержит для каждого канала узла ссылку говорящую какие пункты назначения должны быть смаршрутизированны через этот канал; смотри Рисунок 4.11. Таблица теперь имеет "длину"  deg для  узел с deg каналами; теперь компактность зависит от того как компактно множество пунктов назначения для каждого канала может быть представлено.

Рисунок 4.11 Уменьшение размера таблицы маршрутизации.

4.4.1 Схема разметки деревьев

Первый метод  компактной маршрутизации был предложен Санторо и Кхатибом [SK85]. Метод основан на пометке узлов целыми от 0 до N— I,  таким образом чтобы множество пунктов назначения для каждого канала было интервалом. Пусть  ZN  обозначает  множество {0, 1,..., N- 1}. В этой части все арифметические операции по модулю  N, т.e., (N— 1) + 1º 0.

Определение 4.19 Циклический интервал [a, b) в ZN  – множество целых определенное как

                       ì {a, a +1,..., b -1}                  если a<b

            [a,b)= í {0,. . ., b- 1, a,..., N-1}          если  a³b

                       î

Заметим что  [a, a) = ZN, и для a ¹ b дополнение [a, b) – [b, a). Циклический интервал [a, b) называется линейным если a < b.

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

Доказательство. Возьмем произвольный узел vо за корень дерева и для каждого w пусть обозначим за T[w] поддерево  T с корнем в w. Возможно перенумеровать  узлы таким образом чтобы для каждого  w  числа для означивания узлов в  T[w] составляли линейный интервал, на пример префиксным обходом  дерева как на Рисунке 4.12.  В этом порядке, w – первый узел дерева T[w] который посетится и после w все узлы T[w] посетятся перед узлами не входящими в T[w]; следовательно  узлы в T[w] перенумерованы линейным интервалом [lw, lw +|T{w]|) (1w метка w).

Через [aw, bw) обозначим интервал чисел означивающие узлы в T[w]. Сосед  w – один из двух сыновей или отец w. Узел w передает к сыну u  пакеты с пунктом назначения в  T[u], т.е., узлы с числами в  [au, bu). Узел w передает  своему отцу пакеты с пунктами назначения не в  T[w], т.е., узлы с номерами в
 ZN \[aw,bw) = [bw,aw).          []

Рисунок 4.12 Префиксный обход дерева

Циклический интервал может быть представлен использование  только 2 log N  бит дающих начальный и конечный пункт. Так ка в этом приложении объединение разъединенных интервалов в объединении ZN  должно хранится, достаточно logN бит на интервал. Хранится только начальная точка интервала для каждого канала; конечная точка эквивалентна начальной точке следующего интервала в том же узле. Начальная точка интервала приписанного каналу  uw в узле u дается как

                    ì         lw                       если w сын u,

         auw =  í

                    î      lu+|T[u]|              если  w отец u

Положим что каналы узла u со степенью degu помечены a1,..., adeg u , где a1 < ,...,< adeg u ,  передающая процедура дана в Алгоритме 4.13. Метки  каналов отображают ZN в сегменты degu  , каждый соответствует одному каналу; см. Рисунок 4.14. Заметим что существует (не более чем) один интервал который не линейный. Если метка отсортированы в узле, соответствующая метка находится за О(log degu)  шагов используя бинарный поиск. Индекс  i вычисляется по модулю degu, т.e., adeg u+1  == a1.

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

if d = lu

       then доставить пакет локально

       else begin   выбрать ai, т.ч.  d Î [ai, ai+1) ;

                           послать пакет через канал с меткой ai

       end

Алгоритм 4.13 Интервальная передача (для узла  u).

Рисунок 4.14 Часть  ZN в узле.

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

Сравним длины  путей выбранное этой схемой с оптимальными путями, пусть dT(u, v) обозначает расстояние от u до v в T и dG(u, v)  расстояние от u до v в G. Пусть DG обозначает диаметр G, определенный как максимум для любых u и v из dG(u, v).

Лемма 4.21 Нет общего ограничения пропорции между  dT(u, v) и dG(u, v).Это имеет силу только в специальном случае измерения переходами путей.

Доказательство. Выберем G как кольцо из N узлов, и заметим что дерево охвата G  получается удалением одного канала, скажем xy, из G. Теперь dG(x, y) = 1 и dT(x, y) = N-1,таким образом пропорция  N—1. Пропорция может быть гораздо больше выбором большего кольца.                                       []

Следующая Лемма полагается на симметричность стоимостей каналов, т.е., это значит что wuw = wwu .Это подразумевает что dG(u, v) = dG(v, u) для всех  u и v.

Лемма 4.22 T может быть выбрано таким образом чтобы для всех u и v, dT(u, v) £ 2G.

Доказательство. Выберем T  как оптимальное дерево стока для узла wo (как в Теореме 4.2). Тогда

                            dT(u, v) £ dT(u, wo) + dT(wo,v)

                                         = dT(u, wo)+ dT(v, wo)  по симметричности  w

                                          = dG(u, wo)+ dG(v, wo) по симметричности T

                                          = DG+DG                                по определению DG

[]

В заключении , a путь выбранный одной схемой может быть плохом если сравнить с оптимальным  путём между этими же двумя узлами (Лемма 4.21), но если выбрано подходящее дерево охвата, он в s не более чем два раза хуже пути между двумя другими узлами в системе(Лемма 4.22).

Схема разметки деревьев имеет следующие недостатки.

(1)  Каналы не принадлежащие T не используются

(2) Трафик сосредоточен в  дереве,(может произойти перегрузка).

(3)Каждый отказ канала делит сеть.

4.4.2 Интервальная маршрутизация

Ван Ливен и Тэн [LT87] расширили схему разметки деревьев до сетей не являющихся деревьями таким образом что каждый канал используется для передачи пакета.

Определение 4.23 Схема разметки деревьев  (ILS)для сети это

(1) обозначение различными метками из ZN  узлов сети, и,

(2) Для каждого узла, обозначение различными метками  из ZN  каналов данного узла

Алгоритм интервальной маршрутизации предполагает что  ILS дана, и пакеты передаются как в Алгоритме 4.13.

Определение 4.24 Схема интервальной разметки применим  если все пакеты передаются этим путем которым достигнут своего пункта назначения.

Можно показать что применимая схема интервальной разметки  существует для каждой связной сети G (Теорема 4.25); для произвольной связной сети, однако, схема обычно не очень эффективна. Оптимальность путей выбранных схемой интервальной маршрутизации будет изучена после существующего доказательства.

Теорема 4.25 Для каждой связной сети G применимая схема интервальной разметки  существует.

Доказательство. Схему применимой интервальной пометка построим расширением схемы разметки деревьев  Санторо и Кхатиба, применив к дереву охвата сети T . В данном дереве охвата  ребро ветви – ребро которое не принадлежит дереву охвата. Более того, v  потомок  u если только u Î T[v]. Основная проблема как означить метки ребер ветвей (ребра дерева будут помечены схемой разметки деревьев),  дерево охвата выбирается таким образом чтобы все ребра ветвей приняли ограниченную форму

Лемма 4.26 Существует  дерево охвата такое что между узлом потомком этого узла.

Доказательство. Каждое дерево охвата полученное обходом в глубину через сеть имеет это свойство; смотри [Tar72] и Часть 6.4.             []

В продолжении, пусть  T  будет зафиксированное дерево охвата поиска в глубину в G.

Определение 4.27 Поиск в глубину ILS для  G (в отношении к  T)  – схема разметки для которой выполняются следующие правила.

(1) Метки узлов означены префиксным обходом в T, т.е., узлы в поддереве T[w] помечены числами из [lw, ,lw+|T[w]|). Обозначим  kw = lw+ |T[w]|.

(2) Метку ребра  uw в узле u обозначим auw.

(a)  Если uw ребро ветви то auw = lw

(b)  Если w сын  u (в T) то auw = lw

(c)  Если w отец u то  auw = ku  если ku ¹ N и u имеет ветвь к корню. (В последней ситуации, ребро ветви помечаем  0 в u по правилу (a),таким образом означивание метки  ku  нарушило бы требование что все метки различны. Метки считаются по модулю N, т.е.  N º0.)

(d)  Если w отец u, u имеет ветвь к корню, и  ku º N, тогда  auw = lw.

Все примеры поиска в глубину ILS даны на Рисунке 4.15. Заметим что все ребра ветвей помечены по правилу (2a), ребра к отцам узлов 4, 8, и 10 помечены  по правилу (2c), и ребро к отцу узла 9 помечено по правилу (2d).

Теперь покажем верность схемы обхода в глубину ILS . Заметим что vÎT[u] Û lv Î [lu, ku). Следующие три  леммы относятся к ситуации когда узел u передает пакет с пунктом назначения v к узлу w (соседу  u) используя Алгоритм 4.13. Это подразумевает что lv Î [auw, a) для некоторой метки a в u, и что нет метки a’¹auw  в узле u такой что a' Î [auw,, lv).

Страницы: 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