Принципи та алгоритми маршрутизації в інтернет

4. Принципи та алгоритми маршрутизації в Інтернет

4.1. Проблема маршрутизації в мережі Internet

Алгоритм маршрутизації є тим фундаментом, на якому будується вся робота базової мережі з архітектурою TCP / IP. Забезпечення надійних мережевих послуг вимагає певної динаміки маршрутизації. Несподівані зміни в зв'язності базової мережі повинні розглядатися як звичайні явища і відповідним чином оброблятися, так само як і перевантаження окремих напрямків і каналів.

Існує ряд вимог, які слід враховувати при виборі прийнятного алгоритму маршрутизації:
· Алгоритм маршрутизації повинен розпізнавати відмову і відновлення каналів зв'язку або інших IP-маршрутизаторів і перемикатися на інші, які підходять маршрути. Час перемикання маршрутів повинно бути меншим, ніж типовий тайм-аут користувача протоколу ТСР (приблизно 1 хв);
· Алгоритм повинен виключати утворення циклів, петель і ефекту «пінг-понг» в призначуваних маршрутах як між сусідніми IP-маршрутизаторами, так і для віддалених IP-маршрутизаторів. Існування перерахованих вище ефектів не повинно перевищувати типового тайм-ауту користувача протоколу TCP (приблизно 1 хвилина);
· Навантаження, створювана керуючими повідомленнями, які необхідні для роботи алгоритму маршрутизації, не повинна відчутно погіршувати або порушувати нормальну роботу мережі. Зміна стану мережі, яке може перервати нормальну роботу в деякій локальній області мережі, не повинно надавати впливу на віддалені ділянки;
· Оскільки розміри мережі постійно збільшуються, необхідно забезпечити ефективне використання мережевих ресурсів, наприклад, зміна матриць маршрутів виконувати частинами, передаючи з глобальних мереж тільки доповнення до баз даних по маршрутизації;
· Розмір бази даних по маршрутизації не повинен перевищувати деякої константи, що не залежить від топології мережі, помноженої на кількість вузлів і на середню зв'язність мережі. Хороша реалізація не повинна вимагати зберігання повної бази даних по маршрутизації в кожному IP-маршрутизатор;
· Якщо використовуються метрики, засновані на досяжності вузла і затримки в доставці пакета, то вони не повинні залежати від прямої зв'язності з усіма іншими IP-маршрутизаторами або від використання механізмів широкомовної передачі, специфічних для деяких мереж. Процедури опитування не повинні вносити істотних додаткових витрат;
· Маршрути за замовчуванням слід використовувати в якості первинних припущень про маршрутизації, щоб потім вибирати остаточне напрямок передачі.

Крім перерахованих вище завдань IP-маршрутизатор повинен забезпечувати ефективний розподіл власних ресурсів як по пропускній здатності каналів, так і за обсягом буферних ЗУ, використовуваних для зберігання пакетів, які очікують передачу. Найбільш очевидна стратегія «першим прийшов - першим обслужений» (FCFS - First Come First Served) може виявитися неприйнятною в умовах перевантаження мережі.

Так, наприклад, не можна допустити, щоб високошвидкісний канал захопив весь обсяг буферних ЗУ, нічого не залишивши низкоскоростному каналу. У хороших алгоритмах обов'язково повинно враховуватися поле «Тип сервісу» заголовка IP-пакета; IP-маршрутизатор може призначити більший пріоритет IP-пакетів, що передає керуючу або службову інформацію.

Нарешті, алгоритм маршрутизації повинен забезпечувати надійний алгоритм визначення стану кожного каналу зв'язку і вузла в базовій мережі і, якщо потрібно, стан хост-ЕОМ.
Для цього потрібен, принаймні, протокол канального рівня, що передбачає періодичний обмін кадрами через кожен канал зв'язку.
Однак цього часто виявляється недостатньо, тому додатково потрібен спеціальний механізм в алгоритмах маршрутизації.
З технічних, адміністративних, географічним, а також іноді і політичних міркувань IP-маршрутизатори групуються в так звані «автономні системи».
IP-маршрутизатори, що входять в одну автономну систему, контролюються однією організацією, що забезпечує їх супровід, і використовують загальні для даної автономної системи алгоритми маршрутизації.

