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

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

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

. . , / ) ) ++ (число упорядоченных пар и, v , для которыхD u [v]= г),и значением функции / будем считать (N + 1)-местный набор/(т) = (to,t\,...,tfj).На множестве таких наборов введем лексикографический порядок Д/. Здесь нуж­но вспомнить о том, что (N^-1-1, ^/) является вполне упорядоченным множеством4.3. Алгоритм Netchange145Лемма 4.17. Обработка сообщений типа m yd ist приводит к уменьше­нию значения /.Д о к а з а т е л ь с т в о .

Предположим, что в узел и, у которого Du[v] =поступило сообщение (mydist, v, d ^ ) , и после выполнения перевычисленияновое значение переменной Da[v\ становится равным d. Из описания алгоритмавытекает, что d ^ d%+ 1 .Случай d < d i . Тогда d = с?2 + 1, и отсюда следует, что значение Ер (равнокак и t d ,) уменьшается на единицу, и только значения td, у которых d > d 2 ,увеличиваются.

Отсюда следует, что значение функции / уменьшается.Случай d = d i . Узел и не отправляет никаких новых сообщений типа my­dist, и на функции / это сказывается только в том, что значение 0 2 уменьшаетсяна единицу. Поэтому значение / уменьшается.Случай d > d i . Тогда значение(равно как и lrg) уменьшается на единицу,и только значения О, у которых d > d\, увеличиваются. Отсюда следует, чтозначение функции / уменьшается.□= d\,Теорема 4.18. Если начиная с какого-то момента топология сети оста­ется неизменной, то спустя конечное числю шагов алгоритм достигаетстабильной конфигурации.Д о к а з а т е л ь с т в о .

Если топология сети не претерпевает никаких изме­нений, то в дальнейшем происходит только обработка сообщений типа mydist,и согласно предыдущей лемме с каждым таким переходом значение функции /уменьшается. В таком случае вследствие фундированности множества значенийфункции / может произойти только конечное число переходов. Значит, послеконечного числа шагов алгоритм достигнет конфигурации, в которой предикатstable обращается в истину.□4.3.3.

Обсуждение алгоритмаФормальная корректность алгоритма, гарантирующая сходимость результатавычисления к правильным таблицам за конечное число шагов, после того как про­изойдет последнее топологическое изменение, мало что говорит нам о настоящемповедении алгоритма. На практике предикат stable может иметь значение falseбольшую часть времени (это происходит при частых топологических изменениях),а когда предикат stable ложен, ничего определенного о таблицах маршрутизациине известно.

Они могут содержать циклы или даже вообще давать неверную ин­формацию о достижимости вершин-адресатов. Поэтому предложенный алгоритмможно использовать только в таких приложениях, где топологические измене­ния настолько редки, что время сходимости алгоритма невелико по сравнению сосредним периодом времени, которое проходит между возникновением двух изме­нений в топологии сети. Еще более осложняет ситуацию то обстоятельство, чтопредикат stable задает глобальное свойство, и поэтому с точки зрения отдель­ного узла сети стабильная конфигурация алгоритма неотличима от нестабильнойконфигурации.

Это означает, что ни один узел не может знать наверняка, соот­146Гл. 4. Алгоритмы маршрутизацииветствуют ли его таблицы маршрутизации сложившейся топологии сети, и, сле­довательно, не может задержать отправление пакета, до тех пор пока не будетдостигнута стабильная конфигурация.Асинхронная обработка уведомлений.

В этом параграфе мы до сих пор ис­ходили из предположения о том, что уведомления о топологических измененияхобрабатываются автоматически на протяжении одного перехода при возникно­вении таких изменений. Обработка происходит одновременно по обе стороныудаленного или добавленного канала связи. Лампорт в работе [125] провел бо­лее подробный анализ, позволивший учитывать задержку обработки таких уве­домлений.

Канал связи, ведущий от узла да в узел и, моделируется посредствомпоследовательного соединения трех очередей:1) OQwu — выходная очередь узла да;2) TQWU— очередь сообщений (или пакетов данных), которые уже были пе­реправлены;3) IQwu — входная очередь узла и.При нормальном функционировании канала процесс да отправляет сообщенияпроцессу и, помещая их в очередь OQwu, затем сообщения переходят из очередиOQwu в очередь TQWU, из очереди TQwa в очередь IQWU, и, наконец, и получаетсообщения, удаляя их при этом из очереди IQwa. Когда в канале возникает неис­правность, из очереди TQWU выбрасываются все сообщения.

