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

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

Доказательство. Мы определим класс схем префиксной разметки и докажем, как и в Теореме 4.25, что схемы в этом классе приемлемы. Пусть  T обозначает произвольное дерево охвата в G.

Определение 4.41 Дерево Т  схемы PLS для G  это схема префиксной разметки при которой выполняются следующие правила.

(1) Метка корня – s.

(2) Если w сын  u то 1w  расширяет  lu одним символом; т.е., если u1, ..., uk  сын u в T то 1ui = luai где  a1, . . . , ak  –  k различных символов из S.

(3) Если  uw ветвь то  auw  = lw

(4) Если w сын u то auw = lw.

(5)   Если w отец  uто auw= s  если  u не имеет ветви к корню: в этом случае, auw  = lw

В дереве PLS  каждый узел исключая корень имеет канал помеченный s, и этот  канал соединяет узел с предком (отцом узла или корнем дерева). Заметим что  для каждого канала uw, auw = lw или auw = s. Для всех u и v, v  предок у тогда и только тогда когда lv < lu.

Нужно показать что пакет никогда не  "вклинивается"  в  узел отличный от его  пункта назначения, который, каждый узел отличный от пункт назначения может перенаправить пакет используя Алгоритм 4.20.

Лемма 4.42 Для всех узлоа  u и vтаких что  u ¹ v существует канал в u помеченный  префиксом lv.

Доказательство. Если u не корень T то u имеет канал помеченный s, который является префиксом lv. Если u корень тогда v не является корнем, и v ÎT[u] . Если w  сын  u такой что vÎT[w] то по построению  auw < lv.         []

Следующие три леммы имеют отношение к ситуации когда узел u передает пакет для  узла v к  узлу w (соседу  u) используя  Алгоритм 4.20.

Лемма 4.43 Если u Î T[v] то w предок  u.

Доказательство. Если auv == s  то w предок u как упоминалось выше. Если auw = lw то, так как auw <lv, также lw<lv Это подразумевает что w предок v, и также u.[]

                                                             

Лемма 4.44 Если u предок  v то w предок  v,  ближе к  v чем u.

Доказательство. Пусть w' будет сыном  u таким что  v Î T[w'] тогда auw’ =lw  не пустой префикс lv. Так как  auw  самый длинный  префикс (в u)  lv,  то  auw’< auw < lv, таким образом w предок  v ниже  u.                   []

Лемма 4.45 Если uÏ T[v], то  w предок  v или dT(w, v) < dT(u, v).

Доказательство. Если auw =s  то w отец  u или корень; отец u ближе к  v чем u потому что u ÏT[v], и корень – предок v. Если auw = lw то , так как auw < lv, w – предок v.                        []

Пусть depth будет обозначать  глубину T, т.е., число переходов  в самом длинном  простом пути от корня к листьям. Может быть показано каждый пакет  с пункт назначения v прибудет в свой пункт назначения за не более чем 2 - depth переходов. Если пакет создан в предке v то v достигнется не более чем  depth переходов по лемме 4.44. Если  пакет создан в поддереве T[v] тогда предок  v достигнется  за не более чем depth переходов по лемме 4.43, после которых v достигнется за другие depth переходов по предыдущему замечанию. (По причине того  что путь содержит только предков источника в этом случае, его длина ограничена также depth .) Во всех других случаях предок  v  достигнется в пределах depth переходов по лемме 4.45, после которого v достигнется  в пределах других depth переходов. (Таким образом, в этом случае длина пути ограничена 2 depth.) Это завершает  Доказательство  Теоремы 4.40               

[]

            

Следствие 4.46 Для каждой сети  G с диаметром  DG  (измеренным в переходах)  существует схема префиксной разметки которая доставляет все пакеты за не более чем 2DG переходов.

Доказательство. Воспользуемся  деревом PLS   что качается дерева выбранного в Лемме 4.22.   []

Мы включили  обсуждение  схему разметки деревьев с грубым анализом его пространственных требований. Как и раньше,  depth – глубина T, и пусть k будет максимальным количеством сыновей дюбого узла T. Тогдаe самая длинная метка состоит из  depth символов, и  S должен содержать (по крайней мере) k символов, метка может храниться в depth • log A  бит. Таблица маршрутизации a узла с deg каналами хронится в  0(deg* depth * log k) бит.

