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

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

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

(2) Из bc Î следует, что b и c - буферы одной и той же вершины, или буферы двух вершин, соединенных каналом в G; и

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

Второе требование определяет отображение путей в BG на пути в G; если
b0, b1, ..., bs - путь в BG, то, если u- вершина, в которой располагается буфер bi, u0, u1,..., us - последовательность вершин таких, что для каждого i < s либо uiui+1 Î E, либо ui = ui+1. Путь в G, который получается из этой последовательности пропусканием последовательных повторений, называется образом исходного пути b0, b1,..., bs в BG.

Пакет не может быть помещен в произвольно выбранный буфер; он должен быть помещен в буфер, из которого он еще может достигнуть своего места назначения через путь в BG, т.е., буфер, подходящий для пакета в соответствии с определением.

Определение 5.5 Пусть p - пакет в вершине u с пунктом назначения v. Буфер b в 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 может быть использован для разработки беступикового контроллера bgcBG , записывающий в каждый пакет буфер nb(p, b) и/или состояние вершины, где располагается p.

Определение 5.6 Контроллер bgcBG определяется следующим образом.

Генерация пакета p в u позволяется тогда и только тогда, когда буфер fb(p) свободен. Сгенерированный пакет помещается в этот буфер.

Продвижение пакета p из буфера в u в буфер в w (возможно u = w) позволяется тогда и только тогда, когда nb(p, b) (в w) свободен. Если продвижение имеет место, то пакет p помещается в nb(p, b).

Theorem 5.7 Контроллер bgcBG - беступиковый контроллер.

Доказательство. Если у вершины все буферы пусты, генерация любого пакета позволяется, откуда следует, что bgcBG - контроллер.

Для каждого b Î B, определим класс буфера b как длину самого длинного пути в BG , который заканчивается в b. Заметим, что классы буферов на пути в BG (а точнее, на гарантированном пути) строго возрастающие, т.е., класс буфера nb(p, b) больше, чем класс буфера b.

Т.к. контроллер позволяет размещение пакетов только в подходящих буферах и т.к. изначально нет пакетов, каждая достижимая конфигурация сети под управлением bgcBG содержит пакеты только в подходящих буферах. С помощью индукции "сверху вниз" по классам буферов можно легко показать, что ни один буфер класса 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 размещается в буфере b1 вершины u и буфер nb(p, b1) в вершине w занят. Но существует свободный буфер b2 в u, который подходит для p; более того, nb(p, b2) в вершине w свободен. В таком случае, пакет может быть перемещен через b2 и nb(p, b2).

Сейчас рассмотрим два примера использования буферных графов, а именно, схема адресата(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) и