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

Рис. 1 Способи маршрутизації в мережах передачі даних.
Прийнято відрізняти централізовані та децентралізовані (розподілені) способи маршрутизації. У випадку централізованого способу маршрутизація здійснюється одним центром керування (менеджером мережі), який визначає напрямок руху пакетів через мережу передачі даних. Вузли комутації даної мережі приймають мінімальну участь у маршрутизації і мають відносно просту структуру. В свою чергу, при збільшенні числа вузлів зростає складність організації централізованого керування мережею передачі даних. Істотним недоліком централізованого керування є пряма залежність надійності мережі від надійності її менеджера, яка із зростанням складності останнього має тенденцію до зниження. Крім того, менеджер мережі повинен мати оперативну інформацію про стан мережі, так як вихід з ладу вузла або його перевантаження може призвести до втрати працездатності всієї мережі.
За розподіленого керування кожен вузол самостійно, на основі керуючої інформації, що зберігається в ньому, визначає напрямок передачі пакетів. Це приводить до зростання складності вузлів комутації. Однак система володіє більш високою живучістю, так як вихід з ладу будь-якого вузла комутації не тягне за собою втрату працездатності всієї мережі.
Далі відрізняють просту і табличну маршрутизацію. Проста маршрутизація реалізується без урахування топології і завантаження мережі передачі даних і, як правило, відрізняється низькою ефективністю. За табличної маршрутизації в кожному вузлі комутації формується спеціальна таблиця маршрутів, яка вказує, за яким шляхом може передаватися пакет із заданою адресою, щоб він в найкоротший термін досяг отримувача.
До простої маршрутизації відноситься випадкова та лавинна маршрутизації. Випадкова маршрутизація являє собою метод, за яким пакет передається з вузла в будь-якому, випадково вибраному напрямку, крім напрямку, за яким він надійшов до даного вузла. Існує кінцева ймовірність того, що пакет через визначений момент часу досягне адресата. Метод характеризується значним часом доставки пакетів і неефективним застосуванням перепускної здатності мережі. Проте, різні модифікації випадкової маршрутизації знаходять застосування в мережах з низькою інтенсивністю потоків у випадку необхідності забезпечення стійкої роботи мережі при виході з ладу окремих її компонентів. Можна запропонувати низку мір, які збільшують ефективність даного методу маршрутизації, наприклад, за повторного проходження пакету через вузол змінювати напрямок його подальшої передачі і тому подібне.
В основі лавинної маршрутизації лежить ефект розмноження пакетів, за яким вузол, отримавши пакет, генерує додаткові, ідентичні з ним пакети і передає їх у всіх напрямках, крім того, за яким надійшов пакет. Таким чином копії пакета лавиноподібно розповсюджуються по мережі. Перевагою метода є те, що він забезпечує мінімальну затримку розповсюдження пакетів, поскільки застосовуються всі шляхи через мережу, в тому числі і найкоротший, по якому і прийде перший пакет.
Подальшим розвитком способу простої маршрутизації слід вважати маршрутизацію за попереднім досвідом, за яким забезпечується корекція початково випадково вибраних маршрутів. З цією метою пакети додатково постачаються лічильником пройдених вузлів, на основі змісту якого формується адреса наступного вузла. Таким чином, на початковому етапі маршрутизації шлях прямування пакетів може визначатися випадковим чином, або способом лавинного заповнення пакетів, а потім, по мірі проходження наступних пакетів, шлях їх прямування коригується.
Табличні методи маршрутизації, залежно від моменту формування таблиць маршрутів, поділяються на статичні та динамічні. За статичної маршрутизації таблиці маршрутів формуються при генерації мережі і в наступному, як правило, не змінюються.
До статичних способів маршрутизації відносяться фіксована і маршрутизація способом найкоротшої черги. За фіксованої маршрутизації для будь-якої пари абонентських систем встановлюється одиночний або груповий канали передачі даних.
Маршрутизація способом найкоротшої черги передбачає наявність для кожного вузла комутації таблиці маршрутів з вказівкою декількох варіантів напрямку руху пакетів, за цим вибір конкретного шляху руху здійснюється випадковим чином.
Найефективнішими, але й найскладнішими є способи динамічної (адаптивної) маршрутизації. За динамічної (адаптивної) маршрутизації зміст таблиць маршрутів змінюється залежно від стану і завантаженості каналів передачі даних і вузлів комутації. Для адаптації до зміни навантаження кожний вузол комутації повинен володіти визначеною інформацією про стан мережі передачі даних і, в свою чергу, про її топологію, інтенсивність потоків даних і затримках (чергах) у вузлах комутації. Ця інформація відслідковується (збирається) за допомогою спеціальних керуючих пакетів, якими обмінюються вузли комутації. В загальному випадку найбільш оптимальна маршрутизація досягається за наявності інформації про миттєвий стан мережі та її завантаженості. Однак, це, як правило, призводить до значного збільшення потоку керуючих пакетів у мережі передачі даних і, в кінцевому підсумку, до зниження її ефективності.
Залежно від вибраної стратегії коригування маршрутів відрізняють: централізовану, локальну, розподілену і гібридну маршрутизацію.
У випадку централізованої адаптивної маршрутизації кожен вузол готує і у визначений момент передає менеджеру мережі інформацію про своє завантаження. На підставі цієї інформації менеджер складає глобальну картину стану мережі, і застосовуює її для визначення найкращих маршрутів прямування пакетів. В якості основного критерію оптимальності маршруту виступає час затримки передачі пакетів. Після вирахування оптимальних шляхів менеджер для кожного вузла комутації формує таблиці маршрутів, які далі розсилаються до відповідних вузлів мережі передачі даних.
Залежно від способу збирання інформації про стан мережі і розсилання керуючих директив процес маршрутизації може бути синхронним або асинхронним. У першому випадку збирання інформації і відправлення керуючих директив здійснюється через регулярні інтервали часу. У другому випадку ця процедура здійснюється тільки за істотних змін мережі передачі даних. Як правило, за синхронного режиму здійснюється більш інтенсивний режим обміну службовою інформацією, а за асинхронного режиму необхідний постійний контроль над зміною стану мережі. У всякому разі на менеджері мережі лежить основне навантаження по формуванню маршрутів, яке різко зростає із збільшенням числа вузлів мережі передачі даних. Загальним недоліком централізованих методів маршрутизації є втрата керування мережею під час виходу з ладу менеджера мережі, ймовірність виходу з ладу якого зростає із збільшенням навантаження на нього. Крім того, затримки, що викликані обміном і обробкою великого об’єму керуючої інформації, приводять до зниження ефективності керування мережею, особливо за швидкої зміни потоків даних.
Цих недоліків не мають методи розподіленого керування маршрутизацією, які і знайшли найбільш широке застосування в сучасних глобальних комп’ютерних мережах. Прикладом застосування методу розподіленої маршрутизації є комп’ютерна мережа ARPA, Агентства перспективних досліджень США.
За розподіленої адаптивної маршрутизації кожен вузол сам формує свою таблицю маршрутів, застосовуючи для цього інформацію, що отримується від вузлів, які знаходяться на можливих шляхах до отримувача. Вузли обмінюються інформацією про свій стан, часових затримках і чергах пакетів. При виборі маршрутів додатково враховується час, який потрібен для отримання позитивних підтверджень на попередні пакети. Таким чином, будь-яке істотне відхилення від початкового стану одразу ж передається суміжним вузлам для корекції їх таблиць маршрутів.
Одним з найпростіших варіантів розподіленої маршрутизації є локальна адаптивна маршрутизація, за якої вузол комутації практично сам вибирає маршрути передачі пакетів, не отримуючи інформації від інших вузлів. Таблиці маршрутів завантажуються завчасно, централізованим способом. В подальшому маршрут вибирається на основі відомостей про довжину вихідних черг і топології мережі передачі даних. Пакет направляється найкоротшим шляхом з мінімальною довжиною черги. В цілому, локальна адаптивна маршрутизація забезпечує високу гнучкість роботи мережі передачі даних, швидкий і ефективний метод вирішення проблеми обходу несправних або перевантажених вузлів. В той же час вона характеризується: складністю програми формування і обробки таблиці маршрутів; ймовірністю “автоколивань” і втратою пакета під час руху його при зміні таблиць маршрутів.
Найефективнішим методом маршрутизації слід вважати гібридну маршрутизацію, яка поєднує позитивні риси локальної і централізованої маршрутизації.
Різноманітність в способах маршрутизації пояснюється відсутністю деякого універсального способу, оптимального для різних програмних продуктів і характеристик мережі, а саме: рівня потоку даних, надійністю передачі, часом встановлення наскрізного (через мережу) з’єднання, швидкості передавання блоків даних і т.д.
Однією з основних задач більшості способів маршрутизації є знаходження найкоротшого шляху між відправником і отримувачем інформації. В якості критерію довжини шляху може бути час або вартість передачі інформації. До найрозповсюдженіших алгоритмів вибору найкоротшого шляху відносяться алгоритми Дейкстри і Форда-Фалкерсона. Результати роботи даних алгоритмів рівнозначно можуть застосовуватися для формування таблиць маршрутів, як для централізованого, так і для розподіленого алгоритму маршрутизації.