Распределенные алгоритмы (стр. 39 из 85)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

s_p-1³ f_w

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

f'_w£ f_w+1

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

s_q < f'_w£ f_w+1£ s_p,

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

Контроллер с обратным счетом (backward-count controller). Контроллер, " двойственный " FC , получается, когда решение, принимать ли пакет, основано на количестве шагов, которые пакет уже сделал. Пусть, для пакета p, t_p - количество переходов, которые он сделал от источника. Конечно, 0 £ t_p < k всегда верно.

Определение 5.18 Контроллер BC (Backward-Count) принимает пакет p в вершине u тогда и только тогда, когда t_p > k—f_u.

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

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

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

Контроллер с опережающим состоянием (forward-state controller). Используем обозначение s_p как в предыдущем разделе. Для вершины u определим (как функцию состояния u) вектор состояния , где j - количество пакетов p в u с s_p = s.

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

.

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

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