ref (664672), страница 15

Файл №664672 ref (Распределенные алгоритмы) 15 страницаref (664672) страница 152016-07-312016-07-31СтудИзба

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Регистрация/авторизация

Текст из файла (страница 15)

Теорема 4.13 Алгоритм Чанди и Мизра вычисляет таблицы маршрутизации с минимальным количеством шагов с помощью обменов 0(N²) сообщениями (N²W) бит на канал, и 0(N²|E|) сообщений и 0(N² |E| W) бит всего.

Преимущество алгоритма Чанди и Мизра над алгоритмом Мерлина и Сигалла в его простоте, его меньшей пространственной сложности, и его меньшей временной сложности.

4.3 Алгоритм Netchange

Алгоритм Таджибнаписа Netchange [Taj77] вычисляет таблицы маршрутизации которые удовлетворяют мере "минимальное количество шагов". Алгоритм подобен алгоритму Чанди-Мизра , но содержит дополнительную информацию которая позволяет таблицам только частично перевычисляться после отказа или восстановления канала. Представление алгоритма в этой части придерживается Лампорта [Lam82]. Алгоритм основан на следующих предположениях.

Nl. Узлы знают размер сети (N).

N2. Каналы удовлетворяют дисциплине FIFO.

N3. Узлы уведомляют об отказах и восстановлениях смежных к ним каналов.

N4. Цена пути – количество каналов в пути.

Алгоритм может управлять отказами и восстановлениями или добавлениями каналов, но положим что узел уведомляет когда смежный с ним канал отказывает или восстанавливается. Отказ и восстановление узлов не рассматривается: на самом деле отказ узла можно рассматриваться его соседями как отказ соединяющего канала. Алгоритм содержит в каждом узле u таблицу Nb_u [v], дающую для каждого пункт назначения v соседа u через которого u пересылает пакеты для v. Требования алгоритмов следующие:

Rl. Если топология сети остается постоянной после конечного числа топологических изменений , тогда алгоритм завершается после конечного числа шагов.

R2. Когда алгоритм завершает свою работу таблицы Nb_u[v] удовлетворяют

если v = u то Nb_u[v] = local ;
если путь из u в v  u существует то Nb_u[v] = w, где w первый сосед u в кротчайшем пути из u в v,
если нет пути из u в v тогда Nb_u[v] = udef.

4.3.1 Описание алгоритма

Алгоритм Таджибнаписа Netchange дан как алгоритмы 4.8 и 4.9. Шаги алгоритма будут сначала объяснены неформально, и, впоследствии правильность алгоритма будет доказана формально. Ради ясности моделирование топологических изменений упрощено по сравнению с [Lam82], примем, что уведомление об изменении обрабатывается одновременно двумя узлами задействованными изменениями. Это обозначено в Подразделе 4.3.3, как асинхронная обработка.

Выбор соседа через которого пакеты для v будут посылаться основан на оценке расстояния от каждого узла до v. Предпочитаемый сосед всегда сосед с минимальной оценкой расстояния. Узел u содержит оценку d(u, v) в D_u[v] и оценки d(w, v) в ndis_u[w, v] для каждого соседа u. Оценка D_u[v] вычисляется из оценок ndis_u[w, v], и оценки ndis_u[w,v] получены посредством коммуникаций с соседями.

Вычисление оценок D_u[v] происходит следующим образом. Если u = v тогда d(u, v) = 0 таким образом D_u[v] становится 0 в этом случае. Если u v, кротчайший путь от u в v (если такой путь существует) состоит из канала из u до сосед, присоединенного к кратчайшему пути из сосед до v, и следовательно d(u, v) = 1 + min d(w, v).

^w^^{Neigh u}

Исходя из этого равенства, узел u v оценивает d(u, v) применением этой формулы к оценочным значениям d(w, v), найденным в таблицах ndis_u[w, v]. Так как всего N узлов, путь с минимальным количеством шагов имеет длину не более чем N—1 . Узел может подозревать что такой путь не существует если оцененное расстояние равно N или больше; значение N используется для этой цели.

var Neigh_u : множество узлов ; (* Соседи u *)

D_u : массив 0.. N ; (* D_u[v] - оценки d(u, v) *)

Nb_u : массив узлов ; (* Nb_u[v]- предпочтительный сосед для v *)

ndis_u : массив 0.. N ; (*ndis_u[w, v] - оценки d(w. v) *)

Инициализация:

begin forall w  Neigh_u, v  V do ndis_u[w, v] := N ,

forall v  V do

begin D_u[v] := N ;

Nb_u[v] := udef

end ;

D_u[u]:= 0 ; Nb_u[u] := local ;

forall w  Neigh_u do послать < mydist, u, 0> к w

end

процедура Recompute (v):

begin if v = u

then begin D_u[v]:= 0 ; Nb_u[v] := local end

else begin (* оценка расстояния до v *)

d := 1 + min{ ndis_u[w, v] : w  Neigh_u} ;

if d < N then

begin D_u[v] := d ;

Nb_u[v] := w with 1 + ndis_u[w, v] = d

end

else begin D_u[v] := N ; Nb_u[v] := udef end

end;

if D_u[v] изменилась then

forall x  Neigh_u do послать < mydist, v, D_u[v]> к x

end

Алгоритм 4.8 Алгоритм Netchange (часть I, для узла u).

Алгоритм требует чтобы узел имел оценки расстояний до v своих соседей. Их они получают от этих узлов послав им сообщение следующим образом. Если узел u вычисляет значение d как оценку своего расстояния до v (D_u[v] = d), то эта информация посылается всем соседям в сообщении < mydist ,v,d>. На получение сообщения v, d> от соседа w, u означивает ndis_u[w, v] значением d. В результате изменения ndis_u[w, v] оценка u расстояния d(u, v) может измениться и следовательно оценка перевычисляется каждый раз при изменении таблицы ndis_u . Если оценка на самом деле изменилась то, на d' например, происходит соединение с соседями используя сообщение <mydist, v, d'>.

Алгоритм реагирует на отказы и восстановления каналов изменением локальных таблиц, и посылая сообщение если оценка расстояния изменилась. Мы предположим что уведомление которое узлы получают о падении или подъеме канала (предположение N3) представлено в виде сообщений < fail,. > и <repair, . >. Канал между узлами u₁ и u₂ смоделирован двумя очередями, Q u₁ u₂ для сообщений от u₁ к u₁ и Q u₂ u₁ для сообщений из u₂ в u₁. Когда канал отказывает эти очереди удаляются из конфигурации (фактически вызывается потеря всех сообщений в обоих очередях) и узлы на обоих концах канала получают сообщение < fail, . > . Если канал между u₁ и u₁ отказывает, u₁ получает сообщение < fail, u₂ > и u₂ получает сообщение < fail, u₁ > . Когда канал восстанавливается (или добавляется новый канал в сети) две пустые очереди добавляются в конфигурацию и два узлы соединяются через канал получая сообщение < repair, . > . Если канал между u₁ и u₂ поднялся u₁ получает сообщение< repair, u₂ > и u₂ получает сообщение < repair, u₁ > .

