Телекомунікаційні системи та мережі. Том 1. Структура й основні функції.  /  Зміст  /  Розділ 10. Технології та протоколи управління в ТКС   /  Тема 10.4. Підсистема мережного управління на рівнях транспорту й доступу

Зміст:

10.4.5. Маршрутизація: мета, основні задачі й протоколи

Визначення маршрутизації: базові поняття й терміни

Маршрутизація (routіng) є однією з ключових функцій мережного рівня ЕМВВС. При цьому під маршрутизацією розуміється, перш за все, процес визначення в телекомунікаційній мережі одного або множини шляхів (маршрутів), оптимальних у рамках обраних критеріїв, між заданою парою або множиною мережних вузлів. Таким чином, шлях (маршрут) — це послідовність мережних вузлів і трактів передачі, які з’єднують задану пару вузлів мережі (рис. 10.4.7).

Рис. 10.4.7. Приклад шляху в мережі

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

Мережний рівень за допомогою маршрутизації також реалізує функції об’єднання мереж, побудованих з використанням різнотипних технологій, що використовують різні принципи адресації, пересилання даних, управління (рис. 10.4.8). Для об’єднання мереж на третьому рівні ЕМВВС, як правило, використовується спеціальний пристрій — маршрутизатор мережі, який підтримує різні технології канального рівня (на рис. 10.4.8 технології Frame Relay і Fast Ethernet) і обробляє блоки даних мережного рівня. При такому підключенні протокольні особливості локалізуються в межах однієї ділянки мережі, а пересилання пакетів здійснюється на базі єдиного протоколу мережного рівня, який має бути налаштований на кожному кінцевому пристрої.

Рис. 10.4.8. Побудова об’єднаної мережі

Маршрутні таблиці та протоколи маршрутизації

Інформація про маршрути зберігається на маршрутизаторі у вигляді спеціальних інформаційних структур, які називаються маршрутними таблицями (МТ). Основна робота зі створення таблиць маршрутизації виконується автоматично, але передбачається й можливість корегування або доповнення їх вручну, тобто адміністративно. Для автоматичної побудови таблиць маршрутизатори обмінюються інформацією про топологію об’єднаної мережі у відповідності зі спеціальним службовим протоколом. Протоколи цього типу називаються протоколами маршрутизації або маршрутними протоколами.

Вибір протоколу маршрутизації (routіng protocols) — це досить складне та багатопланове завдання. Під час його розв’язання слід враховувати такі основні фактори:

  • розмір і зв’язність топології мережі (кількість мережних вузлів і трактів передачі, порядок їхнього з’єднання), а також планове зростання або зміну її структури;
  • характер і обсяг мережного трафіка;
  • підтримуваний рівень безпеки та надійності;
  • вимоги до якості обслуговування;
  • необхідність підтримки масок змінної довжини (VLSM).

На сьогодні на практиці паралельно функціонує у різних мережних технологіях ціла низка різноманітних за своїми функціональними можливостями протоколів маршрутизації. У мережах ІP успішно застосовуються протоколи RIP (Routing Information Protocol), IGRP (Internet Gateway Routing Protocol), Enhanced IGRP, OSPF (Open Shortest Path First), IS-IS (Intermediate System-to-Intermediate System), BGP (Border Gateway Protocol) та EGP (Exterior Gateway Protocol). У технології ATM підтримуються протоколи IISP (Interim Inter-Switch Protocol) і PNNI (Private Network — Network Interface). У стеку Novell функції маршрутизації реалізує протокол NLSP (NetWare Link Services (State) Protocol).

Маршрутні протоколи слід відрізняти від власне мережних протоколів, таких як ІP, ІPX або AppleTalk. І ті й інші забезпечують функції мережного рівня моделі OSІ, тобто беруть участь у доставці пакетів адресатові через різнорідну об’єднану мережу. Але в той час як перші збирають і передають мережею винятково службову інформацію, другі призначені для передачі користувальницьких даних так само, як це роблять протоколи канального рівня. Протоколи маршрутизації використовують мережні протоколи як транспортний засіб. Тому протокол маршрутизації — це протокол, який підтримує мережні протоколи й надає механізми обміну маршрутною інформацією. При обміні маршрутною інформацією пакети протоколу маршрутизації містяться в полі даних пакетів мережного або навіть транспортного рівня, тому з погляду вкладеності пакетів протоколи маршрутизації формально слід було б віднести до більш високого рівня, ніж мережний.

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

