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

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

(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, то

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) вектор состояния , где j - количество пакетов p в u с sp = s.

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

.

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

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

Если w не содержит пакетом, то , откуда следует, что w может принять p, что невозможно. Следовательно, w содержит по крайней мере один пакет; из пакетов в w, пусть q - пакет, расположенный ближе всего к пункту назначения, т.е., sq = min{s : js > 0}. Покажем, что sq < sp, что является противоречием. Из пакетов в w, пусть r - тот, который был принят w позже всех, конечно, sq £ sr выполняется. Пусть  - вектор состояния w прямо перед принятием r. Из принятия r следует

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

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

Таким образом, принимая i = sq,

Теперь используем факт, что p не принята w, т.е.,

Это дает неравенство

sp>sp-1

что и является противоречием.                                    ð

Контроллер с отстающим состоянием (backward-state controller.) Существует также и контроллер, "двойственный" FS, который использует более детальную информацию, чем контроллер BC, и позволяет больше передвижений. Пусть tp выбрано как раньше, и определим вектор состояния как , где  it равно количеству пакетов в вершине u , которые сделали t переходов.

Определение 5.21 Контроллер BS (Backward-State) принимает пакет p в вершине u с вектором состояния  тогда и только тогда, когда

Доказательство того, что BS беступиковый очень похоже на доказательство Теоремы 5.20.

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

Лемма 5.22 Каждое передвижение, позволяемое FC также позволяется FS.

Доказательство. Предположим, что принятие p вершиной u позвляется контроллером FC. Тогда , так что для  i£ sp ,следует , откуда видно, что FS позволяет передвижение.                                            D

В [TU81] было показано, что FC более либеральный, чем BC. FS - более либеральный, чем BS, и BS более либеральный, чем BC. Также было показано, что эти контроллеры самые либеральные из всех, использующих такую же информацию.

5.4 Дальнейшие проблемы

В результатах этой главы отметим, что число буферов, необходимых контроллеру, всегда играло большую роль. Пропускная способность обычно увеличивается, если доступно большое количество буферов. В неструктурированных решениях дано только нижняя граница числа буферов; большее число может использоваться без любой модификации. В структурированных решениях дополнительные буфера должны так или иначе быть вставлены в буферный граф, что может быть выполнено или статически или динамически. Если это выполнено статически, каждый буфер имеет фиксированное расположение в буферном графе, т.е., создается  "более широкий" буферный граф, чем в примерах, приведенных в Разделе 5.2.

Вместо одного буфера fb (p) или nb (p, b) обычно несколько буферов определяются как возможное начало или продолжение пути через буферный граф. Если вставка дополнительных буферов выполняется динамически, то буферный граф сначала создается содержащим как можно меньшее количество буферов; буфера в графе мы называем логическими буферами, во время операции каждый фактический буфер (называемый физическим буфером) может использоваться как любой из логических буферов, но всегда должно гарантироваться, что для каждого логического буфера имеется по крайней мере один физический буферный накопитель. При такой схеме, должен быть зарезервировано только небольшое число буферов, чтобы избежать тупиков, в то время как остальная часть буферов может использоваться свободно.

Страницы: 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, 37, 38, 39, 40, 41, 42