Обработка сообщения <mydist,v,d> от соседа w:

{ <mydist,v,d> через очередь Qwv}

begin получить <mydist,v,d> от w;

ndis_u[w,v] := d ; Recompute (v)

end

Произошел отказ канала uw:

begin получить < fail, w> ; Neigh_u := Neigh_u \ {w} ,

forall v  V do Recompute (v)

end

Произошло восстановление канала uw:

begin получить < repair, w> , Neigh_u := Neigh_u  {w} ;

forall v  V do

begin ndis_u[w, v] := N;

послать < mydist, v, D_u{[v]> to w

end

Алгоритм 4.9 АЛГОРИТМ NETCHANGE (часть 2, для узла и).

Реакция алгоритма на отказы и восстановления выглядит следующим образом. Когда канал между u и w отказывает, w удаляется из Neigh_u и наоборот. Оценка расстояния перевычисляется для каждого пункта назначения и, конечно, рассылается всем существующим соседям если оно изменилось. Это случай если лучший маршрут был через отказавший канал и нет другого соседа w' с ndis_u[w', v]= ndis_u[w, v]. Когда канал восстановлен(или добавлен новый канал) то w добавляется в Neigh_u, но u имеет теперь неоцененное расстояние d(w, v) (и наоборот). Новый сосед w немедленно информирует относительно D_u[v] для всех пунктов назначения v (посылая сообщения<mydist,v, D_u[v]> ). До тех пор пока u получает подобное сообщения от w, u использует N как оценку для d(w,v), т.е., он устанавливает ndis_u[w, v] в N.

P(u, w, V)

up(u, w)  w  Neigh_u (1)

 up(u, w)  Q_wu содержит сообщение <mydist,v,d> 

последнее такое сообщение удовлетворят d = D_u[v] (2)

 up(u, w)  Q_wu не содержит сообщение <mydist,v,d> 

ndis_u[w, v] =D_w [v] (3)

L(u, v) 

u = v  (D_u[v] = 0  Nb_u[v] = local) (4)

 (u  v) w  Neigh_u : ndis_u[w, v] < N - 1)

( D_u[v] = 1 + min ndis_u[w, v] = 1 + ndis_u[Nb_u[v], v]) (5)

^w^^{Neigh u}

 (u  v  w  Neigh_u : ndis_u[w, v] N—1) 

(D_u[v] = N  Nb_u[v] = udef) (6)

Рисунок 4.10 Инварианты P(u, w, v) и L(u, v).

Инварианты алгоритма Netchange. Мы докажем что утверждения являются инвариантами; утверждения даны на Рисунке 4.10. Утверждение P(u, w, v) констатирует что если u закончил обработку сообщения v, .> от w то оценка u расстояния d(w,v) эквивалентна оценке w расстояния d(w, v). Пусть предикат up(u, w) истинен тогда и только тогда когда (двунаправленный) канал между u и w существует и действует. Утверждение L(u, v) констатирует что оценка u расстояния d(u, v) всегда согласована с локальными данными u, и Nb_u[v] таким образом означен.

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

stable = u, w : up(u, w)  Q_wu не содержит сообщений .

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

(1) Получение сообщения <mydist, .,.> . Первое выполнение результирующего кодового фрагмента, как принято, выполняется автоматически и рассматривается отдельным переходом. Обратите внимание что в данном переходе принимается сообщение и возможно множество сообщений отправляется

(2) Отказ канала и обработка сообщения < fail. . > узлами на обоих концах канала.

(3) Восстановление канала и обработка сообщения <repair. . > двумя соединенными узлами.

Лемма 4.14 Для всех u_o, w_o, и v_o, P(u_o, w_o, v_o) –– инвариант.

Доказательство. Изначально, т.e., после выполнения инициализационной процедуры каждым узлом, (1) содержится предположением. Если изначально мы имеем up(u_o, wo), (2) и (3) тривиально содержатся. Если изначально мы имеем up(u_o, w_o), тогда ndis_uo[w_o, v_o] = N. Если w_o = v_o то D_wo[wo] = 0 но сообщение < mydist, v_o, 0> в Q_w0u0, таким образом (2) и (3) истинны. Если w_o  v_o то D_w0[v_o]=N и нет сообщений в очереди, что также говорит что (2) и (3) содержаться. Мы рассмотрим три типа констатированных переходов упомянутых выше.

Тип (1). Предположим что u получает сообщение <mydist,v,d> от w. Следовательно нет топологических изменений и нет изменений в множестве Neigh , следовательно (1) остается истинно. Если vv_o то это сообщение не меняет ничего в P(u_o, w_o, v_o). Если v = v_o, u =u_o, и w=w_o значение ndis_u,[w_o, v_o] может изменится. Однако, если сообщение < mydist, v_o, .> остается в канале значение этого сообщения продолжает удовлетворять (2), так как (2) в сохранности то и (3) также потому что посылка ложна. Если полученное сообщение было последним этого типа в канале то d = D_w0[vo] по (2), которое подразумевает что заключение (3) становится истинным и (3) в сохранности. Посылка (2) становится ложной, таким образом (2) в сохранности. Если v = v_o, u = w_o (и u_o сосед u) заключение (2) или (3) может быть ложно если значение D_w0[v_o] изменилось в следствие выполнения Recompute(v) в w_o. В этом случае, однако, сообщение < mydist, v_o, . > с новым значением посылается к u_o, которое подразумевает что посылка (3) нарушена, и заключение (2) становится истинным, таким образом (2) и (3) сохранены. Это происходит и в случае когда сообщение < mydist, v_o, . > добавляется в Q_w0u0, и это всегда удовлетворяет d = D_w0[v_o]. Если v = v_o и uu_o, w_o ничего не изменяет в P(u_o, w_o, v_o).

Тип (2). Предположим что канал uw отказал. Если u = u_o и w = w_o этот отказ нарушил посылку (2) и (3) таким образом эти правила сохранены. (1) в безопасности потому что w_o удалился из Neigh_u0 и обратно. Нечто произойдет если u = w_o и w = u_o. Если u = w_o но w u_o заключение (2) или (3) может быть нарушено так как значение D_w0 [v_o] изменилось. В этом случае пересылка сообщения < mydist, v_o, . > узлом w_o опять нарушит посылку (3) и сделает заключение (2) истинным, следовательно (2) и (3) в безопасности. Во всех других случаях нет изменений в P(u_o, w_o, v_o).

Тип (3). Предположим добавление канала uw. Если u = u_o и w = w_o то up(v_o,w_o) истинно, но добавлением w_o в Neigh_u0 (и обратно) это защищает(1). Посылка < mydist, v_o, D_w0 [v_o]> узлом w_o делает заключение (2) истинным и посылку (3) ложной, таким образом P(u_o, w_o, v_o) обезопасен. Во всех других случаях нет изменений в P(u_o, w_o, v_o).



Лемма 4.15 Для каждого u_q и v_o, L(u_o, v_o) –инвариант.