За допомогою протоколів маршрутизації маршрутизатори складають карту зв’язків мережі того чи іншого ступеня детальності. На підставі цієї інформації для кожного номера мережі приймається рішення про те, якому наступному маршрутизатору слід передавати пакети, що направляються за даною адресою, щоб маршрут виявився раціональним. Результати таких рішень заносяться в таблицю маршрутизації (рис. 10.4.9). Маршрутизатори зберігають і оновлюють таку важливу інформацію в таблицях маршрутизації:

  • тип протоколу, тобто інформацію про протокол маршрутизації, який зробив запис у таблиці маршрутизації;
  • зв’язку одержувач/наступний вузол, яка повідомляє маршрутизатору про те, що вузол-одержувач або підключений безпосередньо, або може бути досягнутий через інший маршрутизатор — наступний транзитний вузол (next hop), що перебуває на шляху до пункту призначення. Маршрутизатор аналізує адресу одержувача у вхідних пакетах і порівнює її на відповідність із записами в таблиці маршрутизації;
  • метрики маршрутизації (див. нижче);
  • вихідний інтерфейс — інтерфейс, через який мають бути відправлені дані, щоб досягти пункту призначення.

Рис. 10.4.9. Приклад маршрутної таблиці

Метрики протоколів маршрутизації. Критерієм вибору того чи іншого шляху між заданою парою вузлів мережі є мінімум або максимум його «довжини» (ваги, вартості), поданої у вигляді суми «довжин» трактів передачі, які цей шлях утворює. «Довжина» тракту передачі в термінах протоколів маршрутизації називається його метрикою (routіng metrіc). В існуючих протоколах маршрутизації залежно від особливостей розв’язуваної маршрутної задачі використовується досить широкий перелік метрик, які характеризують різні за своєю природою властивості того чи іншого тракту передачі, а саме його фізичну довжину, надійність, пропускну здатність, завантаженість, вартість й ін. (рис. 10.4.10).

Рис. 10.4.10. Метрики маршрутизації

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

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

  1. Оптимальність, яка характеризує здатність протоколу забезпечувати вибір найкращого в рамках певних критеріїв шляху (множини шляхів), наприклад, шлях з мінімальною кількістю переприйомів або шлях, який має максимальну пропускну здатність.
  2. Простота апаратно-програмної реалізації та мінімальні обсяги створюваного службового трафіка при зборі даних про стан ТКС або розсиланні інформації управління.
  3. Стійкість, яка характеризує здатність протоколу забезпечувати ефективне розв’язання маршрутних задач в умовах непередбаченої зміни умов функціонування мережі, наприклад, при відмові мережного обладнання, сплеску абонентського навантаження та ін..
  4. Висока оперативність одержання остаточних маршрутних рішень, особливо в умовах реалізації розподіленої маршрутизації, пов’язаної із забезпеченням збіжності відповідних обчислювальних алгоритмів з розрахунку шуканих шляхів.
  5. Адаптивність, пов’язана зі здатністю протоколу постійно (періодично) відстежувати та своєчасно реагувати на поточні зміни топології мережі, параметрів мережних вузлів (розміри черг) і трактів передачі (пропускна здатність, затримки, втрати пакетів), а також характеристик абонентського навантаження.
  6. Масштабованість, яка характеризує здатність протоколу виконувати визначені функції із заданою якістю при збільшенні розмірності мережі (числа мережних вузлів, трактів передачі та ін.).

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

Поняття про алгоритм маршрутизації

Розрахунок шляхів і формування маршрутних таблиць на мережних вузлах ТКС відбувається відповідно до реалізованого алгоритму (методу) маршрутизації. Алгоритм маршрутизації — це правило призначення вихідної лінії зв’язку даного мережного вузла ТКС для передачі пакета, що базується на інформації, яка міститься в заголовку пакета (адреси відправника та одержувача), а також інформації про завантаження цього вузла (довжина черг пакетів) і, можливо, ТКС у цілому.

Для розв’язання маршрутних задач у рамках існуючих протоколів запропоновано ряд комбінаторних алгоритмів, заснованих на графовому описі мережі зв’язку. Математична модель ТКС у цьому разі представляється зваженим орієнтованим графом G = (R, L), множину вершин якого складають мережні вузли, — множина дуг, яка моделює тракти передачі між вузлами мережі та потужність якої дорівнює n. Як вагові коефіцієнти окремо взятої дуги lij графа G виступають деякі дійсні числа dij, які називаються довжиною (метрикою) дуги. Тому довжина (метрика) орієнтованого шляху p = (lik, lk, g, ..., lm, j) між вузлами ri та rj може визначатися як

Тоді для будь-яких двох вузлів ri та rj графа задача найкоротшого шляху полягає в пошуку такого шляху між цими двома вузлами, який би мав мінімальну довжину (метрику). Наприклад, якщо dij — середня затримка в тому чи іншому тракті передачі, то найкоротший шлях між мережними вузлами ri та rj забезпечуватиме мінімальний час доставки пакетів. У випадку, коли dij — імовірність того, що тракт, який моделюється дугою lij, перебуває в працездатному стані та не залежить від стану інших трактів, то пошук найкоротшого шляху між вузлами ri та rj еквівалентний пошуку найбільш надійного шляху між цими вузлами з метриками дуг (–lndij).

