Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 36
Текст из файла (страница 36)
Алгоритмы маршрутизацииВ начале этапа обработки опорной вершины w каждый узел u, для которого выполнено условие Du [w] < ∞, осведомлен о том, какая вершина являетсяего родителем в дереве Tw , но не располагает сведениями о том, какие вершиныявляются его сыновними вершинами. Поэтому любой узел v должен отправитьсообщение каждому своему соседу u, сообщив процессу u, является ли v сыновней вершиной для u в дереве Tw . Полное решение задачи представлено в описанииалгоритма 4.6. Всякий узел может принять участие в распространении таблицыопорной вершины w, как только он получит известия о том, какие из соседейявляются его сыновними вершинами в дереве Tw .
В алгоритме используются сообщения трех типов.1. Сообщение hys, wi (ys от «your son») отправляется от узла u к узлу xв начале этапа обработки опорной вершины w, если x является родительскойвершиной для u в дереве Tw .2. Сообщение hnys, wi (nys от «not your son») отправляется от узла u к узлуx в начале этапа обработки опорной вершины w, если x не является родительскойвершиной для u в дереве Tw .3. Сообщение hdtab, w, Di отправляется по ходу обработки опорной вершины w по каждому ребру дерева Tw , чтобы доставить таблицу Dw в каждуювершину, которая должна будет воспользоваться этим значением.Если известно, что для описания веса (ребра или пути) в совокупности с именем вершины достаточно W битов, то для оценки сложности представленногоалгоритма можно обратиться к следующей теореме.Теорема 4.9.
Для каждой пары вершин u и v алгоритм 4.6 вычисляетрасстояние между u и v, а в том случае, когда это расстояние конечно,также определяет первый канал в кратчайшем пути.По ходу работы алгоритма по каждому каналу проходит O(N) сообщенийи O(N2 W) битов информации. Таким образом, суммарно по ходу работыалгоритма передается O(N ·|E|) сообщений и O(N 3 · W) битов информации.Кроме того, в каждом узле используется память, объем которой составляет O(N · W) битов.Д о к а з а т е л ь с т в о. Алгоритм 4.6 построен на основе алгоритма 4.5,и это гарантирует его корректность.На каждом этапе обработки опорной вершины w по каждому каналу связипроходят два сообщения вида hys, wi или hnys, wi (по одному сообщению в каждом направлении) и не более одного сообщения вида hdtab, w, Di, и, значит, завремя работы алгоритма по каждому каналу проходит не более 3N сообщений.Сообщения вида hys, wi или hnys, wi содержат O(W) битов, а сообщение видаhdtab, w, Di содержит O(NW) битов, и отсюда следует верхняя оценка битовой сложности обмена информацией по каждому каналу связи.
За время работы алгоритма передается не более N 2 сообщений вида hdtab, w, Di и 2N · |E|сообщений вида hys, wi и hnys, wi; таким образом, всего по сети передаетсяO(N2 · NW + 2N · |E| · W) = O(N3 W) битов информации. Для хранения таблиц Duи Nbu каждому процессу u требуется O(NW) битов памяти.4.2.
Задача построения кратчайших путей для всех пар вершин131На протяжении одного этапа обработки опорной вершины w каждому узлуразрешается передавать и получать только те сообщения, которые имеют отношение к текущему этапу, т. е. такие сообщения, в которых в качестве параметрасодержится имя вершины w.
Если в каналах соблюдается очередность сообщений, то первые сообщения, которые получит каждый узел в начале очередногоэтапа обработки опорной вершины, — это сообщения вида hys, wi и hnys, wi,передаваемые по каждому каналу; затем от узла Nb u [w] будет получено сообщение вида hdtab, w, Di (если узел-адресат содержится в множестве вершин Vw).Аккуратное программирование позволяет избавиться от параметра w во всех сообщениях, если в каналах связи соблюдается очередность сообщений. Если жеочередность следования сообщений нарушается, может случиться так, что узелполучит сообщение с параметром w0 , в то время как он ожидает поступлениясообщения с параметром w, причем опорная вершина w 0 следует по порядку заопорной вершиной w.
В этом случае параметр w позволяет разобраться с тем,какому этапу обработки опорных вершин соответствует полученное сообщение;далее, воспользовавшись локальной буферизацией сообщений (в рамках каналаили процесса), можно устанавливать правильный порядок обработки сообщений.Туэг провел дальнейшую оптимизацию предложенного алгоритма, опираясь наследующее утверждение. (Вершина u2 считается потомком вершины u1 , если u2принадлежит поддереву с корнем u1 .)Лемма 4.10. Пусть u1 6= w, и пусть вершина u2 является потомкомвершины u1 в дереве Tw в начале этапа обработки опорной вершины w.Если на этапе обработки опорной вершины w изменяется расстояниемежду вершиной u2 и некоторой вершиной v, то на этом этапе такжеизменяется расстояние между вершиной u1 и вершиной v.Д о к а з а т е л ь с т в о. Коль скоро u2 является потомком вершины вершины u1 в дереве Tw ,dS (u2 , w) = dS (u2 , u1) + dS (u1 , w).(1)Так как u1 ∈ S, мы имеем неравенствоdS (u2 , v) 6 dS (u2 , u1) + dS (u1 , v).(2)На этом этапе значение Du2 [v] изменяется в узле u2 в том и только том случае,когдаdS (u2 , w) + dS (w, v) < dS (u2 , v).(3)Воспользовавшись неравенствами (2) и (3), подставив правую часть равенства (1)вместо dS (u2 , w) и вычтя из обеих частей образовавшегося неравенства d S (u2 , u1),мы получаем соотношениеdS (u1 , w) + dS (w, v) < dS (u1 , v),(4)из которого следует, что на этом этапе в узле u1 также изменяется значениепеременной Du1 [v] .132Гл.
4. Алгоритмы маршрутизацииСогласно доказанной лемме, алгоритм 4.6 можно улучшить следующим образом. После того как узел u получает сообщение hdtab, w, Di и получает доступ ктаблице Dw , в нем вначале выполняется локальная обработка опорной вершиныw, а затем таблица Dw отправляется сыновним вершинам узла u в дереве T w . Приэтом достаточно передать лишь те элементы таблицы D [v] , для которых в узлеu в ходе локальной обработки опорной вершины w изменились значения D u [v] .Предложенная модификация позволяет получать ациклические таблицы маршрутизации не только в конце каждого этапа обработки опорных вершин (о чемсвидетельствует лемма 4.7), но также на всем протяжении этапа обработки опорных вершин.4.2.3.
Другие алгоритмыПриведенное описание алгоритма Туэга является примером того, как распределенный алгоритм решения некоторой задачи получается непосредственноиз последовательного алгоритма решения той же задачи. Для этого переменныепоследовательного алгоритма разносятся по разным процессам; присваиваниепеременной x (в последовательном алгоритме) выполняет тот процесс, которомуназначена переменная x. Всякий раз, когда в операторе присваивания используются переменные, назначенные другим процессам, необходимо совершить обмен сообщениями между процессами, чтобы доставить значения этих переменныхи провести синхронизацию действий процессов.
Для того чтобы свести обмен сообщениями к минимуму, можно использовать те или иные особенности исходногопоследовательного алгоритма.Алгоритм Туэга достаточно прост для понимания, имеет небольшую сложность и строит оптимальные маршруты; главным недостатком алгоритма является плохая устойчивость («робастность»). Как только изменяется топология сети,все вычисления нужно проводить заново. Кроме того, у алгоритма есть две особенности, из-за которых он становится менее привлекательным с точки зренияпроектирования распределенных алгоритмов.Во-первых, как уже было упомянуто, согласованный выбор очередной опорной вершины (w) всеми узлами сети предполагает, что множество участвующихв алгоритме процессов заранее известно. Но поскольку в общем случае множество участников заранее неизвестно, перед тем как запустить алгоритм Туэга,нужно применить вспомогательный распределенный алгоритм (например, алгоритм Финна (алгоритм 6.8)), чтобы вычислить это множество.Во-вторых, в основу алгоритма Туэга положено многократное применениенеравенства треугольника d(u, v) 6 d(u, w) + d(w, v).
Для вычисления правой части этого неравенства (в узле u) требуется информация о d(w, v), а этаинформация в общем случае оказывается удаленной, т. е. ею не обладает нипроцесс u, ни его соседи. Зависимость от удаленных данных вынуждает нас организовать доставку этой информации удаленным вершинам; в алгоритме Туэгаэтим занимается блок широковещательного распространения сообщений.В качестве альтернативы мы можем рассмотреть следующее уравнение, определяющее значения d(u, v), которое можно использовать в алгоритме построения4.2. Задача построения кратчайших путей для всех пар вершин133кратчайших путей:d(u, v) =0, minw∈Neighuuw + d(w, v)если u = v;иначе.(4.1)Два свойства этого уравнения позволяют конструировать алгоритмы, которыебудут отличаться от алгоритма Туэга.1.
Локальность данных. Для вычисления правой части уравнения (4.1) в узлеu требуется только локально доступная информация (а именно uw) или информация, которая имеется у соседей (а именно d(w, v)). Необходимость в обменеданными между удаленными вершинами отпадает.2. Независимость от вершин-адресатов. Для вычисления расстояния между вершинами u и v требуется знать только расстояние d(w, v) между v и всемисоседями w вершины u.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
