Быстрый поиск

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

Сейчас рассмотрим два примера использования буферных графов, а именно, схема адресата(destination scheme) и схема сколько-было-переходов (hops-so-far scheme).

Схема адресата. Схема адресата использует N буферов в каждой вершине u, с буфером bu[v] для каждого возможного адресата v. Вершина v называется цель буфера bu[v]. Для этой схемы нужно предположить, что алгоритмы маршрутизации продвигают все пакеты с адресатом v по направленному дереву Tv , ориентированному по направлению к v. (На самом деле это предположение может быть ослаблено; достаточно, чтобы каналы, используемые для продвижения по направлению к v, формировали ациклический подграф G.)

Буферный граф определяется как BGd = (B, ), где bu[v1]bw[v2] Î тогда и только тогда, когда v1 = v2 и uw - ребро в Tv1. Чтобы показать, что BGd - ациклический, заметим, что не существует ребер между буферами с различными целями и, что буферы, с одинаковой целью v формируют дерево, изоморфное Tv. Каждый путь P Î P с точкой назначения v - путь в Tv, и по построению существует путь в BGd из буферов с целью v, чей образ - P. Этот путь выбирается в качества гарантированного. Это означает, что для пакета p с адресатом v, сгенерированного в вершине u, fb(p) = bu[v], и, если этот пакет должен продвинуться в w, то nb(p,b) = bw[v].

Определение 5.8 Контроллер dest определяется как bgcBG , с fb и nb определенными как в предыдущем параграфе.

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

Доказательство. dest - беступиковый контроллер, использующий такое количество буферов. ð

Как было отмечено ранее, требование маршрутизации по деревьям стока может быть ослаблено до требования того, что пакеты с одинаковыми пунктами назначения посылаются через каналы, которые формируют ациклический граф. Не достаточно, чтобы P содержало только простые пути, как это показано на примере, данном на Рисунке 5.2. Здесь пакеты из u1 в v направляются через простой путь
á u1, w1, u2, . . ., v ñ, и пакете из u2 в v посылаются через простой путь

á u2, w2, u1, . . ., v ñ.

Рисунок 5.2 маршрутизация, запрещенная для контроллера dest.

Каждый путь в P простой; набор всех каналов, используемых для маршрутизации пакетов в v содержит цикл á u1, w1, u2, w2, u1,v ñ. См. Упражнение 5.2.

Контроллер dest очень прост в использовании, но имеет недостаток - для каждой вершины требуется большое количество буферов, а именно N.

Схема сколько-было-переходов. В этой схеме вершина u содержит k +1 буфер
bu[0], . . ., bu[k]. Предполагается, что каждый пакет содержит счетчик переходов, показывающий, сколько переходов от источника сделал пакет.

Буферный граф определяется как BGh = (B, ), где bu[i] bw[j] Î тогда и только тогда, когда и uw Î E. Чтобы показать, что BGh ациклический, заметим, что индексы буферов строго возрастают вдоль ребер BGh. Т.к. длина каждого пути в P не более k переходов, то существует соответствующий путь в буферном графе; если P = u0, . .., ul (l£ k), то bu0[0],bu1 [1],..., bul[l]-путь в BGh с образом P. Этот гарантированный путь описывается так: fb(p) = bu[0] (для p, сгенерированного в u) и

(p, bu[i]) = bw[i +1] для пакетов, которые должны быть продвинуты из u в w.

Определение 5.10 Контроллер hsf определяется как bgcBGh , с 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.

Последовательность G1, ..., GB ациклических ориентаций G является покрытием из ациклических ориентаций размера B для набора P путей, если каждый путь P Î P может быть записан как конкатенация B путей P1, ..., PB, где Pi - путь в Gi.

Когда возможно покрытие из ациклических ориентаций размера B, может быть сконструирован контроллер, использующий только B буферов на вершину. Пакет всегда генерируется в буфере bu[l] вершины u. Пакет из буфера bu[i], который должен быть продвинут в вершину w помещается в буфер bw [i], если дуга между u и w направлена к w в Gi , и в буфер bw[i + 1], если дуга направлена к u в Gi.

Теорема 5.13 Если покрытие из ациклических ориентаций для P размера B существует, то существует беступиковый контроллер, использующий только B буферов на каждую вершину.

Доказательство. Пусть G1. . .., GB - покрытие, и bu[1], ..., bu[B] - буферы вершины u. Будем писать uw Î , есди дуга uw направлена к w в Gi, и wu Î , если дуга uw направлена к u в Gi. Буферный граф определяется как BGa = (B, ), где bu[i]bw[j] Î тогда и только тогда, когда uw Î E и (i = j /\ uw Î ) или (i + 1 = j /\ wu Î ). Чтобы показать, что этот граф ациклический, отметим, что не существует циклов, содержащих буферы с различными индексами, потому что нет дуг от данного буфера к другому с меньшим индексом. Нет циклов с из буферов с одним и тем же индексом i , потому что эти буферы назначаются в соответствии с ациклическим графом Gi.

