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

Следующие две леммы относятся к случаю когда lu < lv. Мы выведем что

каждый v ( T[u] или lv > ku, и в последнем случае ku < N имеет силу так

что ребро к отцу u помечено ku.

[pic]

Рисунок 4.16 МАРШРУТИЗАЦИЯ ПАКЕТОВ ДЛЯ V В СХЕМЕ РАЗМЕТКИ ILS.

Лемма 4.29 Если lu lu. Таким образом fv(w) < fv(u).

Во-вторых, рассмотрим случай что 1v > 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.

Определение 4.39 Схема префиксной разметки приемлема если все пакеты в

конечном счете достигнут своих пунктов назначения.

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

Доказательство. Мы определим класс схем префиксной разметки и докажем, как

и в Теореме 4.25, что схемы в этом классе приемлемы. Пусть T обозначает

произвольное дерево охвата в G.

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

при которой выполняются следующие правила.

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

(2) Если w сын u то 1w расширяет lu одним символом; т.е., если u1, ...,

uk сын u в T то 1ui = lu(i где (1, . . . , (k – k различных символов из

(.

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

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

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

= lw

В дереве PLS каждый узел исключая корень имеет канал помеченный (, и этот

канал соединяет узел с предком (отцом узла или корнем дерева). Заметим что

для каждого канала uw, (uw = lw или (uw = (. Для всех u и v, v предок у

тогда и только тогда когда lv < lu.

Нужно показать что пакет никогда не "вклинивается" в узел отличный от

его пункта назначения, который, каждый узел отличный от пункт назначения

может перенаправить пакет используя Алгоритм 4.20.

Лемма 4.42 Для всех узлоа u и vтаких что u ( v существует канал в u

помеченный префиксом lv.

Доказательство. Если u не корень T то u имеет канал помеченный (, который

является префиксом 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 == ( то 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 =( то 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 символов, и ( должен содержать (по крайней мере) 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 узлов. Каждый узел не принадлежащий [pic] соединен с одним

из подмножеств путем длиной не больше чем s, иначе муть может быть добавлен

как отдельный кластер. Сформируеи кластеры Сi включением каждого узла не

входящего в [pic] в кластер ближайший к нему. Расширенные кластеры остаются

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

разделенными, и они имеют радиус не более чем 2s. []

Метод маршрутизации означивает цветом каждый пакет, и предполагается что

используется только несколько цветов. Узлы теперь действуют следующим

образом. В зависимости от цвета, пакет или отправляет немедленно по

установленному каналу (соответствующему цвету) или вызывает более сложному

решению. Это подразумевает, что узлы имеют различные протоколы для

обработки пакетов.

Теорема 4.48 [LT86] For каждой сети из N узлов существует метод

маршрутизации который требует не более чем 0([pic]) решений маршрутизации

для каждого пакета, и использует три цвета.

Доказательство. Предположим что решения (по Лемме 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 ([pic] дает ограничение 0([pic]).

[]

Теорема 4.48 устанавливает границу общего числа решений маршрутизации

необходимого для обработке каждого пакета, но не полагается не любой

практический алгоритм с помощью которого эти решения принимаются. Метод

маршрутизации использованный в T может быть схемой маршрутизации деревьев

Санторо и Кхатиба, но так же возможно применить принцип кластеризации к T

тем самым уменьшив число решений маршрутизации даже больше.

Теорема 4.49 [LT86) Для каждой сети из N узелs и каждого положительного

целого числа f ( log N существует метод маршрутизации который требует не

более чем O(f N1/f) решений маршрутизации для каждого пакета, и использует

2f + 1 цветов.

Доказательство. Доказательство подобно доказательству теоремы 4.48, но

вместо выбора s([pic] конструирование применяется рекурсивно к дереву 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, если нет сообщения принятого от этого

соседа. Можно ли модифицировать алгоритм таким образом? Что случиться со

сложностью алгоритма?

Упражнение 4.3 Докажите что следующее утверждение является инвариантом

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

(u, w : ( Mwu ( d(w, vo) ( d

(( u : d(u, vo) ( Du[vo]

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

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

Раздел 4.3

Упражнение 4.4 Дайте значения всех переменных терминального состояния

алгоритма Netchange когда алгоритм применяется к сети со следующей

топологией:

[pic]

После того как терминальное состояние достигнуто, добавляется канал между

A и F. Какое сообщение F пошлет к A когда обработает уведомление ? Какие сообщения A пошлет после получения сообщений от F?

Раздел 4.4

Упражнение 4.5 Дайте пример демонстрирующий что Лемма 4.22 не имеет силу

для сетей с ассиметричной стоимостью каналов.

Упражнение 4.6 Существует ли ILS которая использует не все каналы для

маршрутизации? Она применима? Она оптимальна?

Упражнение 4.7 Дайте граф G и дерево T поиска в глубину графа G такие что

G имеет N = n2 узлов, диаметр G и глубина T – 0(n), и существуют узлы

u и v такие что пакет от u к v доставляется за N — 1 переходов схемой

ILS поиска в глубину. (Граф может быть выбран таким образом что G

непланарный, что предполагает (по Теореме 4.37) что G действительно имеет

оптимальную ILS.)

Упражнение 4.8 Дайте схему ILS поиска в глубину для кольца из N узлов.

Найдите узлы u и v такие что d(u, v) = 2, и схема использует N — 2

переходов для передачи пакета от u к v.

Раздел 4.5

Упражнение 4.9 Докажите что минимальность дерева T в доказательстве Теоремы

4.48 предполагает что оно имеет не более чем m листьев. Докажите что любое

дерево с m листьями имеет не более чем m — 2 узлов ветвления.

5 Беступиковая коммутация пакетов

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

сохраняться в каждом узле перед тем, отправлением к следующему узлу на пути

к адресату. Каждый узел сети для этой цели резервирует некоторый буфер.

Поскольку количество буферного места конечно в каждом узле, могут

возникнуть ситуации, когда никакой пакет не может быть послан потому, что

все буферы в следующем узле заняты, как иллюстрируется Рисунком 5.1. Каждый

из четырех узлов имеет буфера B, каждый из которых может содержать точно

один пакет. Узел s послал t B пакетов с адресатом v, и узел v послал u B

пакетов с адресатом s. Все буфера в u и v теперь заняты, и, следовательно,

ни один из пакетов, сохраненных в t и u не может быть послан к адресату.

Ситуации, когда группа пакетов никогда не может достигнуть их адресата,

потому что они все ждут буфера, в настоящее время занятого другим пакетом в

группе, называются как тупики с промежуточным накоплением. (Другие типы

тупика будут кратко рассмотрены в конце этой главы.) Важная проблема в

проектировании сетей с пакетной коммутацией - что делать с тупиками с

промежуточным накоплением. В этой главе мы разберем несколько методов,

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

избежать возможности тупиков с промежуточным накоплением, вводя

ограничения на то, когда пакет может быть сгенерирован или послан. Методы

избежания тупиков с промежуточным накоплением найдены в сетевом уровне

модели OSI (Подраздел 1.2.2).

[pic]

Figure 5.1 Пример тупика с промежуточным накоплением.

Два вида методов, которые мы рассмотрим, базируются на структурированных и

неструктурированных буферных накопителях.

Методы, использующие структурированные буферные накопители (Раздел 5.2)

идентифицируют для узла и пакета специфический буфер, который должен быть

использован, если пакет генерируется или принимается. Если этот буфер

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

буферные накопители (Раздел 5.3) все буфера равны; метод только

предписывает, может или нет пакет быть принят, но не определяет, в который

буфер он должен быть помещен. Некоторые нотации и определения

представляются в Разделе 5.1, и мы закончим главу обсуждением дальнейших

проблем в Разделе 5.4.

5.1 Введение

Как обычно, сеть моделируется графом G = (V, E); расстояние между узлами

измеряется в переходах. Каждая вершина имеет B буферов для временного

хранения пакетов. Множество всех буферов обозначается B, и символы b, c,

bu, и т.д., используются для обозначения буферов.

Обработка пакетов узлами описывается с помощью трех типов перемещений,

которые могут происходить в сети.

Генерация. Вершина u "создает" новый пакет p (на самом деле, принимая пакет

от протокола более высокого уровня) и размещает его в пустом буфере в u.

Вершина u в таком случае называется источником пакета p.

Продвижение. Пакет p продвигается от вершины u в пустой буфер следующей в

его маршруте вершины w (маршрут определяется, используя алгоритмы

маршрутизации). В результате передвижения буфер, прежде занятый p

становится пустым. Хотя контроллеры, которые мы определим, могут запретить

передвижения, предполагается, что сеть всегда позволяет это движение, т.е.,

если контроллер его не запрещает, то оно применимо.

В системах с синхронной передачей сообщений это перемещение, как легко

видно, является одиночным переходом, как в Определении 2.7. В системах с

асинхронной передачей сообщений, перемещение - не один переход, как в

Определении 2.6, но оно может быть выполнено, например, следующим образом.

Узел u неоднократно передает p к w, но не отбрасывает пакет из буфера, пока

не получено подтверждение. Когда узел w получает пакет, он решает, примет

ли он пакет в одном из буферов. Если примет, пакет помещается в буфер, и

посылается подтверждение u, иначе пакет просто игнорируется. Конечно, могут

быть разработаны более эффективные протоколы для выполнения таких

перемещений, например те, где u не передает p, пока u не уверен, что w

примет p. В любом случае перемещение состоит из нескольких переходов типа

упомянутых в Определении 2.6, но в целях этой главы оно будет

рассматриваться как одиночный шаг.

(3) Выведение. Пакет p, занимающий буфер в вершине назначения, удаляется из

буфера. Предполагается, что сеть всегда позволяет это передвижение.

Обозначим через P множество всех путей, по которым следуют пакеты. Это

множество определяется алгоритмами маршрутизации (см. Главу 4); как это

делается, нас здесь не интересует. Пусть k - количество переходов в самом

длинном пути в P. Это не предполагает, что k равен диаметру G; k может

превосходить диаметр, если алгоритм маршрутизации не выбирает кратчайшие

пути, и k может быть меньше диаметра, если все коммуникации между узлами

происходят на ограниченных дистанциях.

Как видно из примера, данного в начале этой главы, тупики могут возникнуть,

если разрешены произвольные перемещения (исключая тривиальное ограничение,

что u должна иметь пустой буфер, если в u генерируется пакет и w должна

иметь пустой буфер, если пакет продвигается в w). Теперь мы определим

контроллер как алгоритм, разрешающий или запрещающий различные движения в

сети в соответствии со следующими требованиями.

(1) Выведение пакета (в месте его назначения) всегда позволяется.

(2) Генерация пакета в вершине, в которой все буферы пустые, всегда

позволяется.

(3) Контроллер использует только локальную информацию, т.е., решение, может

ли пакет быть принят в вершине u, зависит только от информации, известной u

или содержащейся в пакете.

Второе требование исключает тривиальное решение избежания заблокированных

пакетов (см. Определение 5.2), отказываясь принимать какие-либо пакеты в

сети. Как в Главе 2, пусть Zu обозначает множество состояний вершины u, и

M - множество возможных сообщений (пакетов).

Определение 5.1 Контроллер для сети G = (V, E)-набор пар con={Genu, Foru}u(

V , где Genu ( Zu ( M и Foru ( Zu ( M. Если cu ( Zu - состояние u, где все

буферы пусты, то для всех p ( M, (cu, p) ( Genu.

Контроллер con позволяет генерацию пакета p в вершине u, где состояние u -

cu, тогда и только тогда, когда (cu, p) ( Genu, и позволяет продвижение

пакета p из u в w тогда и только тогда, когда (cw, p) ( Forw. Формальное

определение контроллера не включает условия для выведения пакетов, потому

что выведение пакета (в его месте назначения) всегда позволено.

Передвижения сети под управлением контроллера con - это только те

передвижения сети, которые разрешены con.

Пакет в сети в тупике, если он никогда не может достигнуть своего места

назначения ни в какой последовательности передвижений.

Определение 5.2 Дана сеть G, контроллер con для G, и конфигурация ( G,

пакет p (возникающий в конфигурации () в тупике, если не существует

последовательности передвижений под управлением con, применимой в (, в

которой p выводится. Конфигурация называется тупиковой, если она содержит

пакеты в тупике.

Как показывает пример на Рисунке 5.1, тупиковая ситуация существует для

всех контроллеров. Задача контроллера в том, чтобы не позволить сети войти

в такую конфигурацию. Начальная конфигурация сети - конфигурация, когда в

сети нет пакетов.

Определение 5.3 Контроллер беступиковый, если под управлением этого

контроллера из начальной ситуации не достижима ни одна тупиковая.

5.2 Структурированные решения

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

буферные графы, представленные Merlin и Schweitzer [MS80a]. Идея этих

буферных графов базируется на наблюдении, что (при отсутствии контроллера)

тупик обусловлен ситуацией циклического ожидания. В ситуации циклического

ожидания есть последовательность p0, ..., ps -1 пакетов, таких, что для

каждого i, pi хочет передвинуться в буфер, занятый pi+1 (индексы считаются

modulo s). Циклическое ожидание избегается продвижением пакетов вдоль путей

в ациклическом графе (буферном графе). В Подразделе 5.2.1 будут определены

буферные графы и связанный с ними класс контроллеров, а также представлены

два простых примера буферных графов. В подразделе 5.2.2 будет дана более

запутанная конструкция буферного графа, снова с двумя примерами.

5.2.1 Буферные Графы

Пусть дана сеть G с множеством буферов B.

Определение 5.4 Буферный граф (для G, B) - направленный граф BG на буферах

сети, т.е., BG = (B, [pic]), так, что

(1) BG - ациклический (не содержит прямых циклов);

(2) Из bc ( [pic] следует, что b и c - буферы одной и той же вершины, или

буферы двух вершин, соединенных каналом в G; и

(3) для каждого пути P ( P существует путь в BG, чей образ (см. ниже)-P.

Второе требование определяет отображение путей в BG на пути в G; если

b0, b1, ..., bs - путь в BG, то, если u- вершина, в которой располагается

буфер bi, u0, u1,..., us - последовательность вершин таких, что для каждого

i < s либо uiui+1 ( E, либо ui = ui+1. Путь в G, который получается из этой

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

образом исходного пути b0, b1,..., bs в BG.

Пакет не может быть помещен в произвольно выбранный буфер; он должен быть

помещен в буфер, из которого он еще может достигнуть своего места

назначения через путь в BG, т.е., буфер, подходящий для пакета в

соответствии с определением.

Определение 5.5 Пусть p - пакет в вершине u с пунктом назначения v. Буфер b

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18