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

Определение 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' не содержит тупиковый пакет (в достижимой конфигурации).
Пусть g - достижимая конфигурация с пакетом p в буфере b класса r < R вершины u. Если u - место назначения p, то p может быть выведен и, следовательно, он не в тупике. Иначе, пусть nb(p, b) = c - следующий буфер на гарантированном пути b, и заметим, что класс r' буфера c превосходит r. По гипотезе индукции, c не содержит тупиковых пакетов, значит существует конфигурация d, достижимая из g, в которой c - пуст. Из d p может продвинуться в c, и, по гипотезе индукции, p не тупиковый в результирующей конфигурации d '. Следовательно, p в конфигурации g не в тупике.

Из доказательства видно, что если гарантированный путь содержит "внутренние" ребра буферного графа (ребра между двумя буферами одной вершины), то контроллер должен позволять дополнительные передвижения, с помощью которых пакет помещается в буфер той же вершины. Обычно гарантированный путь не содержит таких ребер. Они используются только для увеличения эффективности продвижения, например, в следующей ситуации. Пакет 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_v1. Чтобы показать, что 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_u0[0],b_u1 [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.