Алгоритми та протоколи маршрутизації

1. Загальні опис

Основними формами кожного маршрутизатора, реалізованим відповідно до протоколів маршрутизації, є:

Визначення найкращих маршрутів до можливих пунктів призначення і збереження отриманої інформації в таблиці маршрутизації;

Передача пакетів за оптимальними шляхами, вибраним з таблиці маршрутизації на основі адрес одержувачів.

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

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

Мережний адреса одержувача

Адреса наступного маршрутизатора, пересилання до якого відповідає оптимальному шляху до пункту призначення;

Характеристику шляху, наприклад, пропускна здатність каналу зв'язку та позначку часу, коли ця характеристика була визначена;

Інформацію про способі пересилання, наприклад, номер вихідного порту.

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

Визначення оптимальності шляхів при формуванні та оновленні таблиці маршрутизації може проводитися відповідно до таких критеріїв або їх комбінаціями, як:

Довжина маршруту, виміряна кількістю маршрутизаторів, через яке необхідно пройти до митницю призначення;

Пропускна здатність каналу зв'язку;

Прогнозована сумарний час пересилання;

Вартість каналу зв'язку.

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

зчитується з заголовка пакету, що відповідає мережевому рівню моделі OSI, адресу призначення, тобто мережеву адресу одержувача;

По таблиці маршрутизації визначається адреса наступного транзитного маршрутизатора, пересилання до якого відповідає оптимальному шляху до пункту призначення;

Замінює в заголовку пакету, відповідний канального рівня моделі OSI, свій МАС-адресу на МАС-адресу обраного транзитного маршрутизатора;

Відсилає пакет обраному транзитному маршрутизатора.

У міру того, як пакет пересувається через мережа, фізичну адресу (МАС-адресу) його одержувача змінюється, але логічний адреса пункту призначення, відповідний мережного рівня моделі OSI, залишається без змін.

2. Вимоги до алгоритму маршрутизації

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

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

За оптимізації певних маршрутів - здатності визначати найкращий маршрут в залежності від заданих показників і їх вагових коефіцієнтів;

За гнучкості -- здатність швидко і точно адаптуватися до змін структури та умов функціонування мережі;

За збіжності -- здатності досягти швидкого угоди між маршрутізаторнамі мережі по оптимальними маршрутами.

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

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

Алгоритми маршрутизації, які не володіють високою гнучкістю і швидкою збіжністю, призводять до утворення петель маршрутизації і навіть виходу з ладу мережі.

3. Класифікація алгоритмів і протоколів маршрутизації

Ознаки класифікації алгоритмів і протоколів маршрутизації в більшості випадків збігаються один з одним. Найбільш важливими ознаками є:

Ступінь динамічності, що відображає наявність або відсутність гнучкості і збіжності;

Кількість одночасно підтримуваних маршрутів до одного пункту призначення;

Спосіб організації маршрутів;

Область впливу;

Спосіб отримання маршрутної інформації.

За ступенем гнучкості і збіжності розрізняють статичні і динамічні алгоритми маршрутизації.

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

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

За кількістю одночасно підтримуваних маршрутів до одного пункту призначення алгоритми маршрутизації можуть мати одномаршрутнимі або многомаршрутнимі.

За способом організації маршрутів розрізняють алгоритми однорівневої і ієрархічної організації.

По області впливу алгоритми маршрутизації можуть бути внутредоменнимі і междоменнимі.

За способом отримання маршрутної інформації розрізняють алгоритми вектора відстані і алгоритми стану каналу.

Список літератури

Джон Вакка. Секрети безпеки в Internet. Переклад з англійської. - Київ; Диалектика, 1997г.

Джеймс Сайміно. Мережі інтранет: внутрішній рух. Перекладів з англійської. - М.: ТОВ «Бук Медіа Паблишер ». 1997р.

Володимир Зима. Безпека глобальних мережевих технологій/В.М. Зима, А.А. і Н.А. Молдавян. СПб и др.: БХВ - Санкт - Петербург, 2000 р.

Для підготовки даної роботи були використані матеріали з сайту http://www.ed.vseved.ru/