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

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

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

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

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

Вимоги

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

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

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

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

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

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

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

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

(англ. adaptive centralized routing)

Опис

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

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

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

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

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

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

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

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

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

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

Опис

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

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

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

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

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

Розподілені алгоритми

Дистанційно-векторний алгоритм

(англ. distance vector routing)

Опис

Також відомий як Distributed Bellman-Ford Routing або Ford Fulkerson Algorithm. Цей алгоритм є розподіленим, ітераційним і асинхронним. Його можна представити як: «розкажи своїм сусідам, як виглядає світ». Кожен вузол веде таблицю маршрутизації з одним записом для кожного маршрутизатора підмережі. Таблиця являє собою вектор, що містить 2 компоненти: обрану лінію і дистанцію. Вузол оцінює дистанцію (кількість хопів, затримку або довжину черги) до кожного сусіда і розсилає її своїм сусідам, які в свою чергу виконують те ж саме. У результаті отриманої інформації кожен вузол заново підраховує таблицю маршрутизації. Застосовується в протоколі маршрутизації RIP. Вперше був застосований в ARPANET.

Алгоритм

Припустимо, що таблиця тільки що була отримана від сусіда X, причому Xi є припущенням X про те, скільки триває шлях до маршрутизатора i. Якщо маршрутизатор знає, що передача даних до X триває m, то він знає так само, що він може досягти будь-який маршрутизатор і через X за Xi + m.

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

"+" : самоорганізація;

"+" : відносно проста реалізація;

"-" : погана конвергенція ( "збіжність");

"-" : складності при розширенні мережі.

Приклад

При використанні алгоритму виникають проблеми при відключенні одного з вузлів від мережі - проблема «Count to Infinity» (рахунок до нескінченності). Запобігання: Split Horizont Algorithm - «не говори мені те, що я сказав тобі».

Маршрутизація станом каналу

(англ. link state routing)

Опис

Алгоритм, що відноситься до адаптивних алгоритмів і заснований на аналізі стану зв'язків. Його можна представити як: «розкажи світові про те, хто твої сусіди». Спочатку вузол знає тільки своїх сусідів і метрику зв'язків, що з'єднують його з ними. У процесі обміну інформацією з сусідніми вузлами, вузол отримує інформацію про топологію мережі, при цьому тільки обмінюється інформацією про що відбулися зміни. В результаті кожен вузол знає всю топологію мережі. Вперше був застосований в ARPANET в 1979 році і прийшов на зміну дистанційно-векторному алгоритму. Причинами переходу служили:

• Зростання пропускної спроможності каналів і відсутність її обліку в дистанційно-векторному алгоритмі
• Повільність дистанційно-векторного алгоритму, викликана «рахунком до нескінченності»

Алгоритм

1. визначення адрес сусідніх вузлів: нові вузли розсилають привітання (HELLO-повідомлення), сусідні вузли повідомляють свої адреси відбувається за допомогою розсилки HELLO-запитів;

2. вимір метрики ліній або часу передачі даних до сусідніх вузлів відбувається в результаті розсилки луна-повідомлень;

3. організація зібраних даних у пакет, який містить особисту адресу, порядковий номер (для уникнення повторень), вік (для відкидання застарілої інформації), дистанцію;

4. розсилка пакетів усіх вузлів мережі (flooding);

5. підрахунок маршрутів на основі отриманої від інших вузлів інформації.

Широкомовна маршрутизація

(англ. broadcast routing)

Термінологія

• unicast - 1:1
• multicast - 1: n
• broadcast - 1: усім