Спосіб маршрутизації з балансуванням навантаження в телекомунікаційних мережах
Номер патенту: 84986
Опубліковано: 11.11.2013
Автори: Гаркуша Сергій Володимирович, Вавенко Тетяна Василівна, Євсєєва Оксана Юріївна, Стерін В'ячеслав Леонідович, Лемешко Олександр Віталійович
Формула / Реферат
Спосіб маршрутизації з балансуванням навантаження в телекомунікаційних мережах, що здійснює багатошляхову маршрутизацію з балансуванням навантаження в каналах ТКМ, який відрізняється тим, що балансування навантаження здійснюється за середньою багатошляховою затримкою пакетів, коли задача маршрутизації розв'язується за умови, що в маршрутах передачі трафіку контурні складові середніх багатошляхових затримок прирівнюються до нуля.
Текст
Реферат: Спосіб маршрутизації з балансуванням навантаження в телекомунікаційних мережах здійснює багатошляхову маршрутизацію з балансуванням навантаження в каналах телекомунікаційних мереж (ТКМ). Крім цього, балансування навантаження здійснюється за середньою багатошляховою затримкою пакетів, коли задача маршрутизації розв'язується за умови, що в маршрутах передачі трафіку контурні складові середніх багатошляхових затримок прирівнюються до нуля. UA 84986 U (54) СПОСІБ МАРШРУТИЗАЦІЇ З БАЛАНСУВАННЯМ НАВАНТАЖЕННЯ В ТЕЛЕКОМУНІКАЦІЙНИХ МЕРЕЖАХ UA 84986 U UA 84986 U 5 10 15 20 25 30 Корисна модель належить до галузі електрозв'язку і є технологією маршрутизації трафіку, може знайти застосування на приграничних вузлах (маршрутизаторах і комутаторах третього рівня) транспортної телекомунікаційної мережі (ТКМ) при розв'язанні задач маршрутизації для забезпечення збалансованого навантаження каналів мережі та покращення якості обслуговування. Відомий спосіб маршрутизації з балансуванням навантаження в ТКМ (див. Wang Υ., Wang Ζ. Explicit routing algorithms for Internet Traffic Engineering // Proc. of 8th International Conference on Computer Communications and Networks. Paris, 1999. - P. 582-588) полягає в тому, що на основі використання потокової багатопродуктової багатополюсної моделі ТКМ розв'язується задача маршрутизації з балансуванням навантаження у каналах зв'язку. В рамках даного способу в ході маршрутизації трафіку здійснюється балансування навантаження за критерієм мінімізації коефіцієнта максимального завантаження каналів ТКМ. Це обумовлено тим, що чим менш завантажені канали ТКМ, тим кращі значення показників якості обслуговування, в тому числі середня затримка та рівень втрат пакетів. Однак дослідження відомого способу маршрутизації з балансуванням навантаження показали, що мінімізація завантаження каналів зв'язку не завжди призводить до максимального підвищення якості обслуговування, особливо це було помічено для мереж з напівдуплексними та дуплексними каналами зв'язку, а також для мереж з неоднорідною структурою, представлених розділимим графом (див. Лемешко А.В. Усовершенствование потоковой модели многопутевой маршрутизации на основе балансировки нагрузки [Электронный ресурс] /А.В. Лемешко, Т.В. Вавенко // Проблеми телекомунікацій. - 2012. - № 1 (6). С. 12 29. Режим доступа к журн.: http://pt.journal.kh.ua/2012/1/1/12 l_lemeshko_ multipath.pdf). Крім того, балансування навантаження в рамках відомого способу призводить до зростання джитера пакетів, викликаного реалізацією багатошляхової стратегії маршрутизації, тобто середні затримки пакетів вздовж різних шляхів можуть суттєво різнитись. Найбільш близьким до запропонованого технічним рішенням є спосіб маршрутизації трафіку (див. патент US № 7.889.661 В2, МПК H04L 12/28, публ. 29.05.2003), в рамках якого розв'язується задача багатошляхової маршрутизації з балансуванням навантаження в каналах ТКМ. В рамках способу-прототипу ТКМ описується за допомогою орієнтованого графа G=(V, Е), де V - це множина вузлів ТКМ, а Е - множина каналів. Пропускна здатність каналу E ij Eij E ТКМ, який з'єднує вузли Vi та Vj, позначена через сij. 35 Кожному k-му трафіку з множини K k K відповідає ряд параметрів: dk, sk, tk - інтенсивність kго трафіку, вузол-джерело та вузол-отримувач відповідно. Керуючою змінною виступає величина xk ij , яка характеризує частку k-го трафіку, що проходить через канал Eij E . У k відповідності до фізики задачі на змінні x ij накладаються обмеження: (1). 0 xk 1 ij Щоб не допустити втрат пакетів на мережних вузлах та у мережі в цілому, забезпечується виконання умов збереження потоку: xk xk 0, k K, i sk , tk ij ji Eij E E ji E k k , xij x ji 1 k K, i sk , E ji E Eij E k k , xij x ji 1 k K, i tk . E ji E Eij E 40 (2) Крім цього, складовою способу є умова забезпечення відсутності перевантаження у каналах зв'язку: dk xk c ij,Eij E ij (3) , де - динамічно керований поріг завантаження каналів ТКМ (максимальне завантаження), на який накладаються наступні обмеження: (4). 0 1 В ході розв'язання задачі маршрутизації трафіком мінімізується максимальне завантаження каналів ТКМ: kK 45 1 UA 84986 U 5 10 15 20 25 (5). min Як показало дослідження, недоліки відомого способу належать і до недоліків способупрототипу. В основу винаходу поставлена задача створити спосіб балансування навантаження в ході розв'язання задачі багатошляхової маршрутизації в телекомунікаційній мережі, який забезпечить підвищення якості обслуговування на підставі використання інших критеріїв при балансуванні навантаження, наприклад критеріїв, пов'язаних безпосередньо з показниками якості обслуговування. Для цього у способі маршрутизації з балансуванням навантаження в телекомунікаційних мережах, згідно з запропонованою корисною моделлю, пропонується відмовитися від мінімізації максимального навантаження каналів ТКМ, як в способі-прототипі, а здійснювати балансування навантаження за середньою багатошляховою затримкою пакетів. При такому підході з метою отримання мінімальної та однакової для всіх шляхів середньої затримки пакетів в запропонованому способі контурні складові по середніх багато шляхових затримках для кожного трафіку k K прирівнюються до нуля, це також сприяє мінімізації джитеру пакетів, який обумовлений реалізацією багатошляхової стратегії маршрутизації, та забезпечує відсутність петель (Лемешко А.В. Тензорная модель многопутевой маршрутизации агрегированных потоков с резервированием сетевых ресурсов, представленная в пространстве с кривизной //Праці УНДІРТ. Випуск № 4 (40). - Одеса: Видання УНДІРТ, 2004. - С. 12-18): k (6), конт. 0 k де конт. - вектор контурних затримок, координати якого визначають суму затримок вздовж кожного незалежного контуру в ТКМ. Кількість незалежних контурів визначається наступних виразом: r=n-m+1, (7) де n - кількість каналів зв'язку, m - кількість вузлів ТКМ. Наприклад, в структурі телекомунікаційної мережі з фіг. 1 є два незалежних контури, а умова (6) для даного випадку набуває вигляду: k конт.1 1,2 2,4 3,4 1,3 ; k конт.2 2,5 4,5 2,4 , де ikj - середня затримка пакетів k-го трафіку в каналі Eij E . , Умова забезпечення відсутності перевантаження у каналах зв'язку (3) набуває вигляд: dk xk c ij,Eij E ij kK 30 35 40 45 (8). При цьому в ході розв'язання задачі маршрутизації змінюється цільова функція (5), а саме мінімізується лінійна форма: (9), min f t X k де X - вектор з координатами x ij , а f - вектор маршрутних метрик ТКМ, . t - операція транспонування матриці. В результаті проведеного дослідження математичної моделі, яка покладена в основу запропонованого способу маршрутизації з балансуванням навантаження в телекомунікаційних мережах, за формулами (1)-(3), (6), (8), (9), при різних вихідних даних було встановлено, що значення показників якості обслуговування при розв'язанні задачі маршрутизації в рамках запропонованого способу кращі, ніж при розв'язанні задачі маршрутизації в рамках способупрототипу (див. формули (1)-(5)). Результати порівняльного аналізу запропонованого способу зі способом-прототипом для структур телекомунікаційних мереж, показаних на фіг. 1-3, представлені на фіг. 4-6 відповідно. Для всіх структур трафік передавався від вузла з найменшим номером до вузла з найбільшим. На структурах ТКМ (фіг. 1-3) позначені пропускні здатності каналів зв'язку (1/с), а також незалежні контури. Порівняльний аналіз був проведений за показником середньої багатошляхової затримки, за яку бралось найбільше значення серед середніх затримок вздовж розрахованих маршрутів (див. Chen J.-C, Chan S.H. Multipath Routing for Video Unicast over Bandwidth-Limited Networks Department of Computer Science // Proc. of GLOBECOM'01: San Antonio, Texas - Vol. 3. - 2001. - p. 1963-1997). Результати аналізу представлені на фіг.4-6. Процес обслуговування в окремих каналах, як приклад, моделювався за допомогою системи масового обслуговування М/М/1. Якщо модель обслуговування змінюється, це вимагає зміни 2 UA 84986 U 5 10 умов (6), однак це не впливає на загальні результати щодо отримання мінімальної та однакової затримки для всіх шляхів, а також забезпечення відсутності петель. Як показали результати досліджень, якість обслуговування в результаті балансування навантаження в ході розв'язання задачі маршрутизації в рамках запропонованого способу за критерієм середньої багатошляхової затримки тим краще, чим більше шляхів проходження трафіку між відправником та отримувачем. Так, у наведених прикладах середні багатошляхові затримки пакетів зменшувалися у середньому на 5-13 % для ТКМ з трьома (фіг. 4), на 15-27 % для ТКМ з чотирма шляхами (фіг. 5), на 20-34 % для ТКМ з п'ятьма шляхами (фіг. 6). При цьому отримано мінімальну та однакову затримку для всіх шляхів, що сприяє мінімізації джитеру пакетів, який обумовлений реалізацією багатошляхової стратегії маршрутизації, а також забезпечується відсутність петель. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 15 20 Спосіб маршрутизації з балансуванням навантаження в телекомунікаційних мережах, що здійснює багатошляхову маршрутизацію з балансуванням навантаження в каналах ТКМ, який відрізняється тим, що балансування навантаження здійснюється за середньою багатошляховою затримкою пакетів, коли задача маршрутизації розв'язується за умови, що в маршрутах передачі трафіку контурні складові середніх багатошляхових затримок прирівнюються до нуля. 3 UA 84986 U 4 UA 84986 U Комп’ютерна верстка С. Чулій Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5
ДивитисяДодаткова інформація
Автори англійськоюLemeshko Oleksandr Vitaliiovych, Vavenko Tetiana Vasylivna, Yevsieieva Oksana Yuriivna, Harkusha Serhii Volodymyrovych
Автори російськоюЛемешко Александр Витальевич, Вавенко Татьяна Васильевна, Евсеева Оксана Юрьевна, Гаркуша Сергей Владимирович
МПК / Мітки
МПК: G06G 3/00
Мітки: мережах, маршрутизації, балансуванням, телекомунікаційних, спосіб, навантаження
Код посилання
<a href="https://ua.patents.su/7-84986-sposib-marshrutizaci-z-balansuvannyam-navantazhennya-v-telekomunikacijjnikh-merezhakh.html" target="_blank" rel="follow" title="База патентів України">Спосіб маршрутизації з балансуванням навантаження в телекомунікаційних мережах</a>
Попередній патент: Установка для виготовлення теплоізоляційного волокнистого матеріалу
Наступний патент: Секатор
Випадковий патент: Верстат висічний