Методи маршрутизації

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

Маршрутизація (routing) – пошук (оптимального) маршруту для передавання мережевого пакета.

Маршрутизатор (router) – мережевий пристрій для маршрутизації. Маршрутизатор визначає маршрут передавання даних між мережами з од­наковою та різною топологією та протоколами. Для визначення маршруту використовують поняття метрики.

Метрика – це умовна вартість передавання мережею. Повний вимір конкретного маршруту дорівнює сумі метрик мереж, які включають в себе маршрут. Маршрутизатор вибирає маршрут із найменшою метрикою. Метрика для мережі призначається залежно від типу протоколу маршрутизації – комбінації правил і процедур, які дозволяють марш­ру­тизаторам інформувати один одного про зміни в мережі. Протоколи маршрутизації також включають процедури для комбінування інформації, отриманої від інших маршрутизаторів. Деякі прості протоколи, наприклад протокол маршрутної інформації RIP (Routing Information Protocol), розглядають всі мережі як однакові. Тоді вартість проходження через кожну мережу одна й та сама, і для визначення метрики підраховуються ділянки. Тобто якщо пакет, для досягнення кінцевого пункту, проходить через 10 мереж, повна вартість становить 10 ділянок. Інші протоколи, такі як OSPF (Open Shortest Path First), дозволяють адміністратору призначити вартість для передавання мережею, засновану на типі необхідного обслу­говування. Маршрут через мережу може мати різну вартість (метрику). Наприклад, якщо для типу сервісу бажана максимальна продуктивність, супутниковий канал має меншу метрику, ніж оптична лінія. З іншого боку, якщо типом сервера бажана мінімальна затримка, оптична лінія має меншу метрику, ніж супутниковий канал. OSPF дозволяє кожному марш­ру­ти­за­тору мати таблицю послідовностей маршрутів, засновану на необхідному ти­пі сервісу. У протоколі маршрутизації BGP (Border Gateway Protocol) прин­цип, за яким визначається шлях, може встановлювати адміністратор [61].

У будь-якій метриці маршрутизатор повинен мати таблиці маршрутизації, щоб визначити подальше передавання пакета. Таблиця маршрутизації задає оптимальний шлях для пакета. Таблиця може бути статичною або динамічною. Статична таблиця – не змінюється та потребує ручного складання та коригування. Динамічна таблиця – оновлюється автоматично, коли в мережі є зміни. Сьогодні Internet потребує динамічних таблиць. Їх потрібно оновити, коли маршрут вийшов з ладу або коли створюється кращий маршрут [61].

Сьогодні Internet – це величезна мережа, тому один протокол марш­рутизації не може обробляти задання оновлення таблиць всіх марш­ру­тизаторів. З цієї причини Internet поділяється на автономні системи. Автономна система (Autonomous System – AS) – група мереж і марш­ру­тизаторів під управлінням одного адміністратора. Маршрутизація всередині автономної системи належить до внутрішньої маршрутизації. Маршру­тизація між автономними системами належить до зовнішньої марш­ру­тизації. Кожна автономна система може обрати протокол внутрішньої маршрутизації для того, щоб обробляти маршрутизацію всередині авто­номної системи. Однак для оброблення маршрутизації між автономними системами вибирається лише один протокол маршрутизації. RIP і OSPF ви­ко­ристовуються для оновлення таблиць маршрутизації всередині авто­ном­ної системи. Протокол BGP застосовується в оновленні таблиць марш­ру­тизації для маршрутизаторів, які об’єднують разом автономні системи [61].

Є такі методи маршрутизації: статичні та динамічні, центра­лізовані,децентралізовані тазмішані.

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

При динамічному управлінні маршрутизація здійснюється за допо­могою змінної таблиці маршрутизації. Маршрутизатор може сам визначати нові шляхи або модифікувати інформацію про старі. При цьому корекція даних про маршрути між станціями і збір інформації для прийняття рішень можуть бути проведені централізованими і децентралізованими методами [81].

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

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

