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

Версія за 10:05, 27 листопада 2009

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

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

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

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

Вимоги

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

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

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

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

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

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

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

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

(англ. 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: усім

Прості методи

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

Multidestination Routing

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

Багатоадресна розсилка

англ. multicast routing

Алгоритм сполучного дерева

англ. spanning tree

Сполучне дерево (Spanning tree): граф, який не містить петель. Сполучне дерево відомо усім вузлам. Відповідно до цього кожен вузол розсилає копії пакетів.

Reverse path forwarding (Reverse path flooding)

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

Reverse path broadcast

На відміну від Reverse path forwarding пакети відправляються тільки по лініях, за якими інші вузли приймають дані.

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