Оставляем читателю (см. Упражнение 5.4) продемонстрировать, что для каждого P Î P существует гарантированный путь с образом P, и что такой путь описывается следующим образом:

Контроллер acoc = bgcBGa - беступиковый контроллер, использующий B буферов в каждой вершине, что доказывает теорему. ð

Коммутация пакетов в кольце. Покрытия из ациклических ориентаций можно использованы при построении беступиковых контроллеров для нескольких классов сетей. Мы сначала представим контроллер для колец, использующий только три буфера на вершину. Для следующей теоремы предполагается, что веса каналов симметричны, т.е., wuw =wwu.

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

Доказательство. Из Теоремы 5.13 достаточно дать покрытие из ациклических ориентаций размером 3 для набора путей, который включает самые короткие пути между всеми парами вершин.

Будем использовать следующую нотацию. Для вершин u и v, dc(u, v) обозначает длину пути из u в v по часовой стрелке и da(u, v) - длина пути против часовой стрелки; dc(v, u) = da(u, v) и d(u, v) = min(dc(u, v), da(u, v)) выполняется. Сумма весом всех каналов называется C (периметр кольца) и очевидно dc(u, v) + da(u, v) = C для всех u, v, так что d(u, v)£ C/2.

Рисунок 5.4 покрытие из ациклических ориентаций для кольца.

Во-первых рассмотрим простой случай, когда Существуют вершины u и v с d(u, v) = C/2. G1 и G3 получаются ориентацией всех ребер по направлению к v, и G2 получается ориентацией всех ребер по направлению к u: см. Рисунок 5.4.

Самый короткий путь из u в v содержится в G1 или G3, и наименьший путь из v в u содержится в G2. Пусть x, y - пара вершин, отличная от пары u, v. Тогда, т.к.
d(x, y) £ C/2, то существует самый короткий путь P между x и y, который не содержит сразу и u, и v. Если P не сдержит ни u, ни v , то он полностью содержится либо в G1 , либо в G2. Если P содержит v , это конкатенация пути в G1 и пути в G2; если P содержит u, это конкатенация пути в G2 и пути в G3.

Если не существует пары 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, и получим T1 ориентацией всех ребер по направлению к r и T2 ориентацией всех ребер от r; см. Рисунок 5.5.

Рисунок 5.5 Покрытие из ациклических ориентаций для дерева.

Простой путь из u в v - конкатенация пути из u к самому нижнему общему предку, который T1, и пути от самого меньшего общего предка к v, который в T2. ð

5.3 Неструктурированные решения

Теперь мы обсудим класс контроллеров, предложенных Toueg и Ullman [TU81]. Эти контроллеры не предписывают, в котором буфере должен быть помещен пакет и используют только простую локальную информацию типа счетчика переходов или числа занятых буферов в узле.

5.3.1 Контроллеры с прямым и обратным счетом

Контроллер с прямым счетом (forward-count controller). Пусть (для пакета p) sp -количество переходов, которые ему необходимо сделать до места назначения; конечно же 0 £ sp £ k выполняется. Не всегда необходимо хранить sp в пакете, т.к. многие алгоритмы маршрутизации хранят эту информацию в каждой вершине; см. например алгоритм Netchange Раздела 4.3. Для вершины u, fu обозначает число пустых буферов в u. Конечно, 0 £ fu£ B всегда выполняется.

Определение 5.16 Контроллер FC (Forward-count) принимает пакет p в вершине u тогда и только тогда, когда sp < fu.

Контроллер принимает пакет, если пустых буферов в вершине больше, чем количество переходов, которые нужно сделать пакету.

Теорема 5.17 Если B > k, то FC - беступиковый контроллер.

Доказательство. Чтобы показать, что в пустой вершине позволяется генерация пакета, заметим, что если все буферы вершины u пусты, fu = B. Новому пакету нужно сделать не более k переходов, так что из B > k следует, что пакет принимается.

Отсутствие тупиков FC будет показано методом от противного: пусть g - достижимая конфигурация контроллера. Получим конфигурацию d , применяя к g максимальную последовательность из передвижений и выведения. В d ни один пакет не может двигаться, и, т.к. g - тупиковая конфигурация, то существует по крайней мере один пакет, оставшийся в сети в конфигурации. Пусть p - пакет в d с минимальным расстоянием до пункта назначения, т.е., sp - наименьшее значение для всех пакетов в d.

Пусть u - вершина, в которой размещается p. Т.к. u не является пунктом назначения p (иначе p мог бы быть выведен), то существует сосед w вершины u , в которую нужно продвинуть p. Т. к. это передвижение не позволяется FC, то

sp-1³ fw

Из sp£ k и из предположения k < B следует, что fu < B, что обозначает, что в вершине w располагается как минимум один пакет (в конфигурации d ). Из пакетов в w, пусть q будет последним пакетом, принятым вершиной w, и пусть f'w обозначает количество пустых буферов в w прямо перед принятием q вершиной w. Т.к. пакет q теперь занимает один из этих f'w буферов и (из выбора q) все пакеты, принятые вершиной w после q были выведены из w, то