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

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

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

. . , uk , что• ui 6= d для всех i,• table_lookupui (d) = ui+1 для всех i < k и• table_lookupuk (d) = u1 .Таблицы называются ациклическими, если они не содержат цикла ни для однойвершины d.122Гл. 4. Алгоритмы маршрутизации4.2. Задача построения кратчайших путей для всех пар вершинЛемма 4.3. Механизм продвижения доставляет каждый пакет по назначению в том и только том случае, когда таблицы маршрутизацииявляются ациклическими.Д о к а з а т е л ь с т в о. Если таблицы маршрутизации содержат цикл длянекоторого узла-адресата d, то пакет, адресованный процессу d, никогда не будет доставлен по назначению, если отправителем является вершина, входящаяв цикл.(* Пакет, адресованный вершине d, был получен или сформирован в вершине u *)if d = uthen доставить пакет локальными средствамиelse отправить пакет вершине table_lookupu (d)Алгоритм 4.2.

Продвижение пакетов по назначению (для узла u).Предположим, что таблицы являются ациклическими и пакет, предназначенный узлу-адресату d (и отправленный из узла-источника u0), продвинулся черезвершины u0 , u1 , u2 , . . .. Если одна и та же вершина встречается в этой последовательности дважды, скажем ui = uj , то таблицы содержат цикл, в данном случаеhui , . .

. , uj i, вопреки предположению об ацикличности таблиц. Значит, каждаявершина встречается в последовательности не более одного раза. Отсюда следует, что эта последовательность является конечной и оканчивается некоторойвершиной uk (k < N). В соответствии с описанием процедуры продвижения пакета указанная последовательность может оканчиваться только вершиной d. Такимобразом, uk = d, и пакет достигает вершины адресата, пройдя не более N − 1звеньев.В некоторых алгоритмах маршрутизации может случиться так, что таблицына этапе их вычисления не обладают свойством ацикличности, но только до техпор, пока не завершится этап вычисления таблиц. При применении такого алгоритма пакет может продвигаться по циклу, пока вычисляются таблицы, но тем неменее доставляется по назначению не более чем за N − 1 звеньев, после того каквычисление таблиц завершается при отсутствии дальнейших изменений топологии.

Если изменения топологии не прекращаются, т. е. структура сети подвергается постоянным преобразованиям, пакеты могут не достичь своего назначениядаже в том случае, если обновляемые таблицы оказываются ациклическими (см.упражнение 4.1).Разветвляемая маршрутизация с минимальной задержкой. Если требуется провести маршрутизацию по путям с наименьшей задержкой, и при этомзадержка в канале связи зависит от его загруженности (и поэтому допущение 1,сделанное в начале этого параграфа является недействительным), то стоимостьиспользования пути нельзя рассматривать как функцию, зависящую только отэтого пути. Кроме того необходимо принимать в расчет трафик по каналу связи.Чтобы избежать заторов на пути (из-за которых возникает большая задержка),пакеты, имеющие один и тот же источник и одного того же адресата, продвигают-yuuv -v uJ-vJvu@123v@@R@v @@uuvJJuJJ^vx@J@@R@J@@uJu vvТрафик в вершине vрасщепления в вершиных xи y.Рис.

4.3. Пример разветвляемой маршрутизациися различными путями; в этом случае трафик расщепляется в одной или нескольких промежуточных вершинах, как это показано на рис. 4.3. Маршрутизация, вкоторых пакеты, направленные по одному и тому же адресу, продвигаются разными путями, называются многопутевой маршрутизацией или расщепленноймаршрутизацией.

Ввиду того что методы расщепленной маршрутизации, как правило, очень сложны, мы не будем рассматривать их в этой главе.4.2. Задача построения кратчайших путейдля всех пар вершинВ этом параграфе мы рассмотрим алгоритм Туэга [194] совместного вычисления таблиц маршрутизации для всех узлов сети.

Для каждой пары вершин (u, v)алгоритм вычисляет длину кратчайшего пути из вершины u в вершину v и заносит в память процесса u первый канал этого пути. Это хорошо известная задачапостроения кратчайших путей для всех пар вершин. В основу распределенного алгоритма Туэга решения этой задачи положен централизованный алгоритмФлойда—Уоршалла [55, § 26.4] . Мы рассмотрим алгоритм Флойда —Уоршаллав § 4.2.1, а затем в § 4.2.2 обратимся к алгоритму Туэга. В § 4.2.3 мы обсудими другие алгоритмы решения задачи построения кратчайших путей для всех парвершин.4.2.1. Алгоритм Флойда—УоршаллаПредположим, что имеется взвешенный граф G = (V, E), в котором каждомуребру uv приписан вес uv . Ясно, что uv = vu , и, кроме того, мы будем считать,что в графе отсутствуют циклы отрицательного веса.

Весом пути hu 0 , . . . , uk iPназывается число, равное ik=−01 ui ui+1 . Расстоянием между вершинами u и vназывается наименьший вес d(u, v) пути, соединяющего вершины u и v (еслитаких путей нет, то расстояние считается бесконечным, d(u, v) = ∞). Задача построения кратчайших путей для всех пар вершин состоит в том, чтобы вычислитьрасстояние d(u, v) для каждой пары вершин u и v.

