Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 33
Текст из файла (страница 33)
Алгоритм называется оптимальным, если он позволяет задействовать «наилучшие» пути.3. Сложность. Алгоритм вычисления таблиц должен использовать как можно меньше сообщений, расходовать как можно более экономно время и память.Другим аспектам сложности, учитывающим, насколько быстро может быть построен маршрут, насколько быстро пакет может быть подготовлен для пересылки,ит. п. , в этой главе будет уделяться меньше внимания.1174. Устойчивость.
В случае изменения топологии (добавления или удаленияканала или вершины) алгоритм вносит изменения в таблицы маршрутизации, длятого чтобы задачу маршрутизации можно было решить в модифицированной сети.5. Адаптивность. Для того чтобы выровнять загруженность каналов и вершин, алгоритм приспосабливает к этому таблицы, избегая прокладывать путичерез те каналы и вершины, которые чрезмерно загружены, и отдавая предпочтение тем каналам и вершинам, на которые в это время возложена наименьшаянагрузка.6. Справедливость.
Алгоритм должен обслуживать всех пользователей в равной мере.Эти требования порой вступают в конфликт друг с другом, и большинство алгоритмов имеют хорошую производительность только относительно некоторого ихподмножества.Сеть, как обычно, представляется графом, вершины которого соответствуютузлам сети, и при этом соседние вершины соединены ребром, если между ними имеется канал связи.
Оптимальность алгоритма зависит от того, какой путьв графе считается «наилучшим»; существует несколько вариантов понятия «наилучший путь», и для каждого из них имеется свой класс алгоритмов маршрутизации.1. Минимальное количество звеньев. Стоимость использования пути определяется количеством звеньев (пройденных каналов или шагов от одной вершины к другой) в этом пути. Алгоритм маршрутизации с минимальным числомзвеньев выбирает пути, имеющих наименьшее возможное число звеньев.2. Кратчайший путь. Каждому каналу связи придается неизменный (неотрицательный) вес, и стоимость пути полагается равной суммарному весу всех каналов пути. Алгоритм кратчайшего пути выбирает путь наименьшей стоимости.3.
Минимальная задержка. Каждому каналу связи придается динамическиизменяемая характеристика, зависящая от трафика через этот канал. Алгоритмминимальной задержки постоянно пересматривает таблицы так, чтобы всегда выбирались пути с (почти) минимальной общей задержкой. Так как задержка, приписанная каналам, зависит от фактического трафика, различные пакеты, переправляемые по сети, влияют друг на друга; степень этого влияния на алгоритмымаршрутизации мы обсудим в конце §4.6.1.Другие варианты понятия оптимальности пути могут оказаться полезными в специальных приложениях, но мы не будем их обсуждать здесь.Содержание главы.
В этой главе будет рассматриваться следующий материал. В §4.6.1 будет показано, что по крайней мере для задачи маршрутизациис наименьшим числом звеньев и по кратчайшему пути можно проложить оптимальные маршруты для всех пакетов, адресованных одному и тому же адресатуd, посредством остовного дерева с корнем в вершине d. Вследствие этого привыборе маршрута источник сообщения может не приниматься во внимание.В §4.6.2 описан алгоритм вычисления таблиц маршрутизации для статической сети со взвешенными каналами. Алгоритм проводит распределенное вычисление кратчайшего пути между любыми двумя парами вершин и помещает118Гл. 4.
Алгоритмы маршрутизациив память каждой вершины-источника первого соседа на пути к тому или иному узлу-адресату. Недостатком этого алгоритма является то, что все вычислениенужно проводить повторно всякий раз, когда топология сети изменяется, т. е.алгоритм неустойчив.Алгоритм Netchange, который рассматривается в §4.6.3, свободен от этогонедостатка: он адаптируем к отказам и восстановлениям, возникающим в каналах связи, путем частичного перевычисления таблиц маршрутизации.
Для тогочтобы упростить анализ алгоритма, мы рассмотрим тот его вариант, в которомстоимость пути определяется числом звеньев в этом пути. Алгоритм Netchangeможно модифицировать так, чтобы применять его и для случая взвешенных каналов, в которых возможны отказы и восстановления.В алгоритмах маршрутизации, представленных в §4.6.2 и 4.6.3, в каждойвершине используются таблицы маршрутизации в зависимости от возможныхпроцессов-адресатов. Для больших сетей, состоящих из компактных вершин,хранение этой информации может быть обременительным. В §4.6.4 будут рассмотрены некоторые стратегии маршрутизации, которые кодируют топологическую информацию в адресе вершины для сокращения объема таблиц маршрутизации и упрощения поиска в этих таблицах.
Эти «компактные» алгоритмы маршрутизации обычно не используют оптимальных путей. Мы проанализируем древесные схемы, схемы интервальной и префиксной маршрутизации.В § 4.6.5 рассматриваются иерархические методы маршрутизации. Эти методыпредусматривают разбиение сети на связанные друг с другом кластеры; маршрутизация внутри кластера и между кластерами проводится по-разному. Такойподход позволяет сократить число решений, которые нужно принять, для тогочтобы проложить маршрут или для того чтобы сократить объем памяти, необходимой для хранения таблиц маршрутизации в каждой вершине.4.1. Маршрутизация на основе узлов-адресатовВыбор маршрута для продвижения пакета обычно проводится только с учетомузла-адресата пакета (и содержимого таблиц маршрутизации) и независимо отисходного отправителя (источника) пакета. Как следует из результатов этого параграфа, при выборе маршрута можно не принимать в расчет источник и тем неменее построить оптимальный путь.
Эти результаты не зависят от того, какомукритерию оптимальности путей отдается предпочтение, при условии, что соблюдается следующее допущение. (Напомним, что путь называется простым, есликаждая вершина встречается в нем не более одного раза, и путь является циклом,если первая его вершина совпадает с последней.)1. Стоимость отправления пакета по пути Р не зависит от того, как этот путьиспользуется, и, в частности, от того, используются ли ребра пути Р для продвижения других сообщений.
В свете этого допущения стоимость использованияпути Р становится функцией, зависящей только от самого пути; в связи с этимусловимся обозначать записью С(Р) стоимость пути Р.2. При последовательном соединении двух путей образуется новый путь, стоимость которого равна сумме стоимостей двух исходных путей, т. е. для всех i =4.1. Маршрутизация на основе узлов-адресатов119= 0, . .
. , k имеет место равенствоС((ио, ui,Ир]) = С((ио, ■■■, т)) + С((щ,iik)).Таким образом, стоимость пустого пути (ио) (ведущего из вершины ио в вершинумо) удовлетворяет условию С((ио)) = 0.3. В графе отсутствуют циклы отрицательной стоимости.(Этим допущениям удовлетворяют критерии стоимости минимального числа звеньев и кратчайшего пути.) Путь из вершины и в вершину v называется оптимальным, если не существует пути меньшей стоимости из и в в. Заметим, чтооптимальный путь может быть не единственным; могут существовать различныепути, имеющие одну и ту же (минимальную) стоимость.Лемма 4.1.
Пусть и и v — вершины из множества V. Если в графе Gесть путь Р из и в v, то имеется также и простой путь из и в и, которыйявляется при этом оптимальным.Д о к а з а т е л ь с т в о . Так как существует конечное число простых путей,существует простой путь So наименьшей стоимости из вершины и в вершину у;здесь мы имеем в виду, что для каждого простого пути Р' из и в v выполняется неравенство С (So) $5 С(Р'). Остается показать, что С(So) является нижнейгранью стоимостей всех (не обязательно простых) путей.Пусть V = {щ, . . . , Wjv}. Последовательно удаляя из пути Р циклы, содержащие вершины oi, 0 2 , и т.
д., можно прийти к заключению о том, что для каждого пути Р из и в о существует простой путь Р ', для которого выполняетсянеравенство С(Р') < С(Р). Пусть Ро = Р. Построим для каждого / = 1, . . . . Nпуть Pt следующим образом. Если вершина о, встречается в пути Pt-\ не более одного раза, то положим Р, = P;_i. В противном случае рассмотрим путьPi- 1 = («о, • • •, «*), и пусть up — это первое вхождение, а м/2 — это последнеевхождение вершины цг в последовательность Pi-\.
Тогда положимPi(«0, ** • , фд (^/ 2 ), ^/2+1, * • • , Uk) ■Согласно построению последовательность вершин Р, является путем из и в о,и при этом каждая из вершин {щ, . . . , оД встречается в ней не более чем одинраз. Следовательно, Рдг — это простой путь из вершины и в вершину о. Путь P,_iсостоит из пути Р,- и цикла Q иИ, . .. , иу., и поэтому C(P,_i) = С(Pi) + C(Q).Так как циклы отрицательного веса отсутствуют, отсюда следует, что С(Р,) < C(P;_i).Поэтому верно неравенство С(Рдг) ^ С(Р).Принимая во внимание особенность выбора пути So, заключаем, что С(So) ^ С(Рд/);отсюда следует неравенство C(So) С С(Р).□Если в графе G есть циклы отрицательного веса, то оптимального пути может и не найтись; стоимость каждого пути можно улучшить, стоит только пройтилишний раз по циклу отрицательной стоимости.
В приведенной ниже теореме'^Точнее говоря, путьобразован в результате последовательного соединения трех путей — путиР[-\ = Фо, • • •, Чу), никла Q = ( Ujl , . . . , Uj2) и пути Р " , = {up, . . . , иф. При этом соединениепутей Р ' _ , и Р ”_ , как раз и образует путь— Прим, перев.120Гл. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
