Распределенные алгоритмы (стр. 26 из 85)

Лемма 4.1. Пусть u, v ÎV. Если путь из u в v существует в G, тогда и существует простой путь, который оптимален.

Доказательство. Так как количество простых путей конечное число, то существует простой путь от u до v, назовем его So, с наименьшей стоимостью, т.е., для каждого простого пути P' из u в v C(So)£C(P’). Осталось показать что C(So) нижняя граница стоимостей всех (не простого) путей

Запишем V = {v1, ..., vn}. Следовательно, удаляя из P циклов, включающие v1, v1, v2 и т.д., покажем что для каждого пути P из u в v существует простой путь P' с C(P')£ C(P). Положим Po =P, и построим для i = 1,..., N путь Pi следующим образом. Если vi входит в Pi-1 тогда Pi = Pi-1. Иначе, запишем Pi-1 = <uo, ...,uk>. Пусть uj1 будет первым и uj2 будет последним вхождением vi в Pi-1 и положим

Pi = <uo, . . . , uj1(=uj2), uj2+1, . . .,uk>

по построению Pi - путь из u к v и содержит все вершины из {v1, ..., vn} только единожды, следовательно PN -простой путь из u в v. Pi-1 состоит из Pi и цикла Q= uo, . . . , uj2 следовательно C(Pi-1) = C(Pi) + C(Q). Так как не существует циклов отрицательного веса, это предполагает C(Pi) £ C(Pi-1) и, следовательно, C(PN )£ C(P).

По выбору So, C(So) £ C(PN,), из которого следует C(So) £ C(P) []

Если G содержит циклы отрицательного веса, оптимальный путь не обязательно существует; каждый путь может быть «побежден» другим путем, который пройдет через отрицательный цикл еще раз. Для следующей теоремы, примите, что G связный (для несвязных графов, теорема может применяться к каждому связному компоненту отдельно).

Теорема4.2. Для каждого d Î V существует Td = (V, Ed) такое что Ed Í E и такое что для каждой вершины v Î V, путь из v к d в Td - оптимальный путь от v к d в G.

Доказательство. Пусть V = { v1, ..., vN }. Мы индуктивно построим последовательность деревьев Ti = (Vi, Ei) (для i = 0, ...,N) со следующими свойствами

(1) Каждое Ti - поддерево G, т.е., Vi Ì V, Ei Ì E, и Ti - дерево.

(2) Каждое Ti (для i < N) поддерево Ti+1.

(3) Для всех i > 0, vi Î Vi и d Î Vi.

(4) Для всех wÎVi, простой путь от w к d в T, - оптимальный путь от w к d в G.

Эти свойства подразумевают, что TN соответствует требованиям для Td.

Конструируя последовательность деревьев, положим Vd = {d} и Eo = Æ . Дерево Ti+1 построим следующим образом. Выберем оптимальный простой путь P=<uo, . . ., uk> от vi+1 к d, и пусть l будет наименьшим индексом таким, что ul Î Ti (такое l существует, потому что ul = d Î Ti ; возможно l = 0). Теперь:

Vi = Vi È{ uj: j <l} и Ei+1 = Ei È {( uj, uj+1) : j < 1}.

(Построение иллюстративно представлено на Рисунке 4.1.) Нетрудно видеть что Ti поддерево Ti+1 и что vi+1 Î Vi+1. Чтобы увидеть что Ti+1 дерево, заметим что по построению Ti+1 связный, и число вершин превосходит число ребер на одно. (T_oимеет последнее свойство, на каждом шаге много вершин и ребер добавлено)

Рисунок 4.1 Построение T_i+1.

Осталось показать, что для всех w Î Vi+1 , (уникальный) путь от w к d в Ti+1 - оптимальный путь от w к d в G. Для вершин w Î Vi Ì Vi+1 это следует, потому что Ti поддерево Ti+1 ; путь от w к d в Ti+1 точно такой же, как путь в Ti, который оптимален. Теперь пусть w = uj, j < l будет вершиной в Vi+1 &bsol;V,. Запишем Q для пути от ui к d в Ti, тогда в Ti+1 uj соединена с d через путь <uj, . . . , ul> соединенный с Q, и осталось показать, что этот путь оптимальный в G. Во-первых, суффикс P' = <ul, . . . , uk> в P оптимальный путь от ul до d, т.е., C(P') = C(Q): оптимальность Q подразумевает что C(P') ³C(Q), и C(Q)< C(P') подразумевает (добавлением стоимости пути) что путь <uo, . . . , ul> соединен с Q имеющий меньший путь, чем P, противоречащий оптимальности P. Теперь положим, что R из uj к d имеет меньшую стоимость, чем путь <uj, . . . , ul> соединенный с Q. Тогда, по предыдущим наблюдениям, R имеет меньшую стоимость, чем суффикс <uj, . . . , uk> P, и это предполагает что путь <uo, . . . , uj> соединенный с R имеет меньшую стоимость, чем P, противоречащий оптимальности P. Ž

