Т.к. контроллер позволяет размещение пакетов только в подходящих буферах и т.к. изначально нет пакетов, каждая достижимая конфигурация сети под управлением bgcBG содержит пакеты только в подходящих буферах. С помощью индукции "сверху вниз" по классам буферов  можно легко показать, что ни один буфер класса r не содержит в такой конфигурации тупиковых пакетов. Пусть R - самый большой класс буфера.

Случай r = R: Буфер b вершины u, имеющий самый большой из возможных классов, не имеет исходящих ребер в BG. Следовательно, пакет, для которого b - подходящий буфер, имеет пункт назначения u и может быть выведен, когда он попадает в буфер b. Значит, ни один буфер класса R не содержит тупиковых пакетов.

Случай r < R: Выдвинем гипотезу, что для всех r' таких, что r < r' £ R, ни один буфер класса r' не содержит тупиковый пакет (в достижимой конфигурации).
Пусть g - достижимая конфигурация с пакетом p в буфере b класса r < R вершины u. Если u - место назначения p, то p может быть выведен и, следовательно, он не в тупике. Иначе, пусть nb(p, b) = c - следующий буфер на гарантированном пути b, и заметим, что класс r' буфера c превосходит r. По гипотезе индукции, c не содержит тупиковых пакетов, значит существует  конфигурация d, достижимая из g, в которой c - пуст. Из d  p может продвинуться в c, и, по гипотезе индукции, p не тупиковый в результирующей конфигурации d '. Следовательно, p в конфигурации g не в тупике.

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

Страницы: 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