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

Здесь 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' не содержит тупиковый пакет (в достижимой

конфигурации).

Пусть ( - достижимая конфигурация с пакетом p в буфере b класса r < R

вершины u. Если u - место назначения p, то p может быть выведен и,

следовательно, он не в тупике. Иначе, пусть nb(p, b) = c - следующий буфер

на гарантированном пути b, и заметим, что класс r' буфера c превосходит r.

По гипотезе индукции, c не содержит тупиковых пакетов, значит существует

конфигурация (, достижимая из (, в которой c - пуст. Из ( p может

продвинуться в c, и, по гипотезе индукции, p не тупиковый в результирующей

конфигурации ( '. Следовательно, p в конфигурации ( не в тупике.

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

"внутренние" ребра буферного графа (ребра между двумя буферами одной

вершины), то контроллер должен позволять дополнительные передвижения, с

помощью которых пакет помещается в буфер той же вершины. Обычно

гарантированный путь не содержит таких ребер. Они используются только для

увеличения эффективности продвижения, например, в следующей ситуации. Пакет

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, [pic]), где bu[v1]bw[v2] (

[pic]тогда и только тогда, когда 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 (.

[pic]

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

Каждый путь в P простой; набор всех каналов, используемых для маршрутизации

пакетов в v содержит цикл ( u1, w1, u2, w2, u1,v (. См. Упражнение 5.2.

Контроллер dest очень прост в использовании, но имеет недостаток - для

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

Схема сколько-было-переходов. В этой схеме вершина u содержит k +1 буфер

bu[0], . . ., bu[k]. Предполагается, что каждый пакет содержит счетчик

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

Буферный граф определяется как BGh = (B, [pic]), где bu[i] bw[j] (

[pic]тогда и только тогда, когда [pic] и 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 индекс буфера, в котором хранился пакет, увеличивался с каждым

переходом. Теперь мы замедлим рост индекса буфера (таким образом экономя на

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

буфера (не путать с классом буфера) с некоторыми, но не обязательно всеми,

переходами. Чтобы избежать циклов в буферном графе, каналы, которые могут

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

[pic]

Рисунок 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 ( [pic], есди дуга uw направлена к w в Gi, и wu

( [pic], если дуга uw направлена к u в Gi. Буферный граф определяется как

BGa = (B, [pic]), где bu[i]bw[j] ( [pic] тогда и только тогда, когда uw (

E и (i = j /\ uw ( [pic]) или (i + 1 = j /\ wu ( [pic]). Чтобы показать,

что этот граф ациклический, отметим, что не существует циклов, содержащих

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

другому с меньшим индексом. Нет циклов с из буферов с одним и тем же

индексом i , потому что эти буферы назначаются в соответствии с

ациклическим графом Gi.

Оставляем читателю (см. Упражнение 5.4) продемонстрировать, что для каждого

P ( P существует гарантированный путь с образом P, и что такой путь

описывается следующим образом:

[pic]

Контроллер 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.

[pic]

Рисунок 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.

[pic]

Рисунок 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 будет показано методом от противного: пусть ( -

достижимая конфигурация контроллера. Получим конфигурацию ( , применяя к (

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

пакет не может двигаться, и, т.к. ( - тупиковая конфигурация, то существует

по крайней мере один пакет, оставшийся в сети в конфигурации. Пусть p -

пакет в ( с минимальным расстоянием до пункта назначения, т.е., sp -

наименьшее значение для всех пакетов в (.

Пусть u - вершина, в которой размещается p. Т.к. u не является пунктом

назначения p (иначе p мог бы быть выведен), то существует сосед w вершины u

, в которую нужно продвинуть p. Т. к. это передвижение не позволяется FC,

то

sp-1( fw

Из sp( k и из предположения k < B следует, что fu < B, что обозначает, что

в вершине w располагается как минимум один пакет (в конфигурации ( ). Из

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

f'w обозначает количество пустых буферов в w прямо перед принятием q

вершиной w. Т.к. пакет q теперь занимает один из этих f'w буферов и (из

выбора q) все пакеты, принятые вершиной w после q были выведены из w, то

f'w ( fw +1

Из принятие q вершиной w следует sq < f'w, и, комбинируя три полученных

неравенства, получаем

sq < f'w ( fw +1( sp,

что противоречит выбору p. (

Контроллер с обратным счетом (backward-count controller). Контроллер, "

двойственный " FC , получается, когда решение, принимать ли пакет, основано

на количестве шагов, которые пакет уже сделал. Пусть, для пакета p, tp -

количество переходов, которые он сделал от источника. Конечно, 0 ( tp < k

всегда верно.

Определение 5.18 Контроллер BC (Backward-Count) принимает пакет p в вершине

u тогда и только тогда, когда tp > k—fu.

Доказательство того, что BC - беступиковый (Упражнение 5.6) очень похоже на

доказательство Теоремы 5.17.

5.3.2 Контроллеры с опережающим и отстающим состоянием

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

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

счетом, но позволяет большое количество передвижений.

Контроллер с опережающим состоянием (forward-state controller). Используем

обозначение sp как в предыдущем разделе. Для вершины u определим (как

функцию состояния u) вектор состояния [pic], где j - количество пакетов p в

u с sp = s.

Определение 5.19 Контроллер FS (Forward-State) принимает пакет p в вершине

u с вектором состояния [pic] тогда и только тогда, когда

[pic].

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

Доказательство. Оставляем читателю показать, что пустая вершина принимает

все пакеты. Предположим, что существует достижимая тупиковая конфигурация

(, и получим конфигурацию ( , применяя максимальную последовательность из

продвижений и выведения. Ни один пакет не может передвигаться и по крайней

мере один пакет остался в (. Выберем пакет p с минимальным значением sp, и

пусть u -вершина, в которой располагается p и w - вершина, в которую p

должен продвинуться. Пусть [pic] - вектор состояния вершины w в (.

Если w не содержит пакетом, то [pic], откуда следует, что w может принять

p, что невозможно. Следовательно, w содержит по крайней мере один пакет; из

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36