Доказательство. Изначально D_u0[uo] = 0 и Nb_u[u_o] = local. Для v_o u_o , изначально ndis_u[w, v_o] = N для всех w  Neigh_u, и D_u0[v_o] = N и Nb_u0[vo] = udef.

Тип (1). Положим что u получил сообщение < mydist, v,d> от w. Если u u_o или v v_o нет переменных упомянутых изменениях L(u_o, v_o) . Если u = u_o и v = v_o значение ndis_u[w, v_o] меняется, но D_u0 [v_o] и Nb_u0[v_o] перевычисляется точно так как удовлетворяется L(v_o, v_o).

Тип (2). Положим что канал uw отказал. Если u = u_o или w = u_o то Neigh_u0 изменился, но опять D_u0[v_o] и Nb_u0[v_o] перевычисляются точно так как удовлетворяется L(u_o, v_o).

Тип (3). Положим что добавлен канал uw . Если u = u_o то изменилсяNeigh_u0 добавлением w, но так как u устанавливает ndis_u0[w, v_o] в N это сохраняет L(u_o, v_o).

4.3.2 Корректность алгоритма Netchange

Должны быть доказаны два требования корректности.

Теорема 4.16 Когда достигнута стабильная конфигурация, таблицы Nb_u[v] удовлетворяют :

(1) если u = v то Nb_u[v] = local;

(2) если путь от u до v u существует то Nb_u[v] = w, где w первый сосед u на кратчайшем пути от u до v;

(3) если нет путь от u до v не существует то Nb_u[v] = udef.

Доказательство. Когда алгоритм прекращает работу, предикат stable добавляется к P(u,w,v) для всех u, v, и w, и это подразумевает что для всех u, v, и w

up(u, w)  ndis_u[w, v] = D_w[v]. (4.2)

Применив также L(u, v) для всех u и v мы получим

0 если u  v

D_u [v] =  1+ min D_w[v] если u v w  Neigh_u : D_w[v] < N -1

N ^w^^{Neigh u} если uv w  Neigh_u : D_w[v] N -1

(4.3)

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

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

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

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

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

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

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

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

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

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

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

и функцию f

f() = (t_o, t₁,..., t_N)

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

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

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

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

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

Случай 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; следовательно таблицы требуют (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

[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 \[a_w,b_w) = [b_w,a_w). []

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

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

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

_uw = 

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

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

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

if d = l_u

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

else begin выбрать _i, т.ч. d  [_i, _i+1) ;

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

end

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

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

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

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

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

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

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

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

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

d_T(u, v)  d_T(u, w_o) + d_T(w_o,v)

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

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

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

[]

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

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

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

(2) Трафик сосредоточен в дереве,(может произойти перегрузка).
(3)Каждый отказ канала делит сеть.
4.4.2 Интервальная маршрутизация
Ван Ливен и Тэн [LT87] расширили схему разметки деревьев до сетей не являющихся деревьями таким образом что каждый канал используется для передачи пакета.
Определение 4.23 Схема разметки деревьев (ILS)для сети это
(1) обозначение различными метками из Z_N узлов сети, и,

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

Алгоритм интервальной маршрутизации предполагает что 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] помечены числами из [l_w, ,l_w+|T[w]|). Обозначим k_w = l_w+ |T[w]|.
(2) Метку ребра uw в узле u обозначим _uw.

Если uw ребро ветви то _uw = l_w

Если w сын u (в T) то _uw = l_w

Если w отец u то _uw = k_u если k_u  N и u имеет ветвь к корню. (В последней ситуации, ребро ветви помечаем 0 в u по правилу (a),таким образом означивание метки k_u нарушило бы требование что все метки различны. Метки считаются по модулю N, т.е. N 0.)

Если w отец u, u имеет ветвь к корню, и k_u  N, тогда _uw = l_w.

Все примеры поиска в глубину ILS даны на Рисунке 4.15. Заметим что все ребра ветвей помечены по правилу (2a), ребра к отцам узлов 4, 8, и 10 помечены по правилу (2c), и ребро к отцу узла 9 помечено по правилу (2d).
Теперь покажем верность схемы обхода в глубину ILS . Заметим что vT[u]  l_v  [l_u, k_u). Следующие три леммы относятся к ситуации когда узел u передает пакет с пунктом назначения v к узлу w (соседу u) используя Алгоритм 4.13. Это подразумевает что l_v  [uw, ) для некоторой метки  в u, и что нет метки ’_uw в узле u такой что '  [_uw,, l_v).

Рисунок 4.15 Интервальная разметка поиском в глубину.
Лемма 4.28 Если l_u > l_v то l_w < I_u
Доказательство. Во-первых, рассмотрим случай _uw  l_v. Узел w не сын u потому что в этом случае _uw = l_w > l_u > l_v .Если uw ветвь то также l_w = _uw < l_v < l_u. Если _w отец u то l_w < l_u выполняется в любом случае. Во-вторых, рассмотрим случай когда _uw – наибольшая метка ребра в u, и нет метки '  l_v (т.е., l_v – нижняя граница нелинейного интервала). В этом случае ребро к отцу u не помечено 0, но имеет метку k_u (потому что 0 l_v, и нет метки '  l_v). Метка k_u – наибольшая метка в данном случае; ребро к сыну или ветви вниз w' имеет _uw’ = l_w’ < k_u, и ветвь к предком w' имеет _uw’ = l_w’ < l_u Таким образом w – отец u в данном случае, что подразумевает 1_w < l_u. []
Следующие две леммы относятся к случаю когда l_u < l_v. Мы выведем что каждый v  T[u] или l_v > k_u, и в последнем случае k_u < N имеет силу так что ребро к отцу u помечено k_u.