Дерево охвата, приложенное к d , называется деревом стока для d, и дерево со свойством, данным в Теореме 4.2 , называется оптимальным деревом стока. Существование оптимальных деревьев стока не является компромиссом оптимальности, если только алгоритмы маршрутизации рассматриваются, для которого механизм пересылки, как в Алгоритме 4.2. В этом алгоритме, table_lookupu локальная процедура с одним параметром, возвращая соседа u (после консультации с таблицами маршрутизации). Действительно, поскольку все пакеты для адресата d могут быть направлены оптимально используя дерево обхвата, приложенное к d, пересылка оптимальна, если, для всего u¹d, table_lookupu(d) возвращает отца u в дереве охвата Td.

Когда механизм пересылки имеет эту форму, и никакие (дальнейшие) изменения топологии не происходят, корректность таблиц маршрутизации может быть удостоверена, используя следующий результат. Таблицы маршрутизации, как говорят, содержат цикл (для адресата d), если существуют узлы u1, . . . , uk такие, что для всех i , ui ¹d, для всех i < k, table_lookupu(d) = ui+1, и table_lookupu(d) = uj+1.. Таблицы, как говорят, являются свободным от циклов, если они не содержат циклов для любого d.

(* Пакет с адресатом d был получен или сгенерирован в узле u *)

if d=u

then доставить «местный» пакет

else послать пакет к table_lookupu (d)

Алгоритм 4.2 Адресат-основанная пересылка (для узла u).

Лемма 4.3 Механизм пересылки доставляет каждый пакет адресату, тогда и только тогда когда таблицы маршрутизации цикл-свободны.

Доказательство. Если таблицы содержат цикл для некоторого адресата d, пакет для d никогда не будет доставлен, если источник - узел в цикле.

Примем, что таблицы цикл-свободны и позволяют пакету с адресатом d (и источник uo) быть посланным через uo, u1, u2, . .. если один встречается дважды в этой последовательности, скажем ui = uj, тогда таблицы содержат цикл, а именно < ui ..., uj> противореча предположению, что таблицы являются цикл-свободными. Таким образом, каждый узел входит единожды, что подразумевает, что эта последовательность конечна, заканчивающаяся, скажем, в узле Великобританию uk (k < N). Согласно процедуре пересылки последовательность может заканчиваться только в d , то есть, uk = d, и пакет достиг адресата за не больше чем N — 1 шагов 

В некоторых алгоритмах маршрутизации случается, что таблицы не цикл-свободны в течение их вычисления. Когда такой алгоритм используется, пакет может пересекать цикл в течение вычисления таблиц, но достигает адресата не больше чем N — 1 шагов после завершения вычисления таблицы, если изменения топологии прекращаются. Если изменения топологии не прекращаются, то есть, сеть подчинена бесконечной последовательности изменений топологии, пакеты не обязательно достигают своего адресата, даже если таблицы цикл-свободны во время модификаций;

Ветвящаяся маршрутизация с минимальной задержкой. При маршрутизации через пути с минимальной задержкой требуется, и задержка канала зависит от использования (таким образом, предположение (1) в начале этого раздела не имеет силу), стоимость использования пути не может просто быть оценена как функция этого единственного пути. Кроме того, трафик на канал должен быть принят во внимание. Избегать скопления пакетов (и возникающую в результате этого задержку) на пути, обычно необходимо посылать пакеты, имеющие ту же самую пару исходный-адресат через различные пути; трафик для этой пары "распределяется" в один или большее количество узлов промежуточного звена как изображено в Рисунке 4.3. Методы маршрутизации, которые используют различные пути к одному адресату, называются много-путевыми или ветвящимися методами маршрутизации. Потому что ветвящиеся методы маршрутизация являются, обычно, очень запутанными, они не будет рассматриваться в этой главе

Рисунок 4.3 Пример буферизованной маршрутизации.

4.2 Проблема кротчайших путей всех пар

Этот раздел обсуждает алгоритм Toueg [Tou80a] одновременного вычисления таблицы маршрутизации для всех узлов в сети. Алгоритм вычисляет для каждой пары (u, v) узлов длину самый короткий пути от u до v и сохраняет первый канал такого пути в u. Проблема вычисления самого короткого пути между любыми двумя узлами графа известна как проблема кротчайшего пути всех пар. Распределенный алгоритм Toueg для этой проблемы основан на централизованном алгоритме Флойда-Уошалла [CLR90, Раздел 26.4]. Мы обсудим алгоритм Флойда-Уошалла в Подразделе 4.2.1, и впоследствии алгоритм Toueg в Подразделе 4.2.2. Краткое обсуждение некоторых других алгоритмов для проблемы кротчайших путей всех пар следует в Подразделе 4.2.3 ..