Протокол OSPF в Quagga (одна зона)

продовження статей про устрій таблиці маршрутизації та про реалізацію протоколу BGP Quagga, в цій статті я розберу як працює протокол OSPF. Я обмежуся нагодою для однієї OSPF зони без редистрибъюции маршрутів з інших протоколів маршрутизації.

Як звичайно, я не стану детально описувати роботу і налаштування протоколу OSPF, і пошлюся де можна більш детально про нього почитати. Обмежуся лише найбільш важливими для подальшого розуміння статті відомостями.

На відміну від протоколів RIP або BGP, які порівнюють прийшли маршрути від різних сусідів та вибирають кращі з них за якими-небудь критеріями, протокол OSPF будує топологічну карту мережі і прокладає по ній найкоротші маршрути до відповідних ip-мереж. Щоб зібрати інформацію про топологію мережі, маршрутизатори обмінюються між собою шматочками інформації про directly connected мережах і своїх сусідів OSPF. Дані шматочки топологічної інформації називаються LSA (Link State Advertisement) і з них, як пазл, можна зібрати повну топологічну карту мережі. Як влаштовані LSA ми розглянемо трохи пізніше, а зараз перейдемо до алгоритму знаходження найкоротшого шляху.

Алгоритм знаходження найкоротшого шляху
Для знаходження найкоротшого шляху використовується алгоритм Дейкстри, роботу якого розглянемо на наступному прикладі. У нас є п'ять маршрутизаторів, сполучених між собою лінками, як показано на малюнку:


R1 є кореневим маршрутизатором, на якому виконується алгоритм знаходження найкоротшого шляху. Цифри на лінках показують вартість (cost) цього лінка. Завдання полягає в тому, щоб знайти від маршрутизатора R1 до кожного з інших маршрутизаторів найкоротший шлях, тобто шлях у якого сумарна вартість лінків мінімальна.

В результаті для кожного маршрутизатора ми повинні обчислити дві речі:

  1. Вартість шляху від R1 до даного маршрутизатора.
  2. Який next-hop використовує R1, щоб досягти даний маршрутизатор.
Ця інформація необхідна, щоб R1 зміг правильно скласти таблицю маршрутизації. Всередині кожного маршрутизатора ми будемо вказувати поточну вартість до нього. Поряд будемо вказувати поточний next-hop, який використовує R1, щоб досягти даний маршрутизатор. Зеленим кольором будемо відзначати маршрутизатори, до яких найкоротший шлях обчислений.

Таким чином, на початковому етапі ми маємо найкоротший шлях тільки до самого маршрутизатора R1, рівний 0. До інших маршрутизаторів вартості дорівнюють нескінченності, а next-hop невідомі.

Зараз ми будемо робити послідовність кроків, кожен з яких буде покращувати вартість шляхів до маршрутизаторів, а в кінцевому рахунку ми обчислимо найкоротші шляхи до всіх з них.

Крок 1. Дивимося сусідів кореневого маршрутизатора.

Сусідами кореневого маршрутизатора R1 є маршрутизатори R2 і R3. Для кожного з них встановлюємо вартість шляхи рівним вартості відповідного лінка і next-hop рівним самому маршрутизатора R2 та R3, як показано на малюнку:


Крок 2. Вибираємо кращого з тих, що залишилися.

На даному кроці ми дивимося всі маршрутизатори, тобто маршрутизатори до яких найкоротший шлях ще не знайдений (білого кольору) і вибираємо з них маршрутизатор з найменшою вартістю шляху до нього. У нашому випадку це маршрутизатор R2 з вартістю 1. Цей маршрутизатор ми сміливо можемо перефарбувати в зелений колір, коротшого шляху для нього не існує.


На малюнку він пофарбований у темний зелений колір, оскільки цей маршрутизатор знадобиться нам на кроці 3.

Крок 3. Дивимося на сусідів виділеного маршрутизатора.

Цей крок схожий на крок 1, тільки замість маршрутизатора R1 ми дивимося на сусідів вибраного на попередньому етапі темно-зеленого маршрутизатора. Для кожного сусіда ми обчислюємо вартість шляху через вибраний маршрутизатор. Якщо вартість такого шляху виходить менше, ніж поточна вартість, то сусідові присвоюємо нову вартість, а next-hop просто копіюємо від обраного маршрутизатора. Виходить така картина:


