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

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

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

Поэтому алгоритмы, в основу которых положеноуравнение (4.1), можно проще адаптировать для учета топологических измене­ний. Примером тому может служить алгоритм, который мы подробно рассмотримв §4.6.3.Алгоритм Мерлина—Сигалла. Алгоритм, предложенный Мерлином и Сигаллом в работе [147], вычисляет таблицы маршрутизации по отдельности длякаждой вершины-адресата; вычисления таблиц для разных вершин-адресатов неоказывают совершенно никакого влияния друг на друга. Для каждой вершиныадресата v алгоритм строит дерево Tv с корнем в вершине v и проводит ите­ративное преобразование этого дерева, с тем чтобы в конце концов получитьоптимальное входное дерево для вершины-адресата v.134Гл. 4.

Алгоритмы маршрутизацииВ каждом узле и хранится оценка расстояния Du[v] до вершины v, а такжеимя того соседа, которому нужно передать пакет, адресованный узлу V, и этот со­сед является родительской вершиной для узла и в дереве Tv. При каждой итера­ции всякий узел и отправляет известную ему оценку расстояния A [v] всем своимсоседям, кроме вершины Nbu[v] (для этого используется сообщение (mydist, и, А, [и])).Как только узел и получает от своего соседа да сообщение (mydist, и, d) и обна­руживает, что d + ыиш < А ,[ у], в узле и значение переменной Nbu[v] полагаетсяравным да, а значение переменной Du[v] полагается равным d + ыиш). Управляю­щим параметром этого преобразования служит вершина v, и для его проведениянужно провести обмен двумя сообщениями, состоящими из W битов, по каждомуканалу связи.В работе [ 147] установлено, что после проведения i итераций все кратчайшиепути, состоящие не более чем из i звеньев, будут правильно вычислены, и поэто­му для вычисления вех кратчайших путей нужно совершить не более N итераций.Кратчайшие пути ко всем вершинам-адресатам вычисляются за счет независи­мого применения предложенного алгоритма ко всем вершинам-адресатам.Теорема 4.11.

Алгоритм Мерлина— Сигалла вычисляет таблицы марш­рутизации по кратчайшим путям, совершая при этом обмен 0(N2) со­общениями и передавая 0(N2 ■W) битов информации по каждому каналусвязи, имея, таким образом, коммуникационную сложность 0(N 2-1£|) и би­товую сложность 0(N 2 • \E\W).Этот алгоритм можно приспособить к изменениям топологии сети и весовыххарактеристик каналов. Важная особенность этого алгоритма состоит в том, чтопо ходу проведения итераций таблицы маршрутизации остаются ациклическими.Алгоритм Чанди—Мисры. Алгоритм, предложенный Чанди и Мисрой в ра­боте [44], вычисляет все кратчайшие пути к заданной вершине-адресату на основепринципа диффузных вычислений.

Суть его такова: распределенное вычисле­ние начинается в одной-единственной вершине, и другие узлы сети поочередноприсоединяются к вычислению только после получения сообщения.Чтобы вычислить расстояние от каждой вершины до заданного узла vq (а так­же предпочтительный исходящий канал связи), каждый узел и устанавливает на­чальное значение Du[vо] = оо и ожидает получения сообщений.

Узел vo отправ­ляет сообщение (mydist, v q , 0) всем своим соседям. Как только вершина и полу­чает сообщение (mydist, vo, d) от соседа да и убеждается в том, что выполняетсянеравенство d + ыиш < A N L значением переменной Du[vо] становится суммаd+Muw, и всем соседям вершины и отправляется сообщение (mydist, vo, Du[vо])(см. алгоритм 4.7).Легко показать, что значениеA N ] всегда является верхней оценкой величи­ны d(u, vo), т. е. неравенство d(u, vo) ^ АЛ по] следует из инварианта алгоритма;см. упражнение 4.3. Чтобы убедиться в том, что алгоритм правильно вычисля­ет расстояния, необходимо показать, что рано или поздно будет достигнута та­кая конфигурация, для которой в каждом узле будет выполняться неравенствоA N ] ^ d(u, vo).

Мы приведем доказательство этого утверждения, в котором4.2. Задача построения кратчайших путей для всех пар вершинv a r D u[vq\: вес135in it оо ;Nbu[vo\ '■вершинаin itudef ;Только для вершины v0:b e g i n £>0o[i>o] : = 0 ;f о ra il w € NeighVo d o send ( m y d is t , vq, 0) towendОбработка сообщения ( m y d is t , Vo, d ), полученного вершиной и от соседа w:{( m y d is t ,vo, d) 6 MWU }vo, d) from w ;b e g i n receive ( m y d is t ,ifd + Ышв < A , [no] t h e nDu[vo\ : = d + (o™ ; Nbu[vo] : = w ;f o r a ll x € Neighu d o send ( m y d is t , vo, Du[vo\) to xb e g inendendА л г о р и т м 4 .7 .Алгоритм Чанди— Мисры (для узла и).подразумевается соблюдение допущения слабой справедливости, гласящего, чтов любом вычислении каждое отправленное сообщение рано или поздно будетполучено.

Существует и такое доказательство, которое никак не опирается науказанное допущение, но оно гораздо сложнее.Теорема 4.12. В любом вычислении алгоритма 4.7 достигается такаяконфигурация , что в каждом узле и выполняется неравенство Du[vо] ^ d(u,Д о к а з а т е л ь с т в о . Рассмотрим некоторое оптимальное входное дере­во Т для вершины vq и занумеруем 2) все вершины, отличные от vo, натуральнымичислами от 1 до N —1 так, чтобы всякий раз, когда щ является родительской вер­шиной для Vj, выполнялось неравенство / < /. Рассмотрим произвольное вычис­ление С и покажем, воспользовавшись индукцией по /, что для каждого номера/, / ^ N — 1, достигается такая конфигурация, в которой для всех номеров /,/ ^ /, выполняется неравенство Dv\ v о] ^ d(vi, vq ).

Заметим, что значение пере­менной Dv\ v о] никогда не увеличивается по ходу работы алгоритма, и поэтому,как только соотношение Dv\ v о] ^ d(vi, vо) оказывается верным в какой-либоконфигурации, оно будет также оставаться верным и во всех последующих кон­фигурациях.2)3десь в доказательстве допущена принципиальная ошибка. Для заданной вершины Vo в сетиможет существовать несколько различных оптимальных входных деревьев, и разные выполненияалгоритма могут строить разные деревья. Правильнее было бы рассмотреть произвольное выполнениеС рассматриваемого алгоритма и показать, что С обязательно завершается. П осле этого вершинысети нумеруются так, чтобы всякий раз, когда последнее изменение значения переменной DVi[vо]в вычислении С предшествует последнему изменению переменной DVj[vо] в том ж е вычислении С,выполнялось неравенство I < j.