Визначення. Конкретний варіант протоколу маршрутизації, що діє всередині однієї автономної системи, називається внутрішнім протоколом маршрутизації (IGP - Interior Gateway Protocol).

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

Визначення. Протокол для обміну службовою інформацією між автономними системами називається зовнішнім протоколом маршрутизації (EGP - Exterior Gateway Protocol).

Кожен IP-маршрутизатор повинен забезпечити реалізацію протоколів фізичного, канального, мережевого рівнів, а також протоколи доступу до мережі. В якості останніх використовуються протоколи Ethernet, Frame Relay, ATM, SLIP, PPP і ряд інших, а для мереж з архітектурою ISO протокол Х.25 / 2 (LAP-B).
Крім того, IP-маршрутизатора необхідна реалізація деякого алгоритму вибору маршруту по таблиці маршрутизації, а також алгоритму її поновлення.

Існують статичні і динамічні алгоритми відновлення таблиці.

Шлюзи, що входять до складу однієї автономної системи, можуть виконувати алгоритм динамічної маршрутизації - протоколи на основі алгоритму Беллмана-Форда і протоколи на основі алгоритму Дейкстри.
Кожній дузі графа ставиться у відповідність дійсне число, зване довжиною дуги; тоді довжина шляху визначається сумою довжин складових його дуг.
Зазвичай це число переприймання або середня затримка пакетів, але можливі і інші метрики, наприклад, пропускна здатність каналу зв'язку, надійність.

Шлюзи, що працюють за алгоритмом Беллмана-Форда. зберігають вектор довжин найкоротших маршрутів до всіх мереж, що входять до складу об'єднаної мережі.
Періодично кожен шлюз передає свій вектор сусіднім шлюзів автономної системи, а елементи вектора, прийнятого від сусіднього шлюзу, складаються з довжинами вихідних ліній зв'язку.
На основі отриманої таблиці будується новий вектор довжин найкоротших маршрутів - алгоритм Беллмана-Форда (DV - алгоритм Distance Vector).
Протоколи на основі DV-алгоритму досить просто реалізуються, вимагають мало пам'яті і процесорного часу, однак вони мають ряд загальних недоліків. При збільшенні кількості мереж, що входять до складу автономної системи, різко зростає кількість інформації, що передається, тому що DV-алгоритм вимагає, щоб всі шлюзи періодично передавали свої вектори довжин маршрутів.

Шлюзи, що працюють за алгоритмом Дейкстри (Shortest Path First - SPF-алгоритм), спочатку визначають найкоротші маршрути по всіх мереж автономної системи. Для цього в кожному шлюзі будується повне дерево найкоротших шляхів з коренем в даному шлюзі.
Процедура побудови дерева найкоротших шляхів використовує принцип, згідно з яким в дерево найкоротших шляхів першої включається дуга з найменшою довжиною, тому алгоритм Дейкстри часто називають першим найкоротшим шляхом.
Після того як в шлюзі побудовано дерево найкоротших шляхів, зміни характеристик ліній зв'язку, що визначають довжини відповідних дуг графа, зміни топології мережі призводять до невеликих додаткових обчислень для коригування дерева найкоротших шляхів.
Шлюзи обмінюються тільки відомостями про довжинах вихідних ліній зв'язку, а не векторами довжин маршрутів, як у випадку алгоритму Беллмана-Форда. Розмір коригувальних пакетів зі службовою інформацією для маршрутизації малий і не залежить від числа мереж в автономній системі. Кожен шлюз посилає такі пакети за допомогою лавинної маршрутизації. При появі в мережі нового шлюзу або включення нової лінії зв'язку зміни в топології мережі не враховуються при маршрутизації протягом деякого часу для того, щоб інформація про зміни встигла досягти всіх шлюзів автономної системи.

