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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук

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

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

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

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

Вимоги

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

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

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

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

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

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

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

Адаптивний централізований алгоритм (англ. adaptive centralized routing)

Опис

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

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

"+" : RCC володіє всією інформацією і може створювати «ідеальні» маршрути; "+" : вузли звільнені від необхідності розрахунку таблиць маршрутизації; "-" : низька надійність; "-" : час від часу потрібно перерахунок таблиць маршрутизації; "-" : некоректна робота при розділених мережах; "-" : IS отримують інформації в різний час; "-" : концентрація трафіку біля RCC.

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