Рисунок 4.16 МАРШРУТИЗАЦИЯ ПАКЕТОВ ДЛЯ V В СХЕМЕ РАЗМЕТКИ ILS.
Лемма 4.29 Если l_u _v то l_w  l_v.
Доказательство. Во-первых, рассмотрим случай когда v  T[u]; пусть w' сын u такой что vT[w’]. Мы имеем _uw’ = l_w'  l_v и это подразумевает что _uw’ _uwl_v < k_w’. Мы вывели что w не является отцом u, следовательно 1_w = _uw, что подразумевает l_w < l_v.
Во-вторых, рассмотрим случай когда l_v  k_u. В этом случае w отец u, это можно показать следующим образом. Ребро к отцу помечено k_u, и k_u  l_v. Ребро к сыну w' узла u помечено 1_w’ < k_u, ребро к ветви вниз w' помечено 1_w’ _u, и ребро ветви вверх w' помечено 1_w’ < l_u. Поэтому w отец u, l_w < l_u < l_v. []
Нормфункция относящаяся к передаче в v может быть определена следующим образом. Наименьший общий предок двух узлов u и v это наименьший узел в дереве который отец u и v. Пусть lca(u, v) означает метку наименьшего общего предка u и v, и определим
f_v(u) = (-lca(u, v), 1_u).
Лемма 4.30 Если l_u < l_v то f_v(w) < f_v(u).
Доказательство. Во-первых рассмотрим случай когда v T[u], что подразумевает lca(u, v) = l_u. Если w' сын u такой что v  T[w’], мы имеем (как в предыдущей Лемме) что 1_w’  l_w < k_w’, следовательно w T[w'], что подразумевает lca(u, v)  l_w’ > l_u. Таким образом f_v(w) < f_v(u).
Во-вторых, рассмотрим случай что 1_v > k_u. Как в предыдущей лемме, w отец u, и поэтому vT[u], lca(w, v)= lca(u, v). Но теперь 1_w < l_u, таким образом f_v(w)< f_v(u). []
Может быть показано что каждый пакет достигает пункта назначения. Поток пакетов для v показан на Рисунке 4.16. Пусть пакет для v сгенерирован в узле u. По Лемме 4.28, метка узла уменьшается с каждым переходом, до тех пор пока, за конечное число шагов, пакет получен узлом w с 1_wl_v. Каждый узел к которому пакет пересылается после w также имеет метку l_v по лемме 4.29. За конечное число шагов пакет получает v, потому что с каждым шагом f_v уменьшается или пакет прибывает в 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 с l_u  0 существует ребро с пометкой 0, и в узле с пометкой 0 существует ребро с меткой 0 или 1. Это показывает что для сетей в общем виде качество методов маршрутизации плохое, но для некоторых классов специальной сетевой топологии качество схемы очень неплохое. Это делает метод процессорных сетей с регулярной структурой, которые используются для реализации параллельных вычислений с виртуальной общей разделяемой памяти.
Не известно точно как, для произвольной сети, лучшие схемы интервальной разметки сравниваются с оптимальными алгоритмами маршрутизации. Некоторые нижние границы длин путей, как подразумевают оптимальные ILS не всегда существуют, было дано Ружечкой(Ruzecka).

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

Рисунок 4.18 Оптимальная ILS для кольца
Теорема 4.33 Существует сеть для которой нет применимой схемы линейноинтервальной разметки
Доказательство. Рассмотрим граф-паук с тремя ногами длины 2, как нарисовано на Рисунке 4.17. Наименьшей матка (0) и наибольшей метка (6) означены два узла, и так как всего три ноги, существует(по крайней мере) одна нога которая не содержит ни меньшую ни большую метку. Пусть x будет первым узлом отцентра в этой ноге. Узел x передает пакета адресованные к 0 и 6 в центр, и единственный линейный интервал который содержит и 0 и 6 это полное множество Z_N . Следовательно, 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 через канал против часовой стрелке, что является оптимальным. []

Рисунок 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 = l_u
then обработать пакет локально
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 то 1_w расширяет l_u одним символом; т.е., если u₁, ..., u_k сын u в T то 1_ui = l_u_i где ₁, . . . , _k – k различных символов из .
(3) Если uw ветвь то _uw = l_w
(4) Если w сын u то _uw = l_w.

Если w отец uто _uw=  если u не имеет ветви к корню: в этом случае, _uw = l_w

В дереве PLS каждый узел исключая корень имеет канал помеченный , и этот канал соединяет узел с предком (отцом узла или корнем дерева). Заметим что для каждого канала uw, _uw = l_w или _uw = . Для всех u и v, v предок у тогда и только тогда когда l_v < l_u.
Нужно показать что пакет никогда не "вклинивается" в узел отличный от его пункта назначения, который, каждый узел отличный от пункт назначения может перенаправить пакет используя Алгоритм 4.20.
Лемма 4.42 Для всех узлоа u и vтаких что u  v существует канал в u помеченный префиксом l_v.
Доказательство. Если u не корень T то u имеет канал помеченный , который является префиксом l_v. Если u корень тогда v не является корнем, и v T[u] . Если w сын u такой что vT[w] то по построению a_uw  l_v. []
Следующие три леммы имеют отношение к ситуации когда узел u передает пакет для узла v к узлу w (соседу u) используя Алгоритм 4.20.
Лемма 4.43 Если u  T[v] то w предок u.
Доказательство. Если a_uv ==  то w предок u как упоминалось выше. Если a_uw = l_w то, так как a_uw l_v, также l_wl_v Это подразумевает что w предок v, и также u.[]
Лемма 4.44 Если u предок v то w предок v, ближе к v чем u.
Доказательство. Пусть w' будет сыном u таким что v  T[w'] тогда a_uw’ =l_w не пустой префикс l_v. Так как a_uw самый длинный префикс (в u) l_v, то a_uw’< a_uw < l_v, таким образом w предок v ниже u. []
Лемма 4.45 Если u T[v], то w предок v или d_T(w, v) < d_T(u, v).
Доказательство. Если a_uw = то w отец u или корень; отец u ближе к v чем u потому что u T[v], и корень – предок v. Если a_uw = l_w то , так как a_uw < l_v, 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 с диаметром D_G (измеренным в переходах) существует схема префиксной разметки которая доставляет все пакеты за не более чем 2D_G переходов.
Доказательство. Воспользуемся деревом 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 существует разбиение сети на кластера C₁,..., C_m такие что
(1) каждый кластер – связный подграф,
(2) каждый кластер содержит по крайней мере s узлов, и
(3) каждый кластер имеет радиус не более чем 2s.
Доказательство. Пусть D₁, ..., Dm будет максимальная коллекция разделенных связных подграфов таких что каждый D_i имеет радиус  s и содержит по крайней мере s узлов. Каждый узел не принадлежащий соединен с одним из подмножеств путем длиной не больше чем s, иначе муть может быть добавлен как отдельный кластер. Сформируеи кластеры С_i включением каждого узла не входящего в в кластер ближайший к нему. Расширенные кластеры остаются содержат по крайней мере s узлов каждый, они остаются связными и разделенными, и они имеют радиус не более чем 2s. []
Метод маршрутизации означивает цветом каждый пакет, и предполагается что используется только несколько цветов. Узлы теперь действуют следующим образом. В зависимости от цвета, пакет или отправляет немедленно по установленному каналу (соответствующему цвету) или вызывает более сложному решению. Это подразумевает, что узлы имеют различные протоколы для обработки пакетов.
Теорема 4.48 [LT86] For каждой сети из N узлов существует метод маршрутизации который требует не более чем 0( ) решений маршрутизации для каждого пакета, и использует три цвета.
Доказательство. Предположим что решения (по Лемме 4.47) даны и заметим что каждый C_i содержит узел c_i такой что d(v, c_i)  2s для каждого v  C_i потому что C_i имеет радиус не более чем 2s. Пусть T будет поддеревом минимального размера из G соединяющее все c_i. Так как T минимально то оно содержит не более чем m листьев, следовательно оно содержит не более чем m-2 узлов разветвлений (узлы степенью большей чем 2); см Упражнение 4.9. Рассмотрим узла T как центры ( c_i), узлы разветвлений, и узлы пути.
Метод маршрутизации сначала посылает пакет к центру c_i кластера источника (зеленая фаза), затем через T к центру c_j кластера пункта назначения (синяя фаза), и наконец внутри C_j к пункту назначения (красная фаза). Зеленая фаза использует фиксированному дерево стока для центра каждого кластера, и не решений маршрутизации. Узлы пути в 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 N^1/f) решений маршрутизации для каждого пакета, и использует 2f + 1 цветов.
Доказательство. Доказательство подобно доказательству теоремы 4.48, но вместо выбора s конструирование применяется рекурсивно к дереву T (оно кластер размера s). Дерево – связная сеть, по существу < 2m узлов потому что узлы пути в T только перенаправляют пакеты из одного фиксированного канала в другой, и может быть игнорирован.
Кластеризация повторяется f раз. Сеть G имеет N узлов. Дерево содержит после одного уровня кластеризации не более чем N/s центров и N/s узлов ветвления, т.е., N.(2/s) необходимых узлов. Если дерево полученное после i уровней кластеризации имеет m_i необходимых узлов, тогда дерево полученное после i +1 уровней кластеризации имеет не более чем m_i/s центров и m_i/s узлов ветвлений, т.е., m_i.(2/s) необходимых узлов. Дерево полученное после f уровней кластеризации имеет не более чем m_f = N.(2/s)^f необходимых узлов.
Каждый уровень кластеризации увеличивает количество цветов на два, следовательно с f уровнями кластеризации будут использоваться 2f+1 цветов. Не более чем 2m_f решений необходимо на самом высоком уровне, и s решений необходимо нв каждом уровне кластеризации в кластере пункта назначения, отсюда количество решений маршрутизации 2m_f + fs. Выбирая s 2N^1/f получим m_f = O(1), следовательно число решений маршрутизации ограничено
f s = O(f N^1/f). []
Использование приблизительно logN цветов приводит к методу маршрутизации которые требуют O(logN) решений маршрутизации.
Упражнения к Части 4
Раздел 4.1
Упражнение 4.1 Предположим что таблицы маршрутизации обновляются после каждого топологического изменения таким образом чтобы они были без циклов даже во время обновлений. Дает ли это гарантию что пакеты всегда обработаются даже когда сеть подвергается бесконечному числу топологических изменений ? Докажите что алгоритм маршрутизации может гарантировать доставку пакетов при продолжающихся топологических изменениях.
Раздел 4.2
Упражнение 4.2 Студент предложил пренебречь посылкой сообщения
< nys, w > из алгоритма 4.6; он аргументировал это тем что узел знает своего соседа и не сын в T_w, если нет сообщения <ys,w> принятого от этого соседа. Можно ли модифицировать алгоритм таким образом? Что случиться со сложностью алгоритма?
Упражнение 4.3 Докажите что следующее утверждение является инвариантом алгоритма Чанди-Мизра для вычисления путей до v_o (Алгоритм 4.7).
u, w : <mydist,v_o,d>  M_wu  d(w, v_o)  d
 u : d(u, v_o)  D_u[vo]