(В § 4.2.2 мы расширим возможности алгоритма, и он будет заносить в память процесса первое ребро путинаименьшего веса.)124Гл. 4. Алгоритмы маршрутизацииДля вычисления всех расстояний в алгоритме Флойда —Уоршалла используется понятие S-путей; это пути, в которых все промежуточные вершины принадлежат подмножеству S множества вершин V.Определение 4.4. Пусть S — некоторое подмножество множества вершин Vграфа G. Путь hu0 , . . .

, uk i называется S-путем, если ui ∈ S для каждого i, 0 << i < k. S-расстоянием между вершинами u и v, которое обозначается d S (u, v),называется наименьший вес S-пути между u и v (если таких путей нет, то расстояние считается бесконечным, dS (u, v) = ∞).Работа алгоритма начинается с построения всех ∅ -путей, а затем множествоS-путей наращивается для все более обширных подмножеств S, до тех пор пока не будут рассмотрены все V -пути. Уместно принять во внимание следующеезамечание.Предложение 4.5.

Для любой вершины u и всякого подмножества Sвыполняется равенство dS (u, u) = 0. Кроме того, если u 6= v, то S-путиподчиняются следующим правилам:1) ∅-путь из вершины u в вершину v существует в том и только томслучае, когда uv ∈ E;2) если uv ∈ E, то d∅ (u, v) = uv ; в противном случае d∅ (u, v) = ∞;3) если S0 = S ∪ {w}, то простой S0 -путь, ведущий из u в v, представляет собой либо S-путь, ведущий из u в v, либо последовательноесоединение двух S-путей, один из которых ведет из u в w, а другой — из w в v;04) если S0 = S ∪ {w}, то dS (u, v) = min (dS (u, v), dS (u, w) + dS (w, v) );5) вершины u и v соединены путем в том и только том случае, когдамежду вершинами u и v существует V-путь;6) d(u, v) = dV (u, v),4.2. Задача построения кратчайших путей для всех пар вершин125Правило (6).

Каждый V -путь является путем и наоборот. Поэтому оптимальный V-путь также является оптимальным путем.begin(* Вначале положить S равным ∅, а D считать равной ∅-расстоянию *)S := ∅ ;forall u, v doif u = v then D [u, v] := 0else if uv ∈ E then D [u, v] := uvelse D [u, v] := ∞ ;(* Добавить к S «центровую» вершину*)while S 6= V do(* Инвариант цикла: ∀u, v : D [u, v] = dS (u, v) *)begin pick w from V \ S ;(* Выполнить глобальную обработку опорной вершины w *)forall u ∈ V do(* Выполнить локальную обработку опорной вершины w для u *)forall v ∈ V doD [u, v] := min (D [u, v] , D [u, w] + D [w, v] ) ;S := S ∪ {w}end (* ∀u, v : D [u, v] = d(u, v) *)endАлгоритм 4.4. Алгоритм Флойда—УоршаллаПри помощи утверждения 4.5 и метода динамического программированиянетрудно разработать алгоритм решения задачи построения кратчайших путейдля всех пар вершин (см. алгоритм 4.4).

В этом алгоритме сначала рассматриваются ∅-пути, а затем последовательно строятся S-пути для расширяющихсямножеств S, до тех пор пока не будут рассмотрены все пути.Д о к а з а т е л ь с т в о. Для всех вершин u и подмножеств S верно нераТеорема 4.6. Алгоритм 4.4 вычисляет расстояние между всеми парамивенство dS (u, u) 6 0, потому что пустой путь (не содержащий ни одного ребра)вершин за Θ (N3) шагов.является S-путем из u в u веса 0. Никакой другой путь не имеет меньшего веса,поскольку в графе G нет циклов отрицательного веса.

Значит, d S (u, u) = 0.Д о к а з а т е л ь с т в о. В начале работы алгоритма D [u, v] = 0, если u =Правило (1). Так как ∅-путь не имеет промежуточных вершин, ∅-путь из u= v, D [u, v] = uv , если uv ∈ E, и D [u, v] = ∞ в остальных случаях. При этомв v состоит только из канала uv.S = ∅. Согласно правилам 1) и 2) утверждения 4.5 мы имеем ∀u, v : D [u, v] == dS (u, v). Если к множеству S добавляется вершина w, то согласно правилам 3)Правило (2). Следует непосредственно из правила 1).и 4) того же утверждения оператор присваивания, уточняющий значение D [u, v] ,Правило (3).

В простом S0 -пути из u в v вершина w либо встречается ровнообеспечивает сохранение выполнимости предложения ∀u, v : D [u, v] = d S (u, v),один раз, либо вообще не встречается. Если не содержит промежуточной вериспользуемого в качестве инварианта цикла. Программа завершает выполнение,шины w, то это S-путь; в противном случае этот путь представляет собой покогда S = V.

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

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