При змішаному управлінні рішення про вибір маршруту прий­мається вузлом з урахуванням рекомендацій центру управління.

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

При однокроковій маршрутизації кожен компонент мережі, що бере участь в передаванні інформації, самостійно визначає, якому наступному компоненту, що знаходиться в зоні прямого доступу, вона повинна бути відправлена. Рішення приймається на підставі аналізу адреси одержувача, яка міститься в пакеті. Повний маршрут передавання даних складається з однокрокових рішень, прийнятих компонентами мережі. Для роботи ал­го­ритмів однокрокової маршрутизації, які є основою відповідних протоколів, на кожному компоненті мережі, що має можливість передавати інфор­ма­цію більш ніж одному компоненту, зазвичай будується спеціальна таблиця маршрутів. У найпростішому випадку кожний запис такої таблиці містить: адресу обчислювального комплексу одержувача; адресу компонента ме­ре­жі, безпосередньо приєднаного до даного, якому слід відправити пакет, призначений для цього одержувача; вказівка про те, якою лінією зв’язку (яким мережевим адаптером) повинен бути відправлений пакет. Одер­жувачів у мережі може бути дуже багато, тому в таблиці маршрутизації використовують певні скорочення. Числові адреси топологічно близько розташованих комплексів (наприклад, комплексів, що належать одній локальній обчислювальній мережі) намагаються обирати з послідовного діапазону адрес. У цьому випадку запис у таблиці маршрутизації може містити не адресу конкретного одержувача, а діапазон адрес для деякої мережі (номер мережі). Якщо для дуже багатьох одержувачів як черговий вузол маршруту використовується один і той самий компонент мережі, а інші маршрути обираються для обмеженого числа одержувачів, то до табли­ці явно заносяться лише записи для цієї невеликої кількості одержува­чів, а для маршруту, що веде до більшої частини всієї мережі, робиться один запис – маршрутизація за замовчуванням (default)(табл. 4.3) [80].

Таблиця 4.3 – Проста таблиця маршрутизації

Адреса одержувача	Адреса наступного компонента	Адреса лінії зв’язку
5 – 12
1 – 4
default

За способами формування та використання таблиць маршрутизації алгоритми однокрокової маршрутизації можна розділити на три класи [80]:

- алгоритми фіксованої маршрутизації;

- алгоритми простої маршрутизації;

- алгоритми динамічної маршрутизації.

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

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

Найбільш гнучкими є алгоритми динамічної або адаптивної маршру­тизації, які вміють оновлювати вміст таблиць маршрутів на основі оброб­лення спеціальних повідомлень, що надходять від інших компонентів мережі, які займаються маршрутизацією. Адаптивна маршрутизація перед­бачає пристосування алгоритму маршрутизації до реального стану мережі. Недоліком методів адаптивної маршрутизації є складність прог­нозування стану мережі. Зараз використовуються такі основні методи адаптивної маршрутизації [16, 19, 28]:

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

- метод якнайшвидшого передавання. Його мета – якнайшвидше передавання пакета. В методі використовується глобальна інформація про наявність та довжину черг до вихідних каналів;

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

- розподілена маршрутизація. У кожному вузлі зберігаються табли­ці маршрутизації, в яких вказані маршрути до кожного з адресатів із міні­мальною затримкою. Спочатку ці таблиці будують на підставі теоретичних обчислень за відомою топологією, а потім ці дані поновлюються з використанням спостережень. У мережі при цьому завжди існує трафік маршрутизації (до 50 % трафіку);

