Принципи маршрутизації

Найважливішою задачею мережного рівня є маршрутизація — передача пакетів між двома кінцевими вузлами в складеній мережі.

Розглянемо принципи маршрутизації на прикладі складеної мережі, зображеної на рисунку 4. У цій мережі 20 маршрутизаторів поєднують 18 мереж в загальну мережу; SI, S2, ... , S20 — це номера мереж. Маршрутизатори мають по декілька портів (принаймні, по два), до яких приєднуються мережі. Кожен порт маршрутизатора можна розглядати як окремий вузол мережі: він має власну мережну адресу і власну локальну адресу в тій підмережі, що до нього підключена. Наприклад, маршрутизатор під номером 1 має три порти, до яких підключені мережі SI, S2, S3. На малюнку мережні адреси цих портів позначені як М1(1), М1(2) і М1(3). Порт М1(1) має локальну адресу в мережі з номером S1, порт М1(2) — у мережі S2, а порт М1(3) — у мережі S3. Таким чином, маршрутизатор можна розглядати як сукупність декількох вузлів, кожний з який входить у свою мережу. Як єдиний пристрій маршрутизатор не має ні окремої мережної адреси, ні якої-небудь локальної адреси.

У складних складених мережах майже завжди існує декілька альтернативних маршрутів для передачі пакетів між двома кінцевими вузлами. Маршрут — це послідовність маршрутизаторів, що повинен пройти пакет відправника до пункту призначення. Так, пакет, відправлений з вузла А в вузол В, може пройти через маршрутизатори 17,12, 5,4 і 1 чи маршрутизатори 17, 6 і 3. Неважко знайти ще кілька маршрутів між вузлами А и В.

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

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

Таблиця 3 – Таблиця маршрутизації маршрутизатора 4

Номер мережі призначення	Мережна адреса наступного маршрутизатора	Мережна адреса вихідного порта	Відстань до мережі призначення	Примітка
S1	М1(2)	М4(1)	1
S2	-	М4(1)	0 (під’єднана)
S3	М1(2)	М4(1)	1
S4	М2(1)	М4(1)	1
S5	-	М4(2)	0 (під’єднана)
S6	М2(1)	М4(1)	2
Default	М5(1)	М4(2)	-

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

Коли на маршрутизатор надходить новий пакет, номер мережі призначення, вилучений з кадру, що надійшов, послідовно порівнюється з номерами мереж з кожного рядка таблиці. Рядок з номером мережі, що збігся, указує, на який найближчий маршрутизатор варто направити пакет. Наприклад, якщо на який-небудь порт маршрутизатора 4 надходить пакет, адресований у мережу S6, то з таблиці маршрутизації випливає, що адреса наступного маршрутизатора — М2(1), тобто черговим етапом руху даного пакета буде рух до порту 1 маршрутизатора 2.

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

Рисунок 4 – Принципи маршрутизації в складеній мережі

маршрутизатор, через який пролягає шлях до всіх цих мереж. Такий маршрутизатор називається маршрутизатором за замовчуванням, а замість номера мережі у відповідному рядку міститься особливий запис, наприклад default. У нашому прикладі таким маршрутизатором за замовчуванням для мережі S5 є маршрутизатор 5, точніше його порт М5(1). Це означає, що шлях з мережі S5 майже до всіх мереж великої складеної мережі пролягає через цей порт маршрутизатора.

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

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

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

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

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

Звернемося знову до мережі, зображеної на рисунку 4. Таблиця маршрутизації для кінцевого вузла В могла б виглядати в такий спосіб (таблиця 4). Тут MB — мережна адреса порту комп'ютера В. На підставі цієї таблиці кінцевий вузол В вибирає, на який із двох наявних у локальній мережі S3 маршрутизаторів варто посилати той чи інший пакет.

Таблиця 4 – Таблиця маршрутизації кінцевого вузла В

Номер мережі призначення		Мережна адреса наступного маршрутизатора		Мережна адреса вихідного порта		Відстань до мережі призначення		Примітка
S1		М1(3)		МВ		1
S2		М1(3)		МВ		1
S3		-		МВ		0

S4	М3(1)	МВ	1
S5	М1(3)	МВ	2
S6	М3(1)	МВ	2
Default	М3(1)	МВ	-

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

Нижче показана таблиця маршрутизації іншого кінцевого вузла складеної мережі – вузла А. (таблиця 5). Компактний вигляд таблиці маршрутизації показує той факт, що всі пакети, що направляються від вузла А, або не виходять за межі мережі S12, або обов’язково проходять через порт 1 маршрутизатора 17. Цей маршрутизатор і визначений в таблиці маршрутизації як маршрутизатор за замовчуванням.

В алгоритмах фіксованої маршрутизації всі записи в таблиці мршрутизації є статичними. Адміністратор мережі сам вирішує, на які маршрутизатори треба передавати пакети з тими чи іншими адресами, і вручну (наприклад, за допомогою утиліти route ОС Unix чи Windows NT) заносить відповідні записи в таблицю маршрутизації. Таблиця, як правило, створюється в процесі завантаження, надалі вона використовується без змін доти, поки її зміст не буде відредаговано вручну. Такі виправлення можуть знадобитись наприклад, якщо в мережі відмовляє який-небудь маршрутизатор і його функції покладаються на інший маршрутизатор. Розрізняють одномаршрутні таблиці, у яких для кожного адресата заданий один шлях, і багатомаршрутні таблиці, що визначають декілька альтернативних шляхів для кожного адресата. У багатомаршрутних таблицях повинне бути задане правило вибору одного з маршрутів. Частіше всього один шлях є основним, а інші — резервними. Зрозуміло, що алггоритм фіксованої маршрутизації з його ручним способом формування таблиць маршрутизації прийнятний тільки в невеликих мережах із простою топологією.

Таблиця 5 – Таблиця маршрутизації кінцевого вузла А

Номер мережі призначення	Мережна адреса наступного маршрутизатора	Мережна адреса вихідного порта	Відстань до мережі призначення	Примітка
S12	-	МА	0

Default

М17(1)

МА

-

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

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

Найбільш розповсюдженим протоколом, заснованим на дистанційно-векторному алгоритмі, є протокол RIP, що розповсюджений у двох версіях — RIP IP, що працює з протоколом IP, і RIP IPX, що працює з протоколом IPX..

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

Щоб зрозуміти, у якому стані знаходяться лінії зв'язку, підключені до його портів, маршрутизатор періодично обмінюється короткими пакетами HELLO зі своїми найближчими сусідами. Цей службовий трафік також засмічує мережу, але не в такому ступені як, наприклад, RIP-пакети, тому що пакети HELLO мають набагато менший обсяг.

Протоколами, заснованими на алгоритмі стану зв'язків, є протоколи IS-IS (Intermediate System to Intermediate System) стека OSI, OSPF (Open Shortest Path First) стека TCP/IP і недавно реалізований протокол NLSP стека Novell.