Предыдущая страница реферата | 20  21  22  23  24  25  26  27  28  29  30 | Следующая страница реферата

которого достаточно для доказательства что 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 определена. Определим, для конфигурации алгоритма (, ti = (число сообщений ) +

(число упорядоченных пар u, v таких что Du[v] = i) и функцию f f(() = (to, t1,..., tN)

f(() кортеж из (N + l) натуральных чисел, в некотором лексиграфическом порядке (обозначенном (l) . напомним что ((, (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 Если топология сети остается неизменной после конечного числа топологических изменений, то алгоритм достигнет стабильной конфигурации за конечное число шагов.

Доказательство. Если сетевая топология остается постоянной только обрабатывая сообщения которые имеют место, и, по предыдущей лемме, значение 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, и когда нормальное функционирование восстановилось сообщение также становится в конец IQwu. предикаты P(u, w, v) принимают слегка более сложную форму но алгоритм остается тот же самый.

Маршрутизация по кротчайшему пути. Возможно означить вес каждого канала и модифицировать алгоритм так чтобы вычислять кратчайший путь вместо пути с минимальным количеством шагов. Процедура Recompute алгоритма Netchange использовать вес канала uw в вычислении оценки длины кратчайший путь через w если константу 1 заменить на wuw. Константа N в алгоритме должна быть заменена верхней границей диаметра сети.
Довольно просто показать что когда модифицированный алгоритм достигнет стабильной конфигурации таблицы маршрутизации будут корректны и содержать оптимальный путь (все циклы в сети должны иметь положительный вес).
Доказательство что алгоритм действительно достигает такого состояния требует более сложной нормфункции.
Даже возможно расширить алгоритм для работы с изменяющимися весами каналов; реакция узла u на изменение веса канала – перевычисление Du[v] для v.
Алгоритм был бы практическим, однако, только в ситуации когда среднее время изменений стоимостей каналов больше времени сходимости что не реально. В этих ситуациях должна алгоритм должен предпочесть гарантию свободы от циклов в течение сходимости, на пример алгоритм Мерлина-Сигалла.
4.4 Маршрутизация с Компактными Таблицами маршрутизации

Обсужденные алгоритмы маршрутизации требуют что бы каждый узел содержал таблицу маршрутизации с отдельной ссылкой для каждого возможного пункта назначения. Когда пакет передается через сеть эти таблицы используются каждом узле пути (исключая пункта назначения). В этой части рассматриваются некоторые организации таблиц маршрутизации которые хранение и поиск механизмов маршрутизации. Как эти таблицы маршрутизации могут быть вычислены распределенными алгоритмами здесь не рассматриваются. Для простоты представления положим что сеть связная.
Стратегию уменьшения таблицы в каждом из трех механизмов маршрутизации, обсуждаемых в этой части, просто объяснить следующим образом. Если таблицы маршрутизации узла хранят выходящий канал для каждого пункта назначения отдельно, таблица маршрутизации имеет длину N; следовательно таблицы требуют ((N) бит, не важно как компактно выходящий канал закодирован для каждого пункта назначения. Теперь рассмотрим перестройку таблицы: таблица содержит для каждого канала узла ссылку говорящую какие пункты назначения должны быть смаршрутизированны через этот канал; смотри Рисунок 4.11.
Таблица теперь имеет "длину" deg для узел с deg каналами; теперь компактность зависит от того как компактно множество пунктов назначения для каждого канала может быть представлено.
[pic]
Рисунок 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 lv то lw < Iu

Доказательство. Во-первых, рассмотрим случай (uw ( lv. Узел w не сын u потому что в этом случае (uw = lw > lu > lv .Если uw ветвь то также lw =
(uw < lv < lu. Если w отец u то lw < lu выполняется в любом случае. Во- вторых, рассмотрим случай когда (uw – наибольшая метка ребра в u, и нет метки (' ( lv (т.е., lv – нижняя граница нелинейного интервала). В этом случае ребро к отцу u не помечено 0, но имеет метку ku (потому что 0( lv, и нет метки (' ( lv). Метка ku – наибольшая метка в данном случае; ребро к сыну или ветви вниз w' имеет (uw’ = lw’ < ku, и ветвь к предком w' имеет
(uw’ = lw’ < lu Таким образом w – отец u в данном случае, что подразумевает
1w < lu. []

Следующие две леммы относятся к случаю когда lu < lv. Мы выведем что каждый v ( T[u] или lv > ku, и в последнем случае ku < N имеет силу так что ребро к отцу u помечено ku.
[pic]
Рисунок 4.16 МАРШРУТИЗАЦИЯ ПАКЕТОВ ДЛЯ V В СХЕМЕ РАЗМЕТКИ ILS.

Лемма 4.29 Если lu ku. Как в предыдущей лемме, w отец u, и поэтому v(T[u], lca(w, v)= lca(u, v). Но теперь 1w < lu , таким образом fv(w)< fv(u). []

Может быть показано что каждый пакет достигает пункта назначения. Поток пакетов для v показан на Рисунке 4.16. Пусть пакет для v сгенерирован в узле u. По Лемме 4.28, метка узла уменьшается с каждым переходом, до тех пор пока, за конечное число шагов, пакет получен узлом w с 1w(lv. Каждый узел к которому пакет пересылается после w также имеет метку (lv по лемме 4.29. За конечное число шагов пакет получает v, потому что с каждым шагом fv уменьшается или пакет прибывает в v, по Лемме 4.30. Это завершает доказательство Теоремы 4.25. []

Эффективность интервальной маршрутизации: общий случай. Теорема 4.25 говорит что корректная ILS существует для каждой сети, но не предполагает ничего о эффективности путей выбранных схемой. Ясно что ILS с поиском в глубину используется для демонстрации существования схемы для каждой сети, но что они не обязательно лучшие возможные схемы. На пример, если схема с обходом в глубину применена к кольцу из N узлов, существуют узлы u и v с d(u, v) == 2, и схема использует N — 2 переходов для передачи пакета от u к v (Упражнение 4.8). Существует ILS для того же кольца что которая пересылает каждый пакет через путь с минимальным количеством шагов.
(Теорема 4.34).

Определение 4.31 ILS оптимальна если она передает все пакеты через оптимальные пути.
ILS общительна если она передает пакет от одного узла к соседу данного узла за один шаг.
ILS линейна если интервал для передачи в каждом ребре линейный.

Мы называли ILS с минимальным количеством шагов (или кротчайший путь) если она оптимальна относительно оценки пути мерой минимальным количеством шагов (или кратчайший путь, соответственно). Просто показать что если схема удовлетворяет мере минимального количества шагов то схема общительна. Также легко проверить что ILS линейна тогда и только тогда когда в каждом узле u с lu ( 0 существует ребро с пометкой 0, и в узле с пометкой 0 существует ребро с меткой 0 или 1. Это показывает что для сетей в общем виде качество методов маршрутизации плохое, но для некоторых классов специальной сетевой топологии качество схемы очень неплохое. Это делает метод процессорных сетей с регулярной структурой, которые используются для реализации параллельных вычислений с виртуальной общей разделяемой памяти.
Не известно точно как, для произвольной сети, лучшие схемы интервальной разметки сравниваются с оптимальными алгоритмами маршрутизации. Некоторые нижние границы длин путей, как подразумевают оптимальные ILS не всегда существуют, было дано Ружечкой(Ruzecka).

[pic]
Рисунок 4.1T Граф-паук с тремя ногами

Теорема 4.32 [Ruz88] Существует сеть G такая что для каждой верной ILS в G существуют узлы u и v такие что пакет от u к v доставлен только после по крайней мере 3/2DG переходов.

Известно как лучшие схемы ILC с поиском в глубину сравниваются с общими лучшими схемами ILS для этих же сетей. Упражнение 4.7 дает очень плохую схему ILS с поиском в глубину для сети которая действительно допускает оптимальную ILS (по Теореме 4.37), но может существовать лучшая схема ILS с поиском в глубину для такой сети.
В ситуациях когда большинство соединений происходят ммежду соседями, будучи общительными достаточные требования для ILS. Так можно показать из
Рисунка 4.15 схема ILS с поиском в глубину не обязательно общительна; узел 4 передает пакеты для узла 2 через узел 1.
Это существенно для применимости метода интервальной маршрутизации, которым рассматриваются циклические интервалы. Хотя некоторые сети допустимы, и даже оптимальны, схемы с линейноинтервальной маршрутизации, не возможно маркировать каждую сеть линейными интервалами. Применимость схемы линейноинтервальной разметки была исследована Бэккером, Ван Лиуином, и
Таном [BLT91].

[pic]
Рисунок 4.18 Оптимальная ILS для кольца

Теорема 4.33 Существует сеть для которой нет применимой схемы линейноинтервальной разметки

Доказательство. Рассмотрим граф-паук с тремя ногами длины 2, как нарисовано на Рисунке 4.17. Наименьшей матка (0) и наибольшей метка (6) означены два узла, и так как всего три ноги, существует(по крайней мере) одна нога которая не содержит ни меньшую ни большую метку. Пусть x будет первым узлом отцентра в этой ноге. Узел x передает пакета адресованные к 0 и 6 в центр, и единственный линейный интервал который содержит и 0 и 6 это полное множество ZN . Следовательно, x также пересылает пакеты для своих соседей через центр, и эти пакеты никогда не достигнут своих пунктов назначения. []

Бэккер, Ван Лиуин и Taн полностью описали класс сетей топологии которых допускают линейные схемы ILS кротчайших путей и представили результаты содержащие классы графических топологий которые допускают адаптацию и линейные схемы ILS с минимальным количеством шагов линейны.

Оптимальность интервальной маршрутизации: специальные топологии.
Было показано что существуют оптимальные схемы интервальной разметки для некоторых классов сетей имеющих регулярную структуру. Сети таких структур используются , например, в реализации параллельных вычислений.

Теорема 4.34 [LT87] Существует схема ILS с минимальным количеством шагов для кольца из N узлов.

Доказательство. Метки узлов означены от 0 до N — I по часовой стрелке. Для узла i канал по часовой стрелке означен меткой i +1 и канал против часовой стрелке означен (i+ [N/2]) mod N, см Рисунок 4.18. С этой схемой разметки узел с меткой i посылает пакеты для узлов i+1, ..., (i+ [N/2] ) -1 через канал по часовой стрелке и пакеты для узлов (i + [N/2]), . . . , i —1 через канал против часовой стрелке, что является оптимальным.

[]

[pic]

Рисунок 4.19 Оптимальная ILS для сетки n x n.

Так как ILS iв Доказательстве Теоремы 4.34 оптимальна , она общительна; она линейна.

Теорема 4.35 [LT87] Существует схема ILS с минимальным количеством шагов для сетки n x n .

Доказательство. Метки узлов означены по рядам в возрастающем порядке, т.е., i-ый узел в j-ом ряду помечен (j - l)n + (i - 1). Канал вверх этого узла помечен 0, канал налево этого узла помечен (j - l)n, канал направо помечен (J - l)n + i, и канал вниз помечен j n, см Рисунок 4.19. Теперь легко проверить что когда узел u передает пакет к узлу v,
Случай 1: если v в ряду большем чем u, тогда u посылает пакет через свой канал наверх;
Случай 2: если v в ряду меньшем чем u, тогда u посылает пакет через свой канал вниз;
Случай 3: если v в том же ряду что и u но левее, u посылает пакет через свой левый канал; и
Случай 4: если v в том же ряду что и u но правее, то u посылает пакет через свой канал направо.
Во всех случаях , u посылает пакет к узлу ближайшему к v, что и подразумевает что выбранный путь оптимальный.

[]

Так как ILS в Доказательстве Теоремы 4.35 оптимальна, он общительна; то схема также линейна.

Теорема 4.36 Существует линейная схема ILS с минимальным количеством шагов для гиперкуба.

Теорема 4.37 [FJ88] Существует схема ILS кротчайших путей для непланарных сетей с произвольными весами каналов.

Интервальная маршрутизация имеет некоторые привлекательные преимущества, как следствия, над механизмами классической маршрутизации основанными на хранении привилегированных каналов отдельно для каждого пункта назначения.
(1) Малая пространственная сложность. Таблицы маршрутизации могут хранится в 0(deg • log N) бит для узла степенью deg.
Эффективность вычислений таблиц маршрутизации. Таблицы маршрутизации для схем ILC c поиском в глубину могут быть вычислены используя распределенный обход сети в глубину, который может использовать O(E) сообщений за время
0(N) ; см Часть 6.4.
Оптимальность. Метод маршрутизации способен выбирать оптимальный петь в некоторых классах сетей, см. Теоремы с 4.34 до 4.37.

Эти преимущества делают метод применимым для процессорных сетей с регулярной топологией. Транспьютеры часто используются для конструирования таких топологий, маршрутизационные чипы Инмос 104 (смотри Раздел 1.1.5) разработаны для использования интервальной маршрутизации.
К сожалению, для сетей с произвольной топологией, когда методы используют схемы ILS с поиском в глубину присутствуют несколько минусов:

(1) Плохая живучесть. Не возможна легкая адаптация схемы ILS с поиском в глубину при добавлении или удалении узла в сети. Дерево ILS не может долго удовлетворять требованию по которому ветвь существует только между узлом и его предком. В результате минимальное изменение топологии сети может потребовать полного перевычисления таблиц маршрутизации, включая вычисление новых адресов (меток) для каждого узла.
Не оптимальность. Схема ILS поиска в глубину может направлять пакет через пути длиной ((N), даже в случаях сетей с малым диаметром; см Упражнение
4.7.

(* A пакет с адресом d был получен или создан узлом u *) if d = lu then обработать пакет локально
[pic] else begin (i := самая ддлинная матка канала т.что (i ( d ; послать пакет через канал помеченый (i end
Алгоритм 4.20 Префиксная передача (для узла u).

4.4.3 Префиксная маршрутизация

Рассмотрев недостатки интервальной маршрутизации, Бэккер, Ван Лиуин, и Taн
[BLT93] разработали метод маршрутизации в котором таблицы могут быть вычислены используя произвольное дерево охвата. Использование неограниченного дерева охвата может увеличить как живучесть так и эффективность. Если a канал добавлен между двумя существующими узлами то дерево охвата остается деревом охвата а новый канал будет ветвью. Если новый узел добавляется вместе с некоторым количеством каналов соединяющих его с существующими узлами то дерево охвата расширяется используя один из каналов и новый узел. Остальные каналы становятся ветвями. Оптимальность может быть улучшена выбором дерева охвата малой глубины (как в лемме 4.22.)

Как метки узлов и каналов в префиксной маршрутизации предпочтительнее использовать строки чем целые числа, используемые в интервальной маршрутизации. Пусть ( – алфавит; в последствии метка будет строкой над (,
( обозначает пустую строку, и (* множество строк над (. Для отбора канала для передачи пакета, алгоритм рассматривает все каналы которые являются префиксами адреса пункта назначения. Выбирается самая длинная из этих меток, и выбранный канал используется для передачи пакета. На пример, предположим что узел имеет каналы с метками aabb, abba, aab, aabc, и aa, и должен переслать пакет с адресом aabbc. Метки каналов aabb, aab, и aa являются префиксами aabbc, и самая длинная из этих трех меток aabb, следовательно узел передаст пакет через канал помеченный aabb. Алгоритм передачи дан как Алгоритм 4.20. Мы пишем ( (( для обозначения что ( префикс
(.

Определение 4.38 Схема префиксной разметки (над () для сети G это:
(1) обозначение различными строками из (* узлов G; и
Для каждого узла, означивание различными строками каналов данного узла.

Алгоритм префиксной маршрутизация предпалагает что схема префиксной разметки (PLS) дана, и перенаправляет пакеты Алгоритмом 4.20.

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.





Предыдущая страница реферата | 20  21  22  23  24  25  26  27  28  29  30 | Следующая страница реферата