- дистанційно-векторна маршрутизація. Компоненти операційних систем на сусідніх обчислювальних комплексах мережі, які займаються вибором маршруту, періодично обмінюються векторами, які явля­ють собою інформацію про відстані від даного компонента до всіх відомих йому адресатів у мережі. Під відстанню звичайно розуміється кількість переходів між компонентами мережі (hops), які необхідно зробити, щоб досягти адресата, хоча можливе існування й інших метрик, що включають швидкість та/або вартість передавання пакета лінією зв’язку. Кожен такий вектор формується на підставі таблиці маршрутів. Вектори модерні­зу­ються з урахуванням відстані, яку вони пройшли при останньому переда­ван­ні. Потім до таблиці маршрутизації вносяться зміни так, щоб в ній містилися лише маршрути з найкоротшими відстанями. При досить тривалій роботі кожен маршрутизатор буде мати таблицю маршрутизації з оптимальними маршрутами до всіх потенційних адресатів. Векторно-дистанційна маршрутизація може бути ефективна тільки у відносно неве­ликих мережах, оскільки є можливість виникнення маршрутних петель при збоях у роботі мережі [80];

- маршрутизація стану зв’язку застосовується для великих мереж. На кожному маршрутизаторі будують таблиці маршрутизації. Маршру­тизатори періодично обмінюються таблицями і вносять до них зміни. Вибір маршруту пов’язаний з пошуком оптимального за вартістю шляху.

Будь-яку комп’ютерну мережу зручно подати у вигляді графу, де вершини графу – це вузли мережі, а ребра графу – лінії зв’язку між вузлами (рис. 4.2).

Рисунок 4.2 – Графічне подання КМ

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

Алгоритм маршрутизації повинен мати такі властивості: надійність, коректність, стабільність, простота і оптимальність. Опти­мальність залежить від параметрів, за якими проводиться оптимізація. Це складне задання навіть для порівняно простих локальних мереж. Серед параметрів оптимізації може бути мінімальна затримка доставки, макси­мальна пропускна здатність, мінімальна ціна, максимальна надійність, мінімальна ймовірність втрати пакета, максимальна безпека, мінімальна ймовірність помилки та ін. [82].

Алгоритми маршрутизації бувають адаптивні (динамічні) і неадап­тивні (статичні). Статичні алгоритми, здійснюючи вибір маршруту, не беруть до уваги існуючу в даний момент топологію або завантаження кана­лів. Адаптивні періодично вимірюють характеристики каналів і постійно досліджують топологію маршрутів. Більшість алгоритмів враховують то­пологію зв’язків, а не їх якість (пропускну здатність, завантаження, якість та ін.). У деяких мережах потоки між вузлами відносно стабільні і перед­бачувані. У цьому випадку з’являється можливість обчислити оптимальну схему маршрутів заздалегідь [82].

Головним параметром при маршрутизації пакета в Internet є IP-адреса його місця призначення. IP ділить всі ЕОМ на маршрутизатори і звичайні ЕОМ, останні, як правило, не розсилають свої маршрутні таблиці. Передбачається, що маршрутизатор має вичерпну інформацію про правильні маршрути. Звичайна ЕОМ має мінімальну маршрутну інфор­мацію (наприклад, адресу маршрутизатора локальної мережі і сервера імен). Проблема оптимальної маршрутизації в Internet досить складна. Розміри маршрутних таблиць ростуть експоненціально. У загальному ви­пад­ку для формування оптимального маршруту потрібно мати вичерп­ну інформацію про всі мережеві сегменти. Це реально лише для локальних мереж малого чи середнього розмірів. Слід також враховувати, що ситуація в мережі постійно змінюється і маршрутизатори для вирі­шен­ня завдань мають обмежені ресурси часу. На практиці оптимізація здій­сню­­ється для обмеженої області сегментів, тоді і обсяг даних, що підля­гають обробленню, скорочується на багато порядків. Тому результуючий маршрут не завжди буде оптимальним.

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

Зазвичай обчислювальні мережі використовують суміш різних стра­те­гій маршрутизації. Для одних адрес призначення може викори­стову­ва­тися фіксована маршрутизація, для інших – проста, для третіх – динамічна. У локальних обчислювальних мережах часто використовуються алгоритми фіксованої маршрутизації, на відміну від глобальних обчислювальних мереж, в яких в основному застосовують алгоритми адаптивної маршру­тизації. Протоколи маршрутизації належать до мережевого рівня еталонної моделі [80].

Дата добавления: 2014-01-20