Алгоритми роботи маршрутизаторів

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

Класифікація

Алгоритми маршрутизації можна розділити на:

• Адаптивні і неадаптівние
• Глобальні і децентралізовані
• Статичні та динамічні

Вимоги

• Точність
• Простота
• Надійність
• Стабільність
• Справедливість
• Оптимальність

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

Адаптивні алгоритми

Опис: беруть до уваги стан лінії.

Переваги та недоліки:

"+" : можливість динамічної адаптації до стану мережі;

"-" : необхідно постійно перераховувати таблиці маршрутизації.

Адаптивний централізований алгоритм

(англ. adaptive centralized routing)

Опис

У мережі існує так званий центр маршрутизації (Routing Control Center, RCC), який отримує інформацію від всіх вузлів про їх сусідніх вузлів, довжині черги та завантаження лінії. У функції RCC входить збір інформації, підрахунок оптимальних маршрутів для кожного вузла, складання таблиць маршрутизації та розсилка їх вузлів.

Переваги та недоліки:

"+" : RCC володіє всією інформацією і може створювати «ідеальні» маршрути;

"+" : вузли звільнені від необхідності розрахунку таблиць маршрутизації;

"-" : низька надійність;

"-" : час від часу потрібно перерахунок таблиць маршрутизації;

"-" : некоректна робота при розділених мережах;

"-" : IS отримують інформації в різний час;

"-" : концентрація трафіку біля RCC.

Ізольований алгоритм

Опис

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

Переваги та недоліки:

"+" : легкість реалізації;

"-" : проблеми при зміні топології і навантаження;

"-" : не відбувається обмін даними про маршрутизації між вузлами.