Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 40
Текст из файла (страница 40)
Корректность алгоритма NetchangeТеперь мы докажем два требования корректности для рассматриваемого алгоритма.Теорема 4.16. Как только достигается стабильная конфигурация, таблицы Nbu [v] удовлетворяют следующим условиям1) если u = v, то Nbu [v] = local;2) если существует путь из вершины u в вершину v 6= u, то Nbu [v] == w, где w — первый сосед вершины u, который встречается накратчайшем пути из u в v;3) если пути из вершины u в вершину v не существует, то Nbu [v] == udef.Д о к а з а т е л ь с т в о. Когда алгоритм завершает свое выполнение, нарядус предикатом stable выполняется и формула P(u, w, v) для всех троек вершин u,v и w, и отсюда следует, что для всех троек u, v и w справедливо соотношениеup(u, w) =⇒ ndisu [w, v] = Dw [v] .(4.2)144Гл.
4. Алгоритмы маршрутизации4.3. Алгоритм NetchangeПринимая во внимание утверждение L(u, v) для всех пар вершин u и v, мы получаем следующее соотношение:если u = v,0,Dw [v] , если u 6= v ∧ ∃w ∈ Neighu : Dw [v] < N − 1, (4.3)Du [v] = 1 + w∈minNeighuN,если u 6= v ∧ ∀w ∈ Neigh : D [v] > N − 1.uwкоторого достаточно, чтобы доказать, что Du [v] = d(u, v) всякий раз, когда вершины u и v находятся в одной и той же компоненте связности сети, и D u [v] = N,если u и v находятся в разных компонентах связности.Вначале мы покажем, воспользовавшись индукцией по d(u, v), что всякийраз, когда вершины u и v находятся в одной и той же компоненте связности сети,верно неравенство Du [v] 6 d(u, v).Случай d (u, v) = 0.
В этом случае u = v, и поэтому Du [v] = 0.Случай d (u, v) = k + 1. В этом случае существует такая вершина w∈Neigh u ,для которой d(w, v) = k. По индуктивному предположению D w [v] 6 k, и отсюдавследствие соотношения (4.3) мы получаем Du [v] 6 k + 1.Теперь мы продемонстрируем, воспользовавшись индукцией по D u [v] , чтовсякий раз, когда Du [v] < N, из вершины u в вершину v существует путь, и приэтом d(u, v) 6 Du [v] .Случай Du [v] = 0. Из формулы (4.3) следует, что Du [v] = 0 только тогда,когда u = v; это означает, что между вершинами u и v есть пустой путь и d(u, v) == 0.Случай Du [v] = k + 1 < N.
Из формулы (4.3) следует, что существует такая вершина w ∈ Neighu , для которой Dw [v] = k. По индуктивному предположению между вершинами w и v существует путь и d(w, v) 6 k; отсюда следует, чтомежду вершинами u и v также есть путь и d(u, v) 6 k + 1.Таким образом, если u и v находятся в одной и той же компоненте связности, то Du [v] = d(u, v), а в противном случае Du [v] = N. Отсюда, принимаяво внимание формулу (4.2) и предложение ∀u, v : L(u, v), получаем заявленныйв утверждении теоремы результат о таблицах Nb u [v] .Чтобы убедиться в том, что стабильная ситуация рано или поздно наступит,после того как завершатся изменения топологии, мы введем нормирующую функцию по отношению к предикату stable.
Для конфигурации нашего алгоритмабудем полагатьti = (число сообщений типа hmydist, . . . , ii) ++ (число упорядоченных пар u, v, для которых D u [v] = i),и значением функции f будем считать (N + 1)-местный наборf( ) = (t0 , t1 , . . . , tN).На множестве таких наборов введем лексикографический порядок 6 l . Здесь нужно вспомнить о том, что (NN+1 , 6l) является вполне упорядоченным множеством(упражнение 2.5).145Лемма 4.17. Обработка сообщений типа mydist приводит к уменьшению значения f.Д о к а з а т е л ь с т в о. Предположим, что в узел u, у которого D u [v] == d1 , поступило сообщение hmydist, v, d2 i, и после выполнения перевычисленияновое значение переменной Du [v] становится равным d. Из описания алгоритмавытекает, что d 6 d2 + 1.Случай d < d1 .
Тогда d = d2 + 1, и отсюда следует, что значение td2 (равнокак и td1 ) уменьшается на единицу, и только значения t d , у которых d > d2 ,увеличиваются. Отсюда следует, что значение функции f уменьшается.Случай d = d1 . Узел u не отправляет никаких новых сообщений типа mydist, и на функции f это сказывается только в том, что значение t d2 уменьшаетсяна единицу. Поэтому значение f уменьшается.Случай d > d1 . Тогда значение td1 (равно как и td2 ) уменьшается на единицу,и только значения td , у которых d > d1 , увеличиваются. Отсюда следует, чтозначение функции f уменьшается.Теорема 4.18. Если начиная с какого-то момента топология сети остается неизменной, то спустя конечное число шагов алгоритм достигаетстабильной конфигурации.Д о к а з а т е л ь с т в о.
Если топология сети не претерпевает никаких изменений, то в дальнейшем происходит только обработка сообщений типа mydist,и согласно предыдущей лемме с каждым таким переходом значение функции fуменьшается. В таком случае вследствие фундированности множества значенийфункции f может произойти только конечное число переходов. Значит, послеконечного числа шагов алгоритм достигнет конфигурации, в которой предикатstable обращается в истину.4.3.3. Обсуждение алгоритмаФормальная корректность алгоритма, гарантирующая сходимость результатавычисления к правильным таблицам за конечное число шагов, после того как произойдет последнее топологическое изменение, мало что говорит нам о настоящемповедении алгоритма.
На практике предикат stable может иметь значение falseбольшую часть времени (это происходит при частых топологических изменениях),а когда предикат stable ложен, ничего определенного о таблицах маршрутизациине известно. Они могут содержать циклы или даже вообще давать неверную информацию о достижимости вершин-адресатов. Поэтому предложенный алгоритмможно использовать только в таких приложениях, где топологические изменения настолько редки, что время сходимости алгоритма невелико по сравнению сосредним периодом времени, которое проходит между возникновением двух изменений в топологии сети.
Еще более осложняет ситуацию то обстоятельство, чтопредикат stable задает глобальное свойство, и поэтому с точки зрения отдельного узла сети стабильная конфигурация алгоритма неотличима от нестабильнойконфигурации. Это означает, что ни один узел не может знать наверняка, соот-146Гл. 4. Алгоритмы маршрутизацииветствуют ли его таблицы маршрутизации сложившейся топологии сети, и, следовательно, не может задержать отправление пакета, до тех пор пока не будетдостигнута стабильная конфигурация.Асинхронная обработка уведомлений. В этом параграфе мы до сих пор исходили из предположения о том, что уведомления о топологических измененияхобрабатываются автоматически на протяжении одного перехода при возникновении таких изменений. Обработка происходит одновременно по обе стороныудаленного или добавленного канала связи. Лампорт в работе [125] провел более подробный анализ, позволивший учитывать задержку обработки таких уведомлений.
Канал связи, ведущий от узла w в узел u, моделируется посредствомпоследовательного соединения трех очередей:1) OQwu — выходная очередь узла w;2) TQwu — очередь сообщений (или пакетов данных), которые уже были переправлены;3) IQwu — входная очередь узла u.При нормальном функционировании канала процесс w отправляет сообщенияпроцессу u, помещая их в очередь OQwu , затем сообщения переходят из очередиOQwu в очередь TQwu , из очереди TQwu в очередь IQwu , и, наконец, u получаетсообщения, удаляя их при этом из очереди IQwu .
Когда в канале возникает неисправность, из очереди TQwu выбрасываются все сообщения. При этом все сообщения из очереди OQwu впоследствии также выбрасываются, а не присоединяются к очереди TQwu , а в конец очереди IQwu добавляется сообщение hfail, wi. Когда возобновляется нормальное функционирование канала связи, в конец очереди IQwu добавляется сообщение hrepair, wi.
В этом случае предикаты P(u, w, v)будут иметь чуть более сложную структуру, но сам алгоритм останется без изменения.Маршрутизация по кратчайшим путям. Каждому каналу связи можно приписать весовой коэффициент; после этого рассмотренный нами алгоритм можномодифицировать так, чтобы он вместо путей с наименьшим числом звеньев вычислял кратчайшие пути. Процедура Перевычисление в алгоритме Netchangeбудет учитывать вес канала связи uw при оценке длины кратчайшего пути черезузел w, если заменить константу 1 на весовой коэффициент uw . При этом константа N должна быть заменена в алгоритме на какую-нибудь верхнюю оценкудиаметра сети.Довольно просто показать, что в том случае, когда модифицированный алгоритм достигает стабильной конфигурации, полученные таблицы маршрутизациидействительно являются правильными и задают оптимальные пути (при условии,что все циклы в сети имеют положительный вес).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
