Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 44

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 44)

в работе [84]. Именами вершин и пометками каналовслужат точки и интервалы в многомерном пространстве, а не в множестве Zyy,и этот метод имеет некоторые преимущества в случае его применения к сетям,имеющим многомерную структуру, подобную декартовым произведениям графов.Более гибким подходом, позволяющим воспользоваться особенностями струк­туры сети, является б у л е в а м а р ш р у т и з а ц и я , предложенная Фламмини и др.[82]. Здесь в качестве имен вершин выступают булевы векторы, а ребра по­мечаются предикатами; сообщение, адресованное узлу с именем X, может бытьотправлено по каналу связи с пометкой L тогда и только тогда, когда £(Х) име­ет истинное значение.

Этот метод позволяет эффективно справляться с сетями,обладающими очень сложной структурой, но при этом, конечно, возникают зна­чительные трудности, связанные с интерпретацией пометок.4.4.3. Префиксная маршрутизацияЧтобы преодолеть недостатки, присущие методам интервальной маршрутиза­ции, Беккер, ван Ливен и Тан в работе [19] разработали метод маршрутизации,в котором таблицы маршрутизации вычисляются на основе произвольного остов-4.4. Маршрутизация с использованием компактных таблиц161ного дерева. Снятие всяких ограничений, налагаемых на структуру остовных де­ревьев, позволяет повысить как устойчивость, так и эффективность маршрутиза­ции.

Если добавить новый канал между существующими вершинами, то остовноедерево по-прежнему останется остовным деревом, а новый канал станет в немстягивающим ребром. Если к графу добавить новый узел вместе с каналами, со­единяющими его с существующими вершинами, то остовное дерево можно рас­ширить, добавив новую вершину и один из ее каналов; остальные каналы стано­вятся стягивающими ребрами. Для повышения оптимальности можно выбиратьостовные деревья малой глубины, о которых говорится в лемме 4.22.В префиксной маршрутизации в качестве пометок для вершин и каналов ис­пользуются строки, а не целые числа, как это принято в интервальной маршрути­зации. Пусть задан алфавит Е; пометками будут служить строки (слова) в алфа­вите Е.

Символом е обозначим пустую строку, а для множества всех строк в ал­фавите Е будем использовать обозначение Е*. Чтобы выбрать канал, по которомунужно продвигать пакет, алгоритм рассматривает все пометки каналов, являю­щиеся префиксом адреса вершины назначения. Выбирается наиболее длиннаяиз таких пометок, и продвижение сообщения проводится по соответствующемуканалу. Например, допустим, что каналы, примыкающие к некоторому узлу, по­мечены строками aabb, abba, aab, aabc и aa и при этом из этого узла нужнодоставить сообщение по адресу aabbc. Пометки каналов aabb, aab и аа явля­ются префиксами строки aabbc, наиболее длинным префиксом является строкаaabb, и, следовательно, узел продвигает пакет по каналу, помеченному строкойaabb. Процедура маршрутизации описана в алгоритме 4.20.

Запись а<ф служитдля обозначения того, что строка а является префиксом строки {3.(* Пакет, адресованный узлу d, получен или сформирован в узле и *)if d = luthen пакет доставлен по адресуelse begin ct, := самая длинная пометка канала, для которой выполняется a; <\d ;отправить пакет по каналу с пометкой а,endАлгоритм 4.20. Продвижение на основе префиксов (для узла и).Определение 4.38. Схемой префиксной разметки (в алфавите Е) для сетиG называется такая разметка узлов и каналов связи сети, при которой1) узлы сети G помечаются различными строками в алфавите Е*,2) для каждого узла примыкающие к нему каналы помечаются различнымистроками.Для заданной схемы префиксной маршрутизации (PLS) продвижение пакетовпроводится согласно алгоритму 4.20.Определение 4.39. Схема префиксной разметки называется правильной ,если всякий пакет, продвигающийся в сети в соответствии с этой схемой, дости­гает своего адресата.162Гл.

4. Алгоритмы маршрутизацииТеорема 4.40. Для каждой связной сети G существует правильная PLS.Д о к а з а т е л ь с т в о . Мы определим класс схем префиксной разметки и до­кажем, подобно тому как мы это сделали в теореме 4.25, что схемы из этогокласса являются правильными. Обозначим символом Т произвольное корневоеостовное дерево графа G.Определение 4.41.

Деревесной PLS для графа G (относительно Т) назовемсхему префиксной разметки, которая построена согласно следующим правилам:1) корневая вершина помечена строкой е;2) если да — сыновняя вершина для и, то строка lw получается из строки /„добавлением одной буквы, т. е. если и\, . . . , Uk — это сыновние вершиныдля и в дереве Т, то lUi = lu-ai, где а \ , . . . , а*. — k разных букв алфавита Е;3) если uw — стягивающее ребро, то aaw = lw.4) если да — сыновняя вершина для и, то aaw = lw;5) если да — родительская вершина для и, то ааш = е, за исключением случая,когда вершина и соединена с корнем стягивающим ребром; в этом случае& -U W=lw -В древесной PLS к каждой вершине, за исключением корневой, примыкаетканал, помеченный строкой е, и этот канал соединяет вершину с одним из еепредков (родительской вершиной или корнем дерева). Следует иметь в виду, чтодля каждого канала uw выполняется одно из двух соотношений auw = lw илиauw = е.

