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

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

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

Обозначим символом k максимальноечисло сыновних вершин для каждого узла дерева Т. Тогда самая длинная по­метка состоит из depth букв, в то время как алфавит У должен содержать по164Гл. 4. Алгоритмы маршрутизациименьшей мере k букв. Это означает, что для хранения произвольной пометки до­статочно выделить depth- log£ битов памяти.

Вся таблица маршрутизации в узле,к которому примыкают deg каналов связи, укладывается в 0(deg ■depth • log6)битов.Ряд других схем префиксной разметки был предложен в работе Беккера и др.[19]. В этой работе был полностью описан класс всех топологических структур,для которых есть оптимальная схема префиксной разметки даже в том случае,когда весовые коэффициенты каналов связи могут динамически изменяться.4.5. Иерархическая маршрутизацияОдин из способов, позволяющих понизить различные показатели стоимостимаршрутизации, предлагает воспользоваться иерархическим разбиением сетии связанными с ним иерархическими методами маршрутизации. Во многих слу­чаях цель состоит в том, чтобы извлечь пользу из того факта, что большая частькоммуникаций в компьютерной сети проводится локально, т.

е. между узлами,которые отстоят друг от друга сравнительно недалеко. Мы сейчас покажем, чтонекоторые из показателей стоимости метода маршрутизации зависят от размеравсей сети, а не от длины выбранного пути.1. Длина адресов. Так как все N узлов сети имеют разные адреса, для хра­нения каждого адреса требуется не менее log Л/ битов; если адрес служит для ко­дирования некоторой информации, как это осуществляется в схеме префиксноймаршрутизации, то для представления адреса может потребоваться и большеечисло битов.2. Размер таблицы маршрутизации. В тех методах маршрутизации, кото­рые были описаны в §§ 4.6.2 и 4.6.3, таблица содержит запись для каждого узласети, и, следовательно, ее размер линейно зависит от размера сети.3. Стоимость обращений к т а б л и ц ы Разумно считать, что стоимостьодного обращения к таблице возрастает по мере увеличения размеров табли­цы и длины адресов.

Общее время, затраченное на обращение к таблицам, придоставке одного сообщения зависит также от того, сколько раз приходится об­ращаться к таблицам.Иерархический метод маршрутизации предполагает разбиение сети на кла­стеры, каждый из которых представляет собой связное множество узлов. Еслиотправитель и адресат пакета находятся в одном кластере, стоимость доставкисообщения будет мала, так как при проведении маршрутизации внутри кластераего можно рассматривать как небольшую изолированную сеть.

В том методе, ко­торый описан в §4.5.1, в каждом кластере зафиксирован некоторый узел (центркластера), при помощи которого можно строить и более сложные маршруты,необходимые для доставки пакетов в другие кластеры. Таким образом, работас обширными таблицами и длинными адресами проводится только в таких цен­трах. Каждый кластер, в свою очередь, может быть подразделен на подкластеры,благодаря чему достигается многоуровневое разделение узлов.Совсем необязательно, чтобы взаимосвязь между кластерами осуществля­лась только через их центры; недостаток такого способа коммуникации состоит4.5. Иерархическая маршрутизация165в том, что весь кластер целиком оказывается чувствительным к неисправностям,которые могут случиться в центре.

Ленферт и др. в работе [132] предложилииерархический метод маршрутизации, в котором каждый узел наделен способно­стью отправлять сообщения за пределы кластера. Тем не менее, в этом методеиспользуются только небольшие таблицы, потому что весь кластер, которомупринадлежит узел, рассматривается как одна вершина. Авербах и др.

в работе[17] использовали принцип иерархической маршрутизации для построения такогокласса схем маршрутизации, в котором достигается компромисс между эффек­тивностью маршрутизации и объемом расходуемой памяти.4.5.1. Сокращение числа узлов, в которых выбираетсямаршрутДо сих пор мы изучали только такие методы маршрутизации, в которых вы­бор маршрута проводится в каждой промежуточной вершине. Это означает, чтов маршруте длины / приходится / раз обращаться к таблицам маршрутизации. Длястратегии маршрутизации с наименьшим числом звеньев величина / ограниченадиаметром сети, но в общем случае, для ациклической стратегии маршрутизации(наподобие интервальной маршрутизации), верхняя оценка этой величины мо­жет быть равна N —1.

В этом параграфе мы займемся изучением одного метода,который позволяет сократить количество обращений к таблицам.Нам потребуется следующая лемма, которая устанавливает возможность раз­биения сети на связные кластеры.Лемма 4.47. Для любого числа s ^ N существует такое разбиениесети на кластеры С\, . . . , Ст, что1 ) каждый кластер является связным подграфом;2 ) каждый кластер содержит не менее s вершин;3) радиус каждого кластера не превышает 2s.Д о к а з а т е л ь с т в о . Рассмотрим максимальную совокупность D \ , . .

. , Dmпопарно непересекающихся связных подграфов, каждый из которых имеет радиусне больше s и содержит не менее s вершин. Каждая вершина, не вошедшая в мно­жество UiL\Di, может быть соединена с одним из этих подмножеств путем, длинакоторого не превосходит s, ибо в противном случае такой путь можно было бывзять в качестве отдельного кластера. Образуем новые кластеры С; путем добав­ления каждой вершины, не вошедшей в множество U^LjA, к ближайшему к нейкластеру А . Полученные в результате этого расширения кластеры по-прежне­му содержат не менее s вершин каждый, по-прежнему остаются связными, и ихрадиус не превосходит величины 2 s.□В рассматриваемом методе маршрутизации каждому пакету приписываетсяокраска, причем количество разных цветов невелико.

