Спосіб балансування навантаження в телекомунікаційних мережах з неоднорідною структурою

Реферат: Спосіб балансування навантаження в телекомунікаційних мережах з неоднорідною структурою, що здійснює управління багатошляховою маршрутизацією та забезпечує ефективне балансування навантаження в рамках моделі маршрутизації з балансуванням навантаження для телекомунікаційних мереж з неоднорідною структурою. Розв'язання задачі управління трафіком здійснено шляхом використання підходу "за підмережами", в рамках якого задача управління трафіком в ході розв'язання задачі маршрутизації з балансуванням навантаження розв'язується окремо для кожної підмережі, на які умовно розбивається мережа з неоднорідною структурою таким чином, щоб зв'язність маршрутизаторів в підмережах була вища, ніж між підмережами. UA 76563 U (12) UA 76563 U UA 76563 U 5 10 15 20 25 30 Корисна модель належить до галузі електрозв'язку і є технологією управління трафіком, може знайти застосування на приграничних вузлах (маршрутизаторах і комутаторах третього рівня) транспортної телекомунікаційної мережі (ТКМ) при вирішенні задач маршрутизації для забезпечення збалансованої завантаженості каналів ТКМ з неоднорідною структурою. Відомий спосіб управління трафіком в ТКМ (див. Wang Y., Wang Z. Explicit routing algorithms for Internet Traffic Engineering // Proc. of 8th International Conference on Computer Communications and Networks. Paris, 1999. - P. 582-588) полягає в тому, що на основі використання потокової багатопродуктової багатополюсної моделі ТКМ розв'язується задача маршрутизації з балансуванням навантаження у каналах зв'язку. В рамках даного способу управління трафіком в ході його маршрутизації покращується рівень балансування завантаження каналів зв'язку. Як відомо, чим вищий рівень балансування навантаження, тим кращі значення показників якості обслуговування, в тому числі середня затримка та рівень втрат пакетів. В рамках відомого способу відбувається розрахунок шляхових потоків таким чином, що їх значення приймають збалансований характер в ході розв'язання оптимізаційної задачі щодо мінімізації максимального завантаження каналів ТКМ. Найкращі результати управління трафіком в рамках відомого способу досягаються для мереж з однорідною структурою, де зв'язність вузлів мережі приблизно однакова. При управлінні трафіком для мереж з неоднорідною структурою, на базі яких переважно і побудовані транспортні ТКМ, мінімізація максимального завантаження каналів зв'язку не завжди призводить до максимального підвищення якості обслуговування, що обумовлено присутністю в мережі "вузьких місць" - каналів з найменшою пропускною здатністю. Значення завантаженості каналу в "вузькому місці" приймає найбільше своє значення серед значень навантажень на інших частинах мережі, що, у свою чергу, перешкоджає мінімізації завантаженності інших каналів, приводячи до їх необґрунтованого зростання, тим самим погіршуючи якість обслуговування. Найбільш близьким до запропонованого технічного рішення є спосіб управління трафіком (див. патент US № 7.889.661 В2, МПК H04L 12/28, публ. 29.05.2003), який забезпечує розв'язання задачі багатошляхової маршрутизації з балансуванням навантаження в рамках моделі маршрутизації з балансуванням навантаження в каналах ТКМ. В рамках способу-прототипу ТКМ описується за допомогою орієнтованого графа G  ( V,E) , де V - це множина вузлів ТКМ, а E - множина каналів. Пропускна здатність каналу E ij ТКМ, який з'єднує вузли Vi та V j (E ij  E) , позначена через c ij . Кожному k-му трафіку з множини K (k  K ) відповідає ряд параметрів: dk , s k , t k - інтенсивність k-го трафіку, вузол-джерело та вузол-отримувач відповідно. Керуючою змінною виступає величина x k , яка характеризує частку ij 35 k-го трафіку, що проходить через канал E ij  E . У відповідності до фізики задачі, на змінні x k ij накладаються обмеження: 0  x k  1. ij (1) Щоб не допустити втрат на мережних вузлах та у мережі в цілому, забезпечується виконання умов збереження потоку: 40    x k   x k  0, k  K, i  s k , t k Eij E ij Eij E ij   k k . (2) ,   x ij   x ij  1 k  K, i  s k Eij E Eij E  k k ,   x ij   x ij  1 k  K, i  t k Eij E Eij E  Крім цього, складовою моделі є умова забезпечення відсутності перевантаження у каналах зв'язку:  k K dk x k  c ij , E ij  E , ij (3) де  - динамічно керований поріг завантаження каналів ТКМ (максимальне завантаження), на який накладаються наступні обмеження: (4) 0    1. 1 UA 76563 U 5 10 15 20 25 30 35 40 45 50 55 В ході розв'язання задачі управління трафіком мінімізується максимальне завантаження каналів ТКМ  : (5)   min. Недоліки способу-прототипу обумовлені його централізованим характером рішень при розв'язанні задач управління трафіком для мереж з неоднорідною структурою, що знижує якість балансування навантаження в окремих частинах ТКМ, а також погіршує числові значення показників якості обслуговування. В основу корисної моделі поставлена задача створити спосіб маршрутизації в телекомунікаційній мережі, який в рамках балансування навантаження забезпечить підвищення якості обслуговування для мереж з неоднорідною структурою, в яких зв'язність вузлів ТКМ може суттєво різнитися. Ця задача вирішена таким чином. У способі балансування навантаження в телекомунікаційних мережах з неоднорідною структурою, що здійснює управління багатошляховою маршрутизацією та забезпечує ефективне балансування навантаження в рамках моделі маршрутизації з балансуванням навантаження для телекомунікаційних мереж з неоднорідною структурою, згідно з запропонованою корисною моделлю, розв'язання задачі управління трафіком здійснено шляхом використання підходу "за підмережами", в рамках якого задача управління трафіком в ході розв'язання задачі маршрутизації з балансуванням навантаження розв'язується окремо для кожної підмережі, на які умовно розбивається мережа з неоднорідною структурою таким чином, щоб зв'язність маршрутизаторів в підмережах була вища, ніж між підмережами. З метою адаптації рішення для мереж з неоднорідною структурою запропоновано змінити підхід до розв'язання задачі маршрутизації, а саме: розв'язувати задачу маршрутизації не у рамках централізованого методу, як в способі-прототипі, а в рамках методу "за підмережами". При такому підході задача маршрутизації в рамках моделі (1)-(5) розв'язується окремо для кожної підмережі, на які можна розбити мережу. Такий підхід дозволяє отримати більш високу якість балансування навантаження в підмережах мережі, тим самим покращити числові значення основних показників якості обслуговування (середню затримку, джитер, рівень втрат пакетів). Розв'язання задачі управління трафіком в рамках запропонованого способу "за підмережами" здійснюється наступним чином: 1. Телекомунікаційна мережа умовно розбивається на підмережі таким чином, щоб зв'язність вузлів в підмережах була вища, ніж між підмережами. 2. Для кожної підмережі окремо формалізується та розв'язується задача управління трафіком в рамках моделі (1)-(5) в ТКМ. 3. Оцінюється якість балансування в підмережах та в ТКМ в цілому. На фіг. 1-5 показані результати порівняльного аналізу запропонованого методу зі способомпрототипом. Для прикладу була вибрана топологія ТКМ, представлена на фіг. 1, де трафік передавався від вузла-відправника 1 до вузла-одержувача 9. На структурі ТКМ позначені пропускні здатності каналів зв'язку (1/с). На фіг. 2 показано порівняння якості балансування для всієї мережі в рамках способу-прототипу та способу "за підмережами" в залежності від інтенсивності трафіку, що надходить до мережі (1/с). Для мережі в цілому якість балансування у способі "за підмережами" не підвищується, та в рамках кожної підмережі маємо суттєве покращення якості балансування (фіг. 3, 4). На фіг. 5 наведено порівняльні залежності середньої затримки пакетів від інтенсивності трафіку, що надходить в ТКМ. Для розрахунку середніх затримок пакетів канали зв'язку мережі моделювалися, як приклад, у вигляді системи масового обслуговування М/М/1. Як показали результати досліджень, якість обслуговування в результаті управління трафіком в ході розв'язання задачі маршрутизації в рамках запропонованого методу "за підмережами" тим вище, чим вища неоднорідність мережі (чим зв'язність в підмережах вище зв'язаності між підмережами). У наведеному прикладі (фіг. 5) середні затримки пакетів зменшувалися у середньому на 25-30 %. Таким чином, запропонована корисна модель дозволяє отримати більш високу якість балансування навантаження в підмережах мережі, внаслідок чого значно покращаться числові значення основних показників якості обслуговування (середня затримка, джитер, рівень втрат пакетів). 2 UA 76563 U ФОРМУЛА КОРИСНОЇ МОДЕЛІ 5 10 Спосіб балансування навантаження в телекомунікаційних мережах з неоднорідною структурою, що здійснює управління багатошляховою маршрутизацією та забезпечує ефективне балансування навантаження в рамках моделі маршрутизації з балансуванням навантаження для телекомунікаційних мереж з неоднорідною структурою, який відрізняється тим, що розв'язання задачі управління трафіком здійснено шляхом використання підходу "за підмережами", в рамках якого задача управління трафіком в ході розв'язання задачі маршрутизації з балансуванням навантаження розв'язується окремо для кожної підмережі, на які умовно розбивається мережа з неоднорідною структурою таким чином, щоб зв'язність маршрутизаторів в підмережах була вища, ніж між підмережами. 3 UA 76563 U Комп’ютерна верстка М. Ломалова Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4