— Прим, перев.v q ).136Гл. 4. Алгоритмы маршрутизацииБазис (/ = 0). После выполнения блока инициализации vo имеем dipo, Уо) == 0, и DVo[vо] = 0, поэтому неравенство Д , 0 [ио] < d(vо, по) соблюдается и послевыполнения всего процесса.Индуктивный переход / —►/ + 1. Предположим, что была достигнута та­кая конфигурация, в которой для всех узлов с номерами / ^ j выполняется нера­венство DV}[i/0] < d(pi, vo). Рассмотрим вершину vl +\ . Из нее в вершину vo суще­ствует кратчайший путь vj +\ , щ, .

. . , vo длины d(vj+\, vo), в котором уг являетсяродительской вершиной для v-l+\ в дереве Т, и поэтому / < /. Следовательно,по индуктивному предположению может быть достигнута такая конфигурация,в которой Dv.\v о] ^ d(vi, vq). Всякий раз, когда значение Dv\ v о] уменьшается,процесс Vi отправляет сообщение (mydist, vo, Dv\ v о]) своим соседям, и, следо­вательно, сообщение (mydist, vo, d), в котором d ^ d(vi, vo), хотя бы один разотправляется процессу Vj+\.По предположению это сообщение будет получено процессом Vj+\ в неко­торой конфигурации С. Согласно описанию алгоритма после получения этогосообщения будет выполняться неравенство DVj+l [&о] ^ d + « И;+1Иг; как следует извыбора номера i, это влечет за собой неравенство d + (AVj+lVi ^ d(vj+\, vo).□Полное описание алгоритма также включает в себя процедуру, посредствомкоторой узлы могут обнаружить, что вычисление завершилось (обратите внима­ние на замечание в начале §4.3.3, относящееся к алгоритму Netchange).

Этапроцедура обнаружения завершения вычисления является разновидностью алго­ритма Дейкстры—Шолтена, который обсуждается в §8.2.1.Рассмотренный здесь алгоритм отличается от алгоритма Мерлина—Сигалла двумя особенностями. Во-первых, не ожидается того, что узел, отправившийв вершину и сообщение типа mydist, становится родительской вершиной для и.Эта характерная черта алгоритма Мерлина—Сигалла позволяет таблицам марш­рутизации оставаться ациклическими по ходу вычисления и даже при изменениитопологии сети. Во-вторых, обмен сообщениями типа mydist на этапах итера­ции не координируется, а выполняется абсолютно произвольно, и это оказыва­ет нежелательное влияние на сложность алгоритма. Алгоритму может потребо­ваться провести экспоненциально много обменов сообщениями, чтобы вычислитьпути к одной-единственной вершине-адресату v q .

Е сли стоимость всех каналоводинакова (т. е. рассматривается задача оптимальной по числу звеньев марш­рутизации), все кратчайшие пути к вершине vo вычисляются с использованием0(N ■|£|) сообщений (каждое из которых состоит из 0(W) битов), и это приводитнас к следующему результату.Теорема 4.13. Алгоритм Чанди—Мисры вычисляет таблицы маршру­тизации с наименьшим числом звеньев, совершая при этом обмен 0(N 2)сообщениями и передавая 0(N 2 ■W) битов информации по каждому кана­лу связи, и имея, таким образом, коммуникационную сложность 0(N 2 • |£|)и битовую сложность 0{N2 ■|£ | 1Е).Преимуществом алгоритма Чанди—Мисры по сравнению с алгоритмом Мер­лина—Сигалла является его простота, меньшая сложность по объему памятии меньшая сложность по времени исполнения.4.3. Алгоритм Netchange1374.3. Алгоритм NetchangeАлгоритм Netchange был предложен Таджибнаписом в работе [180]; он вы­числяет таблицы маршрутизации, которые являются оптимальными по числу зве­ньев.

Этот алгоритм имеет много общего с алгоритмом Чанди—Мисры, но приэтом в нем поддерживается дополнитльная информация, которая позволяет в слу­чае возникновения неисправности в канале и восстановления работоспособностиканала уточнять таблицы путем их частичного перевычисления.

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

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