Два етапи побудови таблиці маршрутизації
В OSPF процес побудови таблиці маршрутизації розбивається на два крупні етапи. На першому етапі кожен маршрутизатор будує граф зв’язків мережі, в якому вершинамі графа є маршрутизатори і IP-мережі, а ребрами – інтерфейси маршрутизаторів. Всі маршрутизатори для цього обмінюються з своїми сусідами тією інформацією про графу мережі, яку вони мають в своєму розпорядженні до даного моменту часу.
Цей процес схожий на процес розповсюдження векторів відстаней до мереж в протоколі RIP, проте сама інформація якісно інша – це інформація про топологію мережі. Подібні повідомлення називаються router links advertisement – оголошення про зв’язки маршрутизатора.
Крім того, при передачі топологічній інформації маршрутизатори її не модифікують, як це роблять RIP-маршрутизатори, а передають в незмінному вигляді. В результаті розповсюдження топологічної інформації всі маршрутизатори мережі мають в своєму розпорядженні ідентичні відомості про графу мережі, які зберігаються в топологічній базі даних кожного маршрутизатора.
Другий етап полягає в знаходженні оптимальних маршрутів за допомогою отриманого графа. Кожен маршрутизатор вважає себе центром мережі і шукає оптимальний маршрут до кожної відомої йому мережі. У кожному знайденому таким чином маршруті запам’ятовується тільки один крок – до наступного маршрутизатора, відповідно до принципу однокрокової маршрутизації.
Дані про цей крок і потрапляють в таблицю маршрутизації. Завдання знаходження оптимального шляху на графі є достатньо складним і трудомістким. У протоколі OSPF для її вирішення використовується ітеративний алгоритм Дійкстри. Якщо декілька маршрутів мають однакову метрику до мережі призначення, то в таблиці маршрутизації запам’ятовуються перші кроки всіх цих маршрутів.