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

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

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

В трех леммах, которыеприведены ниже, рассматривается одна и та же ситуация, когда пакет из узла и4.4. Маршрутизация с использованием компактных таблиц153Рис. 4.15. Схема интервальной разметки в глубинупродвигается согласно алгоритму 4.13 по направлению к вершине v через узел да,являющийся соседом вершины и. Это подразумевает, что в узле и для некоторойпометки ос выполняется соотношение 4 € [ а цш, а ) и нет такой пометки ос' ^ a uw,для которой в узле и выполняется включение ос' б [ацш, 4)Лемма 4.28.

Если 4 > 4 то lw < /ц.,Д о к а з а т е л ь с т в о . Вначале рассмотрим случай, когда auw ^ /„. Вер­шина да не является сыновней вершиной для и , поскольку в этом случае мыимели бы осuw = lw > lu > lv. Если uw — стягивающее ребро, то lw = auw ^ 4 << 1а. Если w — родительская вершина для и , то в любом случае выполняетсянеравенство lw < 1и.Далее рассмотрим случай, когда auw — это наибольшее число, помечающееребро, примыкающее к узлу и , и не существует пометки а ' ^ lv (т. е. 4 лежитв нижней части нелинейного интервала). В этом случае ребро, соединяющее и сродительской вершиной, помечено не 0 , а числом k u (поскольку 0 ^ 4 и нет по­метки а' ^ 4)• Тогда число k u является максимальной пометкой; ребро (древесноеили стягивающее), ведущее в вершину-потомок да', имеет пометку auw>= lw><< ku, а ребро, ведущее в вершину-предок да', имеет пометку auw> = lw> < 1и.Значит, да — родительская вершина для и, и отсюда следует неравенство lw << 4 .ПВ двух других леммах рассматривается случай, когда /„ < 4- Мы докажем,что тогда либо об Т[и\, либо 4 Д ku, и при этом в последнем случае выполняетсянеравенство ka < N , благодаря чему ребро, ведущее в родительскую вершину дляи, помечено числом ku.Лемма 4.29.

Если 4 < 4 , mo lw ^ 4Д о к а з а т е л ь с т в о . Вначале рассмотрим случай, когда v € Т[и\. Рас­смотрим ту сыновнюю вершину да' для и , для которой выполняется включениеv б T[w'\. Тогда имеем соотношения auw> = lwi < 4, из которых следует, что°W ^ «и® ^ 4 < kw'- Мы заключили, что да не является родительской верши­ной для и, и поэтому lw = auw, откуда следует, что lw < 4 -154Гл. 4. Алгоритмы маршрутизацииДалее рассмотрим случай, когда lv > klL.

Убедимся, что в этом случае даявляется родительской вершиной для и. Ребро, ведущее к родительской вершине,помечено числом ka, и при этом ku /0. Ребро, ведущее в сыновнюю вершину да'для узла и, помечено числом lw>< ku, стягивающее ребро, ведущее в вершинупотомок да', помечено числом lw>< ku, а стягивающее ребро, ведущее в вершинупредок да', помечено числом lw>< 1и. Так как да — это родительская вершина дляи, выполняется неравенство lw < lu < lv.□Нормирующую функцию, позволяющую отслеживать доставку сообщений ввершину v, можно определить следующим образом. Наименьшим общим пред­ком двух узлов и и v называется наиболее удаленная от корня вершина, котораяявляется предком обеих вершин и ни.

Условимся, что запись lca(u, v) будет обо­значать пометку наименьшего общего потомка вершин и и о, и будем полагать/о(и) = (-1са(и , о), /„).Лемма 4.30. Если /„ < lv, то /Дал) < fv(u).Д о к а з а т е л ь с т в о . Начнем с того случая, когда v € Т[и\ (отсюда сле­дует, что lca(u, v) = /ц). Если w' — это та сыновняя вершина для и, для которойимеет место включение о<Е T[w'], то (так же как и в предшествующей лемме) вы­полняются неравенства lw>^ lw < kw>, и поэтому верно включение w € T[w'], изкоторого следуют неравенства lca(w, v) > lw>> /„.

Таким образом, fv(w) < fv(u).Далее рассмотрим случай, когда lv ^ ku. Так же как и в предыдущей лемме,w является родительской вершиной для и, и, коль скоро v /£.Т[и], выполняет­ся равенство lca(w, v) = lca(u, v). Но теперь lw < /„, вследствие чего вернонеравенство fv(w) < fv(u).□Корень: / = 0Рис. 4.16. Продвижение пакета по направлению к вершине v в схеме интервальнойразметки в глубинуТеперь мы можем убедиться в том, что каждый пакет достигает своего адреса­та. Поток пакетов, направленных в вершину v, изображен на рис.

4.16. Допустим,что пакет, адресованный узлу v, был сформирован в вершине и. Согласно лем­ме 4.28, при прохождении каждого звена маршрута метка вершины убывает, дотех пор пока спустя конечное число продвижений пакет не достигнет такой вер­шины да, для которой выполняется неравенство lw ^ lv. Согласно лемме 4.294.4. Маршрутизация с использованием компактных таблиц155каждая вершина, которой после этого передается пакет, имеет пометку, не пре­восходящую числа lv■Тогда спустя конечное число продвижений пакет достигнетвершины v, так как согласно лемме 4.30, пока пакет не достиг вершины v, прикаждом его продвижении значение функции Д, убывает.□Эффективность интервальной маршрутизации: общий случай. Теорема 4.25гласит, что для каждой сети есть правильная ILS, но в этой теореме ничего неговорится об эффективности путей, которые выбираются на основе такой схе­мы.

Нужно ясно представлять себе, что схемы интервальной разметки в глубинуиспользуются для того, чтобы показать существование такого рода схем длякаждой сети, но это отнюдь не означает, что это наилучшие из возможных схем.Например, если применить схему интервальной разметки в глубину к кольцу, со­стоящему из N вершин, то найдутся две такие вершины и н и , что d(u, и) = 2,а схеме требуется пройти маршрут из N —2 звеньев, чтобы доставить пакет извершины и в вершину v (упражнение 4.8).

Для того же кольца существует ILS,которая обеспечивает доставку каждого пакета по маршруту с наименьшим чис­лом звеньев (теорема 4.34).Чтобы оценить качество методов маршрутизации, вначале введем следующееопределение.Определение 4.31. ILS называется оптимальной, если она продвигает всепакеты по оптимальным путям.. ILS называется добрососедской, если она до­ставляет пакет от любой вершины ко всякому ее соседу за один шаг.

ILS назы­вается линейной , если каждому ребру соответствует линейный интервал.Мы будем назвать ILS минимальной по числу звеньев (или минимальнойпо длине пути), если она является оптимальной относительно меры стоимости,определяемой числом звеньев пути (или соответственно длиной пути). Легко ви­деть, что минимальная по числу звеньев схема является добрососедской.

Такжелегко проверить, что ILS является линейной в том и только том случае, когдак каждой вершине и с пометкой /„ Ф 0 примыкает ребро, помеченное 0 , и к каж­дой вершине с пометкой 0 примыкает ребро с пометкой 0 или 1. Оказывается,для произвольных сетей рассмотренные схемы порождают, вообще говоря, неочень качественные маршруты, но для некоторых типов сетей, имеющих специ­альную топологическую структуру, качество маршрутов оказывается очень хоро­шим. Благодаря этому рассмотренные схемы находят применение при решениизадачи маршрутизации в процессорных сетях регулярной структуры, наподобиетех, которые возникают в параллельных вычислительных системах с виртуальнойглобальной разделяемой памятью.В точности неизвестно, как для одной и той же произвольной сети соотносят­ся друг с другом по качеству решений наилучшая схема интервальной разметкии оптимальный алгоритм маршрутизации.

Некоторые нижние оценки длины пу­тей, свидетельствующие о том, что оптимальные ILS существуют не всегда, былиполучены Ружичкой.Теорема 4.32 ([1 6 5 ]). Существует такая сеть G, что для каждойправильной ILS для сети G найдется пара таких вершин и и и, что пакет156Гл. 4. Алгоритмы маршрутизацииот вершины и к вершине v доставляется по маршруту, состоящему по3пменьшей мере из -D q звеньев.Также неизвестно, как соотносятся по качеству решения для одной и той жесети наилучшая схема интервальной разметки в глубину и наилучшая из всехвозможных схем интервальной разметки. В упражнении 4.7 приводится оченьплохая схема интервальной разметки в глубину для сети, имеющей оптимальную(согласно теореме 4.37) ILS, но, быть может, для той же самой сети есть болеекачественная схема интервальной разметки в глубину.В тех случаях, когда в сети друг с другом сообщаются преимущественно со­седние вершины, добрососедство является достаточным требованием для ILS.Как видно из рис.

4.15 схема интервальной разметки в глубину не обязательноявляется добрососедской: узел 4 переправляет пакет в вершину 2 через верши­ну 1 .Многоинтервальные схемы маршрутизации. Эффективность методов марш­рутизации можно повысить, позволив ребрам иметь несколько пометок; в этомслучае мы будем говорить о многоинтервальных схемах маршрутизации.Действительно, тогда мы можем считать, что множество вершин-адресатов зада­ется объединением нескольких интервалов; увеличивая число интервалов, мож­но добиться того, что даже для произвольной сети может быть получена оп­тимальная маршрутизация.

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

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