Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 45
Текст из файла (страница 45)
Еслиw — это такая сыновняя вершина для u, для которой выполняется включение v ∈∈T [w] , то по определению древесной схемы выполняется соотношение uw /lv .В трех леммах, которые приведены ниже, рассматривается одна и та же ситуация, когда пакет из узла u продвигается согласно алгоритму 4.20 по направлениюк вершине v через узел w, являющийся соседом вершины u.Лемма 4.43. Если u ∈ T [v] , то w является предком u.Д о к а з а т е л ь с т в о. Если uw = , то по построению схемы вершина wявляется предком узла u. Если uw = lw , то, ввиду того что uw / lv , выполняетсясоотношение lw / lv .
Отсюда следует, что w является предком вершины v, а значиттакже и предком вершины u.4.4. Маршрутизация с использованием компактных таблиц163Лемма 4.44. Если узел u является предком узла v, то узел w являетсяпредком узла v, и при этом узел w расположен к вершине v ближе, чемузел u.Д о к а з а т е л ь с т в о. Рассмотрим такую сыновнюю вершину w 0 для узла u,для которой выполняется включение v ∈ T [w0 ] . Тогда uw0 = lw0 — это непустой префикс пометки lv . Так как uw — это наиболее длинный префикс (среди всех пометок каналов, примыкающих к u) строки l v , отсюда следует, чтоuw0 / uw / lv , и поэтому узел w является предком вершины v, который расположен ниже узла u.Лемма 4.45.
Если u 6 ∈T [v] , то либо узел w является предком узла v,либо выполняется неравенство dT (w, v) < dT (u, v).Д о к а з а т е л ь с т в о. Если uw = , то w является либо родительскойвершиной для u, либо корнем дерева. Родительская вершина для узла u расположена ближе к узлу v, чем сам узел u, потому что u 6 ∈T [v] , а корень дереваявляется предком узла v. Если uw = lw , то, ввиду того что uw / lv , узел wявляется предком узла v.Глубиной корневого дерева T называется величина depth, равная числу звеньев самого протяженного простого пути, соединяющего корень дерева с однимиз его листьев.
Как можно заметить, каждый пакет, адресованный узлу v, достигает вершины-адресата, пройдя путь, состоящий не более чем из 2 · depthзвеньев. Если пакет сформирован в узле, который является предком вершины v,то согласно лемме 4.44 узел v достигается не более чем за depth шагов. Еслипакет сформирован в одном из узлов поддерева T [v] , то согласно лемме 4.43 одиниз предков v достигается менее чем за depth шагов, после чего, как было толькочто установлено, пакет достигает вершины v не более чем за depth шагов.
(Учитывая, что в этом случае путь проходит только через узлы, являющиеся предкамивершины-отправителя, можно заключить, что длина пути на самом деле такжене будет превышать величины depth.) Во всех остальных случаях согласно лемме 4.45 какой-нибудь предок узла v будет достигнут не более чем за depth шагов,после чего пакет достигает вершины v не более чем за depth шагов. (Таким образом, в этом случае длина пройденного пути ограничена величиной 2 · depth.)Этим завершается доказательство теоремы 4.40.Следствие 4.46.
Для каждой сети G диаметра DG , измеряемого числомзвеньев пути, существует такая схема префиксной разметки, котораягарантирует доставку всех пакетов не более чем за 2DG шагов.Д о к а з а т е л ь с т в о. Нужно воспользоваться древесной PLS, дерево которой построено так, как это указано в лемме 4.22.Мы завершим наше изучение древесной схемы разметки кратким обсуждением вопроса об объеме памяти, необходимом для ее реализации.
Как и прежде,depth будет обозначать глубину дерева T. Обозначим символом k максимальноечисло сыновних вершин для каждого узла дерева T. Тогда самая длинная пометка состоит из depth букв, в то время как алфавит Σ должен содержать по164Гл. 4. Алгоритмы маршрутизациименьшей мере k букв. Это означает, что для хранения произвольной пометки достаточно выделить depth · log k битов памяти. Вся таблица маршрутизации в узле,к которому примыкают deg каналов связи, укладывается в O(deg · depth · log k)битов.Ряд других схем префиксной разметки был предложен в работе Беккера и др.[19] . В этой работе был полностью описан класс всех топологических структур,для которых есть оптимальная схема префиксной разметки даже в том случае,когда весовые коэффициенты каналов связи могут динамически изменяться.4.5. Иерархическая маршрутизация165в том, что весь кластер целиком оказывается чувствительным к неисправностям,которые могут случиться в центре.
Ленферт и др. в работе [132] предложилииерархический метод маршрутизации, в котором каждый узел наделен способностью отправлять сообщения за пределы кластера. Тем не менее, в этом методеиспользуются только небольшие таблицы, потому что весь кластер, которомупринадлежит узел, рассматривается как одна вершина. Авербах и др. в работе[17] использовали принцип иерархической маршрутизации для построения такогокласса схем маршрутизации, в котором достигается компромисс между эффективностью маршрутизации и объемом расходуемой памяти.4.5.
Иерархическая маршрутизацияОдин из способов, позволяющих понизить различные показатели стоимостимаршрутизации, предлагает воспользоваться иерархическим разбиением сетии связанными с ним иерархическими методами маршрутизации. Во многих случаях цель состоит в том, чтобы извлечь пользу из того факта, что большая частькоммуникаций в компьютерной сети проводится локально, т.
е. между узлами,которые отстоят друг от друга сравнительно недалеко. Мы сейчас покажем, чтонекоторые из показателей стоимости метода маршрутизации зависят от размеравсей сети, а не от длины выбранного пути.1. Длина адресов. Так как все N узлов сети имеют разные адреса, для хранения каждого адреса требуется не менее log N битов; если адрес служит для кодирования некоторой информации, как это осуществляется в схеме префиксноймаршрутизации, то для представления адреса может потребоваться и большеечисло битов.2.
Размер таблицы маршрутизации. В тех методах маршрутизации, которые были описаны в §§ 4.6.2 и 4.6.3, таблица содержит запись для каждого узласети, и, следовательно, ее размер линейно зависит от размера сети.3. Стоимость обращений к таблицы. Разумно считать, что стоимостьодного обращения к таблице возрастает по мере увеличения размеров таблицы и длины адресов. Общее время, затраченное на обращение к таблицам, придоставке одного сообщения зависит также от того, сколько раз приходится обращаться к таблицам.Иерархический метод маршрутизации предполагает разбиение сети на кластеры, каждый из которых представляет собой связное множество узлов.
Еслиотправитель и адресат пакета находятся в одном кластере, стоимость доставкисообщения будет мала, так как при проведении маршрутизации внутри кластераего можно рассматривать как небольшую изолированную сеть. В том методе, который описан в §4.5.1, в каждом кластере зафиксирован некоторый узел (центркластера), при помощи которого можно строить и более сложные маршруты,необходимые для доставки пакетов в другие кластеры. Таким образом, работас обширными таблицами и длинными адресами проводится только в таких центрах.
Каждый кластер, в свою очередь, может быть подразделен на подкластеры,благодаря чему достигается многоуровневое разделение узлов.Совсем необязательно, чтобы взаимосвязь между кластерами осуществлялась только через их центры; недостаток такого способа коммуникации состоит4.5.1. Сокращение числа узлов, в которых выбираетсямаршрутДо сих пор мы изучали только такие методы маршрутизации, в которых выбор маршрута проводится в каждой промежуточной вершине. Это означает, чтов маршруте длины l приходится l раз обращаться к таблицам маршрутизации.
Длястратегии маршрутизации с наименьшим числом звеньев величина l ограниченадиаметром сети, но в общем случае, для ациклической стратегии маршрутизации(наподобие интервальной маршрутизации), верхняя оценка этой величины может быть равна N − 1. В этом параграфе мы займемся изучением одного метода,который позволяет сократить количество обращений к таблицам.Нам потребуется следующая лемма, которая устанавливает возможность разбиения сети на связные кластеры.Лемма 4.47. Для любого числа s 6 N существует такое разбиениесети на кластеры C1 , . .
. , Cm , что1) каждый кластер является связным подграфом;2) каждый кластер содержит не менее s вершин;3) радиус каждого кластера не превышает 2s.Д о к а з а т е л ь с т в о. Рассмотрим максимальную совокупность D 1 , . . . , Dmпопарно непересекающихся связных подграфов, каждый из которых имеет радиусне больше s и содержит не менее s вершин. Каждая вершина, не вошедшая в множество ∪mi=1 Di , может быть соединена с одним из этих подмножеств путем, длинакоторого не превосходит s, ибо в противном случае такой путь можно было бывзять в качестве отдельного кластера. Образуем новые кластеры C i путем добавления каждой вершины, не вошедшей в множество ∪ mi=1 Di , к ближайшему к нейкластеру Di .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
