Типи алгоритмів

Цілі проектування.

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

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

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

Швидка збіжність. Збіжність – це процес узгодження всіма маршрутизаторами мережі оптимальних маршрутів. Говорять, що мережа збіглася, коли всі маршрутизатори мережі володіють однаковими та вірними відомостями про стан каналів мережі. Перерахунок метрик та зміна інформації про оптимальні маршрути виникає, оскільки топологія мережі періодично змінюється – одні пристрої виходять з ладу, інші, навпаки, стають доступними. Алгоритми, які володіють повільною збіжністю, можуть спричинити появу петель або виходу з ладу всієї мережі.

Гнучкість. Алгоритми маршрутизації повинні бути гнучкими – швидко та точно пристосовуватися до зміни умов функціонування мережі.

Алгоритми маршрутизації можуть бути класифіковані за типами.

Статичні на противагу динамічним.

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

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

При необхідності можна поєднувати ці два методи.

Одношляхові на противагу багатошляховим.

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

Плоскі на противагу ієрархічним.

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

“Від джерела” на противагу прозорим.

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

Інтрадоменні на противагу інтердоменним.

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

Стану каналу на противагу дистанційно-векторним.

Детальний аналіз даного поділу алгоритмів наводиться нижче.

Дата добавления: 2014-01-07