Дайте пример для которого число сообщений экспоненциально относительно
числа каналов сети.
Раздел 4.3
Упражнение 4.4 Дайте значения всех переменных терминального состояния алгоритма Netchange когда алгоритм применяется к сети со следующей топологией:

После того как терминальное состояние достигнуто, добавляется канал между A и F. Какое сообщение F пошлет к A когда обработает уведомление <repair, A> ? Какие сообщения A пошлет после получения сообщений от F?

Раздел 4.4
Упражнение 4.5 Дайте пример демонстрирующий что Лемма 4.22 не имеет силу для сетей с ассиметричной стоимостью каналов.
Упражнение 4.6 Существует ли ILS которая использует не все каналы для маршрутизации? Она применима? Она оптимальна?
Упражнение 4.7 Дайте граф G и дерево T поиска в глубину графа G такие что G имеет N = n² узлов, диаметр 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).

Figure 5.1 Пример тупика с промежуточным накоплением.
Два вида методов, которые мы рассмотрим, базируются на структурированных и неструктурированных буферных накопителях.
Методы, использующие структурированные буферные накопители (Раздел 5.2) идентифицируют для узла и пакета специфический буфер, который должен быть использован, если пакет генерируется или принимается. Если этот буфер занят, пакет не может быть принят. В методах, использующих неструктурные буферные накопители (Раздел 5.3) все буфера равны; метод только предписывает, может или нет пакет быть принят, но не определяет, в который буфер он должен быть помещен. Некоторые нотации и определения представляются в Разделе 5.1, и мы закончим главу обсуждением дальнейших проблем в Разделе 5.4.
5.1 Введение
Как обычно, сеть моделируется графом G = (V, E); расстояние между узлами измеряется в переходах. Каждая вершина имеет B буферов для временного хранения пакетов. Множество всех буферов обозначается B, и символы b, c, b_u, и т.д., используются для обозначения буферов.
Обработка пакетов узлами описывается с помощью трех типов перемещений, которые могут происходить в сети.
Генерация. Вершина 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, пусть Z_u обозначает множество состояний вершины u, и M - множество возможных сообщений (пакетов).
Определение 5.1 Контроллер для сети G = (V, E)-набор пар con={Gen_u, For_u}_u__V, где Gen_u  Z_u M и For_u Z_u M. Если c_u  Z_u - состояние u, где все буферы пусты, то для всех p  M, (c_u, p)  Gen_u.
Контроллер con позволяет генерацию пакета p в вершине u, где состояние u - c_u, тогда и только тогда, когда (c_u, p)  Gen_u, и позволяет продвижение пакета p из u в w тогда и только тогда, когда (c_w, p)  For_w. Формальное определение контроллера не включает условия для выведения пакетов, потому что выведение пакета (в его месте назначения) всегда позволено. Передвижения сети под управлением контроллера con - это только те передвижения сети, которые разрешены con.
Пакет в сети в тупике, если он никогда не может достигнуть своего места назначения ни в какой последовательности передвижений.
Определение 5.2 Дана сеть G, контроллер con для G, и конфигурация  G, пакет p (возникающий в конфигурации ) в тупике, если не существует последовательности передвижений под управлением con, применимой в , в которой p выводится. Конфигурация называется тупиковой, если она содержит пакеты в тупике.
Как показывает пример на Рисунке 5.1, тупиковая ситуация существует для всех контроллеров. Задача контроллера в том, чтобы не позволить сети войти в такую конфигурацию. Начальная конфигурация сети - конфигурация, когда в сети нет пакетов.
Определение 5.3 Контроллер беступиковый, если под управлением этого контроллера из начальной ситуации не достижима ни одна тупиковая.
5.2 Структурированные решения
Сейчас мы обсудим класс контроллеров, полагающихся на, так называемые, буферные графы, представленные Merlin и Schweitzer [MS80a]. Идея этих буферных графов базируется на наблюдении, что (при отсутствии контроллера) тупик обусловлен ситуацией циклического ожидания. В ситуации циклического ожидания есть последовательность p₀, ..., p_{s -1} пакетов, таких, что для каждого i, p_i хочет передвинуться в буфер, занятый p_i+1 (индексы считаются modulo s). Циклическое ожидание избегается продвижением пакетов вдоль путей в ациклическом графе (буферном графе). В Подразделе 5.2.1 будут определены буферные графы и связанный с ними класс контроллеров, а также представлены два простых примера буферных графов. В подразделе 5.2.2 будет дана более запутанная конструкция буферного графа, снова с двумя примерами.
5.2.1 Буферные Графы
Пусть дана сеть G с множеством буферов B.
Определение 5.4 Буферный граф (для G, B) - направленный граф BG на буферах сети, т.е., BG = (B, ), так, что
(1) BG - ациклический (не содержит прямых циклов);
(2) Из bc  следует, что b и c - буферы одной и той же вершины, или буферы двух вершин, соединенных каналом в G; и
(3) для каждого пути P  P существует путь в BG, чей образ (см. ниже)-P.
Второе требование определяет отображение путей в BG на пути в G; если
b₀, b₁, ..., b_s - путь в BG, то, если u- вершина, в которой располагается буфер b_i, u₀, u₁,..., u_s - последовательность вершин таких, что для каждого i < s либо u_iu_i+1  E, либо u_i = u_i+1. Путь в G, который получается из этой последовательности пропусканием последовательных повторений, называется образом исходного пути b₀, b₁,..., b_s в BG.
Пакет не может быть помещен в произвольно выбранный буфер; он должен быть помещен в буфер, из которого он еще может достигнуть своего места назначения через путь в BG, т.е., буфер, подходящий для пакета в соответствии с определением.
Определение 5.5 Пусть p - пакет в вершине u с пунктом назначения v. Буфер b в u подходит для p, если существует путь в BG из b в буфер c в v, чей образ - путь, которому p может следовать в G.
Один из таких путей в BG будет называться гарантированным путем и nb(p, b) обозначает следующий буфер на гарантированном пути. Для каждого вновь сгенерированного пакета p в u Существует подходящий буфер fb(p) в u.
Здесь fb и nb - аббревиатура первого буфера (first buffer) и следующего буфера (next buffer). Заметим, что буфер nb(p, b) всегда подходит для p. Во всех буферных графов, используемых в этом разделе, nb(p, b) располагается в вершине, отличной от той, где располагается b. Использование "внутренних" ребер в BG, т.е., ребер между двумя буферами одной вершины, обсудим позже.
Контроллер буферного графа. Буферный граф BG может быть использован для разработки беступикового контроллера bgc_BG , записывающий в каждый пакет буфер nb(p, b) и/или состояние вершины, где располагается p.
Определение 5.6 Контроллер bgc_BG определяется следующим образом.
Генерация пакета p в u позволяется тогда и только тогда, когда буфер fb(p) свободен. Сгенерированный пакет помещается в этот буфер.
Продвижение пакета p из буфера в u в буфер в w (возможно u = w) позволяется тогда и только тогда, когда nb(p, b) (в w) свободен. Если продвижение имеет место, то пакет p помещается в nb(p, b).
Theorem 5.7 Контроллер bgc_BG - беступиковый контроллер.
Доказательство. Если у вершины все буферы пусты, генерация любого пакета позволяется, откуда следует, что bgc_BG - контроллер.
Для каждого b  B, определим класс буфера b как длину самого длинного пути в BG , который заканчивается в b. Заметим, что классы буферов на пути в BG (а точнее, на гарантированном пути) строго возрастающие, т.е., класс буфера nb(p, b) больше, чем класс буфера b.
Т.к. контроллер позволяет размещение пакетов только в подходящих буферах и т.к. изначально нет пакетов, каждая достижимая конфигурация сети под управлением bgc_BG содержит пакеты только в подходящих буферах. С помощью индукции "сверху вниз" по классам буферов можно легко показать, что ни один буфер класса r не содержит в такой конфигурации тупиковых пакетов. Пусть R - самый большой класс буфера.
Случай r = R: Буфер b вершины u, имеющий самый большой из возможных классов, не имеет исходящих ребер в BG. Следовательно, пакет, для которого b - подходящий буфер, имеет пункт назначения u и может быть выведен, когда он попадает в буфер b. Значит, ни один буфер класса R не содержит тупиковых пакетов.
Случай r < R: Выдвинем гипотезу, что для всех r' таких, что r < r'  R, ни один буфер класса r' не содержит тупиковый пакет (в достижимой конфигурации).
Пусть  - достижимая конфигурация с пакетом p в буфере b класса r < R вершины u. Если u - место назначения p, то p может быть выведен и, следовательно, он не в тупике. Иначе, пусть nb(p, b) = c - следующий буфер на гарантированном пути b, и заметим, что класс r' буфера c превосходит r. По гипотезе индукции, c не содержит тупиковых пакетов, значит существует конфигурация , достижимая из , в которой c - пуст. Из  p может продвинуться в c, и, по гипотезе индукции, p не тупиковый в результирующей конфигурации  '. Следовательно, p в конфигурации  не в тупике.
Из доказательства видно, что если гарантированный путь содержит "внутренние" ребра буферного графа (ребра между двумя буферами одной вершины), то контроллер должен позволять дополнительные передвижения, с помощью которых пакет помещается в буфер той же вершины. Обычно гарантированный путь не содержит таких ребер. Они используются только для увеличения эффективности продвижения, например, в следующей ситуации. Пакет p размещается в буфере b₁ вершины u и буфер nb(p, b₁) в вершине w занят. Но существует свободный буфер b₂ в u, который подходит для p; более того, nb(p, b₂) в вершине w свободен. В таком случае, пакет может быть перемещен через b₂ и nb(p, b₂).
Сейчас рассмотрим два примера использования буферных графов, а именно, схема адресата(destination scheme) и схема сколько-было-переходов (hops-so-far scheme).
Схема адресата. Схема адресата использует N буферов в каждой вершине u, с буфером b_u[v] для каждого возможного адресата v. Вершина v называется цель буфера b_u[v]. Для этой схемы нужно предположить, что алгоритмы маршрутизации продвигают все пакеты с адресатом v по направленному дереву T_v , ориентированному по направлению к v. (На самом деле это предположение может быть ослаблено; достаточно, чтобы каналы, используемые для продвижения по направлению к v, формировали ациклический подграф G.)
Буферный граф определяется как BG_d = (B, ), где b_u[v₁]b_w[v₂]  тогда и только тогда, когда v₁ = v₂ и uw - ребро в T_v₁. Чтобы показать, что BG_d - ациклический, заметим, что не существует ребер между буферами с различными целями и, что буферы, с одинаковой целью v формируют дерево, изоморфное T_v. Каждый путь P  P с точкой назначения v - путь в T_v, и по построению существует путь в BG_d из буферов с целью v, чей образ - P. Этот путь выбирается в качества гарантированного. Это означает, что для пакета p с адресатом v, сгенерированного в вершине u, fb(p) = b_u[v], и, если этот пакет должен продвинуться в w, то nb(p,b) = b_w[v].
Определение 5.8 Контроллер dest определяется как bgc_BG , с fb и nb определенными как в предыдущем параграфе.
Theorem 5.9 Существует беступиковый контроллер для сети произвольной топологии, который использует N буферов в каждой вершине и позволяет проводить пакеты через произвольно выбранные деревья стока.
Доказательство. dest - беступиковый контроллер, использующий такое количество буферов. 
Как было отмечено ранее, требование маршрутизации по деревьям стока может быть ослаблено до требования того, что пакеты с одинаковыми пунктами назначения посылаются через каналы, которые формируют ациклический граф. Не достаточно, чтобы P содержало только простые пути, как это показано на примере, данном на Рисунке 5.2. Здесь пакеты из u₁ в v направляются через простой путь
 u₁, w₁, u₂, . . ., v , и пакете из u₂ в v посылаются через простой путь
 u₂, w₂, u₁, . . ., v .

