Оставляем читателю (см. Упражнение 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, т.е.,
Это дает неравенство
Страницы: 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, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
