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

Спосіб дворівневої маршрутизації в телекомунікаційних мережах з комутацією віртуальних ка 3 63294 тракту. Всю множину трафіків К, що надходять від абонентів (мереж доступу), залежно від того, на який прикордонний маршрутизатор надходить цей трафік, можна декомпозиціювати на підмножини ________     ,  r ,r  1 mLER    , де k - множина трафіків, що   r надходять на r-й LER. Тоді кожному трафіку з множини Кг зіставляється ряд параметрів: + М r-r-й LER, на який надходить k-й трафік (вузол-джерело); + М p- р-й LER, через який k- й трафік убуває з MPLS-мережі (вузол-одержувач); kr - інтенсивність kr -го трафіка, тобто k-го трафіка, що надходить на r- й LER. Як приклад, на фіг.1 показані інтенсивності 1 2 двох трафіків (  2 і  2 ), що надходять на другий LER та призначені для четвертого та третього LER відповідно. Функціональне описання MPLS- мережі В MPLS- мережі в ході рішення задач маршрутизації в межах потокових моделей необхідно розрахувати один або множину шляхів (Label Switching Path, LSP) між парою прикордонних вузлів відправник-одержувач, а також визначити порядок розподілу між ними трафіка заданої інтенсивності. Умовимося, що з точки зору підвищення масштабованості рішень задач маршрутизації застосуємо дворівневу схему розрахунку: - на нижньому рівні - шукані маршрути підлягають розрахунку незалежно на кожному LER для трафіків, які надходять до нього від абонентів (мереж доступу); - на верхньому рівні - отримані на нижньому рівні рішення координуються з метою запобігання ймовірного перевантаження трактів передачі мережі через децентралізацію прийнятих рішень щодо маршрутизації трафіків. Тоді для кожного r-го LER як шукані виступа ють маршрутні змінні xk r ij , які характеризують інтенсивність kr-го трафіку в тракті i, j   . З метою недопущення втрат пакетів на маршрутизаторах і в мережі в цілому протягом розрахунку маршрутних змінних необхідно забезпечити виконання умов збереження потоку:  k k    x ij r   x ij r  k r при k r   r , i   r ;  j:i, j  j: j,i   k k     x ij r   x ij r  0 при k r   r , i   r ;  p ; j: j,i   j:i, j k k    x ij r   x ij r  kr при k r   r , i   p ;  j:i, j  j: j,i   Система рівнянь-умов (1) повинна виконуватися для кожного трафіка, який надходить на довільний прикордонний маршрутизатор (LER). Крім того, з метою запобігання можливого перевантаження трактів передачі MPLS-мережі протягом розрахунку маршрутних змінних важливо виконати умови (за кількістю трактів передачі):   r   k r  r k x ij r  ij ; i, j  . (2) 4 Варто врахувати, що при децентралізованому розрахунку маршрутних змінних на кожному окремо взятому LER умови (2) в явному вигляді врахувати не представляється можливим, тому що кожен прикордонний маршрутизатор визначає LSP для трафіків користувачів, що надходять до нього, без інформації про результати розрахунку на сусідніх LER. У зв'язку з цим умови (2) запишемо в наступному вигляді:  k kr  r x ij r  ij;  .   s  kr  r k x ij r ; r    , i, j  . s r (3) Значення виразу (3) полягає в тому, що трафік, який маршрутизується з r-го LER, не повинен за своєю інтенсивністю перевищувати доступної пропускної здатності тракту передачі, яка залишилася після обслуговування трафіків інших прикордонних маршрутизаторів. Згідно з фізичним змістом маршрутних змінних, на них слід накласти обмеження вигляду 0  x k r  k r ij (4) У векторно-матричній формі умови (1)-(3) та критерій (4) можна представити в наступному вигляді: r  x r   Crs x s . s  sr (5) При розрахунку вектора шуканих змінних як критерій оптимальності одержуваних рішень виберемо мінімум наступної цільової функції: t  minF при F   c r x r , x r  (6)  де вагові коефіцієнти - координати вектора c r по суті є метрикою тракту (і, j), характеризуючи умовну вартість використання кr-м трафіків цього t тракту; [] - операція транспонування вектору (матриці). Тоді, переходячи до задачі на безумовний екстремум, необхідно максимізувати лагранжіан за множниками Лагранжа  : minF  maxL,  x Де      Crs x s .  r  r   s    s r   (7) Використання методу цільової координації для реалізації багаторівневої стратегії маршрутизації Для рішення сформульованої оптимізаційної задачі використаємо метод цільової координації, в межах якого лагранжіан (7) подамо у вигляді: t     t t L   c r x r   r r  x r  ar    r  Crs x s t  L   c r xr  r    t r  r r    xr  r  s  s r (8) Припустивши, що величини  r є фіксованими, можна останній доданок у виразі (8) привести до вигляду: 5 63294    rt  Crs x s    Crs x s r * s  s r r  s  s r тоді вираз (8) можна записати наступним чином: L   Lr , r  t   t Lr  c r xr  r r  xr    s r де . (9) Таким чином, функція (9) набуває сепарабельної форми, а загальна проблема маршрутизації в MPLS-мережі виявилася декомпозіційованою на ряд маршрутних задач (за кількістю прикордонних маршрутизаторів), де кожна задача маршрутизації на r-му LER, що складається в розрахунку вектора  x r , звелася до максимізації лагранжиану L . Ріr шення завдання максимізації виразу (9) визначає нижній рівень розрахунків - LER-рівень. На верхньому рівні (LSR-рівні), основною задачею якого є Комп’ютерна верстка І. Скворцова координація рішень, отриманих на нижньому рівні з метою недопущення перевантаження трактів передачі мережі (2), здійснюється модифікація вектора множників Лагранжа шляхом виконання наступної градієнтної процедури: r   1  r   r . (10) де r - градієнт функції, який розраховується, виходячи з одержуваних на верхньому рівні  t  sCrs x s s 6  результатів рішення задач маршрутизації ( x r ) на  кожному конкретному r-му LER ( r   ), тобто   t r x    r  x r    sCrs x s xx s  s r (11) Загальна схема дворівневої маршрутизації в MPLS-мережі наведена на фіг.2. Підписне Тираж 23 прим. Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601