Очевидно, OSPF обеспечивает высокую гибкость в плане разграничения автономной системы. Для чего же нужна такая гибкость? Одной из проблем протоколов, анализирующих состояние каналов, является большой объем данных, накапливаемых в базе данных состояний каналов, и объем времени, необходимый для вычисления маршрутов на основе этих данных. Сейчас станет ясно, почему возникает такая проблема.
Каждый OSPF-маршрутизатор выполняет построение ориентированного графа всей сети при помощи алгоритма Дейкстры, служащего для обнаружения кратчайшего пути (Shortest Path First, SPF). Ориентированный граф - это карта сети с точки зрения маршрутизатора. То есть корнем графа является маршрутизатор. Построение графа выполняется на основе данных из базы данных состояния каналов, содержащей информацию о каждом маршрутизаторе сети и обо всех соседях каждого маршрутизатора. Эта база данных для автономной системы, представленной на рис. 7.2, содержит пять маршрутизаторов и десять соседей: у ога один сосед, horseshoe; у horseshoe дв а соседа , ога и crab; у crab тр и соседа - horseshoe, aulds и smith-, у aulds - два соседа, crab и smith; у smith - два соседа, aulds и crab. Граф этой автономной системы в представлении маршрутизатора ога отражен на рис. 7.3.
Алгоритм Дейкстры создает карту следующим образом:
- Локальная система устанавливается в качестве корня карты и получает нулевую стоимость.
- В карту добавляются соседи только что установленной системы. Стоимость сообщения с соседями представлена суммой стоимости сообщения с только что установленной системой и стоимостью, которую эта система афиширует для каждого из соседей. Например, предположим, что crab афиширует стоимость 20 для aulds, а стоимость сообщения с crab - 15. Тогда стоимость aulds на карте ога - 35.
- Выполняется обход карты с выбором самых дешевых маршрутов для всех направлений. Например, когда в карту добавляется aulds, среди его соседей находится smith. Путь к узлу smith через aulds временно добавляется в карту. На третьем шаге алгоритма стоимость сообщения с узлом smith через crab сравнивается со стоимостью сообщения с узлом smith через aulds. Выбор делается в пользу более дешевого пути. На рис. 7.3 отброшенные маршруты представлены пунктирными линиями. Шаги 2 и 3 алгоритма повторяются для каждой системы из базы данных.
