Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 43
Текст из файла (страница 43)
Чтобы убедиться в этом, рассмотрим вначале оптимальные таблицы маршрутизации, вычисленные, например, при помощи алгоритма Netchange, и заметим, что для каждого ребра соответствующее множествовершин-адресатов может быть представлено в виде объединения циклическихинтервалов. При таком элементарном подходе каждому ребру будет приписаноне более N/2 пометок и для каждой вершины будет не более N пометок.
Объемпамяти, необходимый для хранения подобных интервальных таблиц, будет точнотаким же, какой необходим для хранения классических таблиц полной маршрутизации.Теперь попробуем понять, как связаны между собой сложность по объемупамяти и эффективность маршрутизации. Вполне естественно задаться вопросомо том, сколько разных меток необходимо для получения оптимальной маршрутизации. Начало исследований в этом направлении положила работа Фламминии др. [83], в которой был разработан метод поиска подходящих схем и доказательства нижних оценок.
Из результатов этой работы видно, что в общем случаедля достижения оптимальности может потребоваться приписать 0(jV) пометоккаждой линии связи. Но стоит только пойти на маленький компромисс, как сразу же происходит существенное сокращение размера таблиц. Работа Ружички[166] подвела итоги исследования этого компромисса.Маршрутизация при помощи схем линейных интервалов. Для того чтобыприменять интервальные методы маршрутизации, очень важно иметь возможность использовать циклические интервалы. Хотя для некоторых сетей можнопостроить правильные и даже оптимальные схемы разметки линейными интерва4.4.
Маршрутизация с использованием компактных таблиц157лами, тем не менее не каждую сеть можно правильно разметить, ограничившисьтолько линейными интервалами. Вопрос о том, насколько широко можно применять схемы разметки линейными интервалами, был исследован в работе Беккера,ван Ливен и Тана [18].Теорема 4.33. Существует такая сеть, для которой нет правильнойсхемы разметки линейными интервалами.Д о к а з а т е л ь с т в о . Рассмотрим граф с тремя отростками длины два(см. рис.
4.17). Наименьшая пометка (0) и наибольшая разметка (6 ) приписанадвум вершинам, и, коль скоро в графе есть три отростка, имеется хотя бы одинотросток, в котором нет ни наибольшей, ни наименьшей пометки. Рассмотримпервую, считая от центра, вершину х в этом отростке. Узел х продвигает в центрпакеты, адресованные узлам с пометками 0 и 6 , а единственный линейный интервал, который содержит оба числа 0 и 6 , — это все множество Z#. Следовательно,узел х должен будет также продвигать в центр и те пакеты, которые адресованыдругому его соседу, и эти пакеты никогда не достигнут адресата.□Беккер, ван Ливен и Тан полностью описали класс сетей, топология которыхдопускает построение линейных ILS, оптимальных по длине маршрута, а также получили ряд результатов, описывающих классы графов, топология которыхдопускает построение адаптивных линейных ILS, оптимальных по числу звеньев.Полностью охарактеризовать класс сетей, для которых имеются линейные схемы,удалось Fragniaud и Gavoille в работе [94]; Эйлем и др.
в работе [76] показали,что длина путей, которые порождаются линейными схемами в таких сетях, можетдостигать величины 0(D2).Оптимальность интервальной маршрутизации: топологии специальноговида. Оказывается, для некоторых классов сетей, имеющих регулярную структуру, можно построить оптимальные схемы интервальной разметки. Сети с такойГл. 4.
Алгоритмы маршрутизации158структурой возникают, например, при конструировании параллельных компьютеров.Теорема 4.34 ([1 2 8 ]). Для колец с N вершинами существуют минимальные по числу звеньев схемы интервальной разметки.ААА = Адресаты, к которым обращаютсяпротив часовой стрелки из узла iС = Адресаты, к которым обращаютсяпо часовой стрелке из узла iРис. 4.18.
Оптимальная ILS для кольцаД о к а з а т е л ь с т в о . Узлы помечаются числами от 0 до N — 1 в направлении по часовой стрелке. В узле i каналу, примыкающему к этой вершине внаправлении по часовой стрелке, приписывается число i + 1 , а каналу, примыкающему к этой вершине в направлении против часовой стрелки, приписываетсячисло (/+ fjV/2"|) mod N (см. рис. 4.18). При такой схеме разметки узел с номером/ отправляет пакеты, предназначенные вершинам г+ 1 , . . . , (г+|"А/2 ])—1 , по часовой стрелке, а пакеты, предназначенные вершинам (i+\N / 2]),1, — противчасовой стрелки, и этот способ маршрутизации является оптимальным.□Коль скоро ILS, построенная при доказательстве теоремы 4.34, является оптимальной, она также является и добрососедской; но она нелинейна.Теорема 4.35 ([1 2 8 ]). Для решеток размера п х п существуют минимальные по числу звеньев схемы интервальной разметки.Д о к а з а т е л ь с т в о .
Пометки приписываются вершинам в порядке расположения рядов, а в каждом ряду в порядке расположения вершин, т. е. г-йвершине, расположенной в / - м ряду, приписывается число Q — \)п + (г — 1 ).Канал, ведущий вверх, помечается 0, канал, ведущий влево, помечается числом(/ —1 )п, канал, ведущий вправо, помечается числом (/ —l)n + i, а канал, ведущийвниз, помечается числом / • п (см. рис.
4.19).Теперь можно легко проверить, что всякий раз, когда узел и отправляет пакетв адрес вершины v, выполняется один из следующих случаев:случай 1 : если вершина v лежит выше, чем вершина м, то и продвигает пакетпо каналу, направленному вверх;случай 2: если вершина v лежит ниже, чем вершина и, т о и продвигает пакетпо каналу, направленному вниз;4.4.
Маршрутизация с использованием компактных таблицКол.РядКол. i159Кол. п.0г-----( / - 1)п + (i — 1)а - 1)n+j( / - 1 )»-о -/яРяд пФк-___Разметка вершинРазметка канала,примыкающего к узлу (J — 1)я + (г — 1)Рис. 4.19. Оптимальная ILS для решетки размера я х яслучай 3: если v лежит в том же ряду, что и и, но слева, то вершина и продвигает пакет по каналу, направленному влево;случай 4: если v лежит в том же ряду, что и и, но справа, то вершина ипродвигает пакет по каналу, направленному вправо.Во всех этих случаях узел и передает пакет другому узлу, который расположенближе к вершине V.
Отсюда следует оптимальность выбранного пути.□Коль скоро ILS, построенная при доказательстве теоремы 4.35, является оптимальной, она также является и добрососедской; схема является линейной.Следующие два результата будут сформулированы без доказательств; в качестве упражнения читателям предлагется построить схемы разметки, о которыхговорится в этих теоремах.Теорема 4.36. Для гиперкубов существуют минимальные по числу звеньев схемы интервальной разметки.Теорема 4.37 ([9 3 ]).
Для внешне плоских графов, каналы в которыхимеют произвольные весовые коэффициенты, существуют минимальныепо длине пути схемы интервальной разметки.По сравнению с классическими методами маршрутизации, предусматривающими отдельный выбор предпочтительного канала для каждой вершины-адресата,интервальная маршрутизация имеет ряд преимуществ.1. Малая сложность по объему памяти. Если степень вершины равнаdeg, то для хранения таблицы маршрутизации достаточно 0(deg ■logiV) битовпамяти.2. Эффективное вычисление таблиц маршрутизации. Таблицы маршрутизации для схемы интервальной разметки в глубину можно вычислить припомощи распределенного поиска в глубину, который проводится с использованием 0(E) обменов сообщениями за время 0(N) (см.
§6.6.4).160Гл. 4. Алгоритмы маршрутизации3.Оптимальность. Для некоторых классов сетей интервальные методы маршрутизации позволяют выбирать оптимальные пути (см., например, теоремы 4.34—4.37).Благодаря этим положительным качествам рассмотренные в этом параграфе методы маршрутизации пригодны для процессорных сетей с регулярной топологией. Поскольку такого рода топологические структуры часто образуютсяв транспьютерах, интервальная маршрутизация реализована в микроэлектронной схеме маршрутизации Inmos С 104 (см. § 1.1.5).К сожалению, в случае применения метода маршрутизации, использующего схему интервальной разметки в глубину, к сетям с произвольной топологиейпроявляется и целый ряд недостатков.1.
Плохая устойчивость. Если в сети происходит обрыв или восстановление одного из каналов, то адаптировать схему интервальной разметки в глубину к этим изменениям весьма непросто. После этих изменений дерево поискав глубину, положенное в основу ILS, может уже не удовлетворять условию, требующему, чтобы стягивающие ребра всегда соединяли вершину и ее предка. Врезультате даже небольшое изменение топологии сети может повлечь за собойпроведение полного перевычисления всех таблиц маршрутизации, вплоть до проведения новой разметки вершин сети.2.
Неоптимальность. Схемы интервальной разметки в глубину могут продвигать пакеты по маршрутам длины Q(N) даже в тех случаях, когда диаметрсетей невелик (см. упражнение 4.7).В научных публикациях рассматривались разные варианты методов интервальной маршрутизации. Многоинтервальные схемы маршрутизации, о которыхмы говорили ранее, оказались очень удобными для практических приложений,поскольку современные технологии хранения информации позволяют снизить издержки, связанные с введением дополнительных пометок. Многомерный вариантILS описан Фламмини и др.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
