Список ключевых слов: протокол OSPF, объявления о состоянии связей сети, область сети, граф связей сети, база данных топологии сети, алгоритм Дийкстры, сообщения HELLO, алгоритм состояния связей, синхронизация топологических БД, метрика, биты TOS.
Протокол OSPF (Open Shortest Path First — выбор кратчайшего пути первым) являете я достаточно современной реализацией алгоритма состояния связей (он принят в 1991 году) и обладает многими особенностями, ориентированными на применение в больших гетерогенных сетях.
Два этапа построения таблицы маршрутизации
Как и все протоколы маршрутизации, основанные на алгоритме состояния связей, OSPF разбивает процесс построения таблицы маршрутизации на два этапа.
На первом этапе каждый маршрутизатор строит граф связей сети, в котором вершинами графа являются маршрутизаторы и IP-сети, а ребрами — интерфейсы маршрутизаторов. Все маршрутизаторы для этого обмениваются со своими соседями той информацией о графе сети, которой они располагают к данному моменту. Этот процесс похож на процесс распространения векторов расстояний до сетей в протоколе RIP, однако сама информация качественно иная — это информация о топологии сети. Сообщения, с помощью которых распространяется топологическая информация, называются объявлениями о состоянии связей сети (Link State Advertisements, LSA). Кроме того, при передаче топологической информации OSPF маршрутизаторы ее не модифицируют, как это делают RIP- маршрутизаторы, а передают в неизменном виде. В результате все маршрутизаторы сети располагают идентичными сведениями о графе сети, которые хранятся в базе данных о топологии сети.
|
|
Второй этап состоит й нахождении оптимальных маршрутов с помощью полученного графа. Задача нахождения оптимального пути на графе является достаточно сложной и трудоемкой. В протоколе OSPF для ее решения используется итеративный алгоритм Дийкстры. Каждый маршрутизатор считает себя центром сети и ищет оптимальный маршрут до каждой известной ему сети. В каждом найденном таким образом маршруте запоминается только один шаг — до следующего маршрутизатора, в соответствии с принципом одношаговой маршрутизации. Данные об этом шаге и попадают в таблицу маршрутизации. Если несколько маршрутов имеют одинаковую метрику до сети назначения, то в таблице маршрутизации запоминаются первые шаги всех этих маршрутов.