Як правило, пошук найкоротшого шляху здійснюється за допомогою комбінаторних алгоритмів, тобто алгоритмів спрямованого перебору. Основною перевагою комбінаторних алгоритмів розв’язання завдання пошуку найкоротшого шляху є невисока та заздалегідь відома обчислювальна складність їхньої реалізації. Найефктивнішими та найпоширенішими з них є алгоритми Дійкстри (Dijkstra), Беллмана — Форда (Bellman-Ford), Флойда — Уоршела (Floyd-Warshall) та велика кількість різних їх модифікацій. При цьому перші два алгоритми знаходять найкоротші шляхи від обраного вузла-відправника пакетів до всіх інших вузлів, а третій алгоритм знаходить найкоротші шляхи від всіх вузлів до всіх інших вузлів.

Алгоритм Беллмана — Форда. Алгоритм Беллмана — Форда названий за іменами вчених (Bellman, 1957; Ford and Fulkerson, 1962), які першими опублікували ідею алгоритму. Власне ідея досить проста. Маршрутизатор зберігає в таблиці список усіх відомих маршрутів із вказівкою в кожному елементі таблиці мережі одержувача й цілого числа — кількості пересилань до цієї мережі. Періодично кожний маршрутизатор надсилає копію своєї таблиці іншим маршрутизаторам, до яких він має прямий доступ. Одержавши таку копію від маршрутизатора B, маршрутизатор A аналізує отриманий набір адресатів і відстаней до них. Маршрутизатор A заміняє дані у своїй таблиці, якщо маршрутизатору B відомий коротший, ніж наявний у ній, маршрут до одержувача, або якщо в його списку є невідомий йому дотепер маршрутизатор.

На підставі цієї таблиці, відповідно до алгоритму Беллмана — Форда, і розраховується значення метрики (наприклад вартості маршруту, затримки тощо) для кожного та здійснюється пошук мінімального сумарного числа пересилань. Поняття «вектор дистанцій» саме й пов’язане з характером інформації, що періодично передається протоколом інформації. У повідомленнях міститься пара чисел {R, D}, де R — вектор, який визначає вузол-одержувач, a D — відстань до цього вузла-одержувача, тобто один маршрутизатор повідомляє іншому про свою можливість досягти одержувача R за D пересилань.

Під час розрахунку найкоротших шляхів між заданим вузлом і всіма іншими вузлами довжини (метрики) дуг можуть бути як додатними, так і від’ємними, але передбачається, що немає циклів від’ємної довжини. Позначимо також, що dij = ∞, якщо в графі відсутня дуга lij. Послідовність кроків алгоритму Беллмана — Форда полягає в тому, щоб спочатку знайти довжини найкоротших шляхів, за умови, що шляхи містять не більше однієї дуги, потім розраховуються довжини найкоротших шляхів за умови, що шляхи містять не більше двох дуг тощо. Найкоротший шлях за умови, що шлях містить не більше h дуг, надалі називатиметься найкоротшим (≤ h) шляхом.

Нехай Di(h) — довжина найкоротшого (≤ h) шляху від вузла 1 до i-го вузла. Вважатимемо, що Di(h) = 0 для всіх h. Тоді, при ініціалізації алгоритму Беллмана — Форда, спочатку виконується така операція:

Di(0) = ∞ для всіх i ≠ 1.(10.4.1)

При кожному наступному h ≥ 0

(10.4.2)

Роботу алгоритму проілюстровано на рис. 10.4.11.

Число ітерацій алгоритму в найгіршому разі дорівнює (m – 1), кожна ітерація має бути проведена для (m – 1)-го вузла, а для кожного вузла мінімізація здійснюється якнайбільше за (m – 1)-ю змінною. Таким чином, у найгіршому разі обсяг обчислень зростає як m3, що записується у вигляді O(m3) Більш ретельний підрахунок свідчить, що обсяг обчислень дорівнює On), де n — число дуг, а α — максимальне число дуг, що міститься в найкоротшому шляху.

Почасти популярність алгоритму Беллмана — Форда пояснюється тим, що у разі, коли довжини всіх дуг додатні, початкові умови Di(0) для i ≠ 1 можуть бути будь-якими невід’ємними числами й ітерації (10.4.2) можуть виконуватися паралельно для різних вузлів, власне кажучи, у довільному порядку, що має велике значення для аплікацій з розподіленими алгоритмами. На використанні алгоритму Беллмана — Форда засновані протоколи вектора відстаней або дистанційно-векторні протоколи (Vector Distance Protocol), до яких, наприклад, належать протоколи RIP та IGRP.

Рис. 10.4.11. Ілюстрація роботи алгоритму Беллмана — Форда:
а — постановка задачі щодо визначення найкоротшого шляху із наведенням довжин дуг; б — перша ітерація: розрахунок найкоротших шляхів, що містять не більше однієї дуги; в — друга ітерація: розрахунок найкоротших шляхів, що містять не більше двох дуг; г — третя ітерація: розрахунок найкоротших шляхів, що містять не більше трьох дуг; д — результат розв’язання задачі: підсумкове дерево найкоротших шляхів