Несколько другая схема префиксной разметки бала предложена Бэккером. [BLT93]. Его статья также характеризует класс топологий который допускает   оптимальные схемы префиксной разметки когда веса связей могут меняться динамически.

4.5 Иерархическая маршрутизация

Путь сокращения различных параметров стоимости метода маршрутизации - использование иерархического разделения сети и метода ассоциативной  иерархической маршрутизации. Цель в большинстве случаев состоит в том, чтобы использовать факт, что многие связи в сетях компьютеров являются локальными, то есть, между узлами на относительно малых расстояниях  друг от друга. Некоторые из параметров стоимости метода маршрутизации зависят от размера полной сети скорее чем длина выбранного пути, почему, мы теперь объясним

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

(2) Размер таблицы маршрутизации. В методах  маршрутизации описываемые в разделах 4.2 и 4.3, таблица содержит ссылку на каждый узел, и таким образом имеет линейный размер.

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

В методе иерархической маршрутизации , сеть разделена на кластера, каждый кластер есть связное подмножество узлов. Если  источник и пункт назначения  пакета  в одном кластере, цена передачи сообщения низка, потому что пакет маршрутизируется внутри кластера, кластер трактуется как небольшая изолированная сеть. Для метода описанного в разделе 4.5.1, в каждом кластере зафиксирован простой узел (центр кластера) который может делать наиболее сложные маршрутизационные решения необходимые для пересылки пакетов в другие кластера. Таким образом, большие  таблицы маршрутизации и манипуляция длинными адресами необходима только в центрах. Каждый кластер сам может разделиться на подкластеры для многоуровневого деления узлов.

Не  необходимо но желательно чтобы каждая коммутация между кластерами велась через центр; этот тип конструкции имеет такой недостаток  что весь кластер становится уязвимым на отказ центра. Лентферт [LUST89] описал метод иерархической маршрутизации в котором все узлы в равной степени могут посылать сообщения  другим кластерам. Также метод использует только маленькие таблицы, потому что ссылки на кластеры к которым узел не принадлежит  трактуется как простой узел. Овербух [ABNLP90] использует парадигму иерархической маршрутизации для конструирования класса схем маршрутизации которые всегда балансируют между эффективностью и пространственными требованиями.

4.5.1 Уменьшение количества решений маршрутизации

Все обсужденные методы  маршрутизации  требуют чтобы решения маршрутизации  делались в каждом промежуточном узле, что подразумевает  что для маршрута длиной l  происходит l обращений к таблицам маршрутизации. Для  стратегий  минимального количества шагов l  ограничено диаметром сети, но  в общем, стратегии маршрутизация  без циклов  (такие как интервальная маршрутизация)  N—1 – лучшая граница которая может быть достигнута. В этом разделе мы обсудим  метод с помощью которого табличные поиски могут быть уменьшены.

Мы будем использовать следующую лемму, которая подразумевает существование подходящего разбиения сети на связные кластера.

Лемма 4.47 Для каждого  s £ N  существует разбиение сети на кластера C1,..., Cm такие что

(1) каждый кластер – связный подграф,

(2) каждый кластер содержит по крайней мере s узлов, и

(3) каждый кластер имеет радиус не более чем 2s.

Доказательство. Пусть D1, ..., Dm  будет максимальная коллекция разделенных связных подграфов таких что каждый  Di имеет радиус £ s и содержит по крайней мере s узлов. Каждый узел не принадлежащий  соединен с одним из подмножеств путем длиной не больше чем s, иначе муть может быть добавлен как отдельный кластер. Сформируеи кластеры Сi включением каждого узла не входящего в  в кластер ближайший к нему. Расширенные кластеры остаются содержат по крайней мере s узлов каждый, они остаются связными и разделенными, и они имеют радиус не более чем 2s.               []

Метод маршрутизации означивает цветом каждый пакет, и предполагается что используется только несколько цветов. Узлы теперь действуют следующим образом. В зависимости от цвета, пакет или отправляет немедленно по установленному каналу (соответствующему цвету) или вызывает более сложному решению. Это подразумевает, что узлы имеют различные протоколы для обработки пакетов.

