Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 44
Текст из файла (страница 44)
Пометки приписываются вершинам в порядке расположения рядов, а в каждом ряду в порядке расположения вершин, т. е. i-йвершине, расположенной в j-м ряду, приписывается число (j − 1)n + (i − 1).Канал, ведущий вверх, помечается 0, канал, ведущий влево, помечается числом(j − 1)n, канал, ведущий вправо, помечается числом (j − 1)n + i, а канал, ведущийвниз, помечается числом j · n (см. рис. 4.19).Теперь можно легко проверить, что всякий раз, когда узел u отправляет пакетв адрес вершины v, выполняется один из следующих случаев:случай 1: если вершина v лежит выше, чем вершина u, то u продвигает пакетпо каналу, направленному вверх;случай 2: если вершина v лежит ниже, чем вершина u, то u продвигает пакетпо каналу, направленному вниз;Кол.
iРяд n159Кол. nuuuun − 1(j − 1)n + (i − 1)uu u0+uuuuuuuuuuuuuuuuuuuuРазметка вершин(j − 1)nk(j − 1)n + ijnРазметка канала,примыкающего к узлу (j − 1)n + (i − 1)Рис. 4.19. Оптимальная ILS для решетки размера n × nслучай 3: если v лежит в том же ряду, что и u, но слева, то вершина u продвигает пакет по каналу, направленному влево;случай 4: если v лежит в том же ряду, что и u, но справа, то вершина uпродвигает пакет по каналу, направленному вправо.Во всех этих случаях узел u передает пакет другому узлу, который расположенближе к вершине v. Отсюда следует оптимальность выбранного пути.Коль скоро ILS, построенная при доказательстве теоремы 4.35, является оптимальной, она также является и добрососедской; схема является линейной.Следующие два результата будут сформулированы без доказательств; в качестве упражнения читателям предлагется построить схемы разметки, о которыхговорится в этих теоремах.Теорема 4.36.
Для гиперкубов существуют минимальные по числу звеньев схемы интервальной разметки.Теорема 4.37 ([93]). Для внешне плоских графов, каналы в которыхимеют произвольные весовые коэффициенты, существуют минимальныепо длине пути схемы интервальной разметки.По сравнению с классическими методами маршрутизации, предусматривающими отдельный выбор предпочтительного канала для каждой вершины-адресата,интервальная маршрутизация имеет ряд преимуществ.1.
Малая сложность по объему памяти. Если степень вершины равнаdeg, то для хранения таблицы маршрутизации достаточно O(deg · log N) битовпамяти.2. Эффективное вычисление таблиц маршрутизации. Таблицы маршрутизации для схемы интервальной разметки в глубину можно вычислить припомощи распределенного поиска в глубину, который проводится с использованием O(E) обменов сообщениями за время O(N) (см.
§ 6.6.4).160Гл. 4. Алгоритмы маршрутизации3. Оптимальность. Для некоторых классов сетей интервальные методы маршрутизации позволяют выбирать оптимальные пути (см., например, теоремы 4.34 –4.37).Благодаря этим положительным качествам рассмотренные в этом параграфе методы маршрутизации пригодны для процессорных сетей с регулярной топологией. Поскольку такого рода топологические структуры часто образуютсяв транспьютерах, интервальная маршрутизация реализована в микроэлектронной схеме маршрутизации Inmos C104 (см. § 1.1.5).К сожалению, в случае применения метода маршрутизации, использующего схему интервальной разметки в глубину, к сетям с произвольной топологиейпроявляется и целый ряд недостатков.1. Плохая устойчивость.
Если в сети происходит обрыв или восстановление одного из каналов, то адаптировать схему интервальной разметки в глубину к этим изменениям весьма непросто. После этих изменений дерево поискав глубину, положенное в основу ILS, может уже не удовлетворять условию, требующему, чтобы стягивающие ребра всегда соединяли вершину и ее предка. Врезультате даже небольшое изменение топологии сети может повлечь за собойпроведение полного перевычисления всех таблиц маршрутизации, вплоть до проведения новой разметки вершин сети.2. Неоптимальность.
Схемы интервальной разметки в глубину могут продвигать пакеты по маршрутам длины Ω (N) даже в тех случаях, когда диаметрсетей невелик (см. упражнение 4.7).В научных публикациях рассматривались разные варианты методов интервальной маршрутизации. Многоинтервальные схемы маршрутизации, о которыхмы говорили ранее, оказались очень удобными для практических приложений,поскольку современные технологии хранения информации позволяют снизить издержки, связанные с введением дополнительных пометок. Многомерный вариантILS описан Фламмини и др. в работе [84] . Именами вершин и пометками каналовслужат точки и интервалы в многомерном пространстве, а не в множестве Z N ,и этот метод имеет некоторые преимущества в случае его применения к сетям,имеющим многомерную структуру, подобную декартовым произведениям графов.Более гибким подходом, позволяющим воспользоваться особенностями структуры сети, является булева маршрутизация, предложенная Фламмини и др.[82] .
Здесь в качестве имен вершин выступают булевы векторы, а ребра помечаются предикатами; сообщение, адресованное узлу с именем , может бытьотправлено по каналу связи с пометкой L тогда и только тогда, когда L ( ) имеет истинное значение. Этот метод позволяет эффективно справляться с сетями,обладающими очень сложной структурой, но при этом, конечно, возникают значительные трудности, связанные с интерпретацией пометок.4.4. Маршрутизация с использованием компактных таблиц161ного дерева. Снятие всяких ограничений, налагаемых на структуру остовных деревьев, позволяет повысить как устойчивость, так и эффективность маршрутизации.
Если добавить новый канал между существующими вершинами, то остовноедерево по-прежнему останется остовным деревом, а новый канал станет в немстягивающим ребром. Если к графу добавить новый узел вместе с каналами, соединяющими его с существующими вершинами, то остовное дерево можно расширить, добавив новую вершину и один из ее каналов; остальные каналы становятся стягивающими ребрами. Для повышения оптимальности можно выбиратьостовные деревья малой глубины, о которых говорится в лемме 4.22.В префиксной маршрутизации в качестве пометок для вершин и каналов используются строки, а не целые числа, как это принято в интервальной маршрутизации. Пусть задан алфавит Σ; пометками будут служить строки (слова) в алфавите Σ.
Символом обозначим пустую строку, а для множества всех строк в алфавите Σ будем использовать обозначение Σ∗ . Чтобы выбрать канал, по которомунужно продвигать пакет, алгоритм рассматривает все пометки каналов, являющиеся префиксом адреса вершины назначения. Выбирается наиболее длиннаяиз таких пометок, и продвижение сообщения проводится по соответствующемуканалу. Например, допустим, что каналы, примыкающие к некоторому узлу, помечены строками aabb, abba, aab, aabc и aa и при этом из этого узла нужнодоставить сообщение по адресу aabbc. Пометки каналов aabb, aab и aa являются префиксами строки aabbc, наиболее длинным префиксом является строкаaabb, и, следовательно, узел продвигает пакет по каналу, помеченному строкойaabb.
Процедура маршрутизации описана в алгоритме 4.20. Запись / служитдля обозначения того, что строка является префиксом строки .(* Пакет, адресованный узлу d, получен или сформирован в узле u *)if d = luthen пакет доставлен по адресуelse begin i := самая длинная пометка канала, для которой выполняетсяотправить пакет по каналу с пометкой iendi/d ;Алгоритм 4.20. Продвижение на основе префиксов (для узла u).Определение 4.38. Схемой префиксной разметки (в алфавите Σ) для сетиG называется такая разметка узлов и каналов связи сети, при которой1) узлы сети G помечаются различными строками в алфавите Σ ∗ ,2) для каждого узла примыкающие к нему каналы помечаются различнымистроками.4.4.3.
Префиксная маршрутизацияДля заданной схемы префиксной маршрутизации (PLS) продвижение пакетовпроводится согласно алгоритму 4.20.Чтобы преодолеть недостатки, присущие методам интервальной маршрутизации, Беккер, ван Ливен и Тан в работе [19] разработали метод маршрутизации,в котором таблицы маршрутизации вычисляются на основе произвольного остов-Определение 4.39.
Схема префиксной разметки называется правильной,если всякий пакет, продвигающийся в сети в соответствии с этой схемой, достигает своего адресата.162Гл. 4. Алгоритмы маршрутизацииТеорема 4.40. Для каждой связной сети G существует правильная PLS.Д о к а з а т е л ь с т в о. Мы определим класс схем префиксной разметки и докажем, подобно тому как мы это сделали в теореме 4.25, что схемы из этогокласса являются правильными. Обозначим символом T произвольное корневоеостовное дерево графа G.Определение 4.41. Деревесной PLS для графа G (относительно T) назовемсхему префиксной разметки, которая построена согласно следующим правилам:1) корневая вершина помечена строкой ;2) если w — сыновняя вершина для u, то строка lw получается из строки luдобавлением одной буквы, т.
е. если u1 , . . . , uk — это сыновние вершиныдля u в дереве T, то lui = lu .ai , где a1 , . . . , ak — k разных букв алфавита Σ;3) если uw — стягивающее ребро, то uw = lw .4) если w — сыновняя вершина для u, то uw = lw ;5) если w — родительская вершина для u, то uw = , за исключением случая,когда вершина u соединена с корнем стягивающим ребром; в этом случаеuw = lw .В древесной PLS к каждой вершине, за исключением корневой, примыкаетканал, помеченный строкой , и этот канал соединяет вершину с одним из еепредков (родительской вершиной или корнем дерева). Следует иметь в виду, чтодля каждого канала uw выполняется одно из двух соотношений uw = lw илиuw = .
Для любой пары вершин u и v вершина v является предком вершины uв том и только том случае, когда lv / lu .Прежде всего нам нужно показать, что ни один пакет не «зависает» в тех узлах, которые не являются его адресатами, т. е. есть каждый узел, не являющийсяадресатом пакета, может продвинуть этот пакет, руководствуясь алгоритмом 4.20.Лемма 4.42. Для любой пары узлов u и v, u 6= v, существует канал связи, примыкающий к вершине u и помеченный строкой, которая являетсяпрефиксом пометки lv .Д о к а з а т е л ь с т в о. Если вершина u не является корнем дерева T, то к uпримыкает канал, помеченный пустой строкой , которая является префиксом l v .Если u — корень дерева, то вершина v отлична от корня, и поэтому v ∈ T [u] .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