Алгоритм Дійкстри. Цей алгоритм вимагає, щоб довжини всіх дуг були додатні, що в сучасних мережах, як правило, виконується. Обсяг обчислень у найгіршому разі для цього алгоритму значно менший, ніж в алгоритмі Беллмана — Форда. Основна ідея алгоритму полягає в тому, щоб відшукувати найкоротші шляхи в порядку зростання їх довжини. Найкоротшим серед усіх найкоротших шляхів від вузла 1 є шлях, що складається з однієї дуги, що з’єднує вузол 1 з найближчим сусіднім вузлом, оскільки будь-який шлях, який складається з декількох дуг, буде завжди довшим ніж довжина першої дуги, внаслідок припущення про додатність всіх дугових довжин. Наступним найкоротшим серед найкоротших шляхів має бути або шлях з однієї дуги до наступного найближчого сусіда вузла 1, або найкоротший шлях із двох дуг, який проходить через вузол, обраний на першому кроці, тощо.

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

Таким чином, у рамках алгоритму Дійкстри на k-му кроці множина P складається з k найближчих вузлів до вузла 1. Серед усіх шляхів, що з’єднують вузол 1 з яким-небудь вузлом не з множини P, найкоротший шлях повинен пройти по вузлах з P (оскільки dij > 0). Тому (k + 1)-й найближчий вузол і відповідна найкоротша відстань отримуються мінімізацією за jP величини , у результаті чого обчислювальна складність алгоритму Дійкстри становитиме порядку O(m2).

Формально алгоритм Дійкстри працює в такий спосіб.

Ініціалізація алгоритму: P = {1}, D1 = 0 та Dj = d1j для j ≠ 1.

Крок 1: пошук наступного найближчого вузла.

Знайти iP, такий, що .

Покласти P:= P∪{i} Якщо P містить усі вузли, то на цьому робота алгоритму закінчується.

Крок 2: відновлення міток.

Для всіх jP покласти Dj:= min[Dj, Di + dij].

Перейти до кроку 1.

Робота цього алгоритму, а також алгоритму Беллмана — Форда проілюстрована на рис. 10.4.12.

Рис. 10.4.12. Приклад використання алгоритмів Беллмана — Форда та Дійкстри:
а — вихідна структура мережі: dij = dji для всіх lij;
б — робота алгоритму Беллмана — Форда; в — робота алгоритму Дійкстри

Оскільки число операцій, виконуваних алгоритмом Дійкстри на кожному кроці, пропорційно m, а кроки повторюються (m – 1) разів, то обсяг обчислень у найгіршому разі дорівнює O(m2), а не O(m3), як в алгоритмі Беллмана — Форда. Однак для слабозв’язних структур ТКС, у яких n << m2, алгоритм Беллмана — Форда закінчує свою роботу після досить малого числа ітерацій (α << m), у цьому разі обсяг обчислень On) може бути набагато менше, ніж O(m2) алгоритму Дійкстри.

Алгоритм розрахунку найкоротшого шляху, запропонований Дійкстри, покладений в основу протоколів стану каналу, які одержали свою назву від відповідного алгоритму маршрутизації (Link State Algorithm, LSA). До таких протоколів належать, насамперед, протоколи OSPF, PNNI, IS-IS.

Алгоритм Флойда — Уоршелла. Алгоритм Флойда — Уоршелла (R.W.Floyd, S.A.Warshall) на відміну від двох вище розглянутих алгоритмів знаходить найкоротші шляхи відразу для всіх пар вузлів. Як і в алгоритмі Беллмана — Форда, довжини дуг можуть бути як додатними, так і від’ємними, але також не повинно бути циклів від’ємної довжини. У всіх трьох алгоритмах остаточне рішення отримується методом ітерацій, але в кожному алгоритмі число ітерацій залежить від різних величин. Якщо в алгоритмі Беллмана — Форда число ітерацій залежить від числа дуг у шляху і в мережі в цілому, а в алгоритмі Дійкстри — від числа вузлів у мережі, то в алгоритмі Флойда — Уоршелла число ітерацій прямо залежить від кількості вузлів, які допускається використовувати як проміжні вузли на шуканих шляхах. Як і раніше описані алгоритми, алгоритм Флойда — Уоршелла починає свою роботу з розрахунку шляхів, які складаються з однієї дуги (тобто без проміжних вузлів), обраних як вихідні оцінки для довжин найкоротших шляхів. Потім обчислюються найкоротші шляхи з тим обмеженням, що проміжним вузлом може бути тільки вузол 1, потім з обмеженням, що проміжними вузлами можуть бути тільки вузли 1 і 2 тощо.