Рисунок 5.2 маршрутизация, запрещенная для контроллера dest.
Каждый путь в P простой; набор всех каналов, используемых для маршрутизации пакетов в v содержит цикл  u₁, w₁, u₂, w₂, u₁,v . См. Упражнение 5.2.
Контроллер dest очень прост в использовании, но имеет недостаток - для каждой вершины требуется большое количество буферов, а именно N.
Схема сколько-было-переходов. В этой схеме вершина u содержит k +1 буфер
b_u[0], . . ., b_u[k]. Предполагается, что каждый пакет содержит счетчик переходов, показывающий, сколько переходов от источника сделал пакет.
Буферный граф определяется как BG_h = (B, ), где b_u[i] b_w[j]  тогда и только тогда, когда и uw  E. Чтобы показать, что BG_h ациклический, заметим, что индексы буферов строго возрастают вдоль ребер BG_h. Т.к. длина каждого пути в P не более k переходов, то существует соответствующий путь в буферном графе; если P = u₀, . .., u_l (l k), то b_u₀[0],b_u₁ [1],..., b_ul[l]-путь в BG_h с образом P. Этот гарантированный путь описывается так: fb(p) = b_u[0] (для p, сгенерированного в u) и
(p, b_u[i]) = b_w[i +1] для пакетов, которые должны быть продвинуты из u в w.
Определение 5.10 Контроллер hsf определяется как bgc_BGh , с fb и nb определенными в предыдущем параграфе.
Theorem 5.11 Существует беступиковый контроллер для сетей произвольной топологии, который использует D + 1 буфер в каждой вершине (где D - диаметр сети), и требует, чтобы пакеты пересылались по путям с минимальным числом переходов.
Доказательство. Использование путей с минимальным числом переходов дает k = D. Тогда hsf - беступиковый контроллер, использующий D +1 буфер в каждой вершине. (Количество буферов даже может быть меньше, если узлы, расположенные далеко друг от друга, не обмениваются пакетами.) 
В схеме сколько-было-переходов буферы с индексом i используются для хранения пакетов, которые сделали i переходов. Можно спректировать двойственная схема сколько-будет-переходов ( hops-to-go), в которой буферы с индексом i используются для хранения пакетов, которым надо сделать еще i переходов до места назначения; см. Упражнение 5.3.
5.2.2 Ориентации G
В этом подразделе будет рассматриваться метод для построения сложных буферных графов, требующих только несколько буферов на узел,. В контроллере hsf индекс буфера, в котором хранился пакет, увеличивался с каждым переходом. Теперь мы замедлим рост индекса буфера (таким образом экономя на общем количестве буферов в каждом узле), предполагая увеличение индекса буфера (не путать с классом буфера) с некоторыми, но не обязательно всеми, переходами. Чтобы избежать циклов в буферном графе, каналы, которые могут быть пересечены без увеличения индекса буфера, формируют ациклический граф.

