Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 38
Текст из файла (страница 38)
При изложенииматериала в этом параграфе мы будем придерживаться работы Лампорта [125].При построении алгоритма мы будем опираться на следующие допущения.N1. Каждый узел осведомлен о размере всей сети (N).N2. В каналах поддерживается очередность сообщений.N3. Узлы получают уведомления о возникновении неисправностей и восстановлении работоспособности примыкающих к ним каналов.N4. Стоимость пути равна количеству каналов в этом пути.Алгоритм может справиться с возникновением неисправностей и восстановлением работоспособности каналов, а также с добавлением новых каналов связи,но при этом предполагается, что всякий узел немедленно узнает о поврежденииили восстановлении примыкающих к нему каналов связи. Повреждение и восстановление узлов сети в расчет не принимается; считается, что повреждениеузла сети воспринимается его соседями как повреждение каналов, связывающихих с этим узлом.
В каждом узле и алгоритм вычисляет и поддерживает таблицуNbu[v], в которой для каждой вершины-адресата v указывается тот сосед узлаи, которому должен быть отправлен пакет, адресованный вершине и. Мы не можем требовать, чтобы вычисление этих таблиц всегда завершалось за конечноечисло шагов, поскольку постоянные обрывы и восстановления каналов связи могут потребовать столь же частых перевычислений. К алгоритму предъявляютсяследующие требования.R1. Если топология сети после конечного числа изменений остается далеенеизменной, то алгоритм завершает работу после конечного числа шагов.R2. Когда алгоритм завершает работу, таблицы Nbu[v\ удовлетворяют следующим условиям:а) если v = и, то Nbu[v] — local;б) если существует путь из вершины и в вершину v ф и, то Nbu[v] = w, гдеw — это первая вершина-сосед узла и, который следует за и в кратчайшемпути яз и в и;в) если пути из вершины и в вершину v нет, то Nba[v] = udef.4.3.1.
Описание алгоритмаАлгоритм Таджипнаписа Netchange состоит из двух частей: алгоритм 4.8 и алгоритм 4.9. Сначала мы объясним содержательный смысл всех операций алгоритма, а затем формально докажем его корректность. Чтобы добиться ясностиизложения, мы упростили моделирование топологических изменений по сравнению с тем, как это описано в работе [125]: предполагается, что уведомлениеГл.
4. Алгоритмы маршрутизации138о каждом таком изменении обрабатывается одновременно в обоих узлах, которые оказываются затронутыми этим изменением. В §4.3.3 мы укажем, как этиуведомления можно обрабатывать асинхронно.var N e ig h uDuNbun d is u: множество вершин;(* Соседи узла и *)(* Du \v\ — это оценка величины d ( u , v) *)(* N b u [v\ — это предпочтительные соседи вершины ипри отправлении сообщений вершине-адресату и *): массив размера 0.. N ; (* n d i s u [w, ц] — это оценка величины d ( w , v) *): массив размера 0.. N;: массив вершин;Инициализация:b egin forall w e N e ig h u , v € V do n d i s u [w, v] := N ;forall v € V dob egin D u[v\ := N ; N b u [v] := u d e f end;D u [u\ ■= 0 ; N bu[u\ := l o c a l ;forall w € N e ig h u do send (m yd ist, u, 0) to wendПроцедура П е р е в ы ч и с л е н и е (и):b egin if v = иth en b egin D u [v\ := 0 ; N b u [v] := l o c a l en de ls e b egin (* Оценить расстояние до вершины v *)d := 1 + min{ndisu[w,v] : w eNeighu} ;if d < N th enb egin D u [v] := d ;N b u [v] := w с 1 + n d i s u [w, v] = dendelse b egin D u [v] := N ; N b u [v] := u d e f endend;if переменная D u [v] изменила значение th enforall x 6 N e ig h u do send (m ydist, v, Du[v\) to xendАлгоритм 4.8.Алгоритм Netchange (Часть 1, для узла и).Выбор того соседа, которому отправляются пакеты, адресованные узлу v, основывается на оценках расстояния от каждой вершины до узла и.
Предпочтение всегда отдается тому соседу, у которого эта оценка является наименьшей.В памяти узла и хранится оценка Da[v] расстояния d(u, v) и оценки ndisu[w, v ]расстояний d(w, v) для каждого соседа w вершины и. Оценка Du[v] вычисляется на основании оценок ndisu[w, v], а оценки ndisu[w, v] получаются путемвзаимосвязи с соседями.Вычисление оценок Da[v] проводится следующим образом.
Если и = и, тоd(u, v) = 0, и в этом случае значение Du[v] полагается равным 0. Если и Ф и, тократчайший путь из вершины и в вершину v (если таковой существует) состоитиз канала, соединяющего узел и с одним из его соседей, и кратчайшего пути,4.3. Алгоритм Netchange139Обработка сообщения (mydist, v, d), полученного от соседа да:{ Сообщение (mydist, v, d) в начале очереди Qwu }begin receive (mydist, v, d) from да ;ndisu[w, v] := d ; Перевычисление (a)endВ случае выхода из строя канала uw:begin receive (fail, да) ; Neighu '■= Neighu \ {да} ;forall v 6 V do Перевычисление (v )endВ случае восстановления канала uw:begin receive (repair, да) ; Neighu '■ = Neighu U {да} ;forall v € V dobegin ndisu[w, v] := N ;send (mydist, v, Du[v\) to wendendАлгоритм 4.9.Алгоритм N etchange (Часть 2, для узла и).который соединяет этого соседа с вершиной v. Следовательно,d(u, v) =1+minw€~Neighud(w, и).Руководствуясь этим уравнением, мы получаем оценку величины d(u, v) в узлеи Ф v за счет применения указанной формулы к оценкам величин d(w, v), содержащимся в таблицах ndisu[w, v], Коль скоро в сети имеется N узлов, длинапути с наименьшим числом звеньев не превосходит N —1.
Если же вычисленнаяоценка длины не меньше чем N, то можно предполагать, что такого пути вообщене существует; именно для этой цели в таблице используется значение N.В этом алгоритме требуется, чтобы в узле хранились оценки расстояния отсоседних вершин до вершины v. Эти оценки поступают от соседних вершин, таккак они передаются в сообщениях типа mydist следующим образом. Если в узлеи была вычислена оценка d расстояния от него до вершины v (Du[v] = d), то этаинформация передается всем соседним вершинам в сообщении (mydist, v, d).После получения сообщения (mydist, v, d) от соседа w, в узле и переменнойndisu[w, v] присваивается значение d.
В результате изменения значения переменной ndisu[w, v] оценка d(u, v) в узле и может измениться, и поэтому этаоценка перевычисляется всякий раз, когда происходят изменения в таблице ndisuЕсли оценка расстояния и в самом деле изменяется, например становится равной d', то об этом, конечно же, оповещаются все соседи при помощи сообщений(mydist, v, d').В ответ на выход из строя или восстановление работоспособности каналасвязи алгоритм вносит изменения в локальные таблицы и отправляет сообщение типа mydist, если при этом изменяются оценки расстояний. Предполагается,140Гл.
4. Алгоритмы маршрутизациичто уведомления о поломках и починках каналов связи (допущение N3) поступают в виде сообщений типа fail и repairl. Канал связи между узлами и.\ и и2моделируется парой очередей QUlU2 для сообщений от и\ к и.2 и Q„2Ul для сообщений от U.2 к мь Когда канал выходит из строя, эти очереди удаляются изконфигурации (что немедленно влечет за собой потерю всех сообщений в обеихочередях), а узлы по обе стороны канала связи получают сообщение типа fail.Если канал связи между узлами и\ и « 2 обрывается, то процесс и\ получаетсообщение (fail, иг), а процесс « 2 — сообщение (fail, и\). Когда связь в каналевосстанавливается (или в сети появляется новый канал связи), в конфигурациивозникают две новые пустые очереди, а узлы по обе стороны этого канала связиполучают сообщение типа repair.
Если между узлами и\ и « 2 образуется каналсвязи, то процесс и\ получает сообщение (repair, « 2 ), а процесс « 2 — сообщение(repair, и\).Алгоритм предусматривает следующую реакцию на сообщения о разрыве иливосстановлении канала связи. Когда выходит из строя канал связи между узламии и да, вершина да удаляется из списка Neighu, и наоборот. Проводится перевычисление оценок расстояний до каждой вершины, и в случае изменения оценки,об этом узнают все оставшиеся соседи.
Это происходит, если неисправный канал ранее был одним из звеньев наилучшего маршрута и не осталось ни одногососеда да', для которого верно равенство ndisu[w\ v ] = ndisu[w, v]. Когда каналсвязи восстанавливается (или добавляется новый канал), вершина да добавляетсяк списку вершин Neigha, но в памяти узла и еще нет никаких оценок расстояния d(w, v) (и наоборот). Новому соседу да немедленно сообщаются оценки Du[v]расстояний от узла и до всех возможных вершин-адресатов v (путем отправлениясообщений (mydist, v, Du[v]).
До тех пор пока узел и не получит такого сообщения от узла да, величина N будет использоваться в нем для оценки расстоянияd(w, v), т. е. значение переменной ndisa[w, v ] полагается равным N.Р(и, да, v) =ир(и, да) <==>■ да € NeighuЛ ир(и, да) Л Qwu содержит сообщение (m yd ist, v, d)Л=>■ последнее сообщение в очередиудовлетворяет равенству d = Dw[v\ир(и, да) Л Qwu не содержит сообщений (m yd ist, v, d)==>■ ndisu[w, v\ = Dw[v\(1)(2)(3)L(u, ti)ЛЛи = v ==>■ (Du[v] = 0 A Nbu[v] = local )(и Ф v Л Эда e Neighu: ndisu[w, u] < N —1)==>■ {Du[v\ = 1 + min ndisu[w, v\ = \ A-ndisu[Nbu[v\, v\)weNeighu( u / o A V® e Neighu: ndisu[w, u] ^ N —1){Du[v] = N A Nbu[v] = udef)Рис. 4.10. Инварианты P(u, да, и) и L(u, v)(4)(5)( 6)4.3. Алгоритм Netchange141Инварианты алгоритма Netchange. Мы установим, что утверждения, приведенные на рис.
4.10, являются инвариантами. Формула Р(и, да, v) выражаетутверждение о том, что если процесс и завершил обработку сообщений типа mydist, полученных от процесса да, то оценка расстояния d(w, v) в узле и совпадаетс оценкой расстояния d(w, v) в узле да. Мы будем считать, что предикат up {и, да)принимает значение true тогда и только тогда, когда между узлами к и ю есть(двунаправленный) исправный канал связи. Формула L(u, v) гласит, что оценки расстояний d(u, v) и содержимое списка Nba[v] в узле и всегда согласованос теми данными, которые хранятся в локальной памяти узла и.Вычисление алгоритма завершается, когда в каналах связи не остается ни одного сообщения, находящегося на этапе пересылки. Конфигурации такого вида неявляются заключительными конфигурациями для всей системы в целом, потомучто вычисление системы может быть продолжено, после того как какой-нибудьканал выйдет из строя или восстановит свою работоспособность (что потребуетреакции со стороны алгоритма).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
