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

Поточна версія на 15:26, 4 січня 2010

Підготував: студент 56 групи Мошуренко Андрій

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

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

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

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

Вимоги

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

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

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

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

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

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

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

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

(англ. 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

У теорії комп'ютерних мереж unicast або односпрямована (одностороння) передача даних має на увазі під собою передачу пакетів єдиного адресату. Дана схема пакетної маршрутизації даних є прямим протиставленням широкомовної схеми маршрутизації.

• multicast - 1: n

Multicast (англ. групова передача) - спеціальна форма широкомовлення, при якій копії пакетів направляються певній підмножині адресатів.

• broadcast - 1: усім

Broadcast - передача (мовлення) сигналів, наприклад аудіо / відео:

• Broadcasting - маршрутизація в комп'ютерних мережах
• Broadcast domain - широкомовний домен в комп'ютерних мережах

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

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

Multidestination Routing

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

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

англ. multicast routing

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

англ. spanning tree

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

Reverse path forwarding (Reverse path flooding)

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

Reverse path broadcast

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

Shortest Path Routing

Опис

Даний алгоритм підраховує найменший маршрут від кореня дерева до вузлів. Сенс полягає у створенні пучка вузлів Q, для яких вже було визначено оптимальний маршрут. Оператор генерує таблиці маршрутизації, які завантажуються при його ініціалізації і більше не змінюються. Грунтується на алгоритмі Дейкстри.

Алгоритм

Найменша відстань від A до D:

1. вузол A позначається як розглянутий

2. присвоїти всім сусіднім вузлам значення з дистанцією до розглянутого вузла B (2, A), G (6, A) і додати їх до списку кандидатів

3. вибрати зі списку кандидатів вузол з найменшою дистанцією B (2, A)

4. позначити цей вузол, як розглянутий і додати його в дерево

5. перейти до пункту 2

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

"+" : простота;

"+" : гарні результати при постійній топології мережі і навантаженні.

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

Flow-Based Routing

Опис

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

Приклад

Заданий граф для capacity і матриця трафіку.

• Підрахунок завантаження кожної лінії:

1. взяти одне з ребер графа

2. знайти, де воно зустрічається в таблиці

3. скласти всі швидкості з таблиці для цього ребра

• Підрахунок затримки для кожного графа за формулою Ti = 1 / (μCi-λi).

• Підрахунок вартості кожного ребра за формулою: Wi = λi / Σλi.

• Підрахунок загальної затримки Toverall = ΣTi • Wi Отримуємо: Toverall = 162.531msec.

Так як отримане значення занадто велике, то його можна зменшити за рахунок заміни шляху з самою великою затримкою DF (Ti, max = 1000msec) на шлях D-> G-> F

Flooding (алгоритм «затоплення»)

Опис

Є самим простим алгоритмом маршрутизації для поширення інформації з мережі. При отриманні пакету кожен вузол пересилає його сусіднім вузлам за винятком того, від якого прийшов пакет.

Ефективність

Даний алгоритм володіє низькою ефективністю через підвищену завантаження мережі.

Способи оптимізації

Для поліпшення ефективності алгоритму використовуються наступні способи:

• Hop counter

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

• Flooding with Acknowledge ( «затоплення з підтвердженнями»)

Однією з проблем простого алгоритму «затоплення» є те, що відправник не знає про те, чи досяг пакет всіх вузлів мережі. Кожен з вузлів мережі відправляє підтвердження про отримання, якщо він отримав підтвердження від всіх вузлів, яким він відправляв пакети.

• Unique resend

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

Інші алгоритми

Multipath Routing

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

Ієрархічна маршрутизація

англ. Hierarchical Routing однорівневі або ієрархічні алгоритми.

Деякі алгоритми маршрутизації оперують у однорівневому просторі, в той час як інші використовують ієрархію маршрутизації. У однорівневій системі маршрутизації всі маршрутизатори рівні по відношенню один до одного. В ієрархічній системі маршрутизації деякі маршрутизатори формують те, що становить основу (базу) маршрутизації. Наприклад, ті, які знаходяться на високошвидкісних магістралях. Пакети з небазових маршрутизаторів переміщуються до базових маршрутизаторів і переміщуються по них до тих пір, поки не досягнуть загальної області пункту призначення. Починаючи з цього моменту, вони переміщаються від останнього базового маршрутизатора через один або кілька небазових маршрутизаторів до кінцевого пункту призначення. Системи маршрутизації часто встановлюють логічні групи вузлів, які називаються доменами або областями. В ієрархічних системах одні маршрутизатори будь-якого домену можуть взаємодіяти з маршрутизаторами інших доменів, в той час як інші маршрутизатори цього домену можуть підтримувати зв'язок з маршрутизаторами тільки в межах свого домену. У дуже великих мережах можуть існувати додаткові ієрархічні рівні. Маршрутизатори найвищого ієрархічного рівня утворюють базу маршрутизації.

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