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

Реферат: UA 99208 U UA 99208 U 5 10 15 Корисна модель належить до технологій управління трафіком і може знайти застосування на прикордонних вузлах транспортної телекомунікаційної мережі (ТКМ) при розв'язанні задач маршрутизації. Відомий спосіб (див. Yasukawa S. Signaling Requirements for Point-to-Multipoint TrafficEngineered MPLS Label Switched Paths (LSPs), RFC4461 // April 2006, 30 p.) реалізує режим віртуальних з'єднань з маршрутизацією «від джерела». Основним недоліком даного способу є відсутність забезпечення ефективного балансування навантаження в мережі. Найбільш близьким до запропонованого технічного рішення є спосіб дворівневої маршрутизації в мережах з комутацією віртуальних каналів (патент UA № 63294, МПК (2011.01) G06G 3/00, опубл. 10.10.2011 бюл. № 19), який забезпечує розв'язання задачі багатошляхової маршрутизації та ефективне балансування навантаження в каналах ТКМ, використовуючи модель ієрархічної маршрутизації. В рамках цього способу ТКМ описується за допомогою орієнтованого графа G=(R, E), де     , Ri  R , i  1 m - множина вершин, що моделює маршрутизатори, R   Ri , i  1, m  - множина   прикордонних маршрутизаторів, де m - кількість прикордонних маршрутизаторів, i, j  E , i, j  1,m; i  j - множина дуг, що моделює канали зв'язку. Для кожного вузла-відправника в ТКМ як шукані виступають маршрутні змінні x k r , які характеризують інтенсивність kr -го потоку ij пакетів, що передається по каналу (i, j); де kr - k-й потік пакетів, що надходить в мережу через r20 25 30 35 й прикордонний маршрутизатор. Змінна k r - це інтенсивність kr -го потоку, а ij - пропускна здатність (i, j)-гo каналу зв'язку. Однак даний спосіб має велику кількість координуючих ітерацій, особливо при високій завантаженості мережі. В основу корисної моделі поставлена задача підвищення збіжності координаційної процедури в ході оптимізації процесу ієрархічної маршрутизації в ТКМ. Такий технічний результат може бути досягнутий тим, що в способі підвищення збіжності координаційної процедури в ході оптимізації процесу ієрархічної маршрутизації в телекомунікаційній мережі, що забезпечує розв'язання задачі багатошляхової маршрутизації та ефективне балансування навантаження в каналах ТКМ, використовуючи модель ієрархічної маршрутизації, згідно з корисної моделлю на кожному приграничному маршрутизаторі при розрахунку маршрутів здійснюють збільшення протокольної метрики каналів зв'язку пропорційно кількості переприйомів між відправником та кожним каналом зв'язку мережі з метою зменшення кількості координуючих ітерацій, що приводить до відповідного зменшення часу розв'язання маршрутних задач та об'єму створюваного при цьому службового навантаження. Зміст заявленого способу пояснюється наступним. З метою недопущення втрат пакетів на маршрутизаторах і в мережі в цілому в ході розрахунку маршрутних змінних необхідно забезпечити виконання умов збереження потоку:   xk r  xk r  1, якщо і  й маршрутизатор  вузол  відправник ; ij ji  j:i, j E j: j,i E   xk r  xk r  0, якщо і  й маршрутизатор  транзитний вузол; (1)  ij ji  j:i, jE j: j,i E   xk r  xk r  1, якщо і  й маршрутизатор  вузол  отримувач . ij ji  j:i, j E j: j,i E      40   Система рівнянь (1) повинна виконуватись для кожного потоку пакетів. Крім цього, складовою моделі є умова забезпечення відсутності перевантаження каналів зв'язку kr xkr  ij . (2) ij  rR k r K 45 Варто зазначити, що при децентралізованому розрахунку маршрутних змінних на кожному окремому вузлі-відправнику умови (2) врахувати у явному вигляді неможливо тому, що кожен маршрутизатор визначає шлях передачі потоку без інформації про результати розрахунку на інших прикордонних маршрутизаторах. Тому умову (2) запишемо у наступному вигляді: 1 UA 99208 U  xk r  ij  ij kr   ks xk s . (3) ij sR  k s K s s r k r K r З метою реалізації багатошляхової маршрутизації на маршрутні змінні слід накласти обмеження вигляду: 0  x k r  1 . (4) ij 5 У векторно-матричній формі умови (1) і (3) можна представити в наступному вигляді   Ar xr  ar ,  де x r - вектор, координатами якого є маршрутні змінні x k r , A r - матриця, що формується ij  згідно з умовою (1), ar - вектор, що формується згідно з умовою (1);  Br xr  C  rsx s , sR  s r 10  де B r , Crs - матриці, що формуються згідно з умовою (3), x s - вектор, координатами якого є маршрутні змінні x k s . ij У ході розрахунку вектора шуканих змінних як критерій оптимальності одержуваних рішень вибираємо мінімум наступної цільової функції t  F xr Hr xr , (5)  rR  15 де Hr - діагональна матриця вагових коефіцієнтів, координати якої по суті є метриками каналів зв'язку ТКМ,  t - операція транспонування вектора (матриці). Тоді, переходячи до задачі на безумовний екстремум, необхідно максимізувати лагранжіан за множниками Лагранжа: minF  maxL ,  x 20 де L  rR  t  xr Hr xr         t r  Br  xr  Crsx s  . (6)   rR  sR    s r     Для розв'язання сформульованої оптимізаційної задачі використано метод цільової координації. В рамках цього методу лагранжіан представляється у вигляді: t    t t L xr Hr xr  r Br  xr   r Crsxs . (7)  rR  25    rR rR  sR  s r Припустивши, що величини  r є фіксованими, вираз (7) можна записати в наступному вигляді L Lr ,  rR  t   t Lr  xr Hr xr  r Br  xr    sR s r 30 35  t s Crsx s , (8)  щоб всі змінні були віднесені до індексу r. Таким чином, лагранжіан набуває сепарабельної форми, а загальна проблема маршрутизації виявилась декомпозиційованою на ряд маршрутних задач (8). Розв'язок задачі щодо мінімізації виразу (8) визначає нижній рівень розрахунків, а на верхньому рівні, основною задачею якого є координація отриманих на нижньому рівні рішень з метою недопущення перевантаження каналів зв'язку (3), здійснюється модифікація векторів множників Лагранжа шляхом виконання наступної градієнтної процедури r   1  r   r , (9) де  - номер ітерації, r - градієнт функції, що розраховується, виходячи з одержаних на нижньому рівні результатів розв'язання задач маршрутизації x * на кожному вузлі-відправнику s 2 UA 99208 U  r x  x  x *  Br x*  s C * rsx s . sR s r 5 10 15 20 25 30 35 (10)  Оптимальні рішення отримуються коли градієнт (10) прагне до нуля. При цьому кількість координуючих ітерацій (10) залежить від кількості потоків, розмірності та завантаженості мережі. Збільшення числа ітерацій призводить до пропорційного зростання об'єму службового трафіку та часу розв'язання маршрутних задач. Тому необхідно забезпечити мінімізацію числа координуючих ітерацій без зниження ефективності запропонованих рішень. В ході дослідження виявлено, що причина зростання кількості координуючих ітерацій (фіг. 5) - це перевантаження віддалених за кількістю переприйомів (хопів) від вузла-відправника або отримувача каналів зв'язку. В ході розв'язання задачі була використана телекомунікаційна мережа, структура якої представлена на фіг. 1. ТКМ містила шість маршрутизаторів та дев'ять каналів зв'язку. В розривах каналів зв'язку позначені їх пропускні здатності (1/с). Нехай в мережі, як приклад, циркулює два потоки. Для першого потоку за вузол-відправник прийнято маршрутизатор R1, а за вузол-отримувач - маршрутизатор R3. Для другого потоку вузол-відправник - маршрутизатор R5, а вузол-отримувач - маршрутизатор R3. Інтенсивність обох потоків складала 200 1/с. Початковий розподіл потоків, отриманий в ході мінімізації (8), показано на фіг. 2, на якому в розривах каналів зв'язку (зверху-вниз) позначено: доля інтенсивності першого потоку пакетів (1/с), доля інтенсивності другого потоку пакетів (1/с), пропускна здатність каналу зв'язку (1/с). При початковому розподілі потоків були перевантажені чотири канали: (1,2), (1,3), (5,3) та (5,4). Проблема перевантаження каналів виникає тому, що обидва маршрутизатори (R1 та R5), які розраховують маршрути для першого та другого потоку відповідно, діють неузгоджено, тобто незалежно один від одного, намагаючись забезпечити збалансоване завантаження мережі з використанням всіх доступних каналів зв'язку ТКМ. Далі відбувається координація маршрутних рішень на верхньому рівні моделі (9), (10) з метою недопущення перевантаження каналів зв'язку. Далі процедура мінімізації (8) повторювалась з врахуванням оновлених значень множників Лагранжа. Результат маршрутизації потоків після сьомої ітерації показано на фіг. 3. Після сьомої ітерації залишилися перевантаженими лише два канали: (1,2) та (5,4). Тобто, з кожною ітерацією завантаженість каналів тим чи іншим потоком, зменшується пропорційно до віддаленості цих каналів за кількістю вузлів від відповідного вузла-відправника або отримувача. На фіг. 4 показано розподіл потоків в ході ієрархічної маршрутизації після тринадцятої ітерації, коли перевантаження каналів зв'язку вже було відсутнє. Таким чином, за результатами проведених досліджень пропонується для кожного потоку забезпечити збільшення метрики використання ним каналів зв'язку пропорційно до віддаленості цих каналів за кількістю вузлів від відповідного вузла-відправника або отримувача. Тому для кожного з потоків для модифікації метрик пропонуються наступні вирази: Mi*  Mn  q  pi , i   pi  min hopis, hopid  1 ; (11) де Mn i - метрика і-го каналу зв'язку, яка формується тим чи іншим протоколом маршрутизації; q - коефіцієнт зміни метрики (q > 0); hopis -мінімальна кількість вузлів між 40 45 50 вузлом-відправником та і-м каналом зв'язку; hopid - мінімальна кількість вузлів між вузломотримувачем та і-м каналом зв'язку. Використовуючи дану процедуру в рамках запропонованого способу підвищення збіжності координаційної процедури в ході оптимізації процесу ієрархічної маршрутизації в телекомунікаційній мережі, була розрахована кількість ітерацій в залежності від інтенсивностей потоків пакетів (фіг. 6). Результати досліджень показали, використання процедури модифікації метрики (11) забезпечило підвищення збіжності координаційної процедури шляхом зменшення в 1,5-5 разів кількості координуючих ітерацій (фіг. 7) в залежності від розміру мережі, числа потоків та їх інтенсивностей (завантаженості ТКМ). Таким чином, використання запропонованої корисної моделі дозволяє підвищити масштабованість рішень щодо маршрутизації в телекомунікаційній мережі, скоротити кількість координуючих ітерацій при реалізації ієрархічної маршрутизації, тим самим скоротивши об'єми пов'язаного з цим службового навантаження та знизивши інерційність управління мережею в цілому. 3 UA 99208 U ФОРМУЛА КОРИСНОЇ МОДЕЛІ 5 10 15 Спосіб підвищення збіжності координаційної процедури в ході оптимізації процесу ієрархічної маршрутизації в телекомунікаційній мережі, що забезпечує розв'язання задачі багатошляхової маршрутизації та ефективне балансування навантаження в каналах телекомунікаційної мережі (ТКМ), використовуючи модель ієрархічної маршрутизації, який відрізняється тим, що на кожному приграничному маршрутизаторі при розрахунку маршрутів здійснюють збільшення протокольної метрики каналів зв'язку пропорційно кількості переприйомів між відправником та кожним каналом зв'язку мережі з метою зменшення кількості координуючих ітерацій, що приводить до відповідного зменшення часу розв'язання маршрутних задач та об'єму створюваного при цьому службового навантаження. 4 UA 99208 U 5 UA 99208 U 6 UA 99208 U Комп’ютерна верстка Д. Шеверун Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7