Узлы ведут себя следую­щим образом. Пакет, в зависимости от его окраски, либо немедленно продвигает­ся по заранее выделенному каналу, либо обращается с вызовом к более сложной166Гл. 4. Алгоритмы маршрутизациипроцедуре выбора маршрута. Здесь допускается возможность того, что для об­работки пакетов разные узлы используют разные протоколы.Теорема 4.48 ( [ 127] ) .

Для каждой сети, состоящей из N узлов, суще­ствует такой метод маршрутизации, которому требуется обращатьсяне более 0(\/N ) раз к таблицам маршрутизации для доставки каждогопакета', в этом методе используются три цвета.Д о к а з а т е л ь с т в о . Предположим, что задано такое разбиение сети нат кластеров, о котором говорится в лемме 4.47. В таком случае в каждом класте­ре Ci есть такой узел с*, что для любой вершины v € С; выполняется неравенствоd{u, ci) + 2s, поскольку радиус кластера С; не превосходит 2s. Рассмотрим под­дерево Т графа G, которое имеет минимальный размер среди всех поддеревьев,соединяющих все вершины с*.

Так как поддерево Т является минимальным, у негоесть не более m листьев, также не более m — 2 вершин-развилок (т. е. вершин,степень которых больше 2, см. упражнение 4.9). Вершины дерева Т разделимна три класса: центры щ, вершины-развилки и оставшиеся вершины, которыебудем называть путевыми.Наш метод построения маршрута работает так: вначале пакет переправляетсяв центр с; того кластера, которому принадлежит узел-отправитель (зеленая фа­за), затем пакет переправляется по дереву Т в центр c-j того кластера, которомупринадлежит узел-адресат (синяя фаза), и, наконец, он переправляется в класте­ре С/ в сам узел-адресат (красная фаза).

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

Ввершинах-развилках и центрах дерева Т для построения маршрута приходитсяобращаться к таблицам. В красной фазе для продвижения пакета применяетсястратегия построения кратчайших маршрутов в пределах одного кластера; по­этому число обращений к таблицам в этой фазе ограничено величиной 2s. Такимобразом, общее число обращений к таблицам ограничено величиной 2т —2 + 2 s,которая, в свою очередь, не превосходит величины 2N/s —2 + 2s. Выбрав s ~ \/N ,мы получаем требуемую оценку 0{\/N).□В теореме 4.48 установлена верхняя оценка общего числа обращений к табли­цам, которые необходимо совершить для доставки каждого пакета, и эта оценкане зависит от какого-либо конкретного алгоритма построения таблиц маршру­тизации. В качестве метода построения маршрута в дереве Т можно взять дре­весную схему маршрутизации Санторо и Хатиба, но и к самому дереву Т можнотакже применить принцип кластеризации, чтобы еще более сократить число об­ращений к таблицам.Теорема 4.49 ([ 127]).

Для любой сети, состоящей из N вершин, и длялюбого натурального числа / ^ log N существует метод построения марш­рутов, позволяющий доставлять пакеты по любому адресу, осуществляя4.6. Упражнения к главе 4167при этом не более 0 (f ■N 1^) обращений к таблицам маршрутизации и ис­пользуя 2 / + 1 цветов.Д о к а з а т е л ь с т в о . Идея доказательства подобна той, которая исполь­зовалась для доказательства теоремы 4.48, однако, вместо того, чтобы выбиратьs~y/N , метод построения схемы маршрутизации применяется рекурсивно к дере­ву Т (с тем же самым размером кластера s). Это дерево является связной сетью,в которой, по существу, имеется менее 2т вершин, поскольку на путевые вер­шины дерева Т, перекладывающие пакеты из одного канала в другой, можно необращать внимания.Эта кластеризация повторяется / раз.

Допустим, что в исходной сети G содер­жится N узлов. Тогда дерево, построенное после первой кластеризации, содержитне более N /s центров и N /s вершин-развилок, т. е. всего не более N(2/s) суще­ственных вершин. Если же дерево, построенное после г-кратной кластеризации,содержит ш; существенных вершин, то после проведения очередной (г н- 1 )-й кла­стеризации будет получено дерево, в котором содержится не более m i/s центрови mi/s вершин-развилок, т. е.

не более m;(2/s) существенных вершин. Дерево,построенное после /-кратной кластеризации, будет иметь не более mf = N(2/s)fсущественных вершин.На каждом уровне кластеризации добавляются два новых цвета, и поэтомудля проведения /-кратной кластеризации необходимо использовать 2 / + 1 цветов.На самом верхнем уровне кластеризации к таблицам приходится обращаться неболее 2т/ раз, и, кроме того, на каждом промежуточном уровне кластеризациик таблицам маршрутизации приходится обращаться s раз, чтобы локализоватьвершину-адресат.

В результате общее число обращений к таблицам становитсяравным 2mj + fs. Если выбрать s ~ 2N x^ , то получим mf = 0(1); поэтому числообращений к таблицам будет ограничено величиной / • s = 0 (f ■N {^).□Если мы будем использовать приблизительно log N цветов, то в результатеможем получить метод построения маршрутов, в котором требуется осуществ­лять 0(logiV) обращений к таблицам маршрутизации. Однако проверка окраскипакета в этом случае также становится разновидностью обращения к таблице, хо­тя для этой цели приходится использовать маленькие таблицы (размера O(logjV)в худшем случае), и доля вершин, в которых проверяется окраска, также мала.4.6. Упражнения к главе 44.6.1Упражнение 4.1. Допустим, что таблицы маршрутизации так обновляют­ся после каждого изменения топологической структуры сети, что они остаютсяациклическими по ходу обновления. Может ли это служить гарантией того, чтопакеты всегда доставляются по адресу даже в том случае, когда сеть претерпе­вает бесконечно большое количество топологических изменений?168Гл.

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

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