З метою більш строгого опису алгоритму позначимо через Dij(k) довжину найкоротшого шляху від i-го вузла до j-го вузла при обмеженні, що тільки вузли 1, 2, …, k можуть використовуватися як проміжні вузли на шляху. Формально алгоритм Флойда — Уоршелла працює в такий спосіб.

Крок 1: ініціалізація алгоритму: Dij(0) = dij для ∀i, j (ij).

Крок 2: для k = 0, 1, ..., m – 1,

Dij(k + 1) = min[Dij(k), Di(k + 1)(k) + D(k + 1)j(k) для ∀i, j (ij).

Оскільки кожний з кроків відбувається для кожної пари вузлів, то обсяг обчислень для алгоритму Флойда — Уоршелла дорівнює O(m3) тобто такий же, як і в алгоритмі Дійкстри, повтореного для всіх вузлів, обраних як відправник.

Недоліки алгоритмів пошуку найкоротшого (тобто єдиного) шляху між кожною парою вузлів у мережі пов’язані з обмеженими можливостями забезпечення збалансованого завантаження мережі та якості обслуговування одночасно за декількома показниками, оскільки кожному тракту передачі мережі ставилося у відповідність усього одне число (довжина, метрика), пов’язане з тим або іншим одним показником QoS. Відзначені недоліки послужили поштовхом до досить інтенсивних розробок у напрямку вдосконалення розглянутих алгоритмів.

Огляд протоколів маршрутизації

Протокол RIP. RIP (Routing Information Protocol) — один з перших протоколів внутрішньої маршрутизації, що застосовувалися в Інтернеті (1982 р.). Перша версія протоколу RIP описана в специфікації RFC 1058, а друга (RIP ver. 2) — в специфікації RFC 2453. В цьому протоколі метрикою є кількість пересилань між вузлами (hops). Ця метрика не забезпечує облік пропускної здатності, надійності та завантаженості трактів передачі, а також характеристик трафіка користувачів.

RIP — це протокол дистанційно-векторної маршрутизації, що ґрунтується на використанні вектора відстаней (Distance Vector). Він не дозволяє забезпечити функціонування широкомасштабних мереж через обмеженість числа пересилань (hops) до 15. Для пошуку шляху використовується алгоритм Беллмана — Форда. Цей протокол застосовувався для перших маршрутизаторів Інтернету, побудованих на міні-ЕОМ типу Honeywell 516 (8-розрядні мікропроцесори типу Intel 8080 або Zilog Z80).

Робота протоколу RIP заснована на широкомовному розсиланні повідомлень про коректування маршрутів. Періодичність розсилання оновлень — 30 с. Розсилаються повні копії таблиць маршрутизації незалежно від того, змінені вони чи ні. RIP схильний до утворення петель у розрахованих маршрутах. У RIPv2 допускається балансування навантаження на шляхах з рівною «довжиною» (вартістю).

Протоколи IGRP/EIGRP. Протокол IGRP (Interior Gateway Routing Protocol) і його розширена версія EIGRP (Enhanced Interior Gateway Routing Protocol) розроблені в корпорації Cisco. І якщо протокол IGRP — це дистанційно-векторний протокол, то EIGRP — протокол змішаного типу.

Протокол IGRP розроблений у середині 1980-х рр. і заснований на широкомовному розсиланні повідомлень із подальшим використанням періодичних таймерів (90 с). Розсилаються повні копії своїх маршрутних таблиць. У цьому протоколі використовується комбінована метрика, заснована на обліку пропускної здатності каналу, часової затримки, надійності каналу і його завантаженості. Протокол ІGRP підтримує до 255 пересилань.

Балансування навантаження в протоколі ІGRP може здійснюватися на шляхах з однаковою та різною «вартістю». Сам трафік розподіляється по різних шляхах пропорційно їх «вартості». Балансування навантаження на шляхах з однаковою вартістю здійснюється автоматично, а для використання шляхів з різною вартістю необхідна додаткова конфігурація та настроювання обладнання (команди варіантності/розбіжності — varіance).

Протокол EIGRP розроблено на початку 1990-х рр. і є спробою сумістити переваги дистанційно-векторних протоколів і протоколів стану каналів. У ньому залишилися від IGRP без зміни максимальне число пересилань (225) і типи використовуваних метрик. Для усунення петель у маршрутах і оперативному реагуванні на зміни в мережі використовується алгоритм дифузійного оновлення DUAL (Distributed Update Algotithm). EIGRP не використовує періодичні оновлення про стан мережі, а використовує інкрементні оновлення (incremental updates).

Протокол OSPF (Open Shortest Path First) належить до класу протоколів стану каналів (Link State Protocol). Дослівний переклад — першим обирається найкоротший шлях. «Open»-специфікація протоколу вільно поширюється, на відміну, наприклад, від специфікації протоколу EIGRP. RFC 2328 — основний діючий документ по OSPF.

Окрім того, протокол OSPF дозволяє визначити для будь-якої мережі значення метрики залежно від типу послуги TOS (Type of Service). В OSPF підтримуються метрики пропускної здатності та затримки. Метрика, що оцінює пропускну здатність каналу, визначається, наприклад, компанією Cisco, як кількість секунд, необхідних для передачі 100 Мбіт. Метрика затримки — час у мікросекундах, необхідний маршрутизатору для обробки, постановки в чергу та передачі пакетів. Для кожної з метрик протокол OSPF будує окрему таблицю маршрутизації. Стандартний порядок розрахунку метрики, що оцінює показники надійності, затримки й вартості, поки не визначений. Цей порядок визначається адміністратором.

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

Протокол IS-IS (Intermediate System — to — Intermediate System) є продуктом ISO на базі мережної архітектури DECNet Phase V. Попередником протоколу IS-IS є протокол маршрутизації DPR (DECNet Routing Protocol). У термінології ISO «проміжна система» (intermediate system, IS) — маршрутизатор мережі, а «кінцева система» (end system, ES) — хост.

Існує також протокол ES-IS для організації обміну інформації в ланці «кінцева система» — «проміжна система». IS-IS успішно функціонує в мережах, що містять понад 500 маршрутизаторів. IS-IS — протокол стану каналів (зв’язків).

IS-IS сам по собі не підтримує протокол ІP, тому використовують інтегрований IS-IS (Integrated IS-IS). Протокол IS-IS стандартизовано і в рамках IETF: в RFC 1142 «OSI IS-IS Intra-domain Routing Protocol», а також у RFC 1195 «Use of OSI IS-IS for routing in TCP/IP and dual environments» (використання протоколу IS-IS у мережах TCP/IP і в двопротокольному середовищі).

Основна адитивна метрика протоколу IS-IS — число, яке не перевищує 1024 для маршруту та 64 для окремого каналу. Ця метрика встановлюється адміністратором. Також використовуються такі три типи метрик: затримка (delay); вартість передачі по каналу, що характеризує комунікаційні витрати (expense); помилки (error). IS-IS підтримує можливість задавати в полі QoS пакета співвідношення між цими чотирма метриками.

Протокол EGP. Окрім того, у сучасних мережних технологіях, що підтримують ієрархічні структури маршрутизаторів, виділяються логічні групи вузлів, називані доменами, автономними системами (AS) або областями, у рамках яких реалізуються єдині принципи адміністрування. Для здійснення маршрутизації в межах подібних доменів можуть використовуватися спеціальні протоколи — протоколи внутрішньодоменної маршрутизації. Для організації маршрутизації між різними доменами використовуються протоколи міждоменної маршрутизації. Подібний розподіл характерний для ІP-мереж, у рамках яких за аналогією виділяються протоколи внутрішнього (Interior Gateway Protocols, IGP) та зовнішнього (Exterior Gateway Protocols, EGP) шлюзу. На відміну від IGP-протоколів RIP, IGRP, EIGRP, OSPF, які в IP-мережах використовуються як внутрішньодоменні, протоколи EGP (Exterior Gateway Protocol) та BGP (Border Gateway Protocol) є міждоменними протоколами (рис. 10.4.13).

Рис. 10.4.13. Внутрішньодоменна та міждоменна маршрутизація

Протокол EGP описано в RFC 904 (квітень 1984). EGP служить для організації зв’язку між приграничними маршрутизаторами в мережі Інтернет, які, у свою чергу, належать різним автономним системам. Необхідно враховувати, що для зв’язку з маршрутизаторами всередині своєї автономної системи приграничний маршрутизатор, окрім підтримки EGP, також має підтримувати протоколи класу IGP, оскільки всю інформацію про свою автономну систему протокол EGP одержує від IGP-протоколів.

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

Протокол BGP. Протокол BGP розроблений компаніями IBM і Cisco. BGP описано в документах RFC-1267, BGP-3; RFC-1268; RFC-1467, RFC 1771 (BGP-4: -1265-66, 1655). Він призначений для забезпечення маршрутизації без зациклень пакетів як між автономними системами, так і в межах однієї подібної системи. Не всі вузли, що використовують протокол BGP, є маршрутизаторами, навіть якщо обмінюються маршрутною інформацією із приграничним маршрутизатором сусідньої автономної системи.

BGP використовує протокол транспортного рівня для передачі службової інформації. Це підвищує надійність, оскільки протоколи транспортного рівня спроектовані для гарантованої доставки інформації. Як транспортний протокол застосовується TCP. Спочатку маршрутизатори, що працюють за протоколом BGP, обмінюються повними таблицями маршрутів, потім розсилаються тільки оновлення при змінах у таблицях. На відміну від інших протоколів, BGP не вимагає періодичного оновлення таблиць маршрутизації, натомість зберігаються останні версії таблиць сусідів. Хоча протокол обслуговує всілякі шляхи в певну мережу, у своїх повідомленнях про оновлення (updates messages) він розсилає інформацію тільки про найкращий шлях.

Протокол BGP здатний виявляти зациклення маршрутизації та має гнучкі можливості визначення стратегії маршрутизації й агрегування маршрутів, тобто логічного об’єднання кількох ІP-мереж в одну «супермережу», що дозволяє значно скорочувати розміри таблиць маршрутизації. Основи агрегування маршрутів в Інтернеті описані в RFC 2519.

Основна мета BGP — маршрутизація транзитного трафіка. Місцевий трафік або починається, або завершується в автономній системі; в іншому випадку це транзитний трафік. Системи без транзитного трафіка не мають потреби в BGP (їм достатньо EGP для спілкування із транзитними вузлами). Зараз BGP поступово витісняє EGP з мережі Інтернет.

Протокол PNNI. Ще одним із протоколів стану каналу є протокол PNNI (Private Network — Network Interface). Слід зазначити, що цей протокол розроблявся для підтримки специфікації QoS в ATM (стандарт RFC 2386). Архітектура АТМ сама по собі є QoS-сумісною, яка підтримує всі метрики, необхідні для забезпечення постійного рівня сервісу маршрутизації. Базовими метриками протоколу PNNI є: адміністративний ваговий коефіцієнт (Administrative Weight, AW) — довільно обирана адміністратором вартість; доступна швидкість передачі чарунок (Available Cell Rate, AvCR) — пропускна здатність лінії; максимальна затримка передачі чарунок (Maximum Cell Transfer Delay, MaxCTD) — затримка передачі чарунок в каналі; відсоток втрат (Cell Loss Ratio, CLR) — середня кількість загублених під час передачі чарунок; розкид затримки (Cell Delay Variation, CDV); підсумкова метрика, яка дорівнює різниці відсотка втрат каналу та відсотка втрат оточення; максимальна швидкість передачі (Maximum Cell Rate, MaxCR), максимальна пропускна здатність каналу. Всі названі метрики можуть призначатися адміністратором або динамічно, або статично. За допомогою цих метрик протокол маршрутизації PNNІ обчислює придатність обраного шляху для доставки чарунок до місця призначення.

Технологія інжинірингу трафіка

Одним з потужних методів впливу на ефективне використання ресурсів мережі є технологія Traffіc Engіneerіng (TE) або в дослівному перекладі «інжиніринг трафіка». У вузькому значенні, яке найбільше відповідає назві, під TE розуміються методи та механізми досягнення збалансованості завантаження всіх ресурсів мережі за рахунок раціонального вибору шляхів проходження трафіка через мережу. Механізм управління трафіком надає можливість установлювати явний шлях, за яким прямуватимуть потоки даних.

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

Ще один істотний недолік традиційних методів маршрутизації трафіка в існуючих ТКС полягає в тому, що шляхи обираються без урахування поточного завантаження ресурсів мережі. Якщо найкоротший шлях уже перевантажений, то пакети однаково надсилатимуться саме цим шляхом. Класичним прикладом неефективності такого підходу є так звана «риба» — мережа з топологією, наведеною на рис. 10.4.14. Незважаючи на те, що між вузлами А та Е існує два шляхи (верхній — через комутатор B і нижній — через комутатори С і D), весь трафік від вузла А до вузла Е відповідно до традиційних принципів маршрутизації прямує тільки за верхнім шляхом. Тільки тому, що нижній шлях (на одну ретрансляційну ділянку) довший, ніж верхній, він ігнорується, хоча міг би працювати «паралельно» з верхнім шляхом.

Рис. 10.4.14. Приклад неефективності використання найкоротших шляхів на топології «риба»

У мережі, поданій на рис. 10.4.14, верхній шлях продовжуватиме використовуватися навіть тоді, коли його ресурсів не вистачатиме для обслуговування трафіка від вузла А до вузла Е, а нижній шлях простоюватиме, хоча, можливо, ресурсів вузлів D, С і каналів зв’язку між ними вистачило б для якісної передачі пакетів цього трафіка. Цей приклад, який є типовим для сучасних ТКС, демонструє очевидні недоліки існуючих методів розподілу ресурсів мережі — одні ресурси працюють із перевантаженням, а інші не використовуються зовсім. Традиційні методи боротьби з перевантаженнями цю проблему розв’язати не можуть, тому стали потрібні якісно інші механізми.

Методи інжинірингу трафіка. Вихідними даними для методів інжинірингу трафіка є:

  • характеристики транспортної мережі — її топологія, а також продуктивність складових її вузлів і каналів зв’язку (рис. 10.4.15);
  • відомості про запропоноване навантаження мережі, тобто про потоки трафіка, які мережа має передати між своїми приграничними вузлами (рис. 10.4.16).

Рис. 10.4.15. Топологія мережі та продуктивність її ресурсів

Рис. 10.4.16. Запропоноване навантаження на мережу

Нехай продуктивність процесора кожного мережного вузла достатня для обслуговування трафіка всіх його вхідних інтерфейсів, навіть якщо трафік надходить на інтерфейс із максимально можливою швидкістю, що дорівнює пропускній здатності інтерфейсу. Тому при резервуванні ресурсів вважатимемо ресурсами пропускну здатність каналів зв’язку між вузлами, що визначає також пропускну здатність двох інтерфейсів, пов’язаних цим каналом. У свою чергу, кожний потік характеризується точкою входу в мережу, точкою виходу з мережі та профілем трафіка. Для отримання оптимальних рішень можна використати детальний опис кожного потоку, наприклад враховувати величину можливої пульсації трафіка або вимоги щодо QoS. Однак оскільки кількісно оцінити їхній вплив на роботу мережі досить складно, то для визначення субоптимального розподілу шляхів проходження потоків через мережу, як правило, враховуються тільки їхні середні швидкості передачі пакетів, що й показано на рис. 10.4.16.

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

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

Максимальний рівень використання ресурсів обирається таким чином, щоб механізми контролю перевантаження могли забезпечити необхідну якість обслуговування. У найбільш примітивному вигляді це полягає у тому, що для еластичного трафіка максимальне значення завантаженості мережного ресурсу вибирається не більше ніж 0,9, а для чутливого до затримок трафіка — не більше ніж 0,5. Оскільки на практиці резервування здійснюється не для всіх потоків, то потрібно залишити частину пропускної здатності для вільного використання. Тому наведені максимальні значення зазвичай зменшують до 0,75 і 0,25 відповідно. Наведені для прикладу числові значення обираються емпіричним шляхом, хоча в перспективі для їх розрахунку необхідно використовувати теоретично обґрунтовані адаптивні процедури.

Найчастіше використовують на практиці таку постановку та розв’язання задачі ТЕ: визначити такий набір маршрутів для заданої множини потоків трафіка, для якого всі значення коефіцієнтів використання ресурсів уздовж маршруту проходження кожного потоку не перевищують деякого заданого порога Kmax. На рис. 10.4.17 показано один з варіантів розв’язання цієї задачі для вихідних даних з рис. 10.4.15 і 10.4.16. Знайдені маршрути гарантують, що максимальний коефіцієнт використання будь-якого ресурсу для будь-якого потоку не перевищує 0,6.

Рис. 10.4.17. Розподіл навантаження по мережі з вибором шляхів проходження трафіка

Розв’язання задачі ТЕ можна здійснювати по-різному:

  • у фоновому режимі (завчасно). Для цього потрібно знати максимальне (рекомендоване) значення коефіцієнта використання ресурсу та вихідні дані про стан мережі: топологію та продуктивність мережі, а також імовірні вхідні й вихідні точки потоків трафіка та середню швидкість передачі даних у них. Тоді розв’язання задачі ТЕ полягає у розрахунку шуканих маршрутів при фіксованих вихідних даних;
  • в оперативному режимі задача ТЕ, ґрунтуючись не на ймовірному, а на реальному профілю трафіка, розв’язується в реальному масштабі часу на вузлах мережі з використанням модифікацій існуючих протоколів маршрутизації. Модифікація протоколів маршрутизації полягає в тому, що вони повідомляють один одному не тільки топологічну інформацію, але й поточне значення вільної пропускної здатності кожного мережного ресурсу.

Після того як рішення знайдено, необхідно його реалізувати, тобто втілити в таблицях маршрутизації. На цьому етапі може виникнути проблема — у тому разі, якщо необхідно ці маршрути прокласти в мережі з дейтаграмним режимом передачі пакетів. Справа в тому, що таблиці маршрутизації цих мереж ураховують тільки адреси призначення пакетів. Вузли таких мереж (наприклад, ІP-мереж) не працюють із потоками, для них потік у явному вигляді не існує, кожний пакет при його просуванні є незалежною одиницею комутації. Можна сказати, що таблиці просування цих мереж описують тільки топологію мережі (напрямок просування до певних адрес призначення). Тому привнесення методів резервування в дейтаграмні мережі відбувається з великими труднощами, а на практиці методи інжинірингу трафіка сьогодні використовуються лише в мережах з віртуальними каналами, для яких не становить складності реалізувати знайдене рішення для групи потоків. Кожному потоку (або групі потоків з однаковими маршрутами) виділяється віртуальний канал, який прокладається відповідно до обраного маршруту. Методи інжинірингу трафіка успішно застосовуються в мережах ATM і Frame Relay, що працюють на основі техніки віртуальних каналів. Існує також технологія MPLS, яка розроблена спеціально як засіб привнесення техніки віртуальних каналів в ІP-мережі. В MPLS-мережах уже використовуються або планується використовувати модифіковані протоколи маршрутизації та сигналізації з відповідною приставкою ТЕ. На призначенні та задачах протоколів сигналізації, які використовуються для розв’язання задач забезпечення QoS, зупинимося в наступному підрозділі.