Завантажити PDF файл.

Формула / Реферат

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

Текст

Реферат: Спосіб маршрутизації з балансуванням навантаження в телекомунікаційних мережах здійснює багатошляхову маршрутизацію з балансуванням навантаження в каналах телекомунікаційних мереж (ТКМ). Крім цього, балансування навантаження здійснюється за середньою багатошляховою затримкою пакетів, коли задача маршрутизації розв'язується за умови, що в маршрутах передачі трафіку контурні складові середніх багатошляхових затримок прирівнюються до нуля. 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 В ході розв'язання задачі маршрутизації трафіком мінімізується максимальне завантаження каналів ТКМ: kK 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 kK 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>

Подібні патенти