Виды динамической маршрутизации

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

(Distance Vector Algorithms, DVA) и алгоритмах состояния связей (Link State Algorithms, LSA).

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

В алгоритмах дистанционно-векторного типа каждый маршрутизатор периодически и широковещательно рассылает по сети вектор расстояний от себя до всех известных ему сетей. Под расстоянием обычно понимается число промежуточных маршрутизаторов (число так называемых «хопов», то есть прыжков, от английского hop), через которые, пакет должен пройти, прежде чем попадет в соответствующую сеть (может использоваться и другая метрика, учитывающая не только число перевалочных пунктов, но и время прохождения пакетом по связи между соседними маршрутизаторами). Получив вектор от соседнего маршрутизатора, каждый маршрутизатор добавляет к нему информацию об известных ему других сетях, о которых он узнал непосредственно (если они подключены 1 к его портам) или из аналогичных объявлений других маршрутизаторов, а затем рассылает новое значение вектора снова по сети, В конце концов, каждый маршрутизатор узнает информацию об имеющихся в интерсети сетях и о расстоянии до них через соседние маршрутизаторы.

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

Наиболее распространенным протоколом, основанным на дистанционно-векторном алгоритме, является протокол RIP, который распространен в двух версиях - RIP IP, работающий с протоколом IP, и RIP IPX, работающий с протоколом IPX.

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

Широковещательная рассылка используется здесь только при изменениях

состояния связей, что происходит в надежных сетях не так часто.

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

короткими пакетами со своими ближайшими соседями. Этот трафик также широковещательный, но он циркулирует только между соседями и не так засоряет сеть.

Протоколами, основанными на алгоритме состояния связей, являются протоколы IS-IS (Intermediate System to Intermediate System) стека OSI, OSPF (Open Shortest Path First) стека TCP/IP и NLSP стека Novell, реализованный совсем недавно.

Протокол OSPF имеет ряд особенностей, специально ориентированных на использование в больших корпоративных сетях. К ним относятся:

• Применение процедур аутентификации маршрутизаторов, исключающих внедрение в сеть «злоумышленников», отводящих трафик с помощью нелегальных маршрутизаторов.

• Использование поля качества сервиса в пакете IP для автоматической балансировки загрузки параллельных линий,

• Отказ от обязательного присваивания IP-адресов портам, работающим на выделенные линии, что упрощает работу администратора при конфигурировании маршрутизатора и экономит IP адреса.

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

• Возможность импорта таблиц маршрутизации из частей сети, называемых автономными системами, в которых работают отличные от OSPF протоколы маршрутизации. Это дает возможность оставлять в неизменном виде маршрутизаторы небольших сетей, работающие по протоколу RIP, применяя в остальной части корпоративной сети протокол OSPF.

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

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

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

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

Гибридная адаптивная маршрутизация. Основана на использовании таблиц маршрутов, рассылаемых ЦМ узлам сети, в сочетании с анализом длинны очередей в узлах. Гибридная маршрутизация компенсирует недостатки централизованной и локальной маршрутизаций воспринимает их преимущества: маршруты центра соответствуют глобальному состоянию сети, а учет текущего состояния узла обеспечивает своевременность решения задачи.