В цілому, алгоритм Дейкстри, в порівнянні з алгоритмом Беллмана-Форда, забезпечує більш реальну оцінку ситуації в мережі, більш швидку реакцію на важливі зміни в мережі (такі, як включення нової лінії зв'язку) і зменшує зациклення пакетів; проте алгоритм Дейкстри складніше в реалізації і вимагає в кілька разів більше пам'яті.

4.2. Внутрішні протоколи маршрутизації

Поле Протокол 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 використовує число стрибків (кроків) до мети. Такий вид метрики не враховує відмінностей в пропускної здатності або завантаженості окремих сегментів мережі.
Кожному маршруту ставиться у відповідність таймер тайм-ауту і «збирач сміття». Таймер тайм-ауту скидається кожен раз, коли маршрут ініціалізується або коригується. Якщо з часу останньої корекції пройшло 3 хвилини або отримано повідомлення в тому, що вектор відстані дорівнює 16, маршрут вважається закритим, але запис про нього не стирається, поки не закінчиться час «збирання сміття» (2 хвилини). При появі еквівалентного маршруту перемикання на нього не відбувається.
Протокол RIP досить простий, але не позбавлений недоліків:
- потрібно багато часу для відновлення зв'язку після збою в маршрутизаторі (хвилини); в процесі встановлення режиму можливі цикли;
- число кроків - важливий, але не єдиний параметр маршруту, та й 15 кроків - не межа для сучасних мереж.

Протокол "HELLO". Програмне забезпечення Fuzzball для шлюзу LSI / 11 включає в себе реалізацію протоколу IGP під назвою "HELLO". На відміну від RIP в ньому критерієм вибору маршруту служить час, а не відстань, тому "HELLO" вимагає досить точної синхронізації служб часу шлюзів.

Протокол IS-IS. З огляду на, з одного боку, широке поширення мереж з архітектурою TCP / IP, з іншого боку, підвищена увага урядових і комерційних організацій до архітектури ЕМВОС; очікується, що архітектури TCP / IP і ЕМВОС будуть існувати довгий час разом. Тому виникає необхідність в шлюзах, здатних маршрутизировать одночасно IP- і ЕМВОС-трафік.
Протокол IS-IS (Intermediate System to Intermediate System Protocol, RFC 1 195) забезпечує підтримку понять IP-підмережі, змінної маски підмережі, маршрутизацію на основі значення поля «Тип сервісу» в заголовку IP-пакета і поняття зовнішнього маршруту.
Протокол IS-IS є динамічним протоколом маршрутизації, побудованим на основі SPF-алгоритму.

4.3. Зовнішні протоколи маршрутизації

Зовнішні протоколи маршрутизації призначені головним чином для зв'язку між автономними (незалежними) системами.

Протокол EGP (Exterior Gateway Protocol) один з відомих протоколів цього типу (RFC 827, 888, 904, 911, 1092, 1093).
Документ RFC 827, який запропонував першу модель шлюзу для взаємодії зі шлюзами інших автономних систем, і документ RFC 888, що представляє собою розвиток цієї моделі, накладали істотне обмеження на топологію мережі Internet, припускаючи деревоподібну дворівневу структуру, коренем якої є так звана «магістральна» автономна система , що складається з «магістральних» шлюзів.
Головною перевагою такої моделі вважалася неможливість освіти в деревовидної топологічної структурі циклічних маршрутів між автономними системами.

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

Як правило, локальні шлюзи передають по зовнішньому протоколу тільки відомості, що стосуються своїх автономних систем, щоб не збільшувати без необхідності трафік в мережах.

Протокол BGP (Border Gateway Protocol, RFC 1 267) - це протокол маршрутизації між автономними системами в мережі Internet; він побудований на основі досвіду, накопиченого при експлуатації протоколу EGP.
Головна мета BGP - скоротити транзитний трафік. Протокол BGP використовує розширене поняття автономної системи. В даному випадку всередині автономної системи шлюзи можуть використовувати кілька різних протоколів маршрутизації і кілька метрик. Однак всередині автономної системи повинен існувати єдиний план маршрутизації, що дозволяє розглядати автономну систему як єдине ціле.

Протокол BGP використовує в якості транспортного протоколу протокол ТСР.
Хост-ЕОМ, що виконують протокол BGP, не обов'язково повинні одночасно бути шлюзами.
Хост-ЕОМ, яка не є шлюзом, може обмінюватися маршрутною інформацією зі шлюзами за допомогою протоколу EGP або внутрішнього протоколу маршрутизації.
Ця хост-ЕОМ може потім використовувати протокол BGP для обміну маршрутною інформацією з граничним шлюзом інший автономної системи.

Мал. 4.1. архітектура маршрутизатора

Мал. 4.2. Обробка на вхідному порту