Відмінності між версіями «Алгоритми роботи маршрутизаторів»
Andrey (обговорення • внесок) (→Маршрутизація станом каналу) |
Andrey (обговорення • внесок) (→Класифікація) |
||
Рядок 5: | Рядок 5: | ||
Алгоритми маршрутизації можна розділити на: | Алгоритми маршрутизації можна розділити на: | ||
− | * Адаптивні і | + | * Адаптивні і неадаптивні |
* Глобальні і децентралізовані | * Глобальні і децентралізовані | ||
* Статичні та динамічні | * Статичні та динамічні |
Версія за 09:10, 24 листопада 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. підрахунок маршрутів на основі отриманої від інших вузлів інформації.