ЛЕКЦІЯ №7 Основи маршрутизації

План лекції:

  1. Поняття маршрутизації
  2. Маршрутні таблиці та протоколи маршрутизації
  3. Метрики протоколів маршрутизації.
  4. Поняття про алгоритм маршрутизації

 

1.Поняття маршрутизації

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

Тракт зв’язку, тракт передачі, комплекс технічного обладнання та ліній зв’язку, призначений для формування спеціалізованих каналів передачі інформації.

Рисунок 7.1 — Приклад шляху в мережі

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

Джίтер (англ. jitter — тремтіння) — небажані фазові та/або частотні випадкові спотворення під час передачі сигналу. 

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

Рисунок 7.2 —  Побудова об’єднаної мережі

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

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

Вибір протоколу маршрутизації (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-адрес у таблицях маршрутизації вказуються номери мереж, які зібрані в об’єднану мережу. Іншою відмінністю таблиць маршрутизації від адресних таблиць мостів є спосіб їхнього створення. У той час як міст будує таблицю, пасивно спостерігаючи за минаючими через нього інформаційними кадрами, що посилають через нього кінцеві вузли мережі один одному, маршрутизатори самі ініціюють обмін спеціальними службовими пакетами, повідомляючи сусідам про відомі їм мережі, маршрутизатори та про зв’язки цих мереж з маршрутизаторами. Крім топології зв’язків враховуватися при розрахунку шляхів може також і їхня пропускна здатність. Це дозволяє маршрутизаторам швидше адаптуватися до змін конфігурації мережі, а також правильно передавати пакети в мережах з довільною топологією, що допускає наявність контурів.

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

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

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

3 Метрики протоколів маршрутизації.

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

Рисунок 7.4 — Метрики маршрутизації

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

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

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

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

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

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

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


Контрольні питання:

  1. Надайте поняття маршрутизації.
  2. Що таке шлях(маршрут) ?
  3. Назвіть основні цілі маршрутизації.
  4. Надайте поняття маршрутної таблиці.
  5. Надайте поняття протоколу маршрутизації. Назвіть протоколи маршрутизації.
  6. Яка інформація зберігається у таблицях маршрутизації?
  7. Надайте поняття метрики протоколу маршрутизації.
  8. Надайте поняття динамічної та статичної маршрутизації.
  9. Надайте поняття алгоритму маршрутизації. Назвіть найпоширеніші алгоритми.

Література:

1 Буров Є. Комп’ютерні мережі. Підручник. Львів: БаК, 2018. — 256 с.

2       Маршрутизація: мета, основні задачі й протоколи, https://www.znanius.com/3820.html

3 Арсенюк І.Р., Яровий А.А. Комп’ютерні мережі, електроний підручник, https://web.posibnyky.vntu.edu.ua/fitki/3yarovijk_komp_merezhi/index.html