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

Реферат: UA 99837 U UA 99837 U 5 10 15 20 25 Корисна модель належить до галузі електрозв'язку і є технологією маршрутизації трафіку, може знайти застосування на приграничних вузлах (маршрутизаторах і комутаторах третього рівня) транспортної телекомунікаційної мережі (ТКМ) при розв'язанні задач відмовостійкої маршрутизації для покращення якості обслуговування. Відомий спосіб відмовостійкої маршрутизації в ТКМ (див. Basic Specification for IP Fast Reroute: Loop-Free Alternates. RFC 5286 / A. Atlas, A. Zinin. - 2008 [Електронний ресурс]. - Режим доступу: http://tools.ietf.org/html/rfc5286 (дата звернення: 25.10.2014) полягає у реалізації ідей, що покладені в концепцію технології швидкої перемаршрутизації. В рамках даного способу в ході відмовостійкої маршрутизації трафіку здійснюється переключення потоків трафіку на резервний маршрут при відмові основного. Резервний маршрут розраховується одночасно з основним, при цьому реалізується одна з схем захисту: захист вузла, каналу чи маршруту. Однак відомий спосіб відмовостійкої маршрутизації має ряд недоліків, які можуть призвести до зниження якості обслуговування, а саме: при використанні відомого способу не враховується те, що в каналах зв'язку одночасно можуть протікати потоки основних та резервних маршрутів; у відомому способі не передбачена технологія захисту від перевантаження каналів у випадку, якщо тільки деякі потоки переключаться з основного на резервні маршрути; на практиці використовується тільки схема по захисту каналу. Найбільш близьким до запропонованого технічного рішення є спосіб відмовостійкої маршрутизації трафіку (див. Urra A., Calle E., Marzo J.L. Partial Disjoint Path for Multi-layer Protection in GMPLS Networks // Proceedings. 5th International Workshop on Design of Reliable Communication Networks, 2005. (DRCN 2005), p. 165-170), в рамках якого розв'язується задача переключення потоків трафіку на резервний маршрут при відмові основного. В рамках способу-прототипу ТКМ описується за допомогою орієнтованого графа G  ( V,E) , де V - це множина вершин (вузлів зв'язку ТКМ), а E - множина дуг графа (каналів зв'язку ТКМ). Для кожного каналу зв'язку, що моделюється дугою (i, j)  E , задається пропускна здатність каналу, що вимірюється в пакетах за секунду (1/с), яка позначена i, j . З кожним k  м потоком пов'язано ряд параметрів: rk - середня інтенсивність потоку на вході мережі; sk - вузолджерело; dk - вузол-отримувач. При розв'язанні задачі маршрутизації необхідно розрахувати 30 множину змінних xk j , кожна з яких характеризує долю інтенсивності k -го потоку в каналах i, зв'язку; k  K де K - множина потоків в мережі. При одношляховій маршрутизації виконуються умови: (1)  xk j  0;1 , i, а при необхідності реалізації багатошляхових рішень умови (1) замінюються на. (2) 0  xk j  1 . i, Крім того, щоб не допустити втрат пакетів на мережних вузлах та у мережі в цілому, забезпечується виконання умов збереження потоку: 35    x k j   x k,i  0; k  K, i  sk , dk ; i, j  j:(i, j)E j:( j,i)E   xk j   xk,i  1; k  K, i  sk ; (3)  i, j j:( j,i)E  j:(i, j)E  x k j   x k,i  1; k  K, i  dk ; i, j   j:( j,i)E  j:(i, j)E Для розрахунку резервного маршруту разом з невідомими змінними (2) розраховуються додаткові керуючі змінні xk j -, які характеризують частку k -го потоку, що протікає в каналі i, 40 (i, j)  E резервного маршруту. На змінні xk j також накладаються обмеження подібні до (1)-(3). i, Крім цього, в структурі способу-прототипу для запобігання перетину основного і резервного маршрутів при реалізації різних схем резервування мережних ресурсів вводиться ряд додаткових умов-обмежень: - при реалізації схеми захисту (i, j) - каналу в модель необхідно ввести умови: (4) xk j  xk j  0 , i, i, виконання яких гарантує використання (i, j) - каналу лише одним маршрутом - або основним, або резервним; 1 UA 99837 U - при реалізації схеми захисту i -го вузла модель доповнюється умовою:  xk j x k j  0 , i, i, (5) i:(i, j)E виконання якої гарантує використання i -го вузла (тобто всіх інцедентних йому каналів) або основним, або запасним маршрутом; - для забезпечення захисту маршруту (маршрутів) в модель вводиться умова:  xk j xk j  0 , i, i, (6) (i, j)E 5 10 що еквівалентно задоволенню вимог щодо відсутності в основному і запасному маршрутах спільних вузлів і каналів (крім вузла-відправника та вузла-одержувача). Важливе місце в структурі математичної моделі потокової маршрутизації займають умови запобігання перевантаженню каналів зв'язку. Зміст цих умов полягає в тому, щоб сумарна інтенсивність потоків, що протікають в певному каналі зв'язку, не перевищувала його пропускну здатність. Розрахунок множини основних маршрутів будемо здійснювати відповідно до умов (див. Лемешко А.В., Романюк А.А., Козлова Е.В. Модель отказоустойчивой маршрутизации в MPLS-cemu // Труды Северо-Кавказского филиала Московского технического университета связи и информатики. - Ростов-на-Дону: ПЦ "Университет" СКФ МТУСИ, 2013,с. 203-206):   r k xk j  i, j , (i, j)  E . i, (7) kK (i, j) 15 20 25 30 35 Як показало дослідження, недоліки відомого способу належать і до недоліків способупрототипу. В основу корисної моделі поставлена задача створити спосіб відмовостійкої маршрутизації мультипотокового трафіку з підтримкою різних схем резервування мережних ресурсів, в рамках якого б враховувалось те, що в каналах зв'язку одночасно можуть протікати потоки основних та резервних маршрутів та був передбачений механізм щодо захисту від перевантажень каналів зв'язку у випадку, якщо тільки деякі потоки переключаться з основного на резервні маршрути. Ця задача вирішується наступним чином. На фіг. 1-5 показано приклад використання способу відмовостійкої маршрутизації для одношляхового випадку з реалізацією схеми захисту каналу для двох потоків для топології мережі, що представлена на фіг. 1. Для цього у способі відмовостійкої маршрутизації мультипотокового трафіку в телекомунікаційних мережах, згідно з запропонованою корисною моделлю, умови (7) необхідно модифікувати, ввівши в ліву частину нерівності змінні xk j . У разі реалізації відмовостійкої i, маршрутизації в рамках моделі (1) - (6) важливо врахувати, що в один і той же момент часу можуть відмовити лише деякі елементи (вузли, канали) мережі, тобто в одному і тому ж каналі зв'язку можуть протікати потоки основних і резервних маршрутів. Сумарна інтенсивність потоків, що протікають по вибраному каналу зв'язку, буде розраховуватися для "гіршого випадку", тобто до уваги братиметься більша з інтенсивностей k -го потоку, що належить до основного або резервного маршруту. Тоді для варіанта одношляхової маршрутизації, коли невідомі маршрутні змінні носять булівський характер (1), умови запобігання перевантаженню матимуть вигляд k   k k  x i, j  x i, j  (8)   r  k k   ij, (i, j)  E , kK (i, j)  x i, j x i, j  1  а для випадку організації багатошляхової маршрутизації умови (8) модифікуються в нерівність 1   (9)   r k  ( xk j  xkj )  ( xk j  xkj )2   i, j , (i, j)  E . i, i, i, i, 2 kK (i, j)   При розрахунку маршрутних змінних в ході розв'язання задачі відмовостійкої маршрутизації в ТКМ мінімізується наступна цільову функція: F   kK (i, j)E 40 c k j xk j  i, i,   cikjxk j , , i, (10) kK (i, j)E де c k j і cikj - маршрутні метрики каналів для основного і запасного маршрутів відповідно. i, , Функція (10) чисельно характеризує сумарні витрати на формування та використання основного і резервного маршрутів між парою вузлів відправник-одержувач. Паралельно з розрахунком маршрутів визначається порядок їх використання потоками користувачів. Модель (1) - (10) необхідно доповнити умовою (див. Lemeshko О., Romanyuk A., Kozlova H. Design schemes for MPLS Fast ReRoute // XIIth International Conference "The 2 UA 99837 U experience of designing and application of CAD systems in microelectronics", Polyana-Svalyava(Zakarpattya), UKRAINE 19-23 February 2013: Publishing House of Lviv Polytechnic, 2013, p. 202203)   kK (i, j)E 5 c k j xk j  i, i,   cikjxk j , , i, (11) kK (i, j)E виконання якої гарантує те, що основний маршрут (мультимаршрут) завжди буде ефективніше (за швидкістю або затримкою пакетів) резервного в рамках вибраних маршрутних метрик c k j і cikj . i, , 10 15 20 25 30 Задача розрахунку маршрутних змінних xk j і xk j при наявності обмежень (1), (3) - (6), (8), i, i, (11) з цільовою функцією (10) належить до класу задач змішаного цілочисельного нелінійного програмування. А при реалізації багатошляхової відмовостійкої маршрутизації, тобто при врахуванні умов (2) і (9) замість виразів (1) і (8) - це задача нелінійного програмування. Запропонована математична модель для способу відмовостійкої маршрутизації для різних : схем резервування мережних ресурсів (1)-(11) вузла (5), каналу (4) і маршруту (6). Новизна способу полягає в модифікації умов запобігання перевантаженню каналів зв'язку, якими, в загальному випадку, одночасно можуть протікати потоки як основних, так і резервних маршрутів. Використання умов (8) і (9) в ході реалізації одно- і багатошляхової маршрутизації дозволить запобігти перевантаженню каналів зв'язку навіть у випадку, якщо лише деякі потоки переключаться з основних шляхів на резервні. Модель охоплює випадок одноадресної (unicast) маршрутизації, але умови (8) і (9) справедливі також і при організації багатоадресної (multicast) або широкомовної (broadcast) маршрутизації. На фіг. 1-5 показано приклад використання способу відмовостійкої маршрутизації для одношляхового випадку з реалізацією схеми захисту каналу для двох потоків для топології мережі, що представлена на фіг. 1. Для першого потоку з інтенсивністю потоку 80 1/с вузломвідправником є перший маршрутизатор, вузлом-отримувачем - п'ятий маршрутизатор. Для другого потоку з інтенсивністю 60 1/с узлом-відправником є другий маршрутизатор, вузломотримувачем - четвертий маршрутизатор. За метрику використовується мінімум кількості переприйомів (хопів). Треба реалізувати схему захисту каналу (1, 3). На фіг. 2 представлено основний маршрут для першого потоку, на фіг. 3 - основний маршрут для другого потоку. На фіг. 4 представлено резервний маршрут для першого потоку, отриманий без використання умови (8), а на фіг. 5 - резервний маршрут для першого потоку, отриманий з використанням умови (8). Таким чином, використання умови (8) в ході реалізації відмовостійкої маршрутизації дозволило запобігти перевантаженню каналів зв'язку у випадку, коли першим потік був переключений з основного маршруту на резервний. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 35 40 45 Спосіб відмовостійкої маршрутизації мультипотокового трафіку з підтримкою різних схем резервування мережних ресурсів, що здійснює захист каналу, вузла та маршруту, задаються умови для здійснення одношляхової та багатошляхової маршрутизації, який відрізняється тим, що в ньому забезпечується відсутність перевантаження каналів зв'язку потоками як основного, так і резервного маршрутів, завдяки виконанню умови запобігання перевантаженню каналів зв'язку, які модифікуються в нерівність:  xk  xk  i, j i, j   r k  k k   ij, (i, j)  E  x x  1 kK (i, j)  i, j i, j  - для одношляхової маршрутизації та 1     r k  ( x k j  x kj )  ( xk j  x kj )2   i, j , (i, j)  E i, i, i, i, 2 kK (i, j)   - для багатошляхової маршрутизації, де xk j - частка інтенсивності k -го потоку в каналі зв'язку i, (i, j)  E ; k  K , де K - множина потоків в мережі; E - множина каналів зв'язку телекомунікаційної мережі; r k - середня інтенсивність потоку на вході мережі; i, j - пропускна 50 здатність каналу (i, j)  E , що вимірюється в пакетах за секунду (1/с), а при розрахунку маршрутних змінних в ході розв'язання задачі відмовостійкої маршрутизації в телекомунікаційній мережі мінімізується наступна цільова функція: 3 UA 99837 U F   kK (i, j)E де ck j i, і cikj , c k j xk j  i, i,   cikj xk j , , i, kK (i, j)E - маршрутні метрики каналів для основного і запасного маршрутів відповідно, що дозволяє запобігти перевантаженню каналів зв'язку навіть у випадку, якщо лише деякі потоки переключаться з основних шляхів на резервні. Комп’ютерна верстка Л. Литвиненко Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4