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

Одна из главных проблем распределенной реализации алгоритма Беллмана-Фор- да для маршрутизаторов (протокол, описанный выше) заключается в том, что она строится на базе исходного алгоритма динамического программирования, пред- полагающего, что стоимости ребер остаются неизменными на протяжении работы алгоритма.

До настоящего момента мы разрабатывали алгоритмы, подразумевая, что программа выполняется на одном компьютере (или группе компьютеров под

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

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

Теперь предположим, что ребро (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_v + M[v] = 4; при этом он считает, что будет использовать свое ребро стоимостью 1 к v, с последующим предполагаемым путем стоимостью 3 из v к t. Узлы s и v будут попеременно обновлять свое расстояние до t, пока один из них не найдет альтернативный маршрут; если сеть действительно теряет связность, как в нашем случае, эти обновления будут продолжаться беско- нечно долго (так называемая проблема отсчета до бесконечности).

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

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

6.10.

<< | >>

↑

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

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

- Windows - Архитектура компьютера - Интернет - Информатика - Компьютер - Компьютерные и телекоммуникационные системы - Программирование - Социальные сети -

- Английский язык - Астрология - Военная литература - Журналистика - Компьютерная инженерия - Педагогика - Право - Психология - Социология -