Відмінності між версіями «Алгоритми роботи маршрутизаторів»

Версія за 08:21, 27 жовтня 2009

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

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

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

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

Вимоги

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

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

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

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

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

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

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

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

Опис

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

Плюси і мінуси

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

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