Теорема 4.48 [LT86] For каждой сети из N узлов существует метод маршрутизации который требует не более чем 0() решений маршрутизации для каждого  пакета, и использует три цвета.

Доказательство. Предположим что решения (по  Лемме 4.47) даны и заметим что каждый Ci содержит узел ci такой что  d(v, ci) £ 2s для каждого v Î Ci  потому что  Ci имеет радиус  не более чем 2s. Пусть  T будет поддеревом минимального размера из G соединяющее все  ci. Так как T  минимально то оно содержит не более чем m листьев, следовательно оно содержит не более чем m-2 узлов разветвлений (узлы степенью большей чем 2); см Упражнение 4.9. Рассмотрим узла  T как центры ( ci), узлы разветвлений, и узлы пути.

Метод  маршрутизации сначала посылает  пакет к центру ci  кластера источника (зеленая фаза), затем через  T к центру  cj кластера пункта назначения  (синяя фаза), и наконец внутри Cj к  пункту назначения  (красная фаза). Зеленая фаза использует фиксированному дерево стока для центра каждого кластера, и не решений маршрутизации. Узлы пути в T  имеют два инцидентных канала, и передают каждый синий пакет через канал ыв дереве которые не принимают пакет. Узлы ветвлений и центры в T должны принимать решения маршрутизации. Для красной фазы используется стратегия кротчайшего пути внутри кластера, которая ограничивает число решений в этой фазе до 2s. Это ограничивает число решений маршрутизации  до 2m - 2 + 2s, что  не более чем 2N/s - 2+ 2s. Выбор s » дает ограничение 0().                                                      []

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

Теорема 4.49 [LT86) Для каждой сети из  N узелs и каждого положительного целого числа f £ log N существует метод  маршрутизации  который требует  не более чем O(f N1/f) решений маршрутизации для каждого  пакета, и использует  2f + 1 цветов.

Доказательство. Доказательство подобно  доказательству теоремы 4.48, но  вместо выбора  s» конструирование применяется рекурсивно к дереву T  (оно кластер размера s). Дерево – связная сеть, по существу  < 2m узлов потому что узлы пути в T  только перенаправляют пакеты из одного фиксированного канала в другой, и может быть игнорирован.

Кластеризация повторяется f  раз. Сеть G имеет N узлов. Дерево содержит после одного уровня кластеризации не более чем N/s центров и N/s узлов ветвления, т.е., N.(2/s) необходимых узлов. Если  дерево полученное после i уровней кластеризации имеет mi необходимых узлов, тогда дерево полученное после  i +1 уровней кластеризации имеет не более чем mi/s центров и mi/s узлов ветвлений, т.е., mi.(2/s) необходимых узлов. Дерево полученное после f уровней кластеризации  имеет не более чем mf = N.(2/s)f необходимых узлов.

Каждый уровень кластеризации увеличивает количество цветов на два, следовательно с f  уровнями кластеризации будут использоваться  2f+1 цветов. Не более чем 2mf решений необходимо на самом высоком уровне, и s решений необходимо нв каждом уровне кластеризации в кластере пункта назначения, отсюда количество решений маршрутизации 2mf + fs.  Выбирая  s »2N1/f получим mf = O(1), следовательно число решений маршрутизации ограничено

f s = O(f N1/f).                   []

Использование приблизительно logN цветов  приводит к методу маршрутизации которые требуют O(logN) решений маршрутизации.

Упражнения к Части 4

Раздел 4.1

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

Раздел 4.2

Упражнение 4.2 Студент предложил пренебречь посылкой сообщения

 < nys, w > из  алгоритма 4.6; он аргументировал это тем что узел знает своего соседа и не сын в Tw, если  нет сообщения <ys,w> принятого от этого соседа. Можно ли модифицировать алгоритм таким образом? Что случиться со сложностью алгоритма?

Упражнение 4.3 Докажите что следующее утверждение является инвариантом алгоритма Чанди-Мизра для вычисления путей до vo (Алгоритм 4.7).

"u, w : <mydist,vo,d> Î Mwu Þ  d(w, vo) £ d

 Ù" u : d(u, vo) £  Du[vo]

Дайте пример для которого число сообщений экспоненциально относительно

числа каналов сети.

Раздел 4.3

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