Тепер повторюємо кроки 2 та 3 доти, доки всі маршрутизатори не стануть зеленими. На етапі 2 у нас один маршрутизатор обов'язково зеленіє, так що такий процес рано чи пізно закінчиться.

Отже, вибираємо кращий з тих, що залишилися, перекрашиваем в зелений колір (маршрутизатор R5):


Дивимося на сусідів виділеного маршрутизатора, покращуємо вартості, копіюємо next-hop:


Видно, що у R3 змінився next-hop, який був скопійований від R5. Вибираємо кращого:


Дивимося на що залишився сусіда:


І отримуємо остаточний результат:


Тепер у нас є вартості шляхів до кожного з маршрутизаторів, а також які next-hop використовувати на кореневому маршрутизаторі для їх досягнення. Тобто ми практично готові скласти таблицю маршрутизації. Проте для безпосереднього застосування в мережах розглянутий вище алгоритм вимагає деякої модернізації.

Модернізація алгоритму знаходження найкоротшого шляху
Вищеописаний алгоритм працює лише з лінками типу точка-точка, коли кожен лінк з'єднує два маршрутизатора. Реальні ж маршрутизатори, можуть з'єднуватися між собою через мережу Ethernet, яка допускає підключення до одного сегмента більш 2-х маршрутизаторів, як показано на рисунку.


У протоколі OSPF така мережа називається транзитним. Для вирішення даної проблеми в OSPF кожна транзитна мережа представляється окремим вузлом в графі. Тобто при обчисленні найкоротшого шляху топологія буде виглядати так:


Вузол N1 як раз і означає транзитну мережу. Тепер у нас кожен лінк з'єднує лише два вузли і можна застосовувати алгоритм знаходження найкоротшого шляху. При розрахунку вартості шляхи враховується тільки вартість лінка від маршрутизатора до транзитної мережі, а від транзитної мережі до маршрутизатора вона вважається рівною 0.

Оскільки транзитна мережа є логічним об'єктом, то якийсь із маршрутизаторів повинен взяти на себе обов'язок щодо створення необхідної топологічної інформації, що описує транзитну мережу. Для цього в OSPF у кожної транзитної мережі вибирається Designated Router (DR), який крім інформації про себе також має обов'язок анонсувати інформацію про транзитної мережі.

Крім того, в таблиці маршрутизації знаходяться маршрути не до маршрутизаторів, а до ip-мереж. Питання з транзитними мережами вирішується просто. Оскільки транзитні мережі представляються вершинами в графі, то вартість маршрутів до транзитних мереж обчислюється в процесі роботи алгоритму пошуку найкоротшого шляху. Інші мережі, наприклад, до мережі яких підключений тільки один маршрутизатор OSPF, вважаються кінцевими (stub) мережами та анонсуються маршрутизаторами, до яких вони підключені. Знаючи вартість найкоротшого шляху до кожного маршрутизатора можна легко обчислити і вартість маршруту до всіх підключених до нього кінцевих мереж.

Link State Advertisement (LSA)
Як я вже говорив, для того, щоб кожен маршрутизатор міг скласти топологію мережі і застосувати до неї алгоритм пошуку найкоротшого шляху, маршрутизатори обмінюються між собою невеликими шматочками інформаціями, званими Link State Advertisement LSA. LSA бувають різних типів і передають різну інформацію. Для нашого випадку з єдиною зоною важливі два типи LSA — LSA тип 1 і LSA тип 2. Кожна LSA тип 1 описує маршрутизатор. LSA тип 2 описує транзитну мережу. Якщо опустити різну службову інформацію, то ці LSA схематично можна представити так:


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

LSA Тип 1 (Router LSA).

У заголовку LSA нам важливі три поля:

  • Тип. Вказує тип LSA. У нашому випадку це тип 1, або Router LSA.
  • LSID. Ідентифікатор LSA. У нашому випадку LSID дорівнює Router ID маршрутизатора, який створює LSA.
  • Adv Router. Ідентифікатор маршрутизатора, який створив LSA. В нашому випадку він також дорівнює Router ID маршрутизатора, який створює LSA, тобто збігається з LSID.
