Алгоритми та протоколи маршрутизації

Залежно від способу формування таблиць маршрутизації однокроковий алгоритми поділяють на три класи:

• алгоритми фіксованої (або статичної) маршрутизації;

• алгоритми простої маршрутизації;

• алгоритми адаптивної (або динамічної) маршрутизації

Якщо маршрутизація є фіксованою, то всі записи в таблиці маршрутизації – статичні. Адміністратор мережі сам вирішує, на які маршрутизатори треба передавати пакети з тими чи іншими адресами, і заносить відповідні записи до таблиці маршрутизації вручну (наприклад, за допомогою утиліти route ОС UNIX або Windows NT).

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

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

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

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

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

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

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

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

Найбільшого поширення набули алгоритми адаптивної, або динамічної маршрутизації. Вони забезпечують автоматичне оновлення таблиць маршрутизації після зміни конфігурації мережі. Використовуючи протоколи адаптивних алгоритмів, маршрутизатори можуть збирати інформацію про топологію зв'язків у мережі та оперативно реагувати на всі зміни конфігурації зв'язків. У таблиці маршрутизації, звичайно, заносять інформацію про інтервал часу, протягом якого даний маршрут залишатимется чинним. Цей час називають часом життя маршруту (Time To Live, TTL).

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

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

Взаємодія маршрутизаторів із серверами маршрутів здійснюється за спеціальними протоколами, наприклад, протоколом вибору наступного кроку (Next Hop Resolution Protocol, NHRP).

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

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

• дистанційно-векторні алгоритми (Distance Vector Algorithm, DVA);