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

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

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

Алгоритмы маршрутизацииподразумевается, что граф G является связным (в случае несвязного графа тео­рема применяется к каждой его компоненте связности по отдельности).Теорема 4.2. Для каждой вершины de. V существует такое дерево Ту == (V, Еу), ЕуСЕ, в котором для любой вершины v € V единственный путьиз v в d в дереве Ту является оптимальным путем из v в d в графе G.Д о к а з а т е л ь с т в о . Пусть V = {щ , .

. . , v^}. Мы построим индуктивноряд деревьев 7) = (V), £)) (для i = 0, . . . , N), обладающих следующими свой­ствами.1. Каждое дерево Т является подграфом графа G, т. е. К; С V, Et С Е.2. Каждое дерево 7) (для i < N ) является поддеревом дерева 7)+i.3. Для каждого i > 0 выполняются включения щ € V) и d € V).4.

Для каждой вершины w <Е К простой путь из вершины w в вершину dв дереве 7) является оптимальным путем из w в d в графе G.Эти свойства гарантируют, что дерево Тм удовлетворяет тем требованиям, кото­рые предъявляются к дереву Ту.Чтобы построить последовательность деревьев, положим Ко = {d} и Тф = 0.Дерево 7)+ i строится следующим образом. Выбирается оптимальный простойпуть Р = (мо, ■■■, up) из гд+1 в d; обозначим символом / такой наименьшийиндекс, для которого выполняется включение и/ € 7) (такой индекс / существует,поскольку ир = d &Е, при этом возможно / = 0). ПоложимKi+i = Vi U {щ : / ' < / } и£)+ 1= Et U {(и/, uj+i) : j < /}.(Эта конструкция изображена на Рис. 4.1.) Нетрудно убедиться в том, что 7)является поддеревом графа 7)+i и т+\ € К +ь Граф 7)+i является деревом, по­скольку по построению 7)+i является связным графом, и число вершин в немпревосходит число ребер в точности на единицу.

(Граф 7о обладает последним изупомянутых свойств, и на каждом этапе к графу добавляется столько же вершин,сколько и ребер.)Рис. 4.1. Построение дерева Ti+i.Остается показать, что для всех вершин w <Е K+i единственный путь из wв d в дереве 7)+i является оптимальным путем из w в d в графе G. Для вер­шин w € Vi С К;+1 это верно, ввиду того что 7) является поддеревом дерева 7)+i,4.1. Маршрутизация на основе узлов-адресатов121и поэтому путь из w в d в дереве 7)+ i тот же самый, что и путь в дереве 7),который по индуктивному предположению является оптимальным.

