Источник: научные работы Донецкого национального технического университета. Серия: Вычислительная техника и автоматизация. Выпуск 106. - Донецк-2006. С. 45-50
Optimal routing algorithms in the complex topology network. The main purpose of this paper is to discus problems of multimedia traffic optimal routing in the complex topology network. The proposed
optimal routing algorithm allows to satisfy different customer's requests to quality of service and to save telecommunication administration's investments.
Забезпечення оптимальної маршрутизації в мережах складної топології є важливою задачею при проектуванні, модернізації та експлуатації телекомунікаційних мереж, бо дозволяє
найбільш раціонально використовувати ресурси мережі (пропускні здатності каналів зв'язку) при одночасному задоволенні різноманітних вимог користувачів. Розроблені на сьогоднішній
день методи і алгоритми маршрутизації засновані на різних підходах, залежно від типу мережі - з комутацією каналів або з комутацією пакетів. Для телефонних мереж, які побудовані як
мережі з комутацією каналів, використовується спрямування основного навантаження через прямі канали (або канали високого використання) та альтернативна маршрутизація через
транзитні вузли для надлишкового трафіку. Ємність пучків у прямому та транзитному напрямках розраховується за першою формулою Ерланга [1]. В інформаційних мережах, де здебільшого
використовується комутація пакетів, реалізовані різноманітні алгоритми маршрутизації, що відрізняються як критериіями оптимальності, так і здатністю до динамічної адаптації цих алгоритмів
до змін у топології мережі [2].
Різниця у підходах до маршрутизації обумовлювалась тим, що телекомунікаційні мережі проектувались для обслуговування двох різних типів трафіка: пакетного (даних) та мовного (реального часу).
Дійсно, усі додатки передачі даних донедавна висували до мережі з комутацією пакетів схожі вимоги з якості транспортного обслуговування: висока чутливість до втрат пакетів і невисока - до їх затримок.
А мовний трафік передавався виключно по мережах з комутацією каналів і висував обмеження на час затримки. Але тепер ситуація змінилася. Сьогодні по інформаційних мережах усе більше передають трафік
реального часу, наприклад, передача телефоних розмов через Інтернет VoIP (Voice over IP), відео-конференції, інтернет-радіо (internet radio), потокове відео (streaming video), інтерактивні ігри (interactive games) та
інше. Для більшості мультимедійних послуг критичним є такі параметри передачі пакетів через мережу, як затримка пакета впродовж усього маршруту від вузла-адресата до вузла-одержувача, дисперсія цієї затримки
(джитер), імовірність втрати пакетів. Ці змінені вимоги приводять до того, що виникає потреба або перебудовувати мережу, або шукати більш ефективні методи та алгоритми маршрутизації, які б оптимально
використовували існуючі ресурси мережі.
Тому дуже актуальною є задача розробки таких алгоритмів оптимальної маршрутизації для мереж складної топології, які б забезпечили з одного боку оптимальне використання існуючого обладнання, тобто збереження
вкладених операторами в мережу інвестицій, а з іншого - задоволення зростаючих вимог різноманітних користувачів до рівня якості мережних послуг.
Оптимальність тих чи інших алгоритмів маршрутизації оцінюється за різними критеріями. Найбільш поширені наступні:
Мінімальна кількість переходів - вартість використання маршруту вимірюється як кількість переходів (пройдені канали або вузли мережі) на найкоротшому маршруті. Згідно з цим пакети направлятимуться по шляху з найменшою кількістю можливих переходів.
Найкоротший шлях - кожний канал статично характеризується своєю вагою і вартість маршруту визначається як сума вагових коефіцієнтів кожного з каналів в маршруті. Згідно з цим пакети направлятимуться по шляху з найнижчою можливою вартістю маршруту.
Мінімальна затримка - кожний канал дінамічно характеризується ваговим коефіціентом в залежності від трафіка в каналі. Алгоритм з мінімальною затримкою багаторазово змінює таблиці маршрутизації так, що вибираються маршрути з мінімальною загальною затримкою.
Математичною моделлю телекомунікаційної мережі при вирішенні задачі маршрутизації є орієнтований граф, у якому кожна вершина позначає вузол комутації (маршрутизатор), а ребро графа - лінію зв'язку. Практично в усіх мережах вибір найкоротшого маршруту робиться згідно з крітерієм мінімальної вартості. Під вартістю розуміють як одиничні характеристики мережі, такі як фінансова вартість, кількість хопів (ретрансляційних ділянок), надійність, пропускна здатність каналу, затримка передачі інформації, так й інтегральні показники, які одночасно враховують усі ці компоненти. Вірно обрані метрики та правила їх комбінування є дуже важливим завданням при аналізі мережі.