Дистанционно-векторные протоколы и протоколы на основе состояния каналов

Протоколы маршрутизации делятся на две категории: дистанционно-векторные и на основе состояния каналов Дистанционно-векторные протоколы фактически являются стандартом динамической маршрутизации. Они основаны на алгоритмах, разработанных в 1960-х годах для маршрутизации в сетях ARPAnet. В основе дистанционно-векторных протоколов лежит уравнение Беллмана (Bellman), а их алгоритмы часто называют алгоритмами Беллмана—Форда (Bellman-Ford).

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

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

Дистанционно-векторные протоколы имеют ряд недостатков.

• В них может произойти зацикливание маршрутов.
• Максимальное расстояние маршрута не может превышать 15 транзитных передач.
• В больших сетях эти протоколы обладают плохой расширяемостью.

Протокол на основе состояния каналов — более современный тип протоколов динамической маршрутизации. В нем используются алгоритмы на основе создания "карты" сетей и поддержания базы данных с информацией о состоянии каналов. Когда происходят какие-либо изменения, база данных обновляется.

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

Конвергенция, т.е. распространение обновленной маршрутной информации на другие маршрутизаторы в методе на основе состояния каналов выполняется быстрее и чаще, чем в дистанционно-векторном методе.

Распространенные протоколы маршрутизации

Выделенные устройства маршрутизации, такие, как маршрутизаторы Cisco, поддерживают динамические протоколы маршрутизации. В некоторых операционных системах (например, в Windows 2000) протоколы динамической маршрутизации можно использовать на компьютере, выполняющем функции маршрутизатора. Наибольшее распространение в IP получили протоколы динамической маршрутизации RIP (Routing Information Protocol) версий 1 или 2 и OSPF (Open Shortest Path First). Оба протокола подробно рассматриваются ниже.

Протокол RIP

Дистанционно-векторный RIP — один из первых протоколов динамической маршрутизации — подробно описан в документе RFC 1058. Происхождение RIP можно проследить от программы Routed, которая была частью BSD UNIX 4.3. Одно из основных достоинств RIP — его статус общепризнанного стандарта.

Маршрутизаторы RIP периодически "объявляют" свою маршрутную информацию. Другим маршрутизаторам. В протоколе RIPvl объявления передаются в широковещательных пакетах, а в RIPv2 дополнительно используется многоадресная рассылка.

Для устранения некоторых недостатков дистанционно-векторного алгоритма RIP в процедурах протокола используются следующие методы:

• расщепление горизонта;
• обратное обновление с устранением ошибки;
• триггерные обновления.

Расщепление горизонта

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

1. Маршрутизатор В получает информацию о том, что маршрутизатор С вышел из строя, и передает эту информацию маршрутизатору А.
2. Маршрутизатор А обновляет свою таблицу маршрутизации с учетом неисправности маршрутизатора С.
3. Маршрутизатор В получает информацию о том, что маршрутизатор С восстановлен. Однако, прежде чем маршрутизатор В передает обновление маршрутизатору А, последний передает маршрутизатору В собственное обновление с информацией о неработающем маршрутизаторе С.
4. Маршрутизатор В обновляет свою таблицу маршрутизации на основе неправильной информации маршрутизатора А.

В методе расщепления горизонта указанная проблема решается следующим образом. Когда маршрутизатор А передает свои обновления маршрутизатору В, он не включает в них маршруты, полученные от него же. Поскольку обновления не передаются обратно, они распространяются по маршрутизаторам не хаотично, а направленно, как круги от брошенного в воду камня.