Предыдущая страница реферата | 22  23  24  25  26  27  28  29  30  31  32 | Следующая страница реферата



Контроллер буферного графа. Буферный граф 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 содержит по крайней мере один пакет; из пакетов в w, пусть q - пакет, расположенный ближе всего к пункту назначения, т.е., sq = min{s : js > 0}. Покажем, что sq < sp, что является противоречием. Из пакетов в w, пусть r - тот, который был принят w позже всех, конечно, sq ( sr выполняется. Пусть [pic] - вектор состояния w прямо перед принятием r. Из принятия r следует
[pic]
Когда [pic] был вектором состояния w, r был принят вершиной w. После этого пакеты могли передвигаться из w, но все пакеты, принятые в w позже, чем r были выведены (из выбора r). Из этого следует
[pic]
Но это означает, что
[pic]
Таким образом, принимая i = sq,
[pic]
Теперь используем факт, что p не принята w, т.е.,
[pic]
Это дает неравенство sp>sp-1
[pic] что и является противоречием. (

Контроллер с отстающим состоянием (backward-state controller.) Существует также и контроллер, "двойственный" FS, который использует более детальную информацию, чем контроллер BC, и позволяет больше передвижений. Пусть tp выбрано как раньше, и определим вектор состояния как [pic], где it равно количеству пакетов в вершине u , которые сделали t переходов.
Определение 5.21 Контроллер BS (Backward-State) принимает пакет p в вершине u с вектором состояния [pic] тогда и только тогда, когда
[pic]
Доказательство того, что BS беступиковый очень похоже на доказательство
Теоремы 5.20.
Сравнение контроллеров. Контроллер с опережающим состоянием более либеральный, чем контроллер с прямым счетом, в том плане, что он позволяет больше передвижений:
Лемма 5.22 Каждое передвижение, позволяемое FC также позволяется FS.
Доказательство. Предположим, что принятие p вершиной u позвляется контроллером FC. Тогда [pic], так что для i( sp ,следует [pic], откуда видно, что FS позволяет передвижение.

D
В [TU81] было показано, что FC более либеральный, чем BC. FS - более либеральный, чем BS, и BS более либеральный, чем BC. Также было показано, что эти контроллеры самые либеральные из всех, использующих такую же информацию.
5.4 Дальнейшие проблемы
В результатах этой главы отметим, что число буферов, необходимых контроллеру, всегда играло большую роль. Пропускная способность обычно увеличивается, если доступно большое количество буферов. В неструктурированных решениях дано только нижняя граница числа буферов; большее число может использоваться без любой модификации. В структурированных решениях дополнительные буфера должны так или иначе быть вставлены в буферный граф, что может быть выполнено или статически или динамически. Если это выполнено статически, каждый буфер имеет фиксированное расположение в буферном графе, т.е., создается "более широкий" буферный граф, чем в примерах, приведенных в Разделе 5.2.
Вместо одного буфера fb (p) или nb (p, b) обычно несколько буферов определяются как возможное начало или продолжение пути через буферный граф.
Если вставка дополнительных буферов выполняется динамически, то буферный граф сначала создается содержащим как можно меньшее количество буферов; буфера в графе мы называем логическими буферами, во время операции каждый фактический буфер (называемый физическим буфером) может использоваться как любой из логических буферов, но всегда должно гарантироваться, что для каждого логического буфера имеется по крайней мере один физический буферный накопитель. При такой схеме, должен быть зарезервировано только небольшое число буферов, чтобы избежать тупиков, в то время как остальная часть буферов может использоваться свободно.
В этой главе было принято, что пакеты имеют фиксированный размер: буфера одинаково большие и каждый буфер может содержать точно один пакет. Проблему может также рассматривать, предположив, что пакеты могут иметь различные размеры. Решения Раздела 5.3 были адаптированы к этому предположению
Bodlaender; см. [Bod86].

5.4.1 Топологические изменения
До этого момента мы явно не рассматривали возможность топологических изменений в сети в течение путешествия пакета от источника до адресата.
После возникновения такого изменения таблицы маршрутизации каждого узла будут модифицироваться, и затем пакет будет послан, используя измененные значения этих таблиц. В результате модификации таблиц, пакет может следовать за путем, которым бы не следовал, если никакие изменения не имели бы место; даже возможен случай, что окончательный маршрут пакета теперь содержит циклы.
Воздействие этого на методы предотвращения тупиков, рассматриваемые в этой главе довольно не интуитивные. контроллер Dest, чья правильность основана на свойстве, что P содержит только простые пути, может использоваться без каких-либо модификаций. Контроллеры, которые рассматривают только верхнюю границу числа переходов, требуют дополнительных предосторожностей при использовании в этом случае.
Контроллер dest. За конечное время после последнего топологического изменения, таблицы маршрутизации сводятся к таблицам свободным от циклов.
Даже не смотря на то, что ситуация циклического ожидания может существовать во время вычисления таблиц, после завершения вычислений буферный граф снова становится ациклическим, и все пакеты хранятся в подходящих буферах.
Следовательно, когда таблицы маршрутизации вычислены, возникшая в результате конфигурация не содержит никаких тупиковых пакетов.
Контроллеры, подсчитывающие переходы. Рассмотрим контроллер, который полагается на предположение, что пакет должен делать не больше k переходов.
Можно выбрать k достаточно большим, чтобы гарантировать с большой вероятностью, что каждый пакет достигает адресата за k переходов, даже если в течение путешествия от источника до адресата происходят некоторые топологические изменения. Для всех пакетов, которые достигают своих адресатов за k переходов, контроллеры сколько-было-переходов, с обратным счетом и с отстающим состоянием могут использоваться без какой-либо модификации. Однако, возможно, что пакет не достиг адресата после k переходов из-за неудачного образца топологических изменений и модификаций таблиц. Если дело обстоит так, пакет сохраняется в неподходящем буфере, и он будет навсегда блокирован в узле, отличном от адресата.
Такие ситуации могут быть решены только в кооперации с протоколами более высокого уровня. Самое простое решение в том, чтобы отбросить пакет. С точки зрения сквозного транспортного протокола, пакет теперь потерян; но с этой потерей можно справиться с помощью протокола транспортного уровня, как было показано в Разделе 3.2.
Отбрасывание пакетов также необходимо для выполнения предположения Раздела
3.2 о том, что максимальное время жизни пакета (. Если пересылка пакета занимает не более (0 единиц времени, то из ограничения времени жизни пакета p следует ограничение k =( /(0 на число переходов, которые может пройти пакет.

5.4.2 Другие виды тупиков
В этой главе рассматривались только тупики с промежуточным накоплением.
Если предположения, сделанные в Разделе 5.1 имеют силу, тупики с промежуточным накоплением - единственно возможные виды тупиков. В практических сетях, однако, эти предположения не всегда выполняются и, как показали Merlin и Schweitzer [MS80b], возможны другие типы тупиков. Merlin и Schweitzer рассматривают четыре типа, а именно: тупик потомства, тупиком выпуска копии, тупик пошагового продвижения, и тупик перетрансляции, и показывают, как можно избежать эти типы тупиков расширением метода буферных графов.
Тупик потомства может возникнуть, когда пакет p может создать в сети другой пакет q, например, отчет об отказе, если произошло столкновение с испорченным каналом. Это ввело бы причинно-следственные отношение между порождением нового пакета (q) и пересылкой или выведением уже существующего
(p), что нарушает предположение Раздела 5.1, что сеть всегда позволяет пересылку и выведение пакета.
Тупика потомства можно избежать, имея две копий буферного графа: одну для первоначальных сообщений и одну для вторичных сообщений. Если потомки могут снова создать следующее поколение, должны использоваться многократные уровни буферного графа.
Тупик выпуска копии может возникнуть, когда источник задерживает копию пакета, пока для пакета не получено (сквозное) подтверждение от адресата.
(Сравните с протоколом основанном на таймере из Раздела 3.2, и предположите, что последовательность inp хранится в том же самом пространстве памяти, которое используется механизмом маршрутизации для временного хранения пакетов.) Это нарушает наше предположение (в Разделе
5.1), что буфер становится пустым, когда пакет, занимающий его, продвигается.
Даны два расширения принципа буферного графа, с помощью которых можно избежать тупика выпуска копии. Первое решение полагается на предположение, что тупик выпуска копии всегда возникает из-за циклического ожидания оригинальных и подтверждающих сообщений. Решение состоит в том, чтобы обрабатывать подтверждения как потомство и хранить их в отдельной копии буферного графа. Во втором решении, которое в большинстве случаев требует меньшего количества буферов, недавно сгенерированные пакеты помещаются в специализированные исходные буфера, в которые не могут быть помещены посылаемы пакеты.
Тупик пошагового продвижения может возникнуть, когда сеть содержит узлы с ограниченной внутренней памятью, которые могут отказываться выводить сообщения, пока некоторые другие сообщения не были сгенерированы. Например, терминал телетайпа должен вывести некоторые символы прежде, чем он сможет принимать следующие символы для отображения. Это нарушает наше предположение, что пакет в адресате всегда может быть выведен.
Тупика пошагового продвижения можно избежать, делая различие между продвигаемыми пакетами и пошаговыми ответами, такими, что пакет первого типа не может быть выведен, пока пакет второго типа не был сгенерирован.
Для разных типов сообщений используются различные копии буферного графа.
Тупик перетрансляции может возникнуть в сетях, где большие сообщения для передачи разделяются на более мелкие пакеты, и ни один пакет не может быть удален из сети, пока все пакеты сообщения не достигли адресата. (Сравните с протоколом скользящего окна Раздела 3.1, где слова удаляются из outp только если были получены все слова с меньшим индексом.) Это нарушает наше предположение, что выведение пакета в адресате всегда возможно.
Тупиков перетрансляции можно избежать, используя отдельные группы буферов для пересылки пакета и перетрансляции.
5.4.3 Лайфлок (livelock)
Из определения тупиковых пакетов (Определение 5.2) следует, что под управлением беступикового контроллера для каждого пакета существует по крайней мере одно вычисление, в котором пакет выводится. Т.к. в общем случае возможно большое количество различных вычислений, то это из этого не следует, что каждый пакет в конечном счете доходит до адресата, даже в бесконечном вычислении, как иллюстрируется Рисунок 5.6. Предположим, что u посылает в v бесконечный поток пакетов, и каждый раз, как только буфер в w становится пустым, принимается следующий пакет из u. Узел s имеет пакет для t, который не заходит в тупик, потому что каждый раз, когда буфер в w становится пустым, имеется возможное продолжение вычисления, в котором пакет принимается вершиной w и посылается к t. Это возможно, но не обязательно, и пакет может остаться в s навсегда. Ситуация этого вида называется лайфлок.
Контроллер, обсуждаемый в этой главе, может быть расширен так, чтобы вообще избежать лайфлоков.
Определение 5.23 Дана сеть, контроллер con, и конфигурация (, пакет p заблокирован (лайфлок), если существует бесконечная последовательность передвижений, применимых в (, в результате которых p не выводится.
Конфигурация ( - конфигурация лайфлока, если она содержит заблокированные пакеты.
[pic]
Рисунок 5.6 Пример лайфлока.

Контроллер свободен от лайфлока, если ни одна конфигурация лайфлока не достижима из конфигурации, в которой нет пакетов.
В оставшейся части этого подраздела будет доказана свобода контроллера буферных графов от лайфлока; в конце будут упомянуты расширения неструктурированных решений.
Контроллер буферного графа. Можно продемонстрировать, что контроллеры
Раздела 5.2 лайфлок-свободны без каких-либо модификаций, если их передвижения в бесконечной последовательности удовлетворяют ряду справедливых предположений. Fl и F2 - сильные предположеня и F3 - слабое предположение.
Fl. Если порождение пакета p предпринимается непрерывно, то каждое бесконечное вычисление, в котором fb (p) свободен в бесконечно большом количестве конфигураций, содержит порождение p.
F2. Если в конфигурации ( пакет p должен быть послан от u до w, то каждое бесконечное вычисление, начинающееся в (, в котором nb (p, b) является свободным в бесконечно большом количестве конфигураций, содержит пересылку p.
F3. Если пакет p находится в своем пункте назначения в конфигурации (, то каждое бесконечное вычисление, начинающееся в (, содержит выведение p.

Лемма 5.24 Если справедливые предположения F2 и F3 удовлетворяются в каждом бесконечном вычислении bgc, то каждый буфер свободен бесконечно часто.
Доказательство. Доказывать будем индукцией сверху вниз по классам буферов.
Как в доказательстве Теоремы 5.7, пусть R - наибольший буферный класс.
Напомним, что в конфигурациях, достижимых под управлением bgc, все пакеты располагаются в подходящих буферах.
Случай r = R: Буфер класса R не имеет исходящих ребер, и, следовательно, пакет из такого буфера достигает пункта назначения. Следовательно, по предположению F3, после каждой конфигурации, в которой такой буфер занят, будет конфигурация, в которой буфер свободен. Отсюда следует, что он пуст в бесконечно большом количестве конфигураций.
Случай r < R: Пусть ( - конфигурация, в которой буфер b класса r < R занят пакетом p. Если p достиг своего пункта назначения, то позже будет конфигурация, в которой b будет пустым из F3. Иначе, p должен быть продвинут в буфер nb(p, b) класса r' > r. По индукции, в каждом бесконечном вычислении, начинающемся в (, этот буфер пуст бесконечно часто. Из этого следует (по F2), что p будет передан и, следовательно, будет конфигурация
(, после которой b будет пуст.

Теорема 5.25 Если справедливые предположения F1, F2 и F3 удовлетворяются, то в каждом бесконечном вычислении каждый пакет, предлагаемый сети, будет выведен из своего пункта назначения.
Доказательство. По Лемме 5.24 все буферы пусты в бесконечно большом количестве конфигураций. Значит (по Fl) каждый паке, который продолжает предлагаться сети, будет сгенерирован. По F2 он будет продвигаться, пока не достигнет своего пункта назначения. (
Легко предположить, что механизм недетерминированного выбора в распределенной системе гарантирует, что эти три предположения удовлетворяются. Альтернативно, предположения могут быть введены добавлением к контроллеру механизма, который гарантирует, что, когда буфер становится пустым, более старым пакетам позволяется входить с большими приоритетами.

Неструктурированные решения. Контроллеры Раздела 5.3 нужно модифицировать, чтобы они стали лайфлок-свободными. Это может быть показано моделированием бесконечного вычисления, в котором непрерывный поток пакетов заставляет контроллер запрещать пересылку некоторого пакета. Toueg [TouSOb] представляет такое вычисление (для FC) и представляет модификацию FS
(подобную представленной здесь для контроллеров буферных графов), которая является лайфлок-свободной.

Упражнения к Главе 5
Раздел 5.1
Упражнение 5.1 Покажите, что не существует беступикового контроллера, который использует только один буфер на вершину и позволяет каждой вершине посылать пакеты по крайней мере одной другой вершине.
Раздел 5.2
Упражнение 5.2 Покажите, что dest не является беступиковым, если маршрутизация пакетов осуществляется как на Рисунке 5.2.
Упражнение 5.3 (Схема сколько-будет-переходов) Дайте буферный граф и функции fb и nb для контроллера, который использует буфер bu[i] для хранения пакетов, которым нужно сделать еще i переходов по направлению к своим пунктам назначения. Каков буферный класс bu [i] ? Нужно ли хранить счетчик переходов в каждом пакете?
Упражнение 5.4 Закончите доказательство того, что граф BGa (определенный в доказательстве Теоремы 5.13)- в самом деле буферный граф, т.е., для каждого пути P ( P существует гарантированный путь с образом P. Покажите, что, как утверждалось, fb и nb в самом деле описывают путь в BGa.
Проект 5.5 Докажите, что существует беступиковый контроллер, для коммутации пакетов в гиперкубе, который использует всего два буфера на вершину и позволяет маршрутизировать пакеты через минимальные пути. Можно ли получить набор используемых путей посредством алгоритма интервальной маршрутизации
(Подраздел 4.4.2)? Можно ли использовать схему линейной интервальной разметки?
Раздел 5.3
Упражнение 5.6 Докажите, что BC и BS - беступиковые контроллеры.
Упражнение 5.7 Докажите, каждое передвижение, позволяемое BC, также позволяется FC.

Часть 2 Фундаментальные алгоритмы

6 Волновые алгоритмы и алгоритмы обхода

При разработке распределенных алгоритмов для различных приложений часто в качестве подзадач возникает несколько общих проблем для сетей процессов.
Эти элементарные задачи включают в себя широковещательную рассылку информации - broadcasting (например, посылка начального или заключительного сообщения), достижение глобальной синхронизации между процессами, запуск выполнения некоторого события в каждом процессе, или вычисление функции, входные данные которой распределены между процессами. Эти задачи всегда решаются путем пересылки сообщений согласно некоторой, зависящей от топологии схеме, которая гарантирует участие всех процессов. Эти задачи настолько фундаментальны, что можно дать решения более сложных задач, таких как выбор (Глава 7), обнаружение завершения (Глава 8), или взаимное исключение, в которых связь между процессами осуществляется только через эти схемы передачи сообщений.
Важность схем передачи сообщений, называемых далее волновыми алгоритмами, оправдывает их рассмотрение отдельно от конкретного прикладного алгоритма, в который они могут быть включены. В этой главе формально определяются волновые алгоритмы (Подраздел 6.1.1) и доказываются некоторые общие результаты о них (Подраздел 6.1.2). Замечание о том, что те же самые алгоритмы могут использоваться для всех основных задач, изложенных выше, т.е. широковещание, синхронизация и вычисление глобальных функций, будет формализовано (Подразделы 6.1.3-5). В Разделе 6.2 представлены некоторые широко используемые волновые алгоритмы. В Разделе 6.3 рассматриваются алгоритмы обхода; это волновые алгоритмы, в которых все события вычисления алгоритма совершенно упорядочены каузальным отношением. В Разделе 6.4 представлены несколько алгоритмов для распределенного поиска в глубину.
Несмотря на то, что волновые алгоритмы обычно используются как подзадачи в более сложных алгоритмах, их полезно рассматривать отдельно. Во-первых, введение новых понятий облегчает последующее рассмотрение более сложных алгоритмов, т.к. свойства их подзадач уже изучены. Во-вторых, определенные задачи в распределенных вычислениях могут быть решены с помощью универсальных конструкций, в качестве параметров которых могут использоваться конкретные волновые алгоритмы. Тот же метод может использоваться для получения алгоритмов для различных сетевых топологий или для различных предположений о начальном знании процессов. Эта глава основана на [Tel91b, Раздел 4.2], где понятие волновых алгоритмов изучается под названием общие алгоритмы.

6.1 Определение и использование волновых алгоритмов
В пределах этой главы считается, если не указано обратное, что сетевая топология фиксирована (не происходит топологических перемен), не ориентирована (каждый канал передает сообщения в обоих направлениях) и связна (существует путь между любыми двумя процессами). Множество всех процессов обозначено через P, а множество каналов - через E. Как и в предыдущих главах, предполагается, что система использует асинхронную передачу сообщений и не существует понятия глобального или реального времени. Алгоритмы из этой главы также могут быть использованы в случае синхронной передачи сообщений (возможно с некоторыми изменениями во избежание тупиков) или с часами глобального времени, если они доступны.
Однако некоторые более общие теоремы в этих случаях неверны; см. Упражнение
6.1.

6.1.1 Определение волновых алгоритмов
Как отмечалось в Главе 2, распределенные алгоритмы обычно допускают большой набор возможных вычислений благодаря недетерминированности как в процессах, так и в подсистеме передачи. Вычисление - это набор событий, частично упорядоченных отношением каузального (причинно-следственного) предшествования ?; см. Определение 2.20. Количество событий в вычислении C обозначается через |C|, а подмножество событий, происходящих в процессе p, обозначается через Cp. Считается, что существует особый тип внутренних событий, называемый decide (принять решение); в алгоритмах этой главы такое событие представляется просто утверждением decide. Волновой алгоритм обменивается конечным числом сообщений и затем принимает решение, которое каузально зависит от некоторого события в каждом процессе.
Определение 6.1 Волновой алгоритм - это распределенный алгоритм, который удовлетворяет следующим трем требованиям:
Завершение. Каждое вычисление конечно:

? C : |C| < ?
Принятие решения. Каждое вычисление содержит хотя бы одно событие decide:

? C : ? e ? C : e - событие decide.
Зависимость. В каждом вычислении каждому событию decide каузально предшествует какое-либо событие в каждом процессе:

? C : ? e ? C : ( e - событие decide ? ? q ? P ? f ? Cq : f ? e).
Вычисление волнового алгоритма называется волной. Кроме того, в вычислении алгоритма различаются инициаторы, также называемые стартерами, и не- инициаторы, называемые последователями. Процесс является инициатором, если он начинает выполнение своего локального алгоритма самопроизвольно, т.е. при выполнении некоторого условия, внутреннего по отношению к процессу. Не- инициатор включается в алгоритм только когда прибывает сообщение и вызывает выполнение локального алгоритма процесса. Начальное событие инициатора - внутреннее событие или событие посылки сообщения, начальное событие не- инициатора - событие получения сообщения.
Существует множество волновых алгоритмов, так как они могут различаться во многих отношениях. Для обоснования большого количества алгоритмов в этой главе и в качестве помощи в выборе одного из них для конкретной цели здесь приведен список аспектов, которые отличают волновые алгоритмы друг от друга; см. также Таблицу 6.19.
Централизация. Алгоритм называется централизованным, если в каждом вычислении должен быть ровно один инициатор, и децентрализованным, если алгоритм может быть запущен произвольным подмножеством процессов.
Централизованные алгоритмы также называют алгоритмами одного источника, а децентрализованные - алгоритмами многих источников. Как видно из Таблицы
6.20, централизация существенно влияет на сложность волновых алгоритмов.
Топология. Алгоритм может быть разработан для конкретной топологии, такой как кольцо, дерево, клика и т.д.; см. Подраздел 2.4.1 и Раздел B.2.
Начальное знание. Алгоритм может предполагать доступность различных типов начального знания в процессах; см. Подраздел 2.4.4. Примеры требуемых заранее знаний:
(a) Идентификация процессов. Каждому процессу изначально известно свое собственное уникальное имя.
(b) Идентификация соседей. Каждому процессу изначально известны имена его соседей.
(c) Чувство направления (sense of direction). См. Раздел B.3.
Число решений. Во всех волновых алгоритмах этой главы в каждом процессе происходит не более одного решения. Количество процессов, которые выполняют событие decide, может быть различным; в некоторых алгоритмах решение принимает только один процесс, в других - все процессы. В древовидном алгоритме (Подраздел 6.2.2) решают ровно два процесса.
Сложность. Меры сложности, рассматриваемые в этой главе, это количество передаваемых сообщений (message complexity), количество передаваемых бит
(bit complexity) и время, необходимое для одного вычисления (определено в
Разделе 6.4). См. также Подраздел 2.4.5.
Каждый волновой алгоритм в этой главе будет дан вместе с используемыми переменными и, в случае необходимости, с информацией, передаваемой в сообщениях. Большинство этих алгоритмов посылают «пустые сообщения», без какой-либо реальной информации: сообщения передают причинную связь, а не информацию. Алгоритмы 6.9, 6.11, 6.12 и 6.18 используют сообщения для передачи нетривиальной информации. Алгоритмы 6.15 и 6.16/6.17 используют различные типы сообщений; при этом требуется, чтобы каждое сообщение содержало 1-2 бита для указания типа сообщения.
Обычно при применении волновых алгоритмов в сообщение могут быть включены дополнительные переменные и другая информация. Многие приложения используют одновременное или последовательное распространение нескольких волн; в этом случае в сообщение должна быть включена информация о волне, которой оно принадлежит. Кроме того, процесс может хранить дополнительные переменные для управления волной, или волнами, в которых он в настоящее время активен.
Важный подкласс волновых алгоритмов составляют централизованные волновые алгоритмы, обладающие двумя дополнительными качествами: инициатор является единственным процессом, который принимает решение; и все события совершенно упорядочены каузальными отношениями. Такие волновые алгоритмы называются алгоритмами обхода и рассматриваются в Разделе 6.3.

6.1.2 Элементарные результаты о волновых алгоритмах
В этом подразделе доказываются некоторые леммы, которые помогают лучше понять структуру волновых вычислений, и приведены две тривиальные нижние границы сложности сообщений волновых алгоритмов.
Структурные свойства волн. Во-первых, каждому событию в вычислении предшествует событие в инициаторе.
Лемма 6.2 Для любого события e ? C существует инициатор p и событие f в Cp такое, что f ? e.
Доказательство. Выберем в качестве f минимальный элемент в предыстории e, т.е. такой, что f ? e и не существует f' ? f. Такое f существует, поскольку предыстория каждого события конечна. Остается показать, что процесс p, в котором находится f, является инициатором. Для начала, заметим, что f - это первое событие p, иначе более раннее событие p предшествовало бы f. Первое событие не-инициатора - это событие получения сообщения, которому предшествовало бы соответствующее событие посылки сообщения, что противоречит минимальности f. Следовательно, p является инициатором.
Волна с одним инициатором определяет остовное дерево сети, где для каждого не-инициатора выбирается канал, через который будет получено первое сообщение.
Лемма 6.3 Пусть C - волна с одним инициатором p; и пусть для каждого не- инициатора q fatherq - это сосед q, от которого q получает сообщение в своем первом событии. Тогда граф T = (P, ET), где ET = {qr: q ? p & r = fatherq } - остовное дерево, направленное к p.
Доказательство. Т.к. количество вершин T превышает количество ребер на 1, достаточно показать, что T не содержит циклов. Это выполняется, т.к. если eq - первое событие в q, из того, что qr ? ET следует, что er ? eq, а ? - отношение частичного порядка.
В качестве события f в пункте (3) Определения 6.1 может быть выбрано событие посылки сообщения всеми процессами q, кроме того, где происходит событие decide.
Лемма 6.4 Пусть C - волна, а dp ? C - событие decide в процессе p. Тогда

? q ? p: ? f ? Cq: ( f ? dp & f - событие send)
Доказательство. Т.к. C - это волна, существует событие f ?Cq, которое каузально предшествует dp; выберем в качестве f последнее событие Cq, которое предшествует dp. Чтобы показать, что f - событие send, отметим, что из определения каузальности (Определение 2.20) следует, что существует последовательность (каузальная цепочка) f = e0, e1, ..., ek = dp, такая, что для любого i < k, ei и ei+1 - либо последовательные события в одном процессе, либо пара соответствующих событий send-receive. Т.к. f - последнее событие в q, которое предшествует dp, e1 происходит в процессе, отличном от q, следовательно f - событие send.

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.

Предыдущая страница реферата | 22  23  24  25  26  27  28  29  30  31  32 | Следующая страница реферата