Рисунок 5.3 Граф и ациклическая ориентация.
Определение 5.12 Ациклическая ориентация G - направленный ациклический граф, который получается ориентацией всех ребер G; см. Рисунок 5.3.
Последовательность G₁, ..., G_B ациклических ориентаций G является покрытием из ациклических ориентаций размера B для набора P путей, если каждый путь P  P может быть записан как конкатенация B путей P₁, ..., P_B, где P_i - путь в G_i.
Когда возможно покрытие из ациклических ориентаций размера B, может быть сконструирован контроллер, использующий только B буферов на вершину. Пакет всегда генерируется в буфере b_u[l] вершины u. Пакет из буфера b_u[i], который должен быть продвинут в вершину w помещается в буфер b_w [i], если дуга между u и w направлена к w в G_i , и в буфер b_w[i + 1], если дуга направлена к u в G_i.
Теорема 5.13 Если покрытие из ациклических ориентаций для P размера B существует, то существует беступиковый контроллер, использующий только B буферов на каждую вершину.
Доказательство. Пусть G₁. . .., G_B - покрытие, и b_u[1], ..., b_u[B] - буферы вершины u. Будем писать uw  , есди дуга uw направлена к w в G_i, и wu  , если дуга uw направлена к u в G_i. Буферный граф определяется как BG_a = (B, ), где b_u[i]b_w[j]  тогда и только тогда, когда uw  E и (i = j /\ uw  ) или (i + 1 = j /\ wu  ). Чтобы показать, что этот граф ациклический, отметим, что не существует циклов, содержащих буферы с различными индексами, потому что нет дуг от данного буфера к другому с меньшим индексом. Нет циклов с из буферов с одним и тем же индексом i , потому что эти буферы назначаются в соответствии с ациклическим графом G_i.
Оставляем читателю (см. Упражнение 5.4) продемонстрировать, что для каждого P  P существует гарантированный путь с образом P, и что такой путь описывается следующим образом:

Контроллер acoc = bgc_BG_a - беступиковый контроллер, использующий B буферов в каждой вершине, что доказывает теорему. 
Коммутация пакетов в кольце. Покрытия из ациклических ориентаций можно использованы при построении беступиковых контроллеров для нескольких классов сетей. Мы сначала представим контроллер для колец, использующий только три буфера на вершину. Для следующей теоремы предполагается, что веса каналов симметричны, т.е., w_uw =w_wu.
Теорема 5.14 Существует беступиковый контроллер для кольцевой сети, который использует всего три буфера на вершину и позволяет маршрутизировать пакеты через самые короткие пути.
Доказательство. Из Теоремы 5.13 достаточно дать покрытие из ациклических ориентаций размером 3 для набора путей, который включает самые короткие пути между всеми парами вершин.
Будем использовать следующую нотацию. Для вершин u и v, d_c(u, v) обозначает длину пути из u в v по часовой стрелке и d_a(u, v) - длина пути против часовой стрелки; d_c(v, u) = d_a(u, v) и d(u, v) = min(d_c(u, v), d_a(u, v)) выполняется. Сумма весом всех каналов называется C (периметр кольца) и очевидно d_c(u, v) + d_a(u, v) = C для всех u, v, так что d(u, v) C/2.

