Распределенные алгоритмы (стр. 32 из 85)

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

[]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

î

Заметим что [a, a) = Z_N, и для 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] перенумерованы линейным интервалом [l_w, l_w +|T{w]|) (1_wметка w).

Через [a_w, b_w) обозначим интервал чисел означивающие узлы в T[w]. Сосед w – один из двух сыновей или отец w. Узел w передает к сыну u пакеты с пунктом назначения в T[u], т.е., узлы с числами в [a_u, b_u). Узел w передает своему отцу пакеты с пунктами назначения не в T[w], т.е., узлы с номерами в
Z_N &bsol;[a_w,b_w) = [b_w,a_w). []

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

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

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

a_uw = í

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

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

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

if d = l_u

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

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

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

end

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