Визначення призначеного раутера

Це здійснюється із використанням протоколу Hello. Тут наведено тільки короткий опис процесу, із повним описом можна ознайомитися в RFC 1583. Раутер перевіряє список своїх сусідів, відкидає всіх, які не мають двостороннього зв’язку або мають пріоритет раутера, рівний нулю, і записує призначений раутер, резервний призначений раутер і пріоритет раутера, задекларований кожним. Раутер додає себе до списку, використовуючи пріоритет раутера, сконфігурований для інтерфейсу, і нуль (невідомий) для значень призначеного раутера і резервного призначеного раутера, якщо раутер, який здійснює обчислення, тільки що з’явився.

Для визначення резервного призначеного раутера застосовують такі правила:

якщо один або більше раутерів декларують самих себе як претендентів на резервний призначений раутер і не були призначеним раутером, то виграє один із них із найвищим пріоритетом;

при рівних пріоритетах виграє раутер із найбільшим значенням ідентифікатора раутера;

якщо нема раутера, який декларує себе як кандидата на резервний призначений раутер, то вибирається раутер із найвищим пріоритетом, незважаючи на те, що він не декларував себе як претендента;

у випадку рівних пріоритетів виграє раутер із найбільшим значенням ідентифікатора раутера.

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

якщо один або декілька раутерів декларують себе як претендентів на призначений раутер, то один із них з найвищим пріоритетом раутера виграє;

у випадку рівних пріоритетів виграє раутер з найбільшим значенням ідентифікатора раутера;

якщо жоден раутер не задекларував себе як претендента на резервний призначений раутер, то резервний призначений раутер стає призначеним раутером.

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

коли з’являється новий раутер, то він не повинен мати змогу перехопити позицію (резервного) призначеного раутера від того раутера, який виконує цю функцію, навіть якщо новий раутер має вищий пріоритет;

підвищення резервного призначеного раутера до статусу призначеного раутера повинно здійснюватися впорядковано і вимагає від резервного прийняти нові обов’язки.

Алгоритм не завжди призводить до того, що раутер із найвищим пріоритетом стає призначеним раутером, а також не завжди раутер із другим вищим пріоритетом стає резервним.

Призначений раутер має такі обов’язки:

призначений раутер генерує оголошення мережевих зв’язків мережі в інтересах мережі. Це оголошення поширюється через область і описує цю мережу для всіх раутерів у всіх мережах у даній області;

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

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

Формування суміжностей

Після того, як виявлені сусіди, встановлний двосторонній зв’язок і (для мережі із багатьма доступами) вибраний призначений раутер, приймається рішення стосовно встановлення або невстановлення суміжностей із сусідами:

для мереж із багатьма доступами всі раутери отримують суміжність як із призначеним раутером, так і з резервним призначеним раутером;

для зв’язків пункт-пункт або для віртуальних зв’язків раутер завжди формує суміжність із раутером на протилежному кінці.

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

Суміжності встановлюються із використанням пакетів опису бази даних (Database Description). Вони містять підсумок бази даних стану зв’язку надавача. Можуть бути використані багато пакетів для опису бази даних, для цього вживають процедуру опитування-відповіді. Раутер із вищим ідентифікатором раутера стає головним (master), інші – підпорядкованими (slave). Пакети опису бази даних, вислані головним раутером (опитування – polls), підтверджуються пакетами опису бази даних, висланими підпорядкованими раутерами (відповіді – responses). Пакети містять номери послідовності для узгодження між опитуваннями і відповідями. Це називають процесом обміну базою даних (Database Exchange Process).

Формат пакету повідомлення Опис бази даних зображений на рис. 3.60.

Рис. 3.60. Формат пакету повідомлення Опис бази даних протоколу OSPF.

Пакет ініціює топологічну базу даних конкретного раутера, який при цьому виступає, як головний (біт S=1), а інші – як підпорядковані йому (біт S=0). Біти I, M використовуються при поділі довгих повідомлень на частини і мають такий сенс: I=1 – перше повідомлення у послідовності опису бази даних; M=1 – додаткове повідомлення, якщо опис бази даних продовжується. Інші поля пакету мають такі значення:

Послідовний номер повідомлення бази даних (Database sequence number) – послідовно нумерує повідомлення для їх впорядкування у приймачі. Початкове повідомлення має випадковий номер R, наступні нумеруються послідовно, починаючи від R.

Наступні 6 полів описують один зв’язок у мережевій топології; ці поля повторюються для кожного зв’язку.

Тип зв’язку (Link type) – описує один із можливих 5 типів зв’язку:

Зв’язки раутера (Router Links Advertisements - RLA), Link type=1 – описує збірку станів інтерфейсів раутера для певної області. Раутер висилає RLA для кожної області, до якої він належить. RLA поширюються всюди у цілій області, але не далі.

Мережеві зв’язки (Network Links Advertisement - NLA), Link type=2 – висилається призначеним раутером. Описує всі раутери, які під’єднані до мережі з багатьма доступами, і поширюються всюди в області, яка містить мережу з багатьма доступами.

Підсумок зв’язків (Summary Links Advertisement - SLA) – резюмує маршрути до призначень поза областю, але всередині автономної системи. Генеруються граничними раутерами областей і поширюються всюди в області. У магістралі оголошуються тільки маршрути всередині області, однак як внутрішньообласні, так і міжобласні маршрути оголошуються в інших областях. Link type=3 стосується до зв’язків у IP-мережі, а Link type=4 – до зв’язків з граничними раутерами.

Зовнішні зв’язки AS (AS external links advertisement), Link type=5 – описує маршрут до призначення, яке є зовнішнім відносно автономної системи. Походить від граничних раутерів AS. Тільки цей тип оголошення поширюється всюди в AS; всі інші типи поширюються тільки у визначених областях.

Оголошений раутер (Adversiting router) – визначає адресу раутера, оголошеного для даного зв’язку.

Послідовний номер зв’язку (Link sequency number) – ціле число, генероване раутером, яке використовується для того, щоб повідомлення не приймалися в невірному порядку.

Контрольна сума зв’язку (Link checksum) – забезпечує зв’язок перед пошкодженням даних.

Тривалість зв’язку (Link age) – містить час у секундах, який минув від моменту встановлення зв’язку; сприяє впорядкуванню повідомлень.

Решта пакету містить список частини або всьго вмісту топологічної бази даних. Кожен розділ у базі даних є оголошенням стану зв’язку. Пакети опису бази даних мають заголовки від цих оголошень. Заголовки однозначно ідентифікують кожне оголошення. Ця інформація використовується при наступній синхронізації бази даних. Формат заголовка стану зв’язку показаний на рис.

Формат пакету OSPF Запит стану зв’язку показаний на рис. 3.61.

Рис. 3.61. Формат пакету OSPF Запит стану зв’язку.

Такі пакети висилаються після обміну повідомленнями опису баз даних із сусідніми раутерами, якщо раутер встановив відсутність у його базі частини даних. Повідомлення-запит містить список потрібних зв’язків; сусід відповідає повною поточною інформацією про ці зв’язки. Три вказані поля (поза заголовком) повторюються для кожного потрібного зв’язку. Якщо список запитів довгий, то може бути потрібно вислати понад один запит.

Раутер поширює інформацію про стан зв’язків через модифікаційні повідомлення. Кожна модифікація містить список оголошень. Формат пакету Модифікація стану зв’язку зображений на рис. 3.62.

Рис. 3.62. Формат пакету Модифікація стану зв’язку.

Кожне оголошення стану зв’язку має заголовок, формат якого показаний на рис. 3.63.

Рис. 3.63. Заголовок оголошення стану зв’язку.

Після заголовка слідуює один із чотирьох можливих форматів опису зв’язків:

від раутера до певної області;

від раутера до певної мережі;

від раутера до фізичних мереж, які містять окрему IP-мережу з підмережами;

від раутера до мереж у інших автономних системах.

У всіх випадках поле Link type у заголовку (рис. 3.63) визначає, про який тип зв’язку йдеться.Тому раутер, який приймає модифікаційне повідомлення, точно знає, чи описане призначення міститься всередині домену, чи зовні нього.

Синхронізація бах даних

Після завершення процесу обміну базами даних кожен раутер має список своїх оголошень зв’язків. Їх запитують у пакетах запиту стану зв’язку (Link State Request). Відповіддю на пакет запиту стану зв’язку є пакет модифікації стану зв’язку, який містить певні або всі відповіді про оголошення станів зв’язку. Не більшеодного запиту стану зв’язку може бути невиконано; якщо відповідь не отримана, то запит мусить бути повторений.

Запити стану зв’язку приходять у п’ятьох форматах. Формат оголошення зв’язків раутера (тип 1) покаазаний на рис.. Це оголошення інкапсульоване в пакет OSPF.

Рис.. Оголошення зв’язків раутера.

Значення полів:

V-біт – якщо він встановлений, то раутер є кінцевим пунктом віртуального зв’язку, якмй використовує цю область як транзитну;

E-біт – якщо він встановлений, то раутер є граничним раутером автономної області;

B - біт – якщо він встановлений, то раутер є граничним раутером області;

Кількість зв’язків (# Links) – кількість зв’язків, олписаних цим оголошенням;

Ідентифікатор зв’язку (Link ID) – ідентифікує, об’єкти, сполучені даним зв’язком. Значення залежать від поля тип:

1 – ідентифікатор сусіднього раутера;

2 – IP-адреса призначеного раутера;

3 – це значення залежить від того, чим є внутрішньообласний маршрут:

для мережі-відгалуження це IP-адреса мережі або підмережі;

для станції – це X’FFFFFFFF’;

для зовнішнього маршруту за замовчуванням AS – це X’00000000’.

4 – ідентифікатор сусіднього раутера.

Дані зв’язку – це значення також залежить від поля тип (детальніше у RFC 1583):

Тип – вказує, який зв’язок під’єднаний:

1 – сполучення пункт-пункт до іншого раутера;

2 – сполучення із транзитною мережею;

3 – сполучення ізмережею-відгалуженням;

4 – віртуальне сполучення.

Кількість метрик (# metric) – кількість різних TOS-метрик, даних для цього зв’язку, крім метрики для TOS 0;

Метрика TOS 0 – вартість використання цього вихідного зв’язку для TOS 0. Всі пакети протоколу OSPF висилаються із IP-полем TOS, встановленим у 0.

TOS – IP-тип послуг, з яким пов’язана ця метрика. RFC 1349 визначає можливі значення TOS у IP-заголовку, використовуючи 4-бітову послідовність. OSPF кодує її, трактуючи послідовність як число і дублюючи його (це зарезервований біт 0, який безпосереднь слідує за значенням поля TOS в IP-данограмі, що дозволяє OSPF включити його у майбутньому до значення TOS). Існують 5 визначених значень:

OSPF	RFC 1349 (IP)	Тип послуг
		Звичайна послуга
		Мінімізація вартості в грошах
		Максимізація надійності
		Максимізація перепускної здатності
		Мінімізація затримки

Метрика – вартість використання цього вихідного зв’язку раутера для трафіку визначеного типу послуг.

Формат оголошення зв’язків мережі (тип 2) показаний на рис. 3.64. Це оголошення інкапсулюється в пакет OSPF.

Рис. 3.64. Оголошення зв’язків мережі.

Значення полів:

маска – маска IP-адреси для мережі;

ідентифікатор раутера k (Router ID k) – IP-адреса раутера k, суміжного з призначеним раутером (включно із раутером-надавачем). Кількість раутерів у списку визначається із поля довжина у заголовку.

Формат оголошення підсумку зв’язків (тип 3 і 4) показаний на рис.. Це оголошення інкапсулюється в пакет OSPF.

Рис.. Оголошення підсумку зв’язків.

Значення полів:

мережева маска – для оголошення стану зв’язку типу 3 це маска IP-адреси для мережі; для типу 4 маска нечинна і повинна дорівнювати нулю;

TOS 0 – нуль;

Метрика – вартість цього маршруту для даного типу послуги в тих самих одиницях, що й використаних для TOS-метрки у оголошення типу 1;

TOS x – нуль або більше входів для додаткових типів послуг; кількість входів можна визначити із поля довжина в заголовку.

Формат оголошення зовнішніх зв’язків показаний на рис. 3.65. Це оголошення інкапсулюється в пакет OSPF.

Рис. 3.65. Оголошення зовнішніх зв’язків.

Значення полів:

мережева маска – маска IP-адреси для мережі;

біт E – тип зовнішньої метрики; якщо він встановлений, то тип = 2, інакше тип = 1;

1 – метрика може бути безпосередньо порівняна із метриками стану зв’язку OSPF;

2 – метрика вважається більшою, ніж всі інші метрики стану зв’язку OSPF.

TOS 0 – нуль;

метрика – вартість цього маршруту; інтерпретація залежить від E-біта;

адреса для пересилання (forvarding address) – IP-адреса, за якою пересилається трафік даних для цього типу послуги, призначений для оголошеного призначення; значення 0 вказує, що трафіки може бути пересланий до граничного раутера AS, від якого походить оголошення;

TOS x - нуль або більше входів для додаткових типів послуг; кількість входів можна визначити із поля довжина в заголовку.

Коли всі відповіді на пакети запиту стану зв’язку отримані, то бази дані зсинхронізовані і раутери описані як повністю суміжні. Ця суміжність тепер додається до оголошень стану зв’язку двох раутерів.

Розрахунок таблиц раутінгу

Використовуючи бази даних стану зв’язку своїх під’єднаних областей, раутер виконує алгоритм SPF для побудови таблиці раутінгу. Таблиця раутінгу завжди будується від початку: модифікації нікоди не робляться на основі таявної таблиці. Стара таблиця раутінгу не знищується, доки відмінності між двома таблицями не ідентифіковані. Розрахунок складається із ряду кроків, описаних нижче; детальніше див. RCF 1583:

Маршрути всередині області очислюються на підставі дерева найкоротших шляхів для кожної під’єднаної області, при чому сам раутер є коренем дерева; раутер також обчислює, чи область може бути транзитною для віртуальних зв’язків.

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

Якщо раутер сполучений з одною або більше транзитними областями, раутер замінює будь-які розраховані маршрут маршрути маршрутами через транзитні області, якщо вони кращі.

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

Коли алгоритм видає багато маршрутів однакової вартості, то OSPF може розподілити навантаження між ними. Максимальна кількість маршрутів з однаковою вартістю, які підтримуються, залежить від впровадження.

Оголошення стану зв’язку

Раутер періодично оголошує свій стан зв’язку, так що відсутність нового оголошення вказує сусіду раутера, що цей раутер зупинений. Усі раутери, які мають встановлений двосторонній зв’язок із сусідами, використовують таймер неактивності для виявлення таких випадків. Якщо таймер не встановлений знову, він може бути скинений і ця подія встановлює машину станів відповідно до того, що сусід зупинений. Це означає, що комунікація мусить бути встановлена знову від початку включно з повторною синхронізацією баз даних. Раутер також повторно висилає свої оголошення, коли його стан змінюється.

Раутер може вислати окремі оголошення стану зв’язку до кожної області. Вони передаються через область за допомогою процедури поширення. Кожен раутер висилає оголошення зв’язків раутера. Якщо раутер є також оголошеним раутером для одної або більше мереж в області, то може породжувати оголошення станів мережі для цих мереж. Граничні раутери областей висилають одне оголошення підсумкового зв’яку для кожного відомого призначення всередині області. Граничні раутери AS породжують одне оголошення зовнішнього зв’язку для кожного відомого зовнішнього призначення. Призначення отримують оголошення по одному в часі, так що зміни в кожному окремому маршруті можуть бути поширені без повторного поширення всієї збірки маршрутів. За допомогою процедури поширення багато оголошень стану зв’язку можуть транспортуватися окремим пакетом модифікації стану зв’язку.