Open Shortest Path First

OSPF(англ. Open Shortest Path First) — протокол динамічної маршрутизації, заснований на технології відстеження стану каналу (link-state technology), що використовує для знаходження найкоротшого шляху Алгоритм Дейкстри (Dijkstra's algorithm).

Протокол OSPF був розроблений IETF в 1988 році. Остання версія протоколу представлена в RFC 2328. Протокол OSPF являє собою протокол внутрішнього шлюзу (Interior Gateway Protocol — IGP). Протокол OSPF поширює інформацію про доступні маршрути між маршрутизаторами однієї автономної системи.

Властивості OSPF

• Висока швидкість збіжності
• Підтримка мережних масок змінної довжини VLSM
• Відсутність обмежень досяжності
• Оптимальне використання пропускної здатності мережі
• Оптимальний вибір шляху маршрутизації

Згідно з RFC 2328 є не запатентований тобто відкритий для громадськості протокол, таким же, як є протокол RIP. Але OSPF на відміну від RIP, має значно більшу швидкість збіжності (рекалькуляції таблиці маршрутизації), немає обмеження на довжину шляху 15-ма хопами (англ. hop, укр. стрибок), враховує пропускну здатність мережі при виборі маршруту. Все це робить OSPF потужним, масштабованим протоколом маршрутизації.

Термінологія протоколу OSPF

• Інтерфейс (interface) — з'єднання маршрутизатора і однієї з підключених до нього мереж. При обговоренні OSPF терміни інтерфейс і канал (link) часто вживаються як синоніми.
• Оголошення про стан каналу (link-state advertisement, LSA) — оголошення описує всі канали маршрутизатора, всі інтерфейси і стан каналів.
• Стан каналу (link state) — стан каналу між двома маршрутизаторами; оновлення відбуваються за допомогою пакетів LSA.
• Метрика (metric) — умовний показник «вартості» пересилки даних по каналу;
• Автономна система (autonomous system) — група маршрутизаторів обмінюються маршрутною інформацією через загальний протокол маршрутизації.
• Зона (area) — сукупність мереж і маршрутизаторів, які мають один і той же ідентифікатор зони.
• Сусіди (neighbours) — два маршрутизатора, що мають інтерфейси в загальній мережі.
• Стан суміжності (adjacency) — взаємозв'язок між певними сусідніми маршрутизаторами встановлений з метою обміну інформацією маршрутизації.

• Hello-протокол (hello protocol) — використовується для підтримки сусідських відносин.
• База даних сусідів (neighbours database) — список всіх сусідів.
• База даних стану каналів (link state database, LSDB) — список усіх записів про стан каналів. Зустрічається також термін топологічна база даних (topological database), вживається як синонім бази даних стану каналів.

• Ідентифікатор маршрутизатора (router ID, RID) — унікальне 32-бітове число, яке унікально ідентифікує маршрутизатор в межах однієї автономної системи.

Опис роботи протоколу

1. Маршрутизатори обмінюються hello-пакетами через всі інтерфейси, на яких активований OSPF. Маршрутизатори, що розділяють загальний канал передачі даних, стають сусідами, коли вони приходять до домовленості при певних параметрах, зазначених в їх hello-пакетах.
2. На наступному етапі роботи протоколу маршрутизатори будуть намагатися перейти в стан суміжності зі своїми сусідами. Перехід у стан суміжності визначається типом маршрутизаторів, які обмінюються hello-пакетами, і типом мережі, по якій передаються hello-пакети. OSPF визначає кілька типів мереж і кілька типів маршрутизаторів. Пара маршрутизаторів, що знаходяться в стані суміжності, синхронізує між собою базу даних стану каналів.
3. Кожен маршрутизатор посилає оголошення про стан каналу маршрутизаторам, з якими він знаходиться в стані суміжності.
4. Кожен маршрутизатор, який отримав оголошення від суміжного маршрутизатора, записує передану в ньому інформацію в базу даних стану каналів маршрутизатора і розсилає копію оголошення всім іншим суміжним з ним маршрутизаторам.
5. Розсилаючи оголошення всередині однієї OSPF-зони, всі маршрутизатори будують ідентичну базу даних стану каналів маршрутизатора.
6. Коли база даних побудована, кожен маршрутизатор використовує алгоритм «найкоротший шлях першим» для обчислення графа без петель, який буде описувати найкоротший шлях до кожного відомого пункту призначення із собою як кореня. Цей граф — дерево найкоротших шляхів.
7. Кожен маршрутизатор будує таблицю маршрутизації зі свого дерева найкоротших шляхів.

Типи мереж, підтримувані протоколом OSPF

• Широкомовні мережі з множинним доступом (Ethernet, Token Ring)
• Точка-точка (T1, E1, комутований доступ)
• Неширокотрансляційні мережі з множинним доступом (NBMA) (Frame relay)

Виділений маршрутизатор (DR) і резервний виділений маршрутизатор (BDR)

У мережах з множинним доступом відносини сусідства встановлюються між всіма маршрутизаторами. Якби всі маршрутизатори в стані сусідства обмінювалися топологічною інформацією, це призвело б до розсилання великої кількість копій LSA. Якщо, приміром, кількість маршрутизаторів в мережі з множинним доступом рівне n, то буде встановлено n(n-1)/2 стосунків сусідства. Кожен маршрутизатор буде розсилати n-1 LSA своїм сусідам, плюс одне LSA для мережі, в результаті мережа згенерує n² LSA. Для запобігання проблеми розсилки копій LSA в мережах з множинним доступом вибираються виділений маршрутизатор (DR) і запасний виділений маршрутизатор (BDR).

Виділений маршрутизатор (designated router, DR) — управляє процесом розсилки LSA в мережі. Кожен маршрутизатор мережі встановлює відносини суміжності з DR. Інформація про зміни в мережі відправляється DR маршрутизатором, які виявили ці зміна, а DR відповідає за те, щоб ця інформація була відправлена іншим маршрутизаторам мережі. Недоліком в схемі роботи з DR маршрутизатором є те, що при виході його з ладу повинен бути вибраний новий DR. Нові відносини сусідства повинні бути сформовані і, поки бази даних маршрутизаторів не синхронізуються з базою даних нового DR, мережа буде недоступна для пересилки пакетів. Для усунення цього недоліку вибирається BDR.

Резервний виділений маршрутизатор (backup designated router, BDR). Кожен маршрутизатор мережі встановлює відносини сусідства не тільки з DR, але і BDR. DR і BDR також встановлюють відносини сусідства і між собою. При виході з ладу DR, BDR стає DR і виконує всі його функції. Так як маршрутизатори мережі встановили відносини сусідства з BDR, час недоступності мережі мінімізується. Маршрутизатор, обраний DR або BDR в одній приєднаній до нього мережі з множинним доступом, може не бути DR (BDR) в інший приєднаній мережі. Роль DR (BDR) є властивістю інтерфейсу, а не властивістю всього маршрутизатора.

Таймери протоколу

• HelloInterval — Інтервал часу в секундах після закінчення якого маршрутизатор відправляє наступний hello-пакет з інтерфейсу. Для широкомовних мереж і мереж точка-точка значення за замовчуванням, як правило, 10 секунд. Для неширокотрансляційних мереж з множинним доступом значення за замовчуванням 30 секунд.
• RouterDeadInterval — Інтервал часу в секундах після закінчення якого сусід буде вважатися «мертвим». Цей інтервал повинен бути кратним значенню HelloInterval. Як правило, RouterDeadInterval дорівнює 4 інтервалам відправки hello-пакетів, тобто 40 секунд.
• Wait Timer — Інтервал часу в секундах після закінчення якого маршрутизатор обере DR в мережі. Його значення дорівнює значенню інтервалу RouterDeadInterval.
• RxmtInterval — Інтервал часу в секундах після закінчення якого маршрутизатор повторно відправить пакет на який не отримав підтвердження про отримання (наприклад, Database Description пакет або Link State Request пакети). Цей інтервал називається також Retransmit interval. Значення інтервалу 5 секунд.

Типи маршрутизаторів, які утворюють мережу OSPF

Внутрішній маршрутизатор (internal router) — маршрутизатор, всі інтерфейси якого належать одній зоні. У таких маршрутизаторів тільки одна база даних стану каналів.

Прикордонний маршрутизатор (area border router, ABR) — з'єднує одну або більше зон з магістральною зоною і виконує функції шлюзу для Міжзонального трафіку. У прикордонного маршрутизатора завжди хоча б один інтерфейс належить магістральної зоні. Для кожної приєднаної зони маршрутизатор підтримує окрему базу даних стану каналів.

Магістральний маршрутизатор (backbone router) — маршрутизатор у якого завжди хоча б один інтерфейс належить магістральної зоні. Визначення схоже на прикордонний маршрутизатор, проте магістральний маршрутизатор не завжди є прикордонним. Внутрішній маршрутизатор, інтерфейси якого належать нульовий зоні, також є магістральним.

Прикордонний маршрутизатор автономної системи (AS boundary router, ASBR) — обмінюється інформацією з маршрутизаторами, які належать іншим автономним системам. Прикордонний маршрутизатор автономної системи може знаходитися в будь-якому місці автономної системи і бути внутрішнім, прикордонним чи магістральним маршрутизатором.

Типи зон

При поділі автономної системи на зони, маршрутизаторам приналежним до однієї зони не відома інформація про детальну топології інших зон.

Поділ на зони дозволяє:

• Знизити навантаження на ЦП маршрутизаторів за рахунок зменшення кількості перерахунків за алгоритмом OSPF
• Зменшити розмір таблиць маршрутизації
• Зменшити кількість пакетів оновлень стану каналу

Кожній зоні присвоюється ідентифікатор зони (area ID). Ідентифікатор може бути зазначений в десятковому форматі або у форматі запису IP-адреси. Однак ідентифікатори зон не є IP-адресами і можуть збігатися з будь-яким призначеним IP-адресою.

Існує кілька типів зон:

Магістральна зона (backbone area)

Магістральна зона (відома також як нульова зона або зона 0.0.0.0) формує ядро мережі OSPF. Всі інші зони з'єднані з нею, і Міжзональний маршрутизація відбувається через маршрутизатор з'єднаний з магістральної зоною. Магістральна зона відповідальна за поширення, маршрутизує інформації між немагістральнимі зонами. Магістральна зона повинна бути суміжною з іншими зонами, але вона не обов'язково повинна бути фізично суміжною; з'єднання з магістральною зоною може бути встановлено і за допомогою віртуальних каналів.

Стандартна зона (standard area)

Звичайна зона, яка створюється за замовчуванням. Ця зона приймає оновлення каналів, сумарні маршрути і зовнішні маршрути.

Тупикова зона (stub area)

Тупикова зона не приймає інформацію про зовнішні маршрути для автономної системи, але приймає маршрути з інших зон. Якщо маршрутизаторам з тупикової зони необхідно передавати інформацію за кордон автономної системи, то вони використовують маршрут за замовчуванням. У тупиковій зоні не може знаходитися ASBR. Виняток з цього правила — ABR може бути і ASBR.

Totally stubby area

Totally stubby area не приймає інформацію про зовнішні маршрути для автономної системи і маршрути з інших зон. Якщо маршрутизаторам необхідно передавати інформацію за межі зони, то вони використовують маршрут за замовчуванням.

Not-so-stubby area (NSSA)

Зона NSSA визначає додатковий тип LSA — LSA type 7. У NSSA зоні може знаходитися ASBR.

Див. також

• IS-IS (Intermediate system to intermediate system)
• Shortest Path Bridging (SPB) — (IEEE 802.1aq)

Посилання

• OSPF Basics [ 15 грудня 2009 у Wayback Machine.]
• Design and Implementation of OpenOSPFD (Paper) [ 2 червня 2006 у Wayback Machine.]
• Design and Implementation of OpenOSPFD (Presentation) [ 7 липня 2011 у Wayback Machine.]
• Cisco OSPF [ 4 лютого 2014 у Wayback Machine.]
• Cisco OSPF Areas and Virtual Links [ 23 липня 2010 у Wayback Machine.]
• Summary of OSPF v2 [ 11 січня 2010 у Wayback Machine.]
• (Vishwas Manral, Manav bhatia and Yasuhiro Ohara)