Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 48
Текст из файла (страница 48)
Чтобыубедиться в том, что в графе BGа отсутствуют контуры, заметим, что в нем нетдуг между буферами с разными назначениями, а буферы с одним и тем же назначением v образуют дерево, изоморфное дереву Ти. Всякий путь Р е Д , оканчивающийся в узле и, является путем в дереве Tv, и по определению рассматриваемогобуферного графа BGa в нем существует такой путь, проходящий по буферам сназначением и, образом которого является путь Р. Именно этот путь в графеBGd и будет считаться гарантированным путем.
Это означает, что для пакета р ,адресованного узлу v и сформированного в узле и, должно выполняться равенство fb(p) = ba[v], и если его нужно отправить в узел да, то должно выполнятьсяравенство nb(p, b) = bw[v].Определение 5.8. Контроллер dest — это контроллер буферного графа bgcBGd,в котором функции fb и nb определены так, как в предыдущем абзаце.Теорема 5.9. Для произвольной связной сети существует беступиковый контроллер , который использует N буферов в каждом узле и позволяет перемещать пакеты по произвольным заранее выбранным входнымдеревьям.Д о к а з а т е л ь с т в о . Как видно из определения контроллера dest, он действительно является беступиковым и использует указанное число буферов.□Как было упомянуто выше, требование маршрутизации по входным деревьямможет быть ослаблено: можно потребовать, чтобы пакеты, адресованные одномуи тому же узлу, отправлялись по каналам, которые образуют ациклический граф.Однако, как показывает пример, изображенный на рис.
5.2, недостаточно того,чтобы в множестве V содержались только простые пути. Здесь пакеты из узлаMi в узел v следуют по простому пути (и\, w\, U2 , . . . , v), а пакеты из узла мг вузел v следуют по простому пути (иг, даг, и\, ...
,v). Каждый путь в множествеV является простым; совокупность всех каналов, используемых для доставкипакетов в узел v, содержит цикл (и\, w\, И2 , да>2 , Mi). Далее см. упражнение 5.2.Контроллер dest очень прост в использовании, но имеет недостаток, которыйсостоит в том, что в каждом узле требуется заводить слишком много буферов,а именно столько, сколько имеется узлов в сети. Можно определить двойствен-5.2. Структурированные решения177Рис.
5.2. Маршрутизация, недопустимая для контроллера destную схему источников, в которой каждый буфер соответствует вершине v-t ииспользуется для хранения пакетов, сформированных в узле г/;.Схема пройденных шагов. В схеме пройденных шагов каждый узел и имеетk + 1 буферов МО], • • • >bu\k\. Предполагается, что в каждом пакете имеетсясчетчик шагов, регистрирующий, сколько раз продвинулся пакет по каналамсвязи, после того как покинул вершину-источник.Пусть задан буферный граф BG\, = (В, BE), в котором bu[i]bw[j] е BE тогдаи только тогда, когда / + 1 = / и uw € Е.
Чтобы убедиться в том, что в графеBGh отсутствуют контуры, заметим, что по мере продвижения пакета индекс буферов, в которые он помещается, строго возрастает. Коль скоро каждый путь измножества V состоит не более чем из k звеньев, в буферном графе обязательнонайдется соответствующий путь: если Р = uq, ... , Ui , где / ^ k, — это путь в сети,то он является образом путиb u № , b u M l - . . , b Ul[i)в графе fiGh.
Этот гарантированный путь определяется следующими соотношениями: fb{p) = МО] дая пакета р, сформированного в узле и, и nb{p, bu[i\) == bw[i + 1 ] для пакета, который должен продвинуться из узла и в узел w.Определение 5.10. Контроллер hsf — это контроллер bgcBGh, в которомфункции fb и nb определены так, как указано в предыдущем абзаце.Теорема 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).Последовательность ациклических ориентаций Gi, . . . , Gg графа G называется ациклическим ориентированным покрытием размера В для совокупностипутей V, если любой путь Р <ЕV можно представить в виде последовательногосоединения В путей Р \ , . . .
, Рд, где каждый путь Р; проходит в ориентированномграфе GyРис. 5.3. Граф и его ациклическая ориентацияЕсли есть ациклическое ориентированное покрытие размера В, то можно построить такой контроллер, которому требуется иметь только В буферов в каждомузле. Пакет, сформированный в узле и, всегда помещается в буфер Ьа[1]. Еслипакет находится в буфере bu[i] узла и, то при продвижении в узел w он либопомещается в буфер bw[i] в том случае, когда в графе Gi дуга направлена извершины и в вершину w, либо помещается в буфер bw[i + 1 ] в том случае, когдав графе Gi дуга направлена из вершины w в вершину и.5.2.
Структурированные решения179Теорема 5.13. Если множество путей V имеет ациклическое ориентированное покрытие размера В, то можно построить беступиковый контроллер, которому требуется иметь только В буферов в каждом узле.Д о к а з а т е л ь с т в о . Пусть задано ациклическое ориентированное покрытие G\, . . . , Gg и пусть в узле и выделены буферы ba[1], •••, Ьи\В\. Условимся использовать запись uw € , если в графе Gj ребро uw направлено извершины и в вершину w, и запись wu € /:, если в графе Gj ребро uw направленоиз вершины w в вершину и. Рассмотрим буферный граф В(}„ = (В, BE), в котором включение bu[i]bw[j] € BE имеет место тогда и только тогда, когда uw € Еи при этом либо выполняется соотношение (г = / A uw € /:,), либо выполняетсясоотношение (г + 1 = / A wu € £)). Чтобы убедиться в том, что этот граф не имеетконтуров, заметим, что циклов, содержащих буферы с разными индексами, бытьне может, поскольку согласно определению этого графа в нем нет дуг, ведущихиз одного буфера в другой буфер с меньшим индексом.
Не может быть такжеи циклов, образованных буферами одного и того же индекса г, потому что связьмежду этими буферами устроена в соответствии с ациклическим графом Gj.Читателям предоставляется возможность самостоятельно показать (см. упражнение 5.4), что для любого пути Р € V есть гарантированный путь, образом которого является Р, и этот путь определяется следующим образом:fb (p )= b u[1 ],если uw € £),если wu € £).Определив буферный граф, в котором каждому узлу отводится В буферов, мыприходим к выводу о том, что существует контроллер, которому требуется иметьтолько В буферов в каждом узле. Этим и завершается доказательство теоремы.□Контроллеры такого вида мы будем называть контроллерами ациклического ориентированного покрытия или коротко АОС-контроллерами. Теперь мыперейдем к демонстрации того, насколько легко можно построить контроллеры,воспользовавшись ациклическими ориентированными покрытиями.Коммутация пакетов в кольце.
При помощи ациклических ориентированных покрытий можно построить беступиковые контроллеры для различных классов сетей. Мы начнем с того, что покажем, как построить контроллер для колец,используя только три буфера в каждом узле. В приведенной ниже теореме считается, что весовые коэффициенты каналов симметричны, т. е. соЦШ) = 1йша.Теорема 5.14.
Для кольцевой сети можно построить контроллер, которому требуется иметь только три буфера в каждом узле, чтобы провести маршрутизацию пакетов по кратчайшим путям.Д о к а з а т е л ь с т в о . Согласно теореме 5.13 для этого достаточно подобрать ациклическое ориентированное покрытие размера три для совокупностипутей, которая содержит для каждой пары узлов кратчайший путь между ними.180Гл. 5. Неблокируемая коммутация пакетовВведем следующие обозначения.
Условимся, что для каждой пары узлов и и озапись dc(u, v ) будет обозначать длину пути, направленного по часовой стрелке,из вершины и в вершину v, запись da(u, v) — длину пути, направленного противчасовой стрелки, из вершины и в вершину v (заметим, что dc(v, и) = da(u, и)),а запись d(u, v) — минимальную из двух величин min (dc(u, v) и da(u, и)). Сумма С весовых коэффициентов всех каналов называется длиной кольца/ Очевидно, что для любой пары узлов и, v верно равенство dc(u, и) + da(u, и) = С, ипоэтому d(u, v ) < С/2.Рис.
5.4. Ациклическое ориентированное покрытие для кольцаВначале рассмотрим простой случай, когда есть пара таких узлов и и и, чтоd(u, v ) = С/2. Ориентированные графы G\ и Gз получены путем ориентации всехребер по направлению к вершине и, а ориентированный граф G2 получен путемориентации всех ребер по направлению к вершине и (см. рис. 5.4).Кратчайший путь из узла и в узел v содержится в графе G i или Сз, а кратчайший путь из в в и содержится в графе Сг- Рассмотрим теперь другую паруузлов х, у, отличную от пары и, v. Тогда, ввиду того что d{x, у) < С/2, существует кратчайший путь Р из узла х в узел у , который не содержит либо вершину и ,либо вершину V.
Если Р не содержит ни и , ни и, то этот путь целиком содержитсялибо в графе Gi, либо в графе G2 . Если Р проходит через и, то он образуетсяпоследовательным соединением пути в графе G\ и пути в графе G2 . Если Р проходит через и, то он образуется последовательным соединением пути в графе G2и пути в графе G3 .Если нет такой пары узлов и, v, для которой верно равенство d{u, и) = С/2,то выберем такую пару узлов, для которой величина d{u, и) наиболее близкак С/2. Нетрудно показать, что если бы нашлась пара узлов х, у , кратчайшийпуть между которыми было бы нельзя представить в виде последовательногосоединения путей в указанных ориентированных графах, то величина d(x, у) былабы ближе к С/2, нежели d(u, v).□5.2.
Структурированные решения181Рис. 5.5. Ациклическое ориентированное покрытие для дереваКоммутация пакетов в дереве. Для древесной сети можно построить контроллер, которому требуется иметь только два буфера в каждом узле.Теорема 5.15. Для древесной сети существует контроллер , которомутребуется иметь только два буфера в каждом узле.Д о к а з а т е л ь с т в о . Согласно теореме 5.13 достаточно подобрать ациклическую ориентацию для дерева, которая сможет покрыть все простые пути.Выберем произвольную вершину г и рассмотрим два дерева: Т\, в котором вседуги направлены к вершине г, и Тг, в котором все дуги направлены от вершины г(см. рис. 5.5). Всякий простой путь из вершины и в вершину v представляет собой последовательное соединение пути из и в вершину, являющуюся наименьшимобщим предком вершин и и и в дереве 7), и пути из этого наименьшего общегопредка в вершину v в дереве 7г.□Поскольку описанную здесь схему можно применить к остовному дереву наименьшей глубины, построенному для произвольной сети, мы фактически установили, что для любой сети возможна беступиковая маршрутизация, требующая 2буфера в каждом узле.
Но пути, которые при этом будут задействованы, в общемслучае могут оказаться неоптимальными.Применение АОС-контроллеров. Как показывает нам пример с кольцевыми сетями, для применения АОС-контроллеров могут потребоваться весьмаспециальные пути, по которым должны распространяться сообщения. В связис этим возникает ряд вопросов, исследованию которых был посвящен ряд работпоследних лет.Можно ли, используя минимальное число буферов, переправлять пакеты пооптимальным путям? Если это невозможно, то какова взаимосвязь между буферной сложностью и эффективностью маршрутизации? Штефанкович в работе [179] показал, что АОС-контроллеры не столь уж экономны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
