OSPF

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

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

OSPF пропонує рішення наступних завдань:

• Збільшення швидкості збіжності (у порівнянні з протоколом RIP2, тому що немає необхідності вичікування багаторазових тайм-аутів по 30с).
• Підтримка мережних масок змінної довжини (VLSM).
• Досяжність мережі (швидко виявляються відмовили маршрутизатори, і топологія мережі змінюється відповідним чином).
• Оптимальне використання пропускної здатності (так як будується мінімальний остовних граф за алгоритмом Дейкстри).
• Метод вибору шляху.

Термінологія протоколу 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-бітове число, яке унікально ідентифікує маршрутизатор у межах однієї автономної системи.

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

• Маршрутизатори обмінюються hello-пакетами через всі інтерфейси, на яких активований OSPF. Маршрутизатори, розділяють загальний канал передачі даних, стають сусідами, коли вони приходять до домовленості про певні параметри, зазначених у їх hello-пакетах.
• На наступному етапі роботи протоколу маршрутизатори будуть намагатися перейти в стан суміжності з маршрутизаторами, які перебувають з ним у межах прямого зв'язку (на відстані одного хопу). Перехід у стан суміжності визначається типом маршрутизаторів, які обмінюються hello-пакетами, і типом мережі, по якій передаються hello-пакети. OSPF визначає кілька типів мереж і кілька типів маршрутизаторів. Пара маршрутизаторів, які перебувають у стані суміжності, синхронізує між собою базу даних стану каналів.
• Кожен маршрутизатор посилає оголошення про стан каналу маршрутизаторам, з якими він знаходиться в стані суміжності.
• Кожен маршрутизатор, який отримав оголошення від суміжного маршрутизатора, записує передану в ньому інформацію в базу даних стану каналів маршрутизатора і розсилає копію оголошення всім іншим суміжних з ним маршрутизаторам.
• Розсилаючи оголошення через зону, всі маршрутизатори будують ідентичну базу даних стану каналів маршрутизатора.
• Коли база даних побудована, кожен маршрутизатор використовує алгоритм «найкоротший шлях першим» для обчислення графа без петель, який буде описувати найкоротший шлях до кожного відомому пункту призначення з собою в якості кореня. Цей граф - дерево найкоротших шляхів.
• Кожен маршрутизатор будує таблицю маршрутизації зі свого дерева найкоротших шляхів.

Типи мереж, що підтримуються OSPF

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

Designated router (DR) і backup designated router (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 секунд.

Типи маршрутизаторів

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

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

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

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

Типи оголошень про стан каналу (LSA)

Type 1 LSA - Router LSA - оголошення про стан каналів маршрутизатора. Ці LSA поширюються всіма маршрутизаторами. У LSA міститься опис всіх каналів маршрутизатора і вартість (cost) кожного каналу. Розповсюджуються тільки в межах однієї зони.

Type 2 LSA - Network LSA - оголошення про стан каналів мережі. Поширюється DR у мережах зі множинним доступом. У LSA міститься опис всіх маршрутизаторів приєднаних до мережі, включаючи DR. Розповсюджуються тільки в межах однієї зони.

Type 3 LSA - Network Summary LSA - сумарне оголошення про стан каналів мережі. Оголошення поширюється прикордонними маршрутизаторами. Оголошення описує тільки маршрути до мереж поза зоною і не описує маршрути всередині автономної системи. Прикордонний маршрутизатор відправляє окреме оголошення для кожної відомої йому мережі.

Коли маршрутизатор отримує Network Summary LSA від прикордонного маршрутизатора він не запускає алгоритм обчислення найкоротшого шляху. Маршрутизатор просто додає до вартості маршруту зазначеного в LSA вартість маршруту до прикордонного маршрутизатора. Потім маршрут до мережі через прикордонний маршрутизатор поміщається в таблицю маршрутизації.

Type 4 LSA - ASBR Summary LSA - сумарне оголошення про стан каналів прикордонного маршрутизатора автономної системи. Оголошення поширюється прикордонними маршрутизаторами. ASBR Summary LSA відрізняється від Network Summary LSA тим, що поширюється інформація не про мережі, а про прикордонному маршрутизаторі автономної системи.

Type 5 LSA - AS External LSA - оголошення про стан зовнішніх каналів автономної системи. Оголошення поширюється прикордонним маршрутизатором автономної системи в межах всієї автономної системи. Оголошення описує маршрути зовнішні для автономної системи OSPF або маршрути за замовчуванням (default route) зовнішні для автономної системи OSPF.

Type 6 LSA - Multicast OSPF LSA - спеціалізований LSA, який використовують мультикаст OSPF додатки (Not implemented by CISCO). Type 7 LSA - AS External LSA for NSSA - оголошення про стан зовнішніх каналів автономної системи в NSSA зоні. Це оголошення може передаватися тільки в NSSA зоні. На кордоні зони прикордонний маршрутизатор перетворює type 7 LSA в type 5 LSA.

Type 8 LSA - Link LSA - анонсує link-local адресу і префікс (и) маршрутизатора всім маршрутизаторам розділяє канал (link). Відправляється тільки якщо на каналі присутні більше ніж один маршрутизатор. Розповсюджуються тільки в межах каналу (link).