Теперь рас­смотрим вершину w = Uj, j < /, принадлежащую множеству V;+i \ V). Обозначимсимволом Q путь из вершины м/ в вершину d в дереве Г,. Тогда в дереве 7)+\из вершины Uj в вершину d ведет путь, полученный в результате последователь­ного соединения пути (Uj, . . . , М/) и пути Q. Остается показать, что этот путьявляется оптимальным в графе G. Прежде всего заметим, что суффикс Р1 == (м/, . . . , Uk) пути Р сам по себе является оптимальным путем из вершины щв вершину d, и поэтому С{Р') = C(Q).

Это следует из того, что оптимальностьпути Q предполагает неравенство С(Р') ^ C(Q), а в случае C(Q) < С(Р') мыполучаем (учитывая свойство аддитивности стоимости путей), что, присоединивк пути (мо, . . . , ui) путь Q, мы можем построить путь, имеющий меньшую сто­имость, чем путь Р, вопреки оптимальности пути Р. Предположим теперь, чтонекоторый путь R из Uj в d имеет меньшую стоимость, нежели путь, получен­ный присоединением к пути (Uj, .

. . , М/) пути Q. Тогда, воспользовавшись ранеесделанным замечанием, мы можем прийти к заключению, что стоимость пути Rменьше, чем стоимость суффикса (Uj, . . . , «*,) пути Р, а это означает (с учетомаддитивности стоимости путей), что путь, образованный присоединением к пути(мо, • • •, Uj) пути R, имеет меньшую стоимость, чем Р, вопреки оптимальностипути Р.□Остовное дерево, корнем которого служит вершина d, называется входнымдеревом для d, а дерево, обладающее теми свойствами, которые указаны в теоре­ме 4.2 называется оптимальным входным деревом. Существование оптималь­ного входного дерева означает, что алгоритмы маршрутизации, в основу которыхположен механизм продвижения, описанный в алгоритме 4.2, не поступаютсяоптимальностью.

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

Будем гово­рить, что таблицы маршрутизации (для узла-адресата d) содержат цикл, еслисуществуют такие вершины и \, . . . , Uk, что• Ui Ф d для всех г,• table_lookupu.(d) =для всех / < k и• table_lookupUk(d) = щ.Таблицы называются ациклическими, если они не содержат цикла ни для однойвершины d.122Гл. 4. Алгоритмы маршрутизацииЛемма 4.3. М е х а н и з м п р о д в и ж е н и я д о с т а в л я е т к а ж д ы й п а к е т п о н а ­зн а ч е н и ю в т ом и т олько т ом случае, ко гд а т аблицы м а р ш р ут и за ц и ия вляю т ся ациклическим и.Д о к а з а т е л ь с т в о . Если таблицы маршрутизации содержат цикл длянекоторого узла-адресата d, то пакет, адресованный процессу d, никогда не бу­дет доставлен по назначению, если отправителем является вершина, входящаяв цикл.(* Пакет, адресованный вершине d, был получен или сформирован в вершине и *)if d = иthen доставить пакет локальными средствамиelse отправить пакет вершине ta b le _ lo o k u p u(d)Алгоритм 4.2.

Продвижение пакетов по назначению (для узлаи).Предположим, что таблицы являются ациклическими и пакет, предназначен­ный узлу-адресату d (и отправленный из узла-источника мо), продвинулся черезвершины «о, и ь М2 , __ Если одна и та же вершина встречается в этой последо­вательности дважды, скажем щ = щ, то таблицы содержат цикл, в данном случае(м;, . . . , Uj), вопреки предположению об ацикличности таблиц.

Значит, каждаявершина встречается в последовательности не более одного раза. Отсюда сле­дует, что эта последовательность является конечной и оканчивается некоторойвершиной иц (k < N ). В соответствии с описанием процедуры продвижения паке­та указанная последовательность может оканчиваться только вершиной d . Такимобразом, Uk = d , и пакет достигает вершины адресата, пройдя не более N - 1звеньев.□В некоторых алгоритмах маршрутизации может случиться так, что таблицына этапе их вычисления не обладают свойством ацикличности, но только до техпор, пока не завершится этап вычисления таблиц.

При применении такого алго­ритма пакет может продвигаться по циклу, пока вычисляются таблицы, но тем неменее доставляется по назначению не более чем за N —1 звеньев, после того каквычисление таблиц завершается при отсутствии дальнейших изменений тополо­гии. Если изменения топологии не прекращаются, т. е. структура сети подверга­ется постоянным преобразованиям, пакеты могут не достичь своего назначениядаже в том случае, если обновляемые таблицы оказываются ациклическими (см.упражнение 4.1).Разветвляемая маршрутизация с минимальной задержкой. Если требу­ется провести маршрутизацию по путям с наименьшей задержкой, и при этомзадержка в канале связи зависит от его загруженности (и поэтому допущение 1,сделанное в начале этого параграфа является недействительным), то стоимостьиспользования пути нельзя рассматривать как функцию, зависящую только отэтого пути.

Кроме того необходимо принимать в расчет трафик по каналу связи.Чтобы избежать заторов на пути (из-за которых возникает большая задержка),пакеты, имеющие один и тот же источник и одного того же адресата, продвигают-4.2. Задача построения кратчайших путей для всех пар вершинРис. 4.3.123Пример разветвляемой маршрутизациися различными путями; в этом случае трафик расщепляется в одной или несколь­ких промежуточных вершинах, как это показано на рис. 4.3.

Маршрутизация, вкоторых пакеты, направленные по одному и тому же адресу, продвигаются разны­ми путями, называются многопутевой маршрутизацией или расщепленноймаршрутизацией. Ввиду того что методы расщепленной маршрутизации, как пра­вило, очень сложны, мы не будем рассматривать их в этой главе.4.2. Задача построения кратчайших путейдля всех пар вершинВ этом параграфе мы рассмотрим алгоритм Туэга [194] совместного вычисле­ния таблиц маршрутизации для всех узлов сети. Для каждой пары вершин (и, v)алгоритм вычисляет длину кратчайшего пути из вершины и в вершину v и зано­сит в память процесса и первый канал этого пути.

Это хорошо известная задачапостроения кратчайших путей для всех пар вершин. В основу распределенно­го алгоритма Туэга решения этой задачи положен централизованный алгоритмФлойда—Уоршалла [55, §26.4]. Мы рассмотрим алгоритм Флойда—Уоршаллав §4.2.1, а затем в §4.2.2 обратимся к алгоритму Туэга. В §4.2.3 мы обсудими другие алгоритмы решения задачи построения кратчайших путей для всех парвершин.4.2.1. Алгоритм Флойда— УоршаллаПредположим, что имеется взвешенный граф G = ( V , Е ) , в котором каждомуребру uv приписан вес соцо. Ясно, что соцо = сооц, и, кроме того, мы будем считать,что в графе отсутствуют циклы отрицательного веса. Весом пути («о, .

. . , «*)называется число, равное Хл=о• Расстоянием между вершинами и и vназывается наименьший вес d(u, v) пути, соединяющего вершины и и v (еслитаких путей нет, то расстояние считается бесконечным, d(u, и) = оо). Задача по­строения кратчайших путей для всех пар вершин состоит в том, чтобы вычислитьрасстояние d(u, v) для каждой пары вершин и и и. (В §4.2.2 мы расширим воз­можности алгоритма, и он будет заносить в память процесса первое ребро путинаименьшего веса.)124Гл. 4. Алгоритмы маршрутизацииДля вычисления всех расстояний в алгоритме Флойда—Уоршалла использу­ется понятие 5-путей; это пути, в которых все промежуточные вершины при­надлежат подмножеству S множества вершин V .Определение 4.4.

Пусть S — некоторое подмножество множества вершин Vграфа G. Путь (щ , . . . . и*) называется S -путем, если щ € 5 для каждого г, 0 << / < k. S -расстоянием между вершинами и ни, которое обозначается ds (u, v),называется наименьший вес S-пути между и и и (если таких путей нет, то рас­стояние считается бесконечным, ds (u, v) = оо).Работа алгоритма начинается с построения всех 0-путей, а затем множествоS-путей наращивается для все более обширных подмножеств S, до тех пор по­ка не будут рассмотрены все К-пути. Уместно принять во внимание следующеезамечание.Предложение 4.5.

Для любой вершины и и всякого подмножества Sвыполняется равенство ds (u, и) = 0. Кроме того, если и Д v, то S-nymuподчиняются следующим правилам:1) 0-пут ь из вершины и в вершину v существует в том и только томслучае, когда uv € £;2) если uv е Е , то д®(и, и ) = ы ии; в противном случае d®(u, v) = оо;3) если S' = S U {да}, то простой S '-путь, ведущий из и в и, представ­ляет собой либо S -путь, ведущий из и в и, либо последовательноесоединение двух S -путей, один из которых ведет из и в да, а дру­гой — из дави;4) е с л и S ' = S U {да}, т о d s ' {и, v ) = min ( d s (u , v ), d s (u , да) + d s (w , и ) );5) вершины и и v соединены путем в том и только том случае, когдамежду вершинами и и v существует V-путь;6) d(u, v) = dv (u, v),Д о к а з а т е л ь с т в о .

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

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