Для любой пары вершин и ни вершина v является предком вершины ив том и только том случае, когда lv < 1и.Прежде всего нам нужно показать, что ни один пакет не «зависает» в тех уз­лах, которые не являются его адресатами, т. е. есть каждый узел, не являющийсяадресатом пакета, может продвинуть этот пакет, руководствуясь алгоритмом 4.20.Лемма 4.42.

Для любой пары узлов и и v, и Ф v, существует канал свя­зи, примыкающий к вершине и и помеченный строкой, которая являетсяпрефиксом пометки lv.Д о к а з а т е л ь с т в о . Если вершина и не является корнем дерева Т, то к ипримыкает канал, помеченный пустой строкой е, которая является префиксом lv.Если и — корень дерева, то вершина v отлична от корня, и поэтому v € Т[и\. Еслиw — это такая сыновняя вершина для и, для которой выполняется включение v €€.T[w], то по определению древесной схемы выполняется соотношение o.uw<la. □В трех леммах, которые приведены ниже, рассматривается одна и та же ситуа­ция, когда пакет из узла и продвигается согласно алгоритму 4.20 по направлениюк вершине v через узел w, являющийся соседом вершины и.Лемма 4.43.

Если и € T[v], mo w является предком и.Д о к а з а т е л ь с т в о . Если ааш = е, то по построению схемы вершина даявляется предком узла и. Если auw = lw, то, ввиду того что auw<lv, выполняетсясоотношение lw<lv. Отсюда следует, что да является предком вершины v, а значиттакже и предком вершины и.□4.4. Маршрутизация с использованием компактных таблиц163Лемма 4.44.

Если узел и является предком узла v, то узел да являетсяпредком узла v, и при этом узел да расположен к вершине v ближе, чемузел и.Д о к а з а т е л ь с т в о . Рассмотрим такую сыновнюю вершину да' для узла и ,для которой выполняется включение v е T[w'\. Тогда auw> = lw>— это непу­стой префикс пометки lv. Так как auw — это наиболее длинный префикс (сре­ди всех пометок каналов, примыкающих к и) строки /а, отсюда следует, чтооiuw><\ auw < lv, и поэтому узел да является предком вершины v, который рас­положен ниже узла и.□Лемма 4.45.

Если и /ET[v\, то либо узел да является предком узла v,либо выполняется неравенство dj(w, v) < dr(u, v).Д о к а з а т е л ь с т в о . Если aaw = е, то да является либо родительскойвершиной для и, либо корнем дерева. Родительская вершина для узла и распо­ложена ближе к узлу v, чем сам узел и, потому что и f&T\v\, а корень дереваявляется предком узла и. Если aaw = lw, то, ввиду того что ааш <1 /0, узел даявляется предком узла и.□Глубиной корневого дерева Т называется величина depth , равная числу зве­ньев самого протяженного простого пути, соединяющего корень дерева с однимиз его листьев. Как можно заметить, каждый пакет, адресованный узлу v, до­стигает вершины-адресата, пройдя путь, состоящий не более чем из 2 • depthзвеньев.

Если пакет сформирован в узле, который является предком вершины v,то согласно лемме 4.44 узел v достигается не более чем за depth шагов. Еслипакет сформирован в одном из узлов поддерева T[v\, то согласно лемме 4.43 одиниз предков v достигается менее чем за depth шагов, после чего, как было толькочто установлено, пакет достигает вершины v не более чем за depth шагов. (Учи­тывая, что в этом случае путь проходит только через узлы, являющиеся предкамивершины-отправителя, можно заключить, что длина пути на самом деле такжене будет превышать величины depth.) Во всех остальных случаях согласно лем­ме 4.45 какой-нибудь предок узла v будет достигнут не более чем за depth шагов,после чего пакет достигает вершины v не более чем за depth шагов. (Таким об­разом, в этом случае длина пройденного пути ограничена величиной 2 • depth)Этим завершается доказательство теоремы 4.40.□Следствие 4.46.

Для каждой сети G диаметра Do, измеряемого числомзвеньев пути, существует такая схема префиксной разметки, котораягарантирует доставку всех пакетов не более чем за 2DG шагов.Д о к а з а т е л ь с т в о . Нужно воспользоваться древесной PLS, дерево ко­торой построено так, как это указано в лемме 4.22.□Мы завершим наше изучение древесной схемы разметки кратким обсуждени­ем вопроса об объеме памяти, необходимом для ее реализации. Как и прежде,depth будет обозначать глубину дерева Т.

Характеристики

Список файлов книги