Нижче йде інформація про лінках нашого маршрутизатора. Від типу лінка залежить і передана про лінке інформація. Маршрутизатор може мати лінки трьох різних типів:

Транзитна мережа. Для лінка даного типу передається наступна інформація:

  • Link ID — ip-адреса інтерфейсу Designated Router, підключеного до транзитної мережі.
  • Link Data — ip-адреса інтерфейсу самого маршрутизатора, підключеного до транзитної мережі.
  • Metric — вартість лінка.
Точка-точка. Для лінка типу точка-точка передається:

  • Link ID — ip-адреса інтерфейсу сусіда.
  • Link Data — ip-адреса інтерфейсу самого маршрутизатора.
  • Metric — вартість лінка.
Кінцева (Stub) мережу. Для неї передається:

  • Link ID — власне ip-адресу мережі.
  • Link Data — маска мережі.
  • Metric — вартість лінка.

LSA Тип 2 (Network LSA)

LSA тип 2 передає інформацію про транзитної мережі та анонсується спеціально обраними для кожної транзитної мережі Designated Router.

У заголовку LSA знаходяться чотири важливих поля:

  • Тип. У нашому випадку це тип 2, або Network LSA.
  • LSID. Ідентифікатор LSA. У нашому випадку LSID дорівнює ip-адресу інтерфейсу Designated Router, підключеного до транзитної мережі;
  • Adv Router. Ідентифікатор маршрутизатора, який створив LSA. У нашому випадку він дорівнює Designated Router ID.
  • Mask. Маска мережі.
Далі йде інформація про маршрутизаторів, підключених до транзитної мережі. Для кожного такого маршрутизатора вказується його Router ID.

Кожна LSA відповідає вузлу графа і, в залежності від типу, представляє або маршрутизатор, або транзитну мережу. Маючи всі LSA тепер легко створити топологію мережі. Для цього достатньо зауважити, що Link ID транзитного лінка маршрутизатора відповідає LSID транзитної мережі, і навпаки, Attached Router ID транзитної мережі відповідає LSID підключеного до транзитної мережі маршрутизатора.

Для прикладу на малюнку показана невелика мережа:


відповідні їй LSA:


і топологія:


Всі створені і прийняті LSA зберігаються в базі, званої LSDB (LSA Database). Основне, що потрібно від цієї бази – це мати можливість додавати в неї LSA, перебирати всі LSA певного типу і шукати LSA по ключових полях заголовка LSA.

Переглянути список всіх LSA в LSDB та їх поля можна за допомогою команд show ip ospf database (виводить заголовки всіх LSA), show ip ospf database route (виводить повну інформацію по LSA тип Router) і show ip ospf database network (виводить повну інформацію по LSA тип Network).

Реалізація в Quagga
У Quagga вся база для зберігання LSA (LSDB) розбита на кілька баз, окремих для кожного типу LSA, як показано на малюнку:



Кожна база для зберігання LSA окремого типу влаштовано однаково і зберігає в ній містяться LSA у вигляді описаного в попередньому статті префиксного дерева. Префікс використовується комбінація LSID і Adv Router. Комбінація цих полів унікальна для кожної LSA певного типу в межах зони.

При отриманні нової LSA дана LSA додається в LSDB і запускається процес обчислення найкоротшого маршруту. Процес починається з LSA, відповідної самого маршрутизатора. На основі міститься в ній інформації в пам'яті створюється новий вузол, що відповідає кореневому вузлу в топології. Далі, з LSDB послідовно дістаються LSA, відповідні сусіднім вузлам в топології, створюються нові вузли і обчислюються найкоротші шляхи і next-hop до них, як було описано в алгоритмі найкоротшого шляху. Паралельно, для оброблених вузлів, в таблицю маршрутизації OSPF додаються маршрути до транзитних мереж.

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

На останньому етапі всі вузли в топології видаляються з пам'яті, а маршрути з таблиці маршрутизації OSPF передаються в демон zebra. Схема даного процесу показана на малюнку.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.