Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 49
Текст из файла (страница 49)
Предполагается, что в каждом пакете имеетсясчетчик шагов, регистрирующий, сколько раз продвинулся пакет по каналамсвязи, после того как покинул вершину-источник.~ в котором bu [i] bw [j] ∈ BE~ тогдаПусть задан буферный граф BGh = (B , BE),и только тогда, когда i + 1 = j и uw ∈ E. Чтобы убедиться в том, что в графеBGh отсутствуют контуры, заметим, что по мере продвижения пакета индекс буферов, в которые он помещается, строго возрастает.
Коль скоро каждый путь измножества P состоит не более чем из k звеньев, в буферном графе обязательнонайдется соответствующий путь: если P = u0 , . . . , ul , где l 6 k, — это путь в сети,то он является образом путиbu0 [0] , bu1 [1] , . . . , bul [l]в графе BGh . Этот гарантированный путь определяется следующими соотношениями: fb(p) = bu [0] для пакета p, сформированного в узле u, и nb(p, b u [i]) == bw [i + 1] для пакета, который должен продвинуться из узла u в узел w.Д о к а з а т е л ь с т в о. Как видно из определения контроллера dest, он действительно является беступиковым и использует указанное число буферов.Определение 5.10. Контроллер hsf — это контроллер bgcBGh , в которомфункции fb и nb определены так, как указано в предыдущем абзаце.Как было упомянуто выше, требование маршрутизации по входным деревьямможет быть ослаблено: можно потребовать, чтобы пакеты, адресованные одномуи тому же узлу, отправлялись по каналам, которые образуют ациклический граф.Однако, как показывает пример, изображенный на рис.
5.2, недостаточно того,чтобы в множестве P содержались только простые пути. Здесь пакеты из узлаu1 в узел v следуют по простому пути hu1 , w1 , u2 , . . . , vi, а пакеты из узла u2 вузел v следуют по простому пути hu2 , w2 , u1 , . . . , vi. Каждый путь в множествеP является простым; совокупность всех каналов, используемых для доставкипакетов в узел v, содержит цикл hu1 , w1 , u2 , w2 , u1 i.
Далее см. упражнение 5.2.Контроллер dest очень прост в использовании, но имеет недостаток, которыйсостоит в том, что в каждом узле требуется заводить слишком много буферов,а именно столько, сколько имеется узлов в сети. Можно определить двойствен-Теорема 5.11. Для всякой связной сети диаметра D существует беступиковый контроллер, который использует D + 1 буферов в каждом узлеи требует продвижения пакетов по путям с наименьшим числом звеньев.Д о к а з а т е л ь с т в о. Для путей с наименьшим числом звеньев мы имеемk = D. Тогда hsf действительно является беступиковым контроллером, которомутребуется D + 1 буферов в каждом узле. (Можно ограничиться и меньшим числомбуферов, если обмен сообщениями между отдаленными узлами не проводится.)В схеме пройденных шагов буферы с индексом i используются для храненияпакетов, которые к этому моменту продвинулись i раз по каналам связи.
Можнопостроить и двойственную схему предстоящих шагов. В ней буферы с индек-178Гл. 5. Неблокируемая коммутация пакетовсом i используются для хранения пакетов, которым еще предстоит совершить iпродвижений по каналам связи (см. упражнение 5.3).5.2.2. Ориентации сети GВ этом параграфе мы изучим один метод построения более изощренных буферных графов, которым нужно всего лишь несколько буферов в каждом узле.Контроллер пройденных шагов помещает пакеты в буферы, индекс которых увеличивается с каждым перемещением пакета. Теперь мы сделаем так, что индексбуферов будет увеличиваться гораздо медленнее (и сэкономим, таким образом,общее количество буферов в каждом узле), за счет того что возрастание индекса(не путать с классом буфера!) не обязательно будет происходить на каждом шагепродвижения пакета.
Чтобы не допустить появления циклов в буферном графе,каналы, по которым продвижение пакета происходит без увеличения буферногоиндекса, должны образовывать ациклический граф.Определение 5.12. Ациклической ориентацией графа G называется ориентированный ациклический граф, который образуется за счет установления ориентации всех ребер графа G (см. рис. 5.3).Последовательность ациклических ориентаций G 1 , . . .
, GB графа G называется ациклическим ориентированным покрытием размера B для совокупностипутей P , если любой путь P ∈ P можно представить в виде последовательногосоединения B путей P1 , . . . , PB , где каждый путь Pi проходит в ориентированномграфе Gi .uuHHH u@AX @ XXAAu XX@u@uPPPuPuuuHjHH H1A@AuXXXUR@X@ XzXXA XAu@@u *uPqPP 1- PuPuРис. 5.3. Граф и его ациклическая ориентацияЕсли есть ациклическое ориентированное покрытие размера B, то можно построить такой контроллер, которому требуется иметь только B буферов в каждомузле.
Пакет, сформированный в узле u, всегда помещается в буфер b u [1] . Еслипакет находится в буфере bu [i] узла u, то при продвижении в узел w он либопомещается в буфер bw [i] в том случае, когда в графе Gi дуга направлена извершины u в вершину w, либо помещается в буфер b w [i + 1] в том случае, когдав графе Gi дуга направлена из вершины w в вершину u.5.2. Структурированные решения179Теорема 5.13. Если множество путей P имеет ациклическое ориентированное покрытие размера B, то можно построить беступиковый контроллер, которому требуется иметь только B буферов в каждом узле.Д о к а з а т е л ь с т в о. Пусть задано ациклическое ориентированное покрытие G1 , . .
. , GB и пусть в узле u выделены буферы bu [1] , . . . , bu [B] . Усло~i , если в графе Gi ребро uw направлено извимся использовать запись uw ∈ E~i , если в графе Gi ребро uw направленовершины u в вершину w, и запись wu ∈ E~ в котоиз вершины w в вершину u. Рассмотрим буферный граф BG a = (B , BE),~ром включение bu [i] bw [j] ∈ BE имеет место тогда и только тогда, когда uw ∈ E~i), либо выполняетсяи при этом либо выполняется соотношение (i = j ∧ uw ∈ E~i).
Чтобы убедиться в том, что этот граф не имеетсоотношение (i + 1 = j ∧ wu ∈ Eконтуров, заметим, что циклов, содержащих буферы с разными индексами, бытьне может, поскольку согласно определению этого графа в нем нет дуг, ведущихиз одного буфера в другой буфер с меньшим индексом.
Не может быть такжеи циклов, образованных буферами одного и того же индекса i, потому что связьмежду этими буферами устроена в соответствии с ациклическим графом G i .Читателям предоставляется возможность самостоятельно показать (см. упражнение 5.4), что для любого пути P ∈ P есть гарантированный путь, образом которого является P, и этот путь определяется следующим образом:fb(p) = b(u [1] ,bw [i] ,nb(p, bu [i]) =bw [i + 1] ,~i ,если uw ∈ E~i .если wu ∈ EОпределив буферный граф, в котором каждому узлу отводится B буферов, мыприходим к выводу о том, что существует контроллер, которому требуется иметьтолько B буферов в каждом узле.
Этим и завершается доказательство теоремы.Контроллеры такого вида мы будем называть контроллерами ациклического ориентированного покрытия или коротко AOC-контроллерами. Теперь мыперейдем к демонстрации того, насколько легко можно построить контроллеры,воспользовавшись ациклическими ориентированными покрытиями.Коммутация пакетов в кольце. При помощи ациклических ориентированных покрытий можно построить беступиковые контроллеры для различных классов сетей. Мы начнем с того, что покажем, как построить контроллер для колец,используя только три буфера в каждом узле.
В приведенной ниже теореме считается, что весовые коэффициенты каналов симметричны, т. е. uw = wu .Теорема 5.14. Для кольцевой сети можно построить контроллер, которому требуется иметь только три буфера в каждом узле, чтобы провести маршрутизацию пакетов по кратчайшим путям.Д о к а з а т е л ь с т в о. Согласно теореме 5.13 для этого достаточно подобрать ациклическое ориентированное покрытие размера три для совокупностипутей, которая содержит для каждой пары узлов кратчайший путь между ними.180Гл.
5. Неблокируемая коммутация пакетов5.2. Структурированные решенияВведем следующие обозначения. Условимся, что для каждой пары узлов u и vзапись dc (u, v) будет обозначать длину пути, направленного по часовой стрелке,из вершины u в вершину v, запись da (u, v) — длину пути, направленного противчасовой стрелки, из вершины u в вершину v (заметим, что d c (v, u) = da (u, v)),а запись d(u, v) — минимальную из двух величин min(dc (u, v) и da (u, v)).
Сумма C весовых коэффициентов всех каналов называется длиной кольца / Очевидно, что для любой пары узлов u, v верно равенство d c (u, v) + da (u, v) = C, ипоэтому d(u, v) 6 C/2.uu@@R@@uu?@R@-@R@G1-?uvuu6I@@I@@G26uvuu?@R@-uuuuuur@@uu Tuuu@R@ uuu?u uAAUAu - u?- ur@u- u I@u u T1uKAAuuI@@uu6u -u6Au u ur@@ u - u T2u u RРис. 5.5. Ациклическое ориентированное покрытие для дереваТеорема 5.15. Для древесной сети существует контроллер, которомутребуется иметь только два буфера в каждом узле.@R@G3-uAAAuuКоммутация пакетов в дереве.
Для древесной сети можно построить контроллер, которому требуется иметь только два буфера в каждом узле.dc (u, v) ≈ da (u, v)uvu@@u181?uvРис. 5.4. Ациклическое ориентированное покрытие для кольцаВначале рассмотрим простой случай, когда есть пара таких узлов u и v, чтоd(u, v) = C/2. Ориентированные графы G1 и G3 получены путем ориентации всехребер по направлению к вершине v, а ориентированный граф G 2 получен путемориентации всех ребер по направлению к вершине u (см.
рис. 5.4).Кратчайший путь из узла u в узел v содержится в графе G 1 или G3 , а кратчайший путь из v в u содержится в графе G2 . Рассмотрим теперь другую паруузлов x, y, отличную от пары u, v. Тогда, ввиду того что d(x, y) 6 C /2, существует кратчайший путь P из узла x в узел y, который не содержит либо вершину u,либо вершину v. Если P не содержит ни u, ни v, то этот путь целиком содержитсялибо в графе G1 , либо в графе G2 . Если P проходит через v, то он образуетсяпоследовательным соединением пути в графе G1 и пути в графе G2 . Если P проходит через u, то он образуется последовательным соединением пути в графе G 2и пути в графе G3 .Если нет такой пары узлов u, v, для которой верно равенство d(u, v) = C /2,то выберем такую пару узлов, для которой величина d(u, v) наиболее близкак C/2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