Рисунок 5.4 покрытие из ациклических ориентаций для кольца.
Во-первых рассмотрим простой случай, когда Существуют вершины u и v с d(u, v) = C/2. G₁ и G₃ получаются ориентацией всех ребер по направлению к v, и G₂ получается ориентацией всех ребер по направлению к u: см. Рисунок 5.4.
Самый короткий путь из u в v содержится в G₁ или G₃, и наименьший путь из v в u содержится в G₂. Пусть x, y - пара вершин, отличная от пары u, v. Тогда, т.к.
d(x, y)  C/2, то существует самый короткий путь P между x и y, который не содержит сразу и u, и v. Если P не сдержит ни u, ни v , то он полностью содержится либо в G₁ , либо в G₂. Если P содержит v , это конкатенация пути в G₁ и пути в G₂; если P содержит u, это конкатенация пути в G₂ и пути в G₃.
Если не существует пары u, v с d(u, v) = C/2, выберем пару, для которой d(u, v) как можно ближе к C /2. Теперь может быть показано, что если существует пара x, y такая, что нельзя найти самый короткий как конкатенацию путей в ориентациях покрытия, то d(x, y) ближе к C /2, чем d(u, v). 
Пакетная коммутация в дереве. Покрытия из ациклических ориентаций могут быть использованы для построения контроллера, использующего только два буфера на вершину, для сети в виде дерева.
Теорема 5.15 Существует беступиковый контроллер для сети в виде дерева, который использует только два буфера на вершину.
Доказательство. Из Теоремы 5.13, достаточно дать ациклическую ориентацию для дерева, которая покрывает все простые пути. Выберем произвольную вершину r, и получим T₁ ориентацией всех ребер по направлению к r и T₂ ориентацией всех ребер от r; см. Рисунок 5.5.

Рисунок 5.5 Покрытие из ациклических ориентаций для дерева.
Простой путь из u в v - конкатенация пути из u к самому нижнему общему предку, который T₁, и пути от самого меньшего общего предка к v, который в T₂. 
5.3 Неструктурированные решения
Теперь мы обсудим класс контроллеров, предложенных Toueg и Ullman [TU81]. Эти контроллеры не предписывают, в котором буфере должен быть помещен пакет и используют только простую локальную информацию типа счетчика переходов или числа занятых буферов в узле.
5.3.1 Контроллеры с прямым и обратным счетом
Контроллер с прямым счетом (forward-count controller). Пусть (для пакета p) s_p -количество переходов, которые ему необходимо сделать до места назначения; конечно же 0  s_p  k выполняется. Не всегда необходимо хранить s_p в пакете, т.к. многие алгоритмы маршрутизации хранят эту информацию в каждой вершине; см. например алгоритм Netchange Раздела 4.3. Для вершины u, f_u обозначает число пустых буферов в u. Конечно, 0  f_u B всегда выполняется.
Определение 5.16 Контроллер FC (Forward-count) принимает пакет p в вершине u тогда и только тогда, когда s_p< f_u.
Контроллер принимает пакет, если пустых буферов в вершине больше, чем количество переходов, которые нужно сделать пакету.
Теорема 5.17 Если B > k, то FC - беступиковый контроллер.
Доказательство. Чтобы показать, что в пустой вершине позволяется генерация пакета, заметим, что если все буферы вершины u пусты, f_u = B. Новому пакету нужно сделать не более k переходов, так что из B > k следует, что пакет принимается.
Отсутствие тупиков FC будет показано методом от противного: пусть  - достижимая конфигурация контроллера. Получим конфигурацию  , применяя к  максимальную последовательность из передвижений и выведения. В  ни один пакет не может двигаться, и, т.к.  - тупиковая конфигурация, то существует по крайней мере один пакет, оставшийся в сети в конфигурации. Пусть p - пакет в  с минимальным расстоянием до пункта назначения, т.е., s_p - наименьшее значение для всех пакетов в .
Пусть u - вершина, в которой размещается p. Т.к. u не является пунктом назначения p (иначе p мог бы быть выведен), то существует сосед w вершины u , в которую нужно продвинуть p. Т. к. это передвижение не позволяется FC, то
s_p-1 f_w
Из s_p k и из предположения k < B следует, что f_u < B, что обозначает, что в вершине w располагается как минимум один пакет (в конфигурации  ). Из пакетов в w, пусть q будет последним пакетом, принятым вершиной w, и пусть f'_w обозначает количество пустых буферов в w прямо перед принятием q вершиной w. Т.к. пакет q теперь занимает один из этих f'_w буферов и (из выбора q) все пакеты, принятые вершиной w после q были выведены из w, то
f'_w  f_w +1
Из принятие q вершиной w следует s_q < f'_w, и, комбинируя три полученных неравенства, получаем
s_q < f'_w  f_w +1 s_p,
что противоречит выбору p. 
Контроллер с обратным счетом (backward-count controller). Контроллер, " двойственный " FC , получается, когда решение, принимать ли пакет, основано на количестве шагов, которые пакет уже сделал. Пусть, для пакета p, t_p - количество переходов, которые он сделал от источника. Конечно, 0  t_p < k всегда верно.
Определение 5.18 Контроллер BC (Backward-Count) принимает пакет p в вершине u тогда и только тогда, когда t_p > k—f_u.
Доказательство того, что BC - беступиковый (Упражнение 5.6) очень похоже на доказательство Теоремы 5.17.
5.3.2 Контроллеры с опережающим и отстающим состоянием
Используя более детальную информацию относительно пакетов, находящихся в узле, может быть дан контроллер, который подобен контроллеру с прямым счетом, но позволяет большое количество передвижений.
Контроллер с опережающим состоянием (forward-state controller). Используем обозначение s_p как в предыдущем разделе. Для вершины u определим (как функцию состояния u) вектор состояния , где j - количество пакетов p в u с s_p = s.
Определение 5.19 Контроллер FS (Forward-State) принимает пакет p в вершине u с вектором состояния тогда и только тогда, когда
.
Теорема 5.20 Если B > k, то FS - беступиковый.
Доказательство. Оставляем читателю показать, что пустая вершина принимает все пакеты. Предположим, что существует достижимая тупиковая конфигурация , и получим конфигурацию  , применяя максимальную последовательность из продвижений и выведения. Ни один пакет не может передвигаться и по крайней мере один пакет остался в . Выберем пакет p с минимальным значением s_p, и пусть u -вершина, в которой располагается p и w - вершина, в которую p должен продвинуться. Пусть - вектор состояния вершины w в .
Если w не содержит пакетом, то , откуда следует, что w может принять p, что невозможно. Следовательно, w содержит по крайней мере один пакет; из пакетов в w, пусть q - пакет, расположенный ближе всего к пункту назначения, т.е., s_q = min{s : j_s > 0}. Покажем, что s_q < s_p, что является противоречием. Из пакетов в w, пусть r - тот, который был принят w позже всех, конечно, s_q  s_r выполняется. Пусть - вектор состояния w прямо перед принятием r. Из принятия r следует

Когда был вектором состояния w, r был принят вершиной w. После этого пакеты могли передвигаться из w, но все пакеты, принятые в w позже, чем r были выведены (из выбора r). Из этого следует

Но это означает, что

Характеристики

Тип файла

Документ

Размер

5,45 Mb

Материал

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

Тип материала

Реферат

Предмет

Информатика

Учебное заведение

Неизвестно

Список файлов реферата
raspredelennye-algoritmy-1469939296-45325.zip
ref.doc

Поделитесь ссылкой:

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

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

Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.

Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.

Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.

Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.

Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.

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

Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.

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

Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.

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