1. Типи алгоритмів раутінгу

Алгоритми раутінгу можна класифікувати за типами. Наприклад, алгоритми можуть бути:

статичними або динамічними;

одношляховими або багатошляховими;

плоскими або ієрархічними;

орієнтованими на інтелектуальну станцію або на інтелектуальний раутер;

внутрішньодоменними або міждоменними;

типу “зв’язок-стан” або “вектор-відстань”.

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

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

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

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

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

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

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

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

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

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

Алгоритм “зв’язок-стан” чи “вектор-відстань”. Алгоритми типу “зв’язок-стан” (відомі також під назвою алгоритмів з пріорітетом найкоротшого шляху) висилають інформацію про маршрути до всіх вузлів в об’єднанні мереж. Однак кожен раутер висилає лише частину таблиці маршрутизації, яка описує стан його власних зв’язків. Алгоритми типу “вектор-відстань” (відомі також під назвою алгоритмів Беллмана-Форда) звертаються до кожного раутера за висиланням цілих таблиць або частин їх таблиць раутінгу, але тільки для своїх сусідів. По суті, алгоритми типу “зв’язок-стан” висилають малі модифікації всюди, тоді як алгоритми типу “вектор-відстань” висилають великі модифікації тільки до сусідніх раутерів.

Внаслідок більшої швидкості збіжності алгоритми типу “зв’язок-стан” є досить мало схильні до утворення петель раутінгу, ніж алгоритми з векторною відстанню. З другого боку, алгоритми типу “зв’язок-стан” більш вимогливі до потужності центрального процесора і пам’яті. Через це алгоритми “зв’язок-стан” дорожчі для впровадження та підтримки. Незалежно від цих відмінностей, обидва типи алгоритмів добре працюють у більшості ситуацій.

Термін “вектор-відстань” відноситься до класу алгоритмів, які використовують раутери (шлюзи у термінології TCP/IP) для модифікації раутінгової інформації. Кожен раутер розпочинає роботу із множиною маршрутів для тих мереж або підмереж, до який він безпосередньо під'єднаний, і, можливо, із певними додатковими маршрутами до інших мереж або станцій, якщо мережева топологія така, що протокол раутінгу нездатний коректно створити бажаний раутінг. Цей список міститься у таблиці раутінгу, де кожен вхід ідентифікує мережу-призначення або станцію і вказує “відстань” до цієї мережі (станції). Відстань називають метрикою і вона звичайно вимірюється у “стрибках”.

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

відомий коротший шлях до призначення;

список призначень не містить раутера B;

якщо відстань до призначення, завжди маршрутованого від B до A, змінена.

Цей вид алгоритму простий для впровадження, але має ряд недоліків:

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

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

Алгоритми “вектор-відстань” вживають лічильник стрибків як метрику, не враховуючи швидкість зв’язків або їх надійність. Такі алгоритми використають шлях із лічильником стрибків 2, який проходить через дві низькошвидкісні лінії, замість того, щоб використати шлях із лічильником стрибків 3, який проходить через три високошвидкісні мережі.

Найбільш складним завданням для алгоритмів “вектор-відстань” є запобігання нестабільності. Для цього вживають різні розв’язання.

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

Першою альтернативою до схем “вектор-відстань” є клас протоколів, відомих як “зв’язок-стан, першим найкоротший шлях” (Link State, Shortest Path First).

Важливими властивостями цих протоколів раутінгу є такі:

множина фізичних мереж ділиться на певну кількість областей (area);

всі раутери всередині області мають ідентичні бази даних;

кожна база даних раутера описує повну топологію (тобто описує, які раутери під’єднані до яких мереж) в домені раутінгу; топологія області представлена базою даних, яку називають базою даних станів зв’язку (Link State Database), яка описує всі зв’язки які має кожен раутер в області;

кожен раутер використовує свою базу даних для виведення множини оптимальних шляхів до всіх призначень, з яких він будує свою таблицю раутінгу; алгоритм для визначення оптимальних шляхів називають алгоритмом “першим найкоротший шлях” (Shortest Path First).

У загальному випадку протокол стан-зв’язок працює таким чином. Кожен раутер періодично висилає опис своїх сполучень (стан своїз зв’язків) до своїх сусідів (раутери є сусідами, якщо вони сполучені із тою самою мережею). Цей опис, який називають оголошенням станів зв’язку (Link State Advertisement - LSA), включає сконфігуровану вартість сполучення. LSA поширюється в домені раутінгу. Кожен раутер у домені обслуговує ідентичну зсинхронізовану копію бази даних, складену із цієї інформації про стан зв’язків. Ця база даних описує як топологію домену раутінгу і маршрути до мереж поза доменом, так і маршрути до мереж в інших автономних системах (доменах). Кожен раутер виконує алгоритм у своїй топологічній базі даних, отримуючи дерево найкоротших шляхів. Це дерево найкоротших шляхів містить найкоротший шлях до кожного раутера і до мережі, досяжної для цього раутера. Значення вартості до призначення і наступний стрибок для пересилання данограми отримуються із дерева найкоротших шляхів і вживаються для побудови таблиці раутінгу раутера.

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