Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 46
Текст из файла (страница 46)
Полученные в результате этого расширения кластеры по-прежнему содержат не менее s вершин каждый, по-прежнему остаются связными, и ихрадиус не превосходит величины 2s.В рассматриваемом методе маршрутизации каждому пакету приписываетсяокраска, причем количество разных цветов невелико. Узлы ведут себя следующим образом. Пакет, в зависимости от его окраски, либо немедленно продвигается по заранее выделенному каналу, либо обращается с вызовом к более сложной166Гл.
4. Алгоритмы маршрутизации4.6. Упражнения к главе 4167процедуре выбора маршрута. Здесь допускается возможность того, что для обработки пакетов разные узлы используют разные протоколы.при этом не более O(f · N1/f) обращений к таблицам маршрутизации и используя 2f + 1 цветов.Теорема 4.48 ([127]). Для каждой сети, состоящей из N узлов, существует такой√ метод маршрутизации, которому требуется обращатьсяне более O( N) раз к таблицам маршрутизации для доставки каждогопакета; в этом методе используются три цвета.Д о к а з а т е л ь с т в о.
Идея доказательства подобна той, которая использоваласьдля доказательства теоремы 4.48, однако, вместо того, чтобы выбирать√s ≈ N, метод построения схемы маршрутизации применяется рекурсивно к дереву T (с тем же самым размером кластера s). Это дерево является связной сетью,в которой, по существу, имеется менее 2m вершин, поскольку на путевые вершины дерева T, перекладывающие пакеты из одного канала в другой, можно необращать внимания.Эта кластеризация повторяется f раз. Допустим, что в исходной сети G содержится N узлов.
Тогда дерево, построенное после первой кластеризации, содержитне более N/s центров и N/s вершин-развилок, т. е. всего не более N(2/s) существенных вершин. Если же дерево, построенное после i-кратной кластеризации,содержит mi существенных вершин, то после проведения очередной (i + 1) -й кластеризации будет получено дерево, в котором содержится не более m i /s центрови mi /s вершин-развилок, т. е.
не более mi (2/s) существенных вершин. Дерево,построенное после f-кратной кластеризации, будет иметь не более m f = N(2/s) fсущественных вершин.На каждом уровне кластеризации добавляются два новых цвета, и поэтомудля проведения f-кратной кластеризации необходимо использовать 2f + 1 цветов.На самом верхнем уровне кластеризации к таблицам приходится обращаться неболее 2mf раз, и, кроме того, на каждом промежуточном уровне кластеризациик таблицам маршрутизации приходится обращаться s раз, чтобы локализоватьвершину-адресат.
В результате общее число обращений к таблицам становитсяравным 2mf + fs. Если выбрать s ≈ 2N 1/f , то получим mf = O(1); поэтому числообращений к таблицам будет ограничено величиной f · s = O(f · N 1/f).Д о к а з а т е л ь с т в о. Предположим, что задано такое разбиение сети наm кластеров, о котором говорится в лемме 4.47. В таком случае в каждом кластере Ci есть такой узел ci , что для любой вершины v ∈ Ci выполняется неравенствоd(v, ci) 6 2s, поскольку радиус кластера Ci не превосходит 2s. Рассмотрим поддерево T графа G, которое имеет минимальный размер среди всех поддеревьев,соединяющих все вершины ci . Так как поддерево T является минимальным, у негоесть не более m листьев, также не более m − 2 вершин-развилок (т. е. вершин,степень которых больше 2, см.
упражнение 4.9). Вершины дерева T разделимна три класса: центры ci , вершины-развилки и оставшиеся вершины, которыебудем называть путевыми.Наш метод построения маршрута работает так: вначале пакет переправляетсяв центр ci того кластера, которому принадлежит узел-отправитель (зеленая фаза), затем пакет переправляется по дереву T в центр c j того кластера, которомупринадлежит узел-адресат (синяя фаза), и, наконец, он переправляется в кластере Cj в сам узел-адресат (красная фаза). В зеленой фазе используются заранеевыбранные входные деревья, корнями которых служат центры каждого кластера; в этой фазе нет никаких обращений к таблицам.
Путевые вершины дерева Tинцидентны в точности двум древесным каналам, и поэтому, получив синий пакет по одному из каналов, они всякий раз продвигают его по другому каналу. Ввершинах-развилках и центрах дерева T для построения маршрута приходитсяобращаться к таблицам. В красной фазе для продвижения пакета применяетсястратегия построения кратчайших маршрутов в пределах одного кластера; поэтому число обращений к таблицам в этой фазе ограничено величиной 2s.
Такимобразом, общее число обращений к таблицам ограничено величиной 2m − 2 +√2s,которая, в свою очередь, не превосходитвеличины 2N /s − 2 + 2s. Выбрав s ≈ N,√мы получаем требуемую оценку O( N).В теореме 4.48 установлена верхняя оценка общего числа обращений к таблицам, которые необходимо совершить для доставки каждого пакета, и эта оценкане зависит от какого-либо конкретного алгоритма построения таблиц маршрутизации. В качестве метода построения маршрута в дереве T можно взять древесную схему маршрутизации Санторо и Хатиба, но и к самому дереву T можнотакже применить принцип кластеризации, чтобы еще более сократить число обращений к таблицам.Теорема 4.49 ([127]).
Для любой сети, состоящей из N вершин, и длялюбого натурального числа f 6 log N существует метод построения маршрутов, позволяющий доставлять пакеты по любому адресу, осуществляяЕсли мы будем использовать приблизительно log N цветов, то в результатеможем получить метод построения маршрутов, в котором требуется осуществлять O(log N) обращений к таблицам маршрутизации. Однако проверка окраскипакета в этом случае также становится разновидностью обращения к таблице, хотя для этой цели приходится использовать маленькие таблицы (размера O(log N)в худшем случае), и доля вершин, в которых проверяется окраска, также мала.4.6.
Упражнения к главе 44.6.1Упражнение 4.1. Допустим, что таблицы маршрутизации так обновляются после каждого изменения топологической структуры сети, что они остаютсяациклическими по ходу обновления. Может ли это служить гарантией того, чтопакеты всегда доставляются по адресу даже в том случае, когда сеть претерпевает бесконечно большое количество топологических изменений?168Гл.
4. Алгоритмы маршрутизацииДокажите, что ни один алгоритм маршрутизации не способен обеспечить доставку пакетов по адресу, если сеть испытывает непрерывные изменения топологии.4.6.2Упражнение 4.2. Студент предложил исключить из алгоритма 4.6 отправление сообщений hnys, wi. Он привел следующий аргумент: узел и так узнаето том, что его сосед не является сыновней вершиной, если от этого соседа непоступает сообщений hys, wi.Можно ли таким образом модифицировать алгоритм? Какова будет сложностьтакого алгоритма?Упражнение 4.3. Докажите, что приведенная ниже формула задает инвариант алгоритма Чанди—Мисры вычисления путей, ведущих в вершину v 0 (алгоритм 4.7).∀u, w : hmydist, v0 , di ∈ Mwu∧ ∀u : d(u, v0) 6 Du [v0 ] .=⇒d(w, v0) 6 dПриведите пример выполнения, в котором количество обменов сообщениями экспоненциально зависит от числа каналов в сети.4.6.3Упражнение 4.4. Выясните, какие значения будут иметь все переменные взаключительной конфигурации алгоритма Netchange в том случае, когда этоталгоритм применяется к сети, имеющей следующую топологическую структуру:ABCDE F После того как была достигнута заключительная конфигурация, в сети возникновый канал связи между узлами A и F.
Какое сообщение узел F отправит узлу Aпри обработке уведомления hrepair, Ai? Какое послание узел A отправит узлу Fв ответ на это сообщение?4.6.4Упражнение 4.5. Приведите пример, свидетельствующий о том, что лемма 4.22 неверна для сетей с асимметричной характеристикой стоимости каналов.Упражнение 4.6. Существует ли такая ILS, в которой для построения маршрутов используются не все каналы? Существует ли правильная схема, обладающая этим свойством? Существует ли оптимальная схема, обладающая этимсвойством?Упражнение 4.7.
Приведите пример такого графа G и такого дерева поискав глубину T для графа G, которые обладают следующими свойствами: граф G4.6. Упражнения к главе 4169имеет N = n2 вершин, диаметр графа G и глубина дерева T являются величинами порядка O(n), и при этом существует такая пара узлов u и v, что схемаинтервальной разметки в глубину обеспечивает доставку пакета из вершины uв вершину v по маршруту, состоящему из N − 1 звеньев.(Граф можно выбрать таким, что G будет внешне планарным, и отсюда согласно теореме 4.37 следует, что G действительно имеет оптимальную ILS.)Упражнение 4.8.
Постройте схему интервальной разметки в глубину длякольца, состоящего из N вершин. Покажите, что существуют такие узлы u и v,что d(u, v) = 2, а схема вынуждена построить маршрут, состоящий из N − 2звеньев, для доставки пакета из вершины u в вершину v.4.6.5Упражнение 4.9. Докажите, что из минимальности дерева T, используемогов доказательстве теоремы 4.48, следует, что это дерево имеет не более m листьев.
Докажите, что всякое дерево с m листьями имеет не более m − 2 вершинразвилок.5.1. ВведениеГЛАВА 5НЕБЛОКИРУЕМАЯ КОММУТАЦИЯ ПАКЕТОВСообщения (пакеты), перемещающиеся по коммуникационной сети с пакетнойкоммутацией, должны сохраняться в памяти каждого узла, перед тем как ониотправлены в следующий узел по пути их следования к вершине-адресату.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
