Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 38
Текст из файла (страница 38)
Этапроцедура обнаружения завершения вычисления является разновидностью алгоритма Дейкстры—Шолтена, который обсуждается в § 8.2.1.Рассмотренный здесь алгоритм отличается от алгоритма Мерлина —Сигалла двумя особенностями. Во-первых, не ожидается того, что узел, отправившийв вершину u сообщение типа mydist, становится родительской вершиной для u.Эта характерная черта алгоритма Мерлина—Сигалла позволяет таблицам маршрутизации оставаться ациклическими по ходу вычисления и даже при изменениитопологии сети. Во-вторых, обмен сообщениями типа mydist на этапах итерации не координируется, а выполняется абсолютно произвольно, и это оказывает нежелательное влияние на сложность алгоритма.
Алгоритму может потребоваться провести экспоненциально много обменов сообщениями, чтобы вычислитьпути к одной-единственной вершине-адресату v0 . Если стоимость всех каналоводинакова (т. е. рассматривается задача оптимальной по числу звеньев маршрутизации), все кратчайшие пути к вершине v 0 вычисляются с использованиемO(N · |E|) сообщений (каждое из которых состоит из O(W) битов), и это приводитнас к следующему результату.Теорема 4.13. Алгоритм Чанди—Мисры вычисляет таблицы маршрутизации с наименьшим числом звеньев, совершая при этом обмен O(N 2)сообщениями и передавая O(N2 · W) битов информации по каждому каналу связи, и имея, таким образом, коммуникационную сложность O(N 2 · |E|)и битовую сложность O(N2 · |E|W).Преимуществом алгоритма Чанди—Мисры по сравнению с алгоритмом Мерлина—Сигалла является его простота, меньшая сложность по объему памятии меньшая сложность по времени исполнения.4.3.
Алгоритм Netchange1374.3. Алгоритм NetchangeАлгоритм Netchange был предложен Таджибнаписом в работе [180] ; он вычисляет таблицы маршрутизации, которые являются оптимальными по числу звеньев. Этот алгоритм имеет много общего с алгоритмом Чанди –Мисры, но приэтом в нем поддерживается дополнитльная информация, которая позволяет в случае возникновения неисправности в канале и восстановления работоспособностиканала уточнять таблицы путем их частичного перевычисления.
При изложенииматериала в этом параграфе мы будем придерживаться работы Лампорта [125] .При построении алгоритма мы будем опираться на следующие допущения.N1. Каждый узел осведомлен о размере всей сети (N).N2. В каналах поддерживается очередность сообщений.N3. Узлы получают уведомления о возникновении неисправностей и восстановлении работоспособности примыкающих к ним каналов.N4.
Стоимость пути равна количеству каналов в этом пути.Алгоритм может справиться с возникновением неисправностей и восстановлением работоспособности каналов, а также с добавлением новых каналов связи,но при этом предполагается, что всякий узел немедленно узнает о поврежденииили восстановлении примыкающих к нему каналов связи.
Повреждение и восстановление узлов сети в расчет не принимается; считается, что повреждениеузла сети воспринимается его соседями как повреждение каналов, связывающихих с этим узлом. В каждом узле u алгоритм вычисляет и поддерживает таблицуNbu [v] , в которой для каждой вершины-адресата v указывается тот сосед узлаu, которому должен быть отправлен пакет, адресованный вершине v. Мы не можем требовать, чтобы вычисление этих таблиц всегда завершалось за конечноечисло шагов, поскольку постоянные обрывы и восстановления каналов связи могут потребовать столь же частых перевычислений.
К алгоритму предъявляютсяследующие требования.R1. Если топология сети после конечного числа изменений остается далеенеизменной, то алгоритм завершает работу после конечного числа шагов.R2. Когда алгоритм завершает работу, таблицы Nb u [v] удовлетворяют следующим условиям:а) если v = u, то Nbu [v] = local;б) если существует путь из вершины u в вершину v 6= u, то Nb u [v] = w, гдеw — это первая вершина-сосед узла u, который следует за u в кратчайшемпути из u в v;в) если пути из вершины u в вершину v нет, то Nbu [v] = udef.4.3.1. Описание алгоритмаАлгоритм Таджипнаписа Netchange состоит из двух частей: алгоритм 4.8 и алгоритм 4.9.
Сначала мы объясним содержательный смысл всех операций алгоритма, а затем формально докажем его корректность. Чтобы добиться ясностиизложения, мы упростили моделирование топологических изменений по сравнению с тем, как это описано в работе [125] : предполагается, что уведомление138Гл. 4. Алгоритмы маршрутизациио каждом таком изменении обрабатывается одновременно в обоих узлах, которые оказываются затронутыми этим изменением. В § 4.3.3 мы укажем, как этиуведомления можно обрабатывать асинхронно.var NeighuDuNbundisu: множество вершин;: массив размера 0.. N;: массив вершин;(* Соседи узла u *)(* Du [v] — это оценка величины d(u, v) *)(* Nbu [v] — это предпочтительные соседи вершины uпри отправлении сообщений вершине-адресату v *): массив размера 0..
N ; (* ndisu [w, v] — это оценка величины d(w, v) *)Инициализация:begin forall w ∈ Neighu , v ∈ V do ndisu [w, v] := N ;forall v ∈ V dobegin Du [v] := N ; Nbu [v] := udef end;Du [u] := 0 ; Nbu [u] := local ;forall w ∈ Neighu do send hmydist, u, 0i to wendПроцедура Перевычисление (v):begin if v = uthen begin Du [v] := 0 ; Nbu [v] := local endelse begin (* Оценить расстояние до вершины v *)d := 1 + min{ndisu [w, v] : w ∈ Neighu } ;if d < N thenbegin Du [v] := d ;Nbu [v] := w с 1 + ndisu [w, v] = dendelse begin Du [v] := N ; Nbu [v] := udef endend;if переменная Du [v] изменила значение thenforall x ∈ Neighu do send hmydist, v, Du [v] i to xendАлгоритм 4.8. Алгоритм Netchange (Часть 1, для узла u).Выбор того соседа, которому отправляются пакеты, адресованные узлу v, основывается на оценках расстояния от каждой вершины до узла v. Предпочтение всегда отдается тому соседу, у которого эта оценка является наименьшей.В памяти узла u хранится оценка Du [v] расстояния d(u, v) и оценки ndisu [w, v]расстояний d(w, v) для каждого соседа w вершины u.
Оценка D u [v] вычисляется на основании оценок ndisu [w, v] , а оценки ndisu [w, v] получаются путемвзаимосвязи с соседями.Вычисление оценок Du [v] проводится следующим образом. Если u = v, тоd(u, v) = 0, и в этом случае значение Du [v] полагается равным 0. Если u 6= v, тократчайший путь из вершины u в вершину v (если таковой существует) состоитиз канала, соединяющего узел u с одним из его соседей, и кратчайшего пути,4.3.
Алгоритм Netchange139Обработка сообщения hmydist, v, di, полученного от соседа w:{ Сообщение hmydist, v, di в начале очереди Qwv }begin receive hmydist, v, di from w ;ndisu [w, v] := d ; Перевычисление (v)endВ случае выхода из строя канала uw:begin receive hfail, wi ; Neighu := Neighu \ {w} ;forall v ∈ V do Перевычисление (v)endВ случае восстановления канала uw:begin receive hrepair, wi ; Neighu := Neighu ∪ {w} ;forall v ∈ V dobegin ndisu [w, v] := N ;send hmydist, v, Du [v] i to wendendАлгоритм 4.9. Алгоритм Netchange (Часть 2, для узла u).который соединяет этого соседа с вершиной v.
Следовательно,d(u, v) = 1 +minw∈Neighud(w, v).Руководствуясь этим уравнением, мы получаем оценку величины d(u, v) в узлеu 6= v за счет применения указанной формулы к оценкам величин d(w, v), содержащимся в таблицах ndisu [w, v] . Коль скоро в сети имеется N узлов, длинапути с наименьшим числом звеньев не превосходит N − 1. Если же вычисленнаяоценка длины не меньше чем N, то можно предполагать, что такого пути вообщене существует; именно для этой цели в таблице используется значение N.В этом алгоритме требуется, чтобы в узле хранились оценки расстояния отсоседних вершин до вершины v. Эти оценки поступают от соседних вершин, таккак они передаются в сообщениях типа mydist следующим образом. Если в узлеu была вычислена оценка d расстояния от него до вершины v (D u [v] = d), то этаинформация передается всем соседним вершинам в сообщении hmydist, v, di.После получения сообщения hmydist, v, di от соседа w, в узле u переменнойndisu [w, v] присваивается значение d.
В результате изменения значения переменной ndisu [w, v] оценка d(u, v) в узле u может измениться, и поэтому этаоценка перевычисляется всякий раз, когда происходят изменения в таблице ndis u .Если оценка расстояния и в самом деле изменяется, например становится равной d0 , то об этом, конечно же, оповещаются все соседи при помощи сообщенийhmydist, v, d0 i.В ответ на выход из строя или восстановление работоспособности каналасвязи алгоритм вносит изменения в локальные таблицы и отправляет сообщение типа mydist, если при этом изменяются оценки расстояний. Предполагается,140Гл.
4. Алгоритмы маршрутизации4.3. Алгоритм Netchangeчто уведомления о поломках и починках каналов связи (допущение N3) поступают в виде сообщений типа fail и repairl. Канал связи между узлами u 1 и u2моделируется парой очередей Qu1 u2 для сообщений от u1 к u2 и Qu2 u1 для сообщений от u2 к u1 . Когда канал выходит из строя, эти очереди удаляются изконфигурации (что немедленно влечет за собой потерю всех сообщений в обеихочередях), а узлы по обе стороны канала связи получают сообщение типа fail.Если канал связи между узлами u1 и u2 обрывается, то процесс u1 получаетсообщение hfail, u2 i, а процесс u2 — сообщение hfail, u1 i.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
