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

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

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

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

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

6.10.

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

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

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