Кратчайшие пути и дистанционно- векторные протоколы

В частности, задача нахождения кратчайшего пути имеет практическое применение в сетях передачи данных для определения самого эффективного пути к конечной точке. Сеть представляется графом, узлы которого соответствуют маршрутизато- рам; между v и w существует ребро, если два маршрутизатора соединены прямым каналом связи.
Стоимость cw определяет задержку в канале (v, w); задача нахожде- ния кратчайшего пути со стоимостями определяет путь с наименьшей задержкой от начального узла s к конечному узлу t. Естественно, величины задержек неот- рицательные, поэтому для вычисления кратчайшего пути можно воспользоваться алгоритмом Дейкстры. Однако для вычисления кратчайшего пути по Дейкстре необходимо иметь глобальную информацию о сети: алгоритм должен хранить множество S узлов, для которых кратчайшие пути были определены, и принимать глобальное решение о том, какой узел добавить в S следующим. Хотя на маршру- тизаторах может в фоновом режиме работать протокол, который собирает глобаль- ную информацию для реализации такого алгоритма, решения, ограничивающиеся локальной информацией о соседних узлах, часто оказываются более простыми и гибкими.

Если задуматься, алгоритм Беллмана-Форда, рассмотренный в предыдущем разделе, обладает как раз таким свойством «локальности». Предположим, в каждом узле v будет храниться его значениеM[v]; чтобы обновить это значение, v достаточ- но получить значение M[w] от каждого соседа w и вычислить

miп (cvw + M\w])

на основании полученной информации.

А теперь рассмотрим усовершенствование алгоритма Беллмана-Форда, кото- рое делает его более подходящим для применения в маршрутизаторах, а заодно и ускоряет его работу в практических условиях. Текущая реализация алгоритма Беллмана-Форда может рассматриваться как алгоритм извлечения (pull-based). При каждой итерации i каждый узел v должен связаться с каждым соседом w и «из- влечь» из него новое значение M[w]. Если значение узла w не изменилось, то v не нужно получать его заново; тем не менее узел v знать об этом не может, и поэтому он все равно должен извлечь информацию.

Эта неэффективность наводит на мысль о симметричной реализации, осно- ванной на продвижении, в которой значения передаются только при изменении. А именно, каждый узел w, значение расстояния которого M[w] изменяется при ите- рации, оповещает всех своих соседей о новом значении при следующей итерации; это позволяет соседям обновить свою информацию. Если значение M[w] не изме- нилось, то текущее значение уже известно соседям w и «продвигать» его заново не нужно. Такая схема экономит время выполнения, так как не все значения должны продвигаться при каждой итерации. Также алгоритм может быть завершен пре- ждевременно, если во время итерации ни одно значение не изменилось.

Ниже при- водится полное описание реализации, основанной на продвижении информации.

Push-Based-Shortest-Path(G, s, t) n = количество узлов в G Массив M[V]

Инициализировать M[t] = 0 и M[v] = ∞ для всех остальных v е V

For i = 1............. n - 1

For w e v в произвольном порядке

Если значение M[w] обновлялось при предыдущей итерации Для всех узлов (v, w) в произвольном порядке M[v] = miп(M [v], cw + M[w] )

Если при этом изменяется значение M[v], присвоить first[v] = w Конец цикла Конец For

Если ни одно значение не изменилось в этой итерации, завершить алгоритм Конец For Вернуть M[s]

В этом алгоритме рассылка информации об изменении расстояний соседей осуществляется по раундам, а каждый узел отправляет обновление при каждой итерации, в которой он изменился. Однако если узлы соответствуют маршрутиза- торам в сети, вряд ли следует ожидать, что все будет работать в идеальном порядке; некоторые маршрутизаторы могут сообщать об обновлениях намного быстрее других, а на каких-то маршрутизаторах могут возникнуть задержки. Следова- тельно, маршрутизаторы в конечном итоге будут выполнять асинхронную версию алгоритма: каждый раз, когда на узле w обновляется значениеM[w], узел «акти- визируется» и оповещает своих соседей о новом значении. Если понаблюдать за поведением всех связанных маршрутизаторов, это будет выглядеть примерно так:

Asynchronous-Shortest-Path (G, s, t) n = количество узлов в G Массив M[V]

Инициализировать M[t] = 0 и M[v] = ∞ для всех остальных v е V Объявить t активным узлом, а все остальные узлы - неактивными Пока существует активный узел Выбрать активный узел w

Для всех ребер (v,w) в произвольном порядке M [v] = min(M [v],cw+M [w])

Если при этом изменяется значение M[v], присвоить first[v] = w Узел v становится активным Конец цикла Конец For

Узел w становится неактивным Конец Пока

Можно показать, что даже эта версия алгоритма, практически не координиру- ющая порядок обновлений, придет к правильным значениям расстояний кратчай- шего пути до t при условии, что при каждой активизации узел в конечном итоге сможет связаться со своими соседями.

Разработанный алгоритм использует одну конечную точку t, а все узлы v V

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Кратчайшие пути и дистанционно- векторные протоколы:

  1. 5. Дистанционный способ продажи товаров
  2. Глава 4. Киотский протокол в Украине
  3. § 6. Протокол судебного заседания
  4. Судебные протоколы вообще
  5. Пример обработки протокола.
  6. Базовый протокол устранения проблемы с BSFF
  7. В. Г. Олифер, Н. А. Олифер. 54 Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 3-е изд, 2006
  8. Пути оттока
  9. Будьте верны своему пути
  10. Первая глава НА ПУТИ К ЧЕТВЕРТОМУ ИЗМЕРЕНИЮ
  11. Защита в пути
  12. По пути самосовершенствования
  13. По пути самосовершенствования
  14. Четыре пути к самоуважению
  15. Часть первая. Первые шаги на пути к успеху
  16. НА ПУТИ К ЗРЕЛОМУ СОЕДИНЕНИЮ