Спосіб управління чергами на маршрутизаторах мультисервісної телекомунікаційної мережі

Реферат: Спосіб управління чергами на маршрутизаторах мультисервісної телекомунікаційної мережі, включає обслуговування черг шляхом їх оптимального балансування. При цьому балансування здійснюють завдяки мінімізації верхнього порогу завантаженості множин черг з врахування пріоритетів та довжини пакетів. UA 70088 U (12) UA 70088 U UA 70088 U 5 10 15 20 25 30 Корисна модель належить до технологій управління трафіком і може бути використана в маршрутизаторах телекомунікаційних мереж (ТКМ) для забезпечення балансування навантаження буферного ресурсу мережного вузла. Відомі способи обслуговування черг (див. Шринивас Вегешна. Качество обслуживания в сетях IP. - Μ.: Издательский дом "Вильяме", 2003, С. 89), які здатні забезпечити диференціювання потоків трафіку на основі їх пріоритету, довжини пакета на рівні алгоритму планування черг. Недоліком відомих способів обслуговування черг є те, що обслуговування черг практично не узгоджується з рішенням інших задач по управлінню трафіком (маршрутизація, резервування та розподілення канального ресурсу та ін.). Крім того, залишається автоматизованим лише процес опитування черг (roundrobin), а рішення задач по їх формуванню та визначенню порядку проходження пакетів з черги у канал зв'язку все ще носить переважно статичний характер, тобто розв'язується адміністративно. Найбільш близьким до запропонованого технічним рішенням, вибраним як прототип, є спосіб (див. Huerta, Μ., Padilla, J. J., Hesselbach, X., Fabregat, Ramon, Ravelo O. Buffer Capacity Allocation: A method to QoS support on MPLS networks // Proc. EATIS2006 - Euro American Conference on Telematics and Information Systems, 2006. - P. 14-28.), що включає обслуговування черг, яке відбувається шляхом їх оптимального балансування. Основним недоліком даного способу є те, що він не враховує під час балансування навантаження пріоритет пакетів, що оброблюються, та їх довжину. В основу корисної моделі поставлена задача створити спосіб управління чергами, який покращить показники якості обслуговування в МРLS-мережах шляхом управління чергами, яке полягає у балансуванні навантаження на принципах технології інжинірингу трафіку (Traffic Engineering Queues). Поставлена задача досягається тим, що у способі управління чергами на маршрутизаторах мультисервісної телекомунікаційної мережі, що включає обслуговування черг, яке відбувається шляхом їх оптимального балансування, відповідно до корисної моделі, здійснюють балансування завдяки мінімізації верхнього порогу завантаженості множин черг з врахування пріоритетів та довжини пакетів, які обслуговуються, що сприяє більш якісному обслуговуванню пакетів трафіку з меншою довжиною та більшим пріоритетом. Зміст заявленого способу пояснюється наступним. Позначимо через Μ кількість окремих трафіків або агрегованих по класах чи пріоритетах потоків, через N - максимальну кількість черг на мережному вузлі. Позначимо через аi i  1,  інтенсивність трафіку i-го класу, що надходить на обслуговування до мережного вузла, bj j  1  - частина пропускної здатності вихідного каналу зв'язку, яка виділена j-й черзі j  1  . , ,  35        Одна з ключових відмінностей полягає в тому, що змінні bj. j  1,  будуть розраховуватися динамічно, адаптуючись до змін стану мережного вузла. У ході управління чергами необхідно виконати умову відсутності перевантаження каналу зв'язку:  b j  b, (1) j 1 40 де b - пропускна здатність вихідного каналу зв'язку. З метою запобігти перевантаженню мережного вузла необхідно забезпечити виконання наступної умови:  a b (2) . Введення управляючої змінної хij, що являє собою долю і-го трафіку, яка надходить на обслуговування в j-у чергу надає динамічний характер процесу обслуговування черг у рамках запропонованої моделі. Згідно з фізичним змістом хij мають місце наступні умови: (3) x ij  0,1 i  1 , j  1  , , , i i 1 45   x ij  1, i  1,   ,   (4) j 1  ai xij  b j , ) j  1,   .  5) i 1 1 UA 70088 U Виконання умови (4) гарантує відсутність втрат пакетів в мережному вузлі. Умова (5) вводиться для запобігання перевантаження пропускної здатності каналу зв'язку, що виділяється для передачі пакетів тієї чи іншої черги мережного вузла у процесі управлення. Шуканий вектор має вигляд: x ij bj 5 i  1, ; j  1, , (6) у ході розрахунку якого забезпечується узгодженість в рішенні задач обслуговування черг і динамічного розподілу за ними пропускної здатності вихідного каналу зв'язку. Позначивши поточну завантаженість і максимальну ємкість кожної черги через n j i nmax j відповідно, визначимо їх значення: j  1  n j  nmax j  1  . , , j  10   (7) Головна задача полягає у виборі аналітичного виразу для розрахунку середньої довжини черги у процесі обслуговування. Для формулювання шуканих умов необхідно задатися моделлю трафіку та моделлю обслуговування пакетів у рамках окремо взятої черги, за яку на практиці реалізується схема FIFO (First In - First Out). Замінивши нерівність (7) на часову умову, отримаємо: (8)  j   max j  1  , , j  15   де середня затримка обслуговування  у черзі розраховується за відомою середньою довжиною пакета на основі формули Літтла. Це дозволило отримати умову (8) в більш детальному вигляді nj     ai x ij   ,  max j  1  . j (9) i 1 20 Для відповідності отриманих рішень принципам концепції Traffic Engineering Queues, що стосуються забезпечення збалансованого завантаження буферних ресурсів вводиться наступна умова t f(pj, dj) n j  , ( j  1,  , (10)   де  - верхня межа завантаженості черг на вузлі ТКМ, що динамічно управляється, f(pj) деяка функція від характеристик j-го потоку. У виразі (10) як функція характеристик потоку використовується наступний вираз: f(pj, dj)  25 pj   dj , j  1,  , (11) де  - нормований коефіцієнт, який згладжує різницю у порядку значень пріоритету (0  7) і довжину пакету у байтах. В результаті задача обслуговування черг може бути зведена до задачі балансування їх довжини в ході мінімізації наступної цільової функції: min , (12) x,b, 30 35 40 що відповідає мінімізації верхнього порогу завантаженості черг на вузлі ТКМ, зваженого відносно таких характеристик потоку, як довжина пакету та його пріоритет, що сприяє збалансованому завантаженню всіх черг відповідно до вимог технології Traffic Engineering Queues. Новизна способу управління чергами полягає в тому, що він на відміну від раніше відомих способів враховує особливості технології Traffic Engineering Queues, що має за мету забезпечення балансування навантаження буферного ресурсу - черг мережного вузла. Важливою особливістю запропонованого рішення є те, що балансування у рамках запропонованого способу планується здійснювати, враховуючи пріоритет та довжину черги пакетів. Таким чином технологічна задача по обслуговуванню черг у загальному випадку була зведена до оптимізаційної задачі змішаного математичного програмування, пов'язаної з мінімізацією лінійної функції (12) при наявності нелінійних обмежень (7), (9) i (10), а також булевої природи деяких розрахованих змінних (3). При вирішенні даної задачі пропонується використання добре апробованих методів розв'язання - округлення (Rounding-off), гілок і меж (Branch-and-bound), послідовної лінеаризації (SLP), штрафних функцій (Penalty function), множників Лагранжа (Lagrangian relaxation), імітації отжигу (Simulated annealing), а також 2 UA 70088 U генетичного алгоритму (Genetic algorithm) і різних змішаних (гібридних) методів. Якщо ж недостачі у чергах нема, то розмірність шуканого вектора (6) істотно знижується, а сама задача може розв'язуватися класичними методами нелінійного програмування. 5 10 ФОРМУЛА КОРИСНОЇ МОДЕЛІ Спосіб управління чергами на маршрутизаторах мультисервісної телекомунікаційної мережі, що включає обслуговування черг, яке відбувається шляхом їх оптимального балансування, який відрізняється тим, що здійснюють балансування завдяки мінімізації верхнього порогу завантаженості множин черг з врахування пріоритетів та довжини пакетів, які обслуговуються, що сприяє більш якісному обслуговуванню пакетів трафіку з меншою довжиною та більшим пріоритетом. Комп’ютерна верстка Л.Литвиненко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3