Динамическая маршрутизация
В случае объединения сетей со сложной топологией, когда существует несколько вариантов маршрутов от одного узла к другому и (или) когда состояние сетей (топология, качество каналов связи) изменяется с течением времени, таблицы маршрутов составляются динамически с помощью различных протоколов маршрутизации. Подчеркнем, что протоколы маршрутизации не осуществляют собственно маршрутизацию дейтаграмм- она в любом случае производится модулем IP согласно записям в таблице маршрутов, как обсуждалось выше. Протоколы маршрутизации на основании тех или иных алгоритмов динамически редактируют таблицу маршрутов, то есть вносят и удаляют записи, при этом часть записей может по-прежнему статически вноситься администратором.
В зависимости от алгоритма работы различают дистанционно-векторные протоколы (distance vector protocols) и протоколы состояния связей (link state protocols).
По области применения существует разделение на протоколы внешней (exterior) и внутренней (interior) маршрутизации.
Дистанционно-векторные протоколы реализуют алгоритм Беллмана-Форда (Bellman-Ford). Общая схема их работы такова: каждый маршрутизатор периодически широковещательно рассылает информацию о расстоянии от себя до всех известных ему сетей (“вектор расстояний”). В начальный момент времени, разумеется, рассылается информация только о тех сетях, к которым маршрутизатор подключен непосредственно.
Также каждый маршрутизатор, получив от кого-либо вектор расстояний, в соответствии с полученной информацией корректирует уже имеющиеся у него данные о достижимости сетей или добавляет новые, указывая маршрутизатор, от которого получен вектор, в качестве следующего маршрутизатора на пути в данные сети. Через некоторое время алгоритм сходится и все маршрутизаторы имеют информацию о маршрутах до всех сетей.
Дистанционно-векторные протоколы хорошо работают только в небольших сетях. Подробнее алгоритм их работы будет рассмотрен в . Развитие технологии векторов расстояний - “векторы путей”, применяющиеся в протоколе BGP.
При работе протоколов состояния связей каждый маршрутизатор контролирует состояние своих связей с соседями и при изменении состояния (например, при обрыве связи) рассылает широковещательное сообщение, после получения которого все остальные маршрутизаторы корректируют свои базы данных и пересчитывают маршруты. В отличие от дистанционно-векторных протоколов протоколы состояния связей создают на каждом маршрутизаторе базу данных, описывающую полный граф сети и позволяющую локально и, следовательно, быстро производить расчет маршрутов.
Распространенный протокол такого типа, OSPF, базируется на алгоритме SPF (Shortest Path First) поиска кратчайшего пути в графе, предложенном Дейкстрой (E.W.Dijkstra).
Протоколы состояния связей существенно сложнее дистанционно-векторных, но обеспечивают более быстрое, оптимальное и корректное вычисление маршрутов. Подробнее протоколы состояния связей будут рассмотрены на примере протокола OSPF в .
Протоколы внутренней маршрутизации (например, RIP, OSPF; собирательное название IGP - Interior Gateway Protocols) применяются на маршрутизаторах, действующих внутри автономных систем. Автономная система - это наиболее крупное деление Интернет, представляющее из себя объединение сетей с одинаковой маршрутизационной политикой и общей администрацией, например, совокупность сетей компании Глобал Один и ее клиентов в России.
Область действия того или иного протокола внутренней маршрутизации может охватывать не всю автономную систему, а только некоторое объединение сетей, являющееся частью автономной системы. Такое объединение мы будем называть системой сетей, или просто системой, иногда с указанием протокола маршрутизации, действующего в этой системе, например: RIP-система, OSPF-система.
Маршрутизация между автономными системами осуществляется пограничными (border) маршрутизаторами, таблицы маршрутов которых составляются с помощью протоколов внешней маршрутизации (собирательное название EGP - Exterior Gateway Protocols). Особенность протоколов внешней маршрутизации состоит в том, что при расчете маршрутов они должны учитывать не только топологию графа сети, но и политические ограничения, вводимые администрацией автономных систем на маршрутизацию через свои сети трафика других автономных систем. В настоящее время наиболее распространенным протоколом внешней маршрутизации является BGP.