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

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

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

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

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

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

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

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

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

Недостатки дистанционно-векторного протокола

Одна из главных проблем распределенной реализации алгоритма Беллмана-Форда для маршрутизаторов (протокол, описанный выше) заключается в том, что она строится на базе исходного алгоритма динамического программирования, предполагающего, что стоимости ребер остаются неизменными на протяжении работы алгоритма. До настоящего момента мы разрабатывали алгоритмы, подразумевая, что программа выполняется на одном компьютере (или группе компьютеров под централизованным управлением) и обрабатывает конкретные входные данные. В таком контексте предположение о том, что входные данные не будут изменяться во время выполнения программы, выглядит вполне оправданно. Но стоит перейти к условиям сети с маршрутизаторами, как такое предположение начинает создавать проблемы. Стоимости ребер могут изменяться по самым разным причинам: отдельные каналы могут быть перегружены, передача данных по ним замедляется, а технический сбой в канале (v, w) может повысить стоимость c_vw до ∞.

Следующий пример показывает, какие проблемы могут возникнуть с алгоритмом кратчайшего пути в таких ситуациях. При удалении ребра (v, w) (допустим, канал связи вышел из строя) для узла v будет естественно реагировать следующим образом: узел проверяет, входит ли ребро (v, w) в кратчайший путь к некоторому узлу t, и если входит, — увеличивает расстояние с использованием других соседей. Следует учесть, что это увеличение расстояния от v может вызвать увеличения расстояний у соседей v, если те использовали путь, проходящий через v; в сети начинают распространяться каскадные изменения. Рассмотрим очень простой пример на рис. 6.24: исходный граф состоит из трех ребер (s, v), (v, s) и (v, t), каждое из которых имеет стоимость 1.

Рис. 6.24. При удалении ребра (v, t) распределенный алгоритм Беллмана-Форда начинает “отсчет до бесконечности”

Теперь предположим, что ребро (v, t) на рис. 6.24 удаляется. Как отреагирует узел v? К сожалению, у узла нет глобальной карты сети; он знает только расстояния кратчайших путей каждого из его соседей к t. Следовательно, он не знает, что с удалением (v, t) были потеряны все пути от s к t. Он видит, что M[s] = 2, и обновляет M[v] = c_vs + M[s] = 3, считая, что он будет использовать свое ребро стоимостью 1 к s, с последующим предполагаемым путем стоимостью 2 из s в t. Узнав об этом изменении, узел s обновляет M[s] = c_sv + M[v] = 4; при этом он считает, что будет использовать свое ребро стоимостью 1 к v, с последующим предполагаемым путем стоимостью 3 из v к t. Узлы s и v будут попеременно обновлять свое расстояние до t, пока один из них не найдет альтернативный маршрут; если сеть действительно теряет связность, как в нашем случае, эти обновления будут продолжаться бесконечно долго (так называемая проблема отсчета до бесконечности).

Чтобы избежать возникновения этой проблемы и других сложностей, которые возникают из-за ограниченного объема информации, доступной узлам в алгоритме Беллмана-Форда, проектировщики схем сетевой маршрутизации предпочитают вместо дистанционно-векторных протоколов применять более выразительные протоколы векторов путей, в которых каждый узел хранит не только расстояние и первый переход на пути к цели, но и некоторое представление всего пути. При наличии информации о путях узлам не нужно обновлять свои пути для использования заведомо удаленных ребер; в то же время для хранения полных путей требуется существенно больше памяти. В истории Интернета некогда произошел переход с дистанционно-векторных протоколов на протоколы векторов путей; в настоящее время метод векторов путей задействован в протоколе BGP (Border Gateway Protocol), лежащем в основе маршрутизации в Интернете.