Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 43
Текст из файла (страница 43)
Маршрутизация с использованием компактных таблиц155каждая вершина, которой после этого передается пакет, имеет пометку, не превосходящую числа lv . Тогда спустя конечное число продвижений пакет достигнетвершины v, так как согласно лемме 4.30, пока пакет не достиг вершины v, прикаждом его продвижении значение функции fv убывает.Эффективность интервальной маршрутизации: общий случай. Теорема 4.25гласит, что для каждой сети есть правильная ILS, но в этой теореме ничего неговорится об эффективности путей, которые выбираются на основе такой схемы.
Нужно ясно представлять себе, что схемы интервальной разметки в глубинуиспользуются для того, чтобы показать существование такого рода схем длякаждой сети, но это отнюдь не означает, что это наилучшие из возможных схем.Например, если применить схему интервальной разметки в глубину к кольцу, состоящему из N вершин, то найдутся две такие вершины u и v, что d(u, v) = 2,а схеме требуется пройти маршрут из N − 2 звеньев, чтобы доставить пакет извершины u в вершину v (упражнение 4.8).
Для того же кольца существует ILS,которая обеспечивает доставку каждого пакета по маршруту с наименьшим числом звеньев (теорема 4.34).Чтобы оценить качество методов маршрутизации, вначале введем следующееопределение.Определение 4.31. ILS называется оптимальной, если она продвигает всепакеты по оптимальным путям.. ILS называется добрососедской, если она доставляет пакет от любой вершины ко всякому ее соседу за один шаг. ILS называется линейной, если каждому ребру соответствует линейный интервал.Мы будем назвать ILS минимальной по числу звеньев (или минимальнойпо длине пути), если она является оптимальной относительно меры стоимости,определяемой числом звеньев пути (или соответственно длиной пути).
Легко видеть, что минимальная по числу звеньев схема является добрососедской. Такжелегко проверить, что ILS является линейной в том и только том случае, когдак каждой вершине u с пометкой lu 6= 0 примыкает ребро, помеченное 0, и к каждой вершине с пометкой 0 примыкает ребро с пометкой 0 или 1. Оказывается,для произвольных сетей рассмотренные схемы порождают, вообще говоря, неочень качественные маршруты, но для некоторых типов сетей, имеющих специальную топологическую структуру, качество маршрутов оказывается очень хорошим.
Благодаря этому рассмотренные схемы находят применение при решениизадачи маршрутизации в процессорных сетях регулярной структуры, наподобиетех, которые возникают в параллельных вычислительных системах с виртуальнойглобальной разделяемой памятью.В точности неизвестно, как для одной и той же произвольной сети соотносятся друг с другом по качеству решений наилучшая схема интервальной разметкии оптимальный алгоритм маршрутизации.
Некоторые нижние оценки длины путей, свидетельствующие о том, что оптимальные ILS существуют не всегда, былиполучены Ружичкой.Теорема 4.32 ([165]). Существует такая сеть G, что для каждойправильной ILS для сети G найдется пара таких вершин u и v, что пакет156Гл. 4. Алгоритмы маршрутизацииот вершины u к вершине v доставляется по маршруту, состоящему по3меньшей мере из DG звеньев.2Также неизвестно, как соотносятся по качеству решения для одной и той жесети наилучшая схема интервальной разметки в глубину и наилучшая из всехвозможных схем интервальной разметки.
В упражнении 4.7 приводится оченьплохая схема интервальной разметки в глубину для сети, имеющей оптимальную(согласно теореме 4.37) ILS, но, быть может, для той же самой сети есть болеекачественная схема интервальной разметки в глубину.В тех случаях, когда в сети друг с другом сообщаются преимущественно соседние вершины, добрососедство является достаточным требованием для ILS.Как видно из рис. 4.15 схема интервальной разметки в глубину не обязательноявляется добрососедской: узел 4 переправляет пакет в вершину 2 через вершину 1.Многоинтервальные схемы маршрутизации. Эффективность методов маршрутизации можно повысить, позволив ребрам иметь несколько пометок; в этомслучае мы будем говорить о многоинтервальных схемах маршрутизации.Действительно, тогда мы можем считать, что множество вершин-адресатов задается объединением нескольких интервалов; увеличивая число интервалов, можно добиться того, что даже для произвольной сети может быть получена оптимальная маршрутизация.
Чтобы убедиться в этом, рассмотрим вначале оптимальные таблицы маршрутизации, вычисленные, например, при помощи алгоритма Netchange, и заметим, что для каждого ребра соответствующее множествовершин-адресатов может быть представлено в виде объединения циклическихинтервалов. При таком элементарном подходе каждому ребру будет приписаноне более N/2 пометок и для каждой вершины будет не более N пометок. Объемпамяти, необходимый для хранения подобных интервальных таблиц, будет точнотаким же, какой необходим для хранения классических таблиц полной маршрутизации.Теперь попробуем понять, как связаны между собой сложность по объемупамяти и эффективность маршрутизации.
Вполне естественно задаться вопросомо том, сколько разных меток необходимо для получения оптимальной маршрутизации. Начало исследований в этом направлении положила работа Фламминии др. [83] , в которой был разработан метод поиска подходящих схем и доказательства нижних оценок. Из результатов этой работы видно, что в общем случаедля достижения оптимальности может потребоваться приписать Θ (N) пометоккаждой линии связи.
Но стоит только пойти на маленький компромисс, как сразу же происходит существенное сокращение размера таблиц. Работа Ружички[166] подвела итоги исследования этого компромисса.Маршрутизация при помощи схем линейных интервалов. Для того чтобыприменять интервальные методы маршрутизации, очень важно иметь возможность использовать циклические интервалы.
Хотя для некоторых сетей можнопостроить правильные и даже оптимальные схемы разметки линейными интерва-4.4. Маршрутизация с использованием компактных таблиц157лами, тем не менее не каждую сеть можно правильно разметить, ограничившисьтолько линейными интервалами. Вопрос о том, насколько широко можно применять схемы разметки линейными интервалами, был исследован в работе Беккера,ван Ливен и Тана [18] .Теорема 4.33.
Существует такая сеть, для которой нет правильнойсхемы разметки линейными интервалами.xДвум вершинам,заключенным в рамку,приписаны пометки 0 и 6Рис. 4.17. Граф с тремя отросткамиД о к а з а т е л ь с т в о. Рассмотрим граф с тремя отростками длины два(см. рис. 4.17). Наименьшая пометка (0) и наибольшая разметка (6) приписанадвум вершинам, и, коль скоро в графе есть три отростка, имеется хотя бы одинотросток, в котором нет ни наибольшей, ни наименьшей пометки.
Рассмотримпервую, считая от центра, вершину x в этом отростке. Узел x продвигает в центрпакеты, адресованные узлам с пометками 0 и 6, а единственный линейный интервал, который содержит оба числа 0 и 6, — это все множество ZN . Следовательно,узел x должен будет также продвигать в центр и те пакеты, которые адресованыдругому его соседу, и эти пакеты никогда не достигнут адресата.Беккер, ван Ливен и Тан полностью описали класс сетей, топология которыхдопускает построение линейных ILS, оптимальных по длине маршрута, а также получили ряд результатов, описывающих классы графов, топология которыхдопускает построение адаптивных линейных ILS, оптимальных по числу звеньев.Полностью охарактеризовать класс сетей, для которых имеются линейные схемы,удалось Fragniaud и Gavoille в работе [94] ; Эйлем и др.
в работе [76] показали,что длина путей, которые порождаются линейными схемами в таких сетях, можетдостигать величины O(D2).Оптимальность интервальной маршрутизации: топологии специальноговида. Оказывается, для некоторых классов сетей, имеющих регулярную структуру, можно построить оптимальные схемы интервальной разметки. Сети с такой158Гл. 4. Алгоритмы маршрутизации4.4. Маршрутизация с использованием компактных таблицструктурой возникают, например, при конструировании параллельных компьютеров.Теорема 4.34 ([128]). Для колец с N вершинами существуют минимальные по числу звеньев схемы интервальной разметки.Кол.
1Ряд 1u0uu(j − 1)nunuuРяд juuu@R@AA uAuuAuHH AHuУзел i − 1Ai + dN/2eAAuУзел iA uУзел i + dN/2eAACAuHHHuCuu Ci+1uУзел i + 1CA = Адресаты, к которым обращаютсяпротив часовой стрелки из узла iC = Адресаты, к которым обращаютсяпо часовой стрелке из узла iCРис. 4.18. Оптимальная ILS для кольцаД о к а з а т е л ь с т в о. Узлы помечаются числами от 0 до N − 1 в направлении по часовой стрелке.
В узле i каналу, примыкающему к этой вершине внаправлении по часовой стрелке, приписывается число i + 1, а каналу, примыкающему к этой вершине в направлении против часовой стрелки, приписываетсячисло (i +dN/2e) mod N (см. рис. 4.18). При такой схеме разметки узел с номеромi отправляет пакеты, предназначенные вершинам i+1, . . . , (i+dN /2e) −1, по часовой стрелке, а пакеты, предназначенные вершинам (i +dN /2e), . . . , i − 1, — противчасовой стрелки, и этот способ маршрутизации является оптимальным.Коль скоро ILS, построенная при доказательстве теоремы 4.34, является оптимальной, она также является и добрососедской; но она нелинейна.Теорема 4.35 ([128]). Для решеток размера n × n существуют минимальные по числу звеньев схемы интервальной разметки.Д о к а з а т е л ь с т в о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
