OSPF

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

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

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-пакетах.
  • На наступному етапі роботи протоколу маршрутизатори будуть намагатися перейти в стан суміжності з маршрутизаторами, які перебувають з ним у межах прямого зв'язку (на відстані одного хопу (hop)). Перехід у стан суміжності визначається типом маршрутизаторів, які обмінюються 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) в іншій directly conected мережі. Роль 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).

Типи зон

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

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

  • Знизити навантаження на ЦП маршрутизаторів за рахунок зменшення кількості перерахунків за алгоритмом 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.

Формат заголовку OSPF пакету

OSPF-пакет инкапсулируется безпосередньо в полі даних IP-пакета. Значення поля «протокол верхнього рівня » в заголовку IP-дейтаграми для OSPF дорівнює 89.

     0               1               2               3
     0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   version     |     type      |         packet length         |
    +---------------+---------------+-------------------------------+
    |                          router ID                            |
    +---------------------------------------------------------------+
    |                           area ID                             |
    +-------------------------------+-------------------------------+
    |           checksum            |      authentication type      |
    +-------------------------------+-------------------------------+
    |                       authentication                          |
    +---------------------------------------------------------------+
    |                       authentication                          |
    +---------------------------------------------------------------+
  • version - номер версії протоколу OSPF. Поточна версія OSPF для мереж IPv4 - 2.
  • type - тип OSPF-пакета. У RFC 2328 описано 5 типів пакетів.
  • packet length - довжина пакету, включаючи заголовок.
  • router ID - ідентифікатор маршрутизатора - унікальне 32-хбітное число, що ідентифікує маршрутизатор у межах автономної системи.
  • area ID - 32-хбітний ідентифікатор зони.
  • checksum - поле контрольної суми. Підраховується для всього пакету, включаючи заголовок.
  • authentication type - тип використовуваної схеми аутентифікації. Можливі значення:
    • 0 - аутентифікація не використовується
    • 1 - аутентифікація відкритим текстом
    • 2 - MD5-аутентифікація
  • authentication - поле даних аутентифікації.

Формат hello-пакета

     0               1               2               3
     0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   version     |     type      |         packet length         |
    +---------------+---------------+-------------------------------+
    |                          router ID                            |
    +---------------------------------------------------------------+
    |                           area ID                             |
    +-------------------------------+-------------------------------+
    |           checksum            |      authentication type      |
    +-------------------------------+-------------------------------+
    |                       authentication                          |
    +---------------------------------------------------------------+
    |                       authentication                          |
    +---------------------------------------------------------------+
    |                        network mask                           |
    +-------------------------------+---------------+---------------+
    |        hello interval         |    options    |router priority|
    +-------------------------------+---------------+---------------+
    |                     router dead interval                      |
    +---------------------------------------------------------------+
    |                      designated router                        |
    +---------------------------------------------------------------+
    |                   backup designated router                    |
    +---------------------------------------------------------------+
    |                          neighbor ID                          |
    +---------------------------------------------------------------+
    |                          neighbor ID                          |
    +---------------------------------------------------------------+
    |                             ...                               |

Нижче наведено короткий опис полів hello-пакета.

  • network mask - мережева маска інтерфейсу, через який вирушає hello-пакет.
  • hello interval - hello-інтервал задає частоту розсилки привітальних повідомлень для виявлення сусідів в автономній системі. Для LAN значення за замовчуванням дорівнює 10 секундам.
  • options - 8-бітове поле опцій. Описує можливості маршрутизатора.
  • router priority - пріоритет маршрутизатора - 8-бітове число, що символізує пріоритет маршрутизатора при виборі DR (англ. Designated router) і BDR (англ. Backup designated router).
  • router dead interval - період часу, протягом якого маршрутизатор очікує відповіді сусідів.
  • designated router (DR) - IP-адреса DR.
  • backup designated router (BDR) - IP-адреса BDR.
  • neighbor ID - ідентифікатор сусіда. Список складається з ідентифікаторів сусідів, від яких маршрутизатор отримав hello-пакети протягом часу, заданого в полі router dead interval.