При этом все сооб­щения из очереди OQwu впоследствии также выбрасываются, а не присоединяют­ся к очереди TQwa, а в конец очереди IQwa добавляется сообщение (fail, да). Ко­гда возобновляется нормальное функционирование канала связи, в конец очере­ди IQwu добавляется сообщение (repair, да). В этом случае предикаты Р(и, да, v)будут иметь чуть более сложную структуру, но сам алгоритм останется без изме­нения.Маршрутизация по кратчайшим путям. Каждому каналу связи можно при­писать весовой коэффициент; после этого рассмотренный нами алгоритм можномодифицировать так, чтобы он вместо путей с наименьшим числом звеньев вы­числял кратчайшие пути. Процедура Перевычисление в алгоритме Netchangeбудет учитывать вес канала связи ида при оценке длины кратчайшего пути черезузел да, если заменить константу 1 на весовой коэффициент соцш.

При этом кон­станта N должна быть заменена в алгоритме на какую-нибудь верхнюю оценкудиаметра сети.Довольно просто показать, что в том случае, когда модифицированный алго­ритм достигает стабильной конфигурации, полученные таблицы маршрутизациидействительно являются правильными и задают оптимальные пути (при условии,что все циклы в сети имеют положительный вес). А вот доказательство того,что алгоритм рано или поздно достигает заключительной конфигурации, требуетвведения более сложной нормирующей функции.Можно даже провести такое обобщение этого алгоритма, чтобы он мог ра­ботать с каналами связи, имеющими переменный вес; реакцией узла и на из­менение весового коэффициента канала должно быть перевычисление значений4.4. Маршрутизация с использованием компактных таблицадр.t»iи147кан.®2-ViШ3VNW1канальW1®2Ш3адресаты..., VNVI, ......, Vj, ...WAРис.

4.11. Сокращение размера таблиц маршрутизациипеременных Du[v\ для всех вершин v. Однако такой алгоритм мог бы иметь прак­тическое применение только в тех случаях, когда средний период времени междуизменениями весовых коэффициентов каналов связи значительно превосходитвремя сходимости алгоритма. К сожалению, это совершенно нереальное допу­щение. В данной ситуации предпочтение отдается таким алгоритмам, которыегарантирует ацикличность таблиц маршрутизации на протяжении всего периодасходимости; к их числу относится, например, алгоритм Мерлина—Сигалла.4.4. Маршрутизация с использованием компактных таблицДо сих пор мы имели дело с алгоритмами маршрутизации, которые в каж­дом узле сети создают и поддерживают таблицы маршрутизации с отдельнымвходом для каждой вершины-адресата.

Когда пакет продвигается по сети, обра­щение к таблицам происходит в каждом узле пройденного пути (за исключениемвершины-адресата). В этом параграфе мы займемся изучением такого устройстватаблиц маршрутизации, которое позволяет сократить объем памяти и издержки,связанные с просмотром таблиц. Мы не будем здесь касаться вопросов о том, каквычислять такие таблицы при помощи распределенных алгоритмов. Для простотыописания алгоритмов на протяжении всего этого параграфа мы будем предпола­гать, что все рассматриваемые сети являются связными.Общая стратегия получения таблиц меньшего размера, которая используетсяв каждом из трех алгоритмов, рассматриваемых в этом параграфе, очень проста.Если для каждой вершины-адресата в таблице того или иного узла отдельно ука­зывается соответствующий исходящий канал связи, то таблица маршрутизациибудет неизбежно иметь длину N ; таким образом, для хранения таблицы требует­ся fi(/V) битов памяти независимо от того, насколько компактно закодированы вней имена вершин-адресатов.

Теперь попробуем организовать устройство таблицпо-другому: для каждого канала связи, примыкающего к узлу, построим списоквершин-адресатов, маршруты к которым начинаются с прохождения этого канала(см. рис. 4.11). Если к узлу примыкают deg каналов связи, то и «длина» таблицыбудет равна deg', реальная экономия памяти будет зависеть от того, насколькокомпактно мы сможем представить множество всех вершин-адресатов, соответ­ствующих каждому каналу связи. Чтобы эффективно проводить поиск в таб­148Гл.

4. Алгоритмы маршрутизациилицах, они должны быть устроены так, чтобы для заданной вершины-адресатана основе таблиц можно было быстро выбрать соответствующий ей исходящийканал связи.4.4.1. Схема древесной разметкиПервый компактный метод маршрутизации был предложен Санторо и Хатибом в работе [169]. Этот метод помечает каждую вершину целым числом от Одо /V — 1 таким образом, чтобы для каждого канала связи множество вершинадресатов, сообщение с которыми осуществляется через этот канал, представля­ло собой интервал. Обозначим символом Z^ множество целых чисел {0, 1, .

. . , N —Арифметические операции в этом множестве будут проводиться по модулю N, т. е.(N — 1) + 1 = 0, но при этом в множестве Z будет действовать такой же порядокрасположения элементов, как в натуральном ряде.Определение 4.19. Циклическим интервалом [а, Ь) на множестве Z aj бу­дем называть всякое множество целых чисел, удовлетворяющее следующему со­отношению:_ J {а, а + 1 , . . . , b - 1 },|{ 0 , . .

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

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