Принципи та алгоритми маршрутизації в Інтернет
Внутрішні протоколи маршрутизації
Протокол GGP (Gateway to Gateway Protocol, RFC 823) був розроблений і реалізований фірмою BBN для перших експериментальних шлюзів мережі Internet. Він до цих пір використовується в шлюзах фірми BBN LSI / 11, хоча вважається, що GGP має серйозні недоліки і пізніше був замінений на алгоритм SPF. Алгоритм протоколу GGP визначає маршрут з мінімальним числом переприймання, тобто його мірою довжини є просто число транзитних ділянок мережі між парами шлюзів. Він реалізує розподілене алгоритм найкоротшого шляху, який вимагає глобальної збіжності маршрутних таблиць після змін в топології або зв'язності.
Протокол RIP (Routing Information Protocol, RFC 1058, 1 581, один тисяча п'ятсот вісімдесят дві, 1724) часто використовується для класу протоколів маршрутизації, що базуються на протоколах XNS (Xerox Network System - мережева система Xerox) фірми Xerox. Реалізація протоколу RIP для сімейства протоколів TCP / IP широко доступна, оскільки входить до складу програмного забезпечення ОС UNIX, наприклад, FreeBSD або Linux. В силу своєї простоти протокол RIP має найбільші шанси перетворитися в «відкритий» протокол IGP, тобто протокол, який може використовуватися для спільної роботи шлюзів, що поставляються різними фірмами. При використанні протоколу RIP працює алгоритм динамічного програмування Беллмана-Форда. Як метрики маршрутизації RIP використовує число стрибків (кроків) до мети. Такий вид метрики не враховує відмінностей в пропускної здатності або завантаженості окремих сегментів мережі. Кожному маршруту ставиться у відповідність таймер тайм-ауту і «збирач сміття». Таймер тайм-ауту скидається кожен раз, коли маршрут ініціалізується або коригується. Якщо з часу останньої корекції пройшло 3 хвилини або отримано повідомлення в тому, що вектор відстані дорівнює 16, маршрут вважається закритим, але запис про нього не стирається, поки не закінчиться час «збирання сміття» (2 хвилини). При появі еквівалентного маршруту перемикання на нього не відбувається. Протокол RIP досить простий, але не позбавлений недоліків:
- потрібно багато часу для відновлення зв'язку після збою в маршрутизаторі (хвилини); в процесі встановлення режиму можливі цикли;
- ? число кроків - важливий, але не єдиний параметр маршруту, та й 15 кроків - не межа для сучасних мереж.
Випадок нестійкої роботи мережі по протоколу RIP при зміні конфігурації - відмову лінії зв'язку маршрутизатора M1 з мережею 1. При працездатному стані зв'язку з цим в таблиці маршрутів кожного маршрутизатора є запис про мережу з номером 1 і відповідним відстанню до неї:
При обриві зв'язку з мережею 1 маршрутизатор М1 зазначає, що відстань до цієї мережі прийняло значення 16. Проте отримавши через деякий час від маршрутизатора М2 маршрутне повідомлення про те, що від нього до мережі 1 відстань складає 2 хопу, маршрутизатор М1 нарощує цю відстань на 1 і зазначає, що мережа 1 досяжна через маршрутизатор 2. у результаті пакет, призначений для мережі 1, буде циркулювати між маршрутизаторами М1 і М2 до тих пір, поки не закінчиться час зберігання записи про мережі 1 в маршрутизаторі 2, і він не передасть цю інформацію березня шрутізатору М1.
Для виключення подібних ситуацій маршрутна інформація про відому маршрутизатора мережі не передається тому маршрутизатора, від якого вона прийшла.
Формат повідомлення протоколу RIP 1
Формат повідомлення протоколу RIP 2
Протокол "HELLO". Програмне забезпечення Fuzzball для шлюзу LSI / 11 включає в себе реалізацію протоколу IGP під назвою "HELLO". На відміну від RIP в ньому критерієм вибору маршруту служить час, а не відстань, тому "HELLO" вимагає досить точної синхронізації служб часу шлюзів.
Протокол OSPF (Open Shortest Path First, RFC 1850 1583, 1584, 1587) представляє собою протокол стану маршруту, причому в якості метрики використовується коефіцієнт якості обслуговування. Кожен маршрутизатор має повну інформацію про стан всіх інтерфейсів шлюзів автономної системи. Визначальними є три характеристики: затримка, пропускна здатність і надійність. Переваги OSPF:
Недоліки OSPF - важко отримати інформацію про переваги каналів для вузлів, що підтримують інші протоколи або мають статичну маршрутизацію.
Ієрархічно структурована автономна мережа OSPF з чотирма областями
Безпосередньо пов'язані (тобто досяжні без використання проміжних маршрутизаторів) маршрутизатори називаються "сусідами". Кожен маршрутизатор зберігає інформацію про те, в якому стані на його думку знаходиться сусід. Маршрутизатор покладається на сусідні маршрутизатори і передає їм пакети даних тільки в тому випадку, якщо він впевнений, що вони повністю працездатні. Для з'ясування стану зв'язків маршрутизатори-сусіди досить часто обмінюються короткими повідомленнями HELLO.
У протоколі OSPF використовується кілька часових параметрів, і серед них найбільш важливими є інтервал повідомлення HELLO і інтервал відмови маршрутизатора (router dead interval).