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

При стратегічному підході TE-тракти спочатку обчислюються за допомогою прогнозування матриці трафіку, а потім вже можуть бути адаптовані в залежності від зміни трафіку чи топології (наприклад, пошкодження мережі). Одноразово налаштовані TE-тракти використовуються завжди для маршрутизації потоків між прикордонними маршрутизаторами. Оскільки резервація смуги пропускання в MPLS-TE є чисто логічною,гарантувати її мають додаткові механізми. Контролюючі механізми відповідають за те, аби TE-тракт не використовував ширину смуги пропускання, що перевищує зарезервовану. Такий контроль можна виконати на основі окремих потоків, виконуючи контроль на вхідних потоках (базуючись на запрошуваній потоком смуги пропускання та наявної пропускної здатності у ТЕ-тракті), і далі контролювати кожен потік окремо, або на основі сукупності, обмежуючи сукупний рівень трафіку в межах ТЕ-тракту. Адаптація розміру TE-тракту до зміни трафіку вимагає знання фактичного навантаження TE-тракту. Дані можуть спиратися на вимірюване навантаження трафіку на прикордонних маршрутизаторах або на сукупну смугу пропускання, запрошувану кожним потоком в режимі контролю на основі окремих потоків.

2.3 Функціональна архітектура системи маршрутизації MPLS-TE

У цьому розділі ми пропонуємо загальну архітектуру для опису системи маршрутизації MPLS-TE (рис. 2.4). Це функціональна архітектура, що допомагає в реалізації великого спектру рішень [11]. Вона складається з набору функцій, які називають також будівельними блоками. Деякі з них працюють на маршрутизаторах, інші можуть розміщатися або на маршрутизаторах або на одному чи більшій кількості мережевих серверів. Розрізняються стандартні MPLS-TE блоки і специфічні блоки експлуатації:

* Стандартні функції MPLS-TE включають функцію визначення топології ТЕ, що забезпечується протоколом IGP-TE (або OSPF-TE, або ISIS-TE) і функцію сигналізації LSP, забезпечується протоколом RSVP-TE. Ці стандартні функції знаходяться в маршрутизаторах.

* Специфічні функції експлуатації включають функції агента ТЕ-тракту, обчислення шляху TE-тракту, адаптації та використання TE-тракту Ці функції можуть бути розташовані в маршрутизаторах або винесені на один або декілька серверів. Функція TE-менеджера завжди розташована на мережевому сервері.

У розділах нижче, ми орієнтуємося на п'ять будівельних блоків, що відповідають за оптимізацію ресурсів: TE-Manager (TM), TE-Trunk AGent (TAG), TE-Trunk Computation (TC), TE-Trunk ADaptation (TAD), TE-Trunk Utilization (TU)



Рисунок 2.4 - Загальна архітектура систем маршрутизації MPLS-TE

2.3.1 TE-Manager

TE-Manager (TM) являє собою функціональний орган, який приймає рішення встановлення/видалення/зміни TE-тракту, спираючись на прогнозування матриці трафіку (1), тобто набір сукупних вимог трафіку між кожною парою прикордонних маршрутизаторів. Він посилає запити встановлення/видалення/зміни TE-тракту одному або декільком агентам TE-тракту (2). Ця функція необов'язкова (факультативна), TE-тракт може бути визначений оператором або безпосередньо в налаштуваннях агентів TE-тракту.

2.3.2 TE-Trunk Agent

TE-Trunk Agent (TAG), є серцем архітектури. Він контролює створення/зміни/видалення TE-тракту в мережі. Він координує дії блоків TE-менеджера, адаптації TE-тракту, обчислення шляху TE-тракту, використання TE-тракту і сигналізації LSP. Він обробляє спрямовані ТЕ-менеджером (1) запити встановлення/видалення/зміни TE-тракту, і запити зміни TE-тракту, спрямованих блоком адаптації TE-тракту (3). Агент надсилає запит розрахунку TE-тракту блоку обчислення шляху TE-тракту (4). Після обчислення шляхів менеджер TE-тракту розсилає запити встановлення LSP модулю RSVP-TE (7), щоб прокласти TE-LSP уздовж обчислених шляхів.

Одноразово встановлене TE-LSP, заноситься TAG в базу даних TE-тракту, що містить інформацію про створені ТЕ-тракти (обмеження TE-тракту, шляхи TE-трактів і т.д.) (8). Він також повідомляє блок використання TE-тракту (9) про створений TE-тракт і відповідні LSP. У "мережевому режимі", агент має зв'язуватися з блоками IGP-TE (10) та сигналізації LSP, щоб отримувати повідомлення про пошкодження мережі (зв'язку/вузла) чи TE-LSP. Цей зв'язок дозволяє TAG виявляти пошкодження і викликати блок обчислення шляху TE-тракту, щоб переадресувати TE-тракти шляхом, що уникає пошкоджені елементи.

2.3.3 TE-Trunk Path Computation

TE-Trunk Path Computation (ТС) є одним з основних будівельний блоків в системах маршрутизації MPLS-TE. Він повинен знайти шляхи TE-тракту за допомогою бази даних трафік інжинірингу (TED) (5), яку поповнює IGP (6) і з огляду на потреби TE-тракту. ТС обробляє запити агента TE-тракту. Запит може відноситися до одного TE-тракту або їх набору. Запит може бути проханням встановлення тракту або його зміни. На виході для даного тракту маємо шлях або багато шляхів, чия сукупна пропускна спроможність вдовольняє запитувану трактом.

2.3.4 TE-Trunk Adaptation block

TE-Trunk Adaptation block (TAD) займається адаптацією розміру TE-тракту відповідно фактичному навантаженню. Він збільшує розмір TE-тракту (тобто збільшує сумарну ширину смуги пропускання, виділену для TE-тракту), для передбачення проблеми перевантаження, коли навантаження між двома вузлами зростає, а також зменшує розмір TE-тракту таким чином, щоб не витрачати невикористану смугу пропускання, коли навантаження між парою вузлів зменшується. Перевірки навантаження TE-тракту можна зробити керовані часом, коли воно періодично перевіряється блоком адаптації в базах даних використання TE-тракту (13), або керовані подіями, у цьому випадку блок використання TE-тракту повідомляє адаптаційному блоку, що TE-тракт перевантажений або наближається до того (12). Зауважимо, що цей блок не є обов'язковим і може не використовуватися в деяких системах маршрутизації MPLS-TE.

2.3.5 TE-Trunk Utilization

Блок TE-Trunk Utilization (TU) відповідає за (1) - визначення шляху трафіку усередині TE-тракту, (2) - визначення шляху вхідних потоків всередині ТЕ-LSP (вибір LSP серед набору LSP тієї чи іншої магістралі), (3) - контроль трафіку в TE-тракті (обмеження швидкості), (4) - перевірка фактичного навантаження TE-тракту, і, опціонально, (5) - контроль вхідних потоків всередині TE-трактів. Визначення шляху трафіку усередині TE-трактів, на головному маршрутизаторі може покладатися на IGP (наприклад, магістраль вважається ланкою SPF обчислень), на BGP (наприклад, всі шляхи досягнення кінця магістралі маршрутизуються всередині магістралі), або, нарешті, на статичні маршрути всередині магістралі. Визначення шляху окремих потоків всередині LSP даного TE-тракту, можна зробити або заздалегідь, коли зроблено контроль вхідного потоку, або в реальному часі, спираючись на хеш-функцію, що виконується потоками. Контроль трафіку, тобто обмеження швидкості на прикордонних магістральних маршрутизаторах, можна зробити на основі окремих потоків або на основі сукупного трафіку. Контроль навантаження TE-тракту полягає в оновленні фактичним його рівнем бази даних використання TE-тракту. Ця база даних включає в себе актуальні навантаження LSP. Дані можуть спиратися на вимірюване навантаження трафіку на прикордонних маршрутизаторах або на сукупну смугу пропускання, запрошувану кожним потоком в режимі контролю на основі окремих потоків. Ця інформація може потім використовуватися блоком адаптації TE-тракту з метою передбачення перевантаження в магістралі та забезпечення адаптації до змін матриці трафіку. Він може крім того, використовуватися для контролю вхідних потоків. У режимі визначених потоків блок використання TE-тракту може обробляти запити вхідних потоків. Після прийому запиту вхідного потоку він консультується з базою даних використання TE-тракту (11), і якщо є LSP з достатніми ресурсами, новий потік приймається та база даних використання TE-тракту оновлюється. В іншому разі запит вхідного потоку буде відхилено. Якщо немає TE-тракту з достатньою смугою пропускання, блок використання TE-тракту може запросити у блока адаптації TE-тракту збільшити розмір TE-тракту для забезпечення достатньої пропускної спроможності для нового потоку (12).

2.4 Застосування архітектури: Опції поширення та виконання функцій

У попередньому розділі ми запропонували функціональну архітектуру систем MPLS-TE, яка включає окрім стандартних блоків MPLS-TE особливі елементи, такі як TE-Trunk Computation, TE-Trunk Adaptation, and TE-Trunk Utilization. Ця архітектура може допомогти класифікувати MPLS-TE механізми і покращити модель систем MPLS-TE. Система маршрутизації MPLS-TE дійсно відповідає особливостям реалізації цієї архітектури. Блоки загальної архітектури можуть розташовуватися в різних елементах (централізовано на серверах мережі або розподілено на прикордонних маршрутизаторах). Продуктивність системи маршрутизації MPLS-TE в поняттях масштабованості, реактивності і оптимальності в підсумку залежить від різних варіантів втілення, включаючи перерозподіл функцій. Перш ніж перейти до обговорення цих варіантів, опишемо деякі критерії класифікації.

2.4.1 Критерії класифікації MPLS-TE

Для опису різних підходів до реалізації системи маршрутизації MPLS-TE визначається кілька критеріїв. Ми розрізняємо наступні:

1. Шкала часу:

* Offline (Off - Автономна): Базуючись на прогнозованих матрицях трафіку періодично обчислюються та створюються TE-тракти. Цей режим дає більше часу на обчислення. Це означає, що немає адаптації TE-тракту і переорієнтації LSP при пошкодженнях мережі. У цьому режимі, поновлення може забезпечуватися обчисленням запасного TE-тракту.

* Online (On - Мережева): TE-тракти модифікуються (зміна розміру TE-тракту, зміна маршруту LSP, створення/видалення LSP), у відповідності з еволюцією матриці трафіку або мережевим пошкодженням. У такому режимі, час обчислення шляху має бути мінімальним аби забезпечити швидкий відклик.

2. Метод обчислення шляху:

* Coordinated (Coo - Координований): Шляхи TE-трактів обчислюються беручи до уваги всі запити TE-трактів.

* Uncoordinated (Unc - Некоординований): Шлях (и) TE-тракту з даного прикордонного маршрутизатора обчислюються без урахування ТЕ-трактів, що створюються іншими головними LSR.

3. Розподілення функцій:

* Centralized (Cen - Централізована): Функція знаходиться на єдиному обчислювальному елементі

* Distributed (Dis - Розподілена): Функція розподілена на декількох обчислювальних елементах.

2.4.2 Розподілення функцій

В цьому розділі ми обговоримо розподіл кожної функції архітектури та її вплив на продуктивність системи MPLS-TE. Деякі функції можуть бути лише розподілені, інші - лише централізовані, решта можуть бути або розподілені або централізовані. Коли дві функції розташовані на різних елементах (наприклад, одна знаходиться на прикордонному маршрутизаторі, а інша перебуває на сервері TE), для зв'язку між ними необхідний протокол комунікації. Натомість, коли дві функції перебувають на одному елементі (наприклад, прикордонному маршрутизаторі), немає необхідності в будь-яких протоколах комунікацій, і їхня взаємодія може просто спиратися на програмне забезпечення інтерфейсу (наприклад, API).

* Протоколи MPLS-TE (RSVP-TE і IGP-TE) розподілені на маршрутизаторах (але IGP-TE може пасивно запускатись на блоці обчислення шляху, коли він є централізованим, щоб поповнювати TED).

* Блок використання TE-тракту має бути розподіленим, оскільки він відповідає за маршрутизацію вхідних в ТЕ-тракт потоків і за вимірювання навантаження TE-тракту на прикордонних маршрутизаторах. Централізація цього блоку може вплинути на час відгуку системи MPLS-TE, через велику кількість інформації, якою будуть обмінюватися прикордонні маршрутизатори і TE-сервер.

* За визначенням, TE-менеджер завжди централізований.

* Агент TE-тракту може бути централізованим на мережевому сервері або розподіленим по прикордонним маршрутизаторам. В розподіленому режимі, він підтримує тільки TE-тракти, для яких він є головним. У централізованому сценарії, агент TE-тракту має глобальні знання всіх TE-трактів і потрібен комунікаційний протокол для обміну даними з прикордонними маршрутизаторами (з сигналізацією LSP), щоб запустити налаштування LSP при пошкодженні в мережі. Це може відбуватися, наприклад, за допомогою стандартного протоколу управління (SNMP). Зауважимо, що в централізованому режимі, повідомлення відмови мережі будуть керовані подією (наприклад, SNMP пасткою), з тим щоб звести до мінімуму кількість інформації, обмінюваної між прикордонними маршрутизаторами і TE-сервером.

* Адаптаційна функція TE-тракту завжди пов'язана з агентом ТЕ-тракту, тобто якщо TAG централізований/розподілений, TAD також відповідно централізована/розподілена. Якщо TAD централізований, між блоком використання TE-тракту на прикордонних маршрутизаторах і адаптацією TE-тракту необхідний протокол комунікації, щоб отримувати навантаження LSP. Динамічне виявлення навантаження LSP повинне бути кероване подією, щоб звести до мінімуму обсяг інформації обміну між прикордонними маршрутизаторами і TE-серверами (блок використання TE-тракту посилає сигнал блоку адаптації тільки при досягнення порогу, і це дозволяє уникнути останньому постійних консультацій в базі даних використання TE-тракту). Рознесення цих двох функції (адаптації TE-тракту та агента TE-тракту) недоцільне і вимагатиме обміну великою кількістю інформації.

* Блок обчислення шляху TE-тракту може бути як розподіленим, так і централізованим. (1) Якщо агент TE-тракту централізований, блок обчислення шляху TE-тракту також повинен бути централізованим (режим координації) оскільки рознесення цих двох функцій нераціональне і потребуватиме обміну великих обсягів інформації. (2) Але якщо агент TE-тракту розподілений, блок обчислення шляху TE-тракту може бути розподіленим або централізованим. Коли агент TE-тракту розподілений і блок обчислення шляху TE-тракту централізований, TC стає некоординованим, тому що перелік агентів ТЕ-тракту направляють запити незалежно від один одного.

2.5 Варіанти реалізації

Є кілька підходів для систем маршрутизації MPLS-TE, які отримуються при різних комбінаціях критеріїв, перерахованих вище. Ми обговоримо нижче деякі з цих підходів, які відповідають конкретним реалізаціям в нашій архітектурі [8]

2.5.1 Підхід Off/Cen/Coo MPLS-TE

Розглянемо підхід автономного режиму, коли шляхи TE-тракту, можливо включаючи резервні шляхи, періодично обчислюються без обмежень обчислень в часі, на координованій основі. На рис. 2.5 показано розподіл функцій MPLS-TE при такому підході. Курсор в позиції P1, відокремлює блоки, які централізовані на TE-сервері (див. вище курсору) від тих, які розподілені по прикордонним маршрутизаторам (під курсором). Так як ми в автономному режимі, функція адаптації ТЕ-тракту відсутня. Блоки обчислення шляху TE-тракту, агента ТЕ-тракту і адаптації TE-тракту централізовані (фактично TED ведеться на маршрутизаторі). Інші блоки: використання TE-тракту, IGP-TE, RSVP-TE розташовані на прикордонному маршрутизаторі (фактично IGP-TE і RSVP-TE розташовані на всіх маршрутизаторах). При такому підході, розміщення TE-трактів можна істотно оптимізувати, тому що функція обчислення шляху ТЕ-тракту знає всі запити і може виконати координоване обчислення шляху без обмежень в часі. У свою чергу, за визначенням цього автономного підходу не дозволяється реагувати на зміну руху матриці трафіку або пошкодження мережі, і це може призвести до втрати пакетів при перевантаженнях або зриву обслуговування при пошкодженні мережі. Крім того, навіть якщо такий підхід дозволяє заздалегідь створити резервні шляхи, такий захист не працюватиме при багаторазовому пошкодженні і, отже, стикається з деякими обмеженнями надійності. Таким чином, Off/Cen/Coo підхід явно страждає від нестачі надійності і швидкості реакції, оскільки він не виконує адаптацію до коливання трафіку і зміни топології.

Рисунок 2.5 - Off/Cen/Coo і On/Dis/Unc MPLS-TE механізми

2.5.2 Підхід On/Cen/Coo MPLS-TE

Якщо ми додамо блок адаптації TE-тракту і можливість перерозподілу TE-тракту до попередньої системи, вона потрапляє в мережевий режим, і стає системою On/Cen/Coo MPLS-TE. Такий підхід потребуватиме обміну великою кількістю інформації між прикордонним маршрутизатором та TE-сервером, і має від обмежений часу відклику. Відновлення після збою в роботі мережі відбувається у наступній послідовності: (1) Виявлення пошкодження TE-сервером, (2) Координоване обчислення шляху і (3) Повідомлення про нові шляхи всіх прикордонних маршрутизаторів. Така послідовність може зайняти багато часу, особливо коли постраждало багато магістралей

2.5.3 Підхід On/Dis/Unc MPLS-TE

В цьому мережевому підході система маршрутизації MPLS-TE містить функцію адаптації. Заявки обробляються некоординованим чином. TE-менеджер залишається централізованим, однак всі інші блоки архітектури розподілені по прикордонним маршрутизаторам, що відповідає позиції P2 для курсору централізований/розподілений на рис. 2.5. Такий підхід забезпечує менший час реакції та відновлення, ніж On/Cen/Coo завдяки своїй схемі On/Dis. В дійсності, на додаток до швидкості реакції, яку надає мережевий режим, всі функції даної системи MPLS-TE розташовані на одному елементі (прикордонний маршрутизатор), тобто немає необхідності у великій кількості обмінюваної між прикордонним маршрутизатором і TE-сервером інформації. У свою чергу, це позначається на оптимальності через некоординовану схему. Чим вищий рівень реакційної здатності та надійності, тим більше втрачаємо на оптимальності. Зауважимо, що оптимальність може бути порушена порядком обчислення шляху TE-тракт/LSP. Якщо замість некоординованого використовувати координований режим, то це призведе до системи On/Dis/Coo MPLS-TE

2.5.4 Підхід On/Dis/Coo MPLS-TE

Цей підхід передбачає, що кожен прикордонний маршрутизатор повинен усвідомлювати всі запити TE-тракту і діяти координовано з іншими мережевими прикордонними маршрутизаторами. Це покращує використання мережевих ресурсів, але як і раніше менш вигідне в порівнянні з автономним режимом через обмежену масштабованість. Насправді, прикордонні маршрутизатори можуть бути насичені, оскільки кожен з них має обмінюватися всією інформацією про свої власні TE-тракти/LSP з усіма іншими прикордонними маршрутизаторами. Цей підхід не масштабований через велику кількість TE-трактів у мережі та їх дій (зміна розмірів і т.д.). Отож, цей підхід не видається доцільним.

З аналізу вище видно, що кожен підхід має свої переваги і недоліки. В наступному розділі обговорюватиметься інший підхід, який об'єднує конфліктуючі режими, щоб взяти переваги кожного з них.

2.5.5 Гібридний підхід до MPLS-TE

Цей підхід базується на гібридній схемі: On/Dis/Unc- Off/Cen/Coo. У цьому випадку, TE-тракту обчислюються та встановлюються періодично (наприклад, щотижня) в автономному режимі. Між періодами, у мережевому режимі зміни топології та зміни у матриці передачі (трафіку) обробляються автоматично. Цей механізм підтримує два агенти TE-тракту: централізований, без функції адаптації, і розподілений, з функцією адаптації. Він підтримує також два блоки обчислення шляху, пов'язаних з відповідними агентами TE-тракту (рис. 2.6). Інші блоки розташовані тільки в прикордонних маршрутизаторах.

Таке поєднання двох підходів MPLS-TE видається вдалим, оскільки в ньому взяті переваги оптимальності пропоновані в автономному, централізованому і координованому режимах та швидкої реакції, надійності, масштабованості і живучості, взятих від мережевого, розподіленого і некоординованого режимів. При тому, цей підхід викликає проблеми взаємодії різних режимів. Цей підхід можна застосувати до захищеної топології MPLS-TE, в якій основні TE-тракти знаходяться під захистом запасних TE-трактів зі швидкою переадресацією на місці. Головні TE-тракти створюються мережевим методом, щоб забезпечити якомога більшу пристосовність і найменший можливий час реакції, тоді як запасні TE-тракти створюються в автономному стилі, без обмеження обчислень по часу, так що їхній шлях буде оптимізовано найкращим чином, щоб уникнути загасання резервних ресурсів.



Рисунок 2.6 - Гібридний підхід MPLS-TE

Ключова задача при роботі гібридної схеми полягає в керуванні перемиканням між мережевими та автономними операціями. Труднощі можуть виникати, коли в автономному режимі резервовані ресурси TE-LSP не задані явно. Якщо резервацію не зроблено, мережевий режим ігнорує ресурси, заброньовані автономним. Рішення може полягати у використанні пулів двох смуг пропускання у зв'язці, для мережевих та автономних ресурсів окремо. Ці пули динамічно коригується для уникнення блокування ресурсів пулу, коли ресурси іншого завантажені. При розрахунку шляху береться до уваги тип пулу смуги пропускання. Ще одна проблема пов'язана з послідовністю перетворення ТЕ-трактів між мережевим і автономним режимами (наприклад, міграція з мережевого в автономний). Вона полягає, в даному випадку, у передачі управління TE-тракту від розподіленого агента TE-тракту до централізованого. Розрізняють два сценарії управління TE-трактом (рис. 2.7): (1) Відокремити управління TE-трактам, створеними в централізованому режимі (автономні TE-тракти), від створених в розподіленому режимі (мережеві TE-тракти). Такий підхід дозволяє кожному агенту керувати своїми TE-трактами. Він передбачає два різні типи ТЕ-тракти (автономний TE-тракт і мережевий TE-тракт). (2) Централізоване і розподілене управління одного й того ж TE-тракту. При такому підході, управління тим чи іншим TE-трактом розділяється між централізованим та розподіленим агентами.

Рисунок 2.7 - Управління TE-трактом

Це можливо лише при акуратній співпраці обох агентів. В обох сценаріях потрібен протокол міжагентської комунікації (Inter-Agent Communication Protocol - IACP) (3) для синхронізації агентів та координації міграції між автономним та мережевим режимами. При роздільному управлінні TE-трактами протокол IACP переноситиме інформацію, пов'язану зі створенням, видаленням та розвитком мережевих TE-трактів від розподіленого агента до централізованого. Він також відповідає за інформацію про автономну оптимізацію від централізованого агента розподіленому. При спільному управлінні TE-трактом протокол IACP переносить інформацію дозволу зміни «власності» на TE-тракт між централізованим та розподіленим агентами. Наприклад, це може відбуватися у вигляді схеми Master-Slave (начальник-підлеглий), коли централізований агент є головним і повідомляє розподіленому, коли він має взяти під контроль TE-тракту, тобто коли в спрацьовує автономна оптимізація.

2.6 Використання переважного обслуговування (preemption) для покращення обчислення шляху MPLS-TE

В мережах трафік інжинірингу MPLS (MPLS-TE) з розподіленим на головних маршрутизаторах обчисленням тунельного тракту, тунельні запити обробляються поодинці, в некоординованому режимі, не зважаючи на майбутні та інші запити. Порядок розгляду запитів істотно впливає на оптимізацію мережі та ймовірність блокування. Якщо порядком надходження замовлень управляти неможливо, то в деяких випадках, переупорядкувати порядок запитів, використовуючи функцію вивантаження (preemption) - цілком до снаги. Розглянемо вплив порядку надходження запитів на ефективність роботи мережі та порівняємо 2 стратегії переважного обслуговування для переупорядкування запитів при використанні алгоритму обчислення найкоротшого шляху з обмеженнями (CSPF) при маршрутизації.

Так як вищезазначений «гібридний підхід» має неабиякі складнощі при реалізації, цілком ймовірно використання простішого On/Dis/Unc підходу, але для цього необхідно дещо розвинути його. Справа в тому, що алгоритм маршрутизації Дейкстри, який застосовується при некоординованому обчисленні шляхів, у своїй SPF реалізації має істотний недолік з боку абонента - дуже високою є ймовірність блокування пакетів. Тому розроблено декілька алгоритмів, які мають знизити цю ймовірність, серед них: алгоритми найширшого короткого та найкоротшого широкого шляхів, вимогливий до обчислювальних ресурсів мережі алгоритм мінімізації інтерференцій при маршрутизації, менш вимогливі алгоритми динамічної миттєвої маршрутизації та маршрутизації за допомогою існуючих профілів трафіку.

2.6.1 Вплив порядку надходження запитів на продуктивність системи

Розглянемо простий приклад: у мережу (рис. 2.8), що складається з 6 вузлів та зв'язків між ними з позначеними пропускними спроможностями (у Мб/с) кожного зв'язку, надходять запити на необхідну смугу пропускання (табл. 2.1) для передачі між вузлами 1 та 6 у відповідному порядку.

Рисунок 2.8 - Мережа обслуговування

В залежності від зміни порядку надходження запитів, змінюватиметься і кількість відмов у обслуговуванні. Для всіх можливих перестановок цього порядку кількість відмов зображено на рис. 2.9

Таблиця 2.1 - Смуга пропускання запитів на обслуговування

LSP	L1	L2	L3	L4	L5	L6
Пропускна спроможність (BW)	30	25	35	16	17	20

При цьому було використано алгоритм обчислення шляху CSPF. Серед 720 (6!) можливих порядків слідування запитів можна помітити, що найкращі результати досягнуто при «збільшуваному» порядку слідування, тобто коли найменш вимогливі запити обслуговуються першими, а при «зменшуваному» та «без змін» порядках - одному запиту відмовлено в обслуговуванні. Проте обчислювання всіх можливих порядків на реальних прикладах експонентно збільшуватиме складність маршрутизаторів. Управління встановленням LSP дозволяє збільшити продуктивність, але неможливо керувати порядком надходження запитів, та у деяких ситуаціях можна переупорядкувати встановлені LSP за допомогою механізму переважного обслуговування MPLS (MPLS-TE preemption mechanism).

Рисунок 2.9 - Кількість відмов у обслуговуванні

2.6.2 Динамічне переупорядкування LSP, використовуючи переваги в обслуговуванні

Протокол RSVP-TE включає механізм переваги в обслуговуванні (preemption), який дозволяє LSP з пріоритетом займати місце LSP з нижчим пріоритетом. Останній при цьому переадресовується запасним шляхом або чекає звільнення основного. Протокол має 2 параметра пріоритетності: на встановлення з'єднання та на його втримання. Найнижчий пріоритет позначається 7, а найвищий - 0. Забезпечується 2 види вивантаження (preemption): тверде та м'яке. При твердому потік з більшим пріоритетом одразу займає місце менш пріоритетного та останній роз'єднується і переадресовується альтернативними шляхами або чекає вивільнення основного. При м'якому існує деякий період співіснування обох потоків в одному LSP, що дозволяє планомірніше реагувати на зміну обстановки. Використання механізму може бути необхідне наприклад, коли трафіком даних інтернету зайняті найкоротші шляхи, і голосовий трафік VoIP інакше доставлятиметься із затримкою, що неприпустимо для нього.

Вищезазначений (рис. 2.9) приклад показує, що окрім прописаних у конкретному типі даних параметрах пріоритету можливо знизити ймовірність блокування, вишиковуючи запрошувані потоками смуги пропускання «за зростанням», тобто надаючи їм відповідні пріоритети самотужки. При цьому рівнів пріоритету лише 8, а потоків зазвичай більше, тому деякі різні потоки матимуть однаковий рівень пріоритету. Для призначення пріоритетів використовуються лінійний та нелінійний методи, яким відповідають нижчезазначені послідовності дій.

Лінійний (LR - Linear Repartition):

- сортування LSP-запитів за зростанням

- розбиття шкали запитів смуги пропускання на 8 інтервалів:

, (2.1)

де Bmax - максимальна запрошувана смуга пропускання;

Bmin - мінімальна запрошувана смуга пропускання;

та

- призначення кожному інтервалу Prio пріоритету:

 (2.2)

LSP з одного «інтервалу» матимуть однаковий пріоритет і впорядкувати їх між собою - неможливо. При цьому може бути дуже багато LSP одного пріоритету, яких не можна впорядкувати між собою.

Нелінійний (NLR - Not Linear Repartition)

- сортування LSP-запитів за зростанням

- розбиття шкали на 8 інтервалів Bi, кожен з яких включатиме n=N/8 LSP

- призначення кожному інтервалу Prio пріоритету: при цьому рівень пріоритету призначається однаковий всім n LSP даного інтервалу.

При цьому параметри Bmax та Bmin можуть встановлюватись заздалегідь менеджером TE. Тому LR метод можна використовувати в мережевому розподіленому режимі та робити динамічно розстановку пріоритетів на прикордонних маршрутизаторах. Нелінійний метод вимагає знання параметрів усіх існуючих потоків, тому може використовуватися лише в автономному централізованому режимі з розстановкою пріоритетів за допомогою агента TE.

2.6.3 Чисельна оцінка переваг використання переважного обслуговування

Для оцінки використовуватиме модель мережі з 15 вузлів та 28 двосторонніх зв'язків між ними (рис. 2.10). Пропускна спроможність тонких «ребер» дорівнює 12000, а товстих - 48000 умовних одиниць. Для оцінки підходу використовуватиметься CSFP-алгоритм. При досліді зробимо деякі припущення:

- всі потоки LSP довгострокові (статичні)

- реалізовується повнозв'язна модель між усіма прикордонними маршрутизаторами, тобто мережа завантажується 840 LSP = 15·144=Ner·(Ner - 1)·Nl, де Ner - кількість прикордонних маршрутизаторів (Edge Routers), Nl - кількість LSP між кожною парою прикордонних маршрутизаторів

- для розгляду різної завантаженості мережі помножуємо смугу пропускання LSP на коефіцієнт шкали трафіку k, що збільшується

- для кожного k проведемо 100 дослідів, генеруючи 840 запитів смуги пропускання, рівномірно розподілених між 1 та 50 Мб/с

Оцінювати будемо за показниками:

Відношення відмов LSP: процент запитів, яким було відмовлено через нестачу ресурсів

Максимально завантажений зв'язок: maxi BWi/Ci, де Ci - пропускна спроможність зв'язку i, BWi - кількість трафіку на даному вузлі [14].

Рисунок 2.10 - Топологія експериментальної мережі

Вплив порядку

Для початку відмітимо режими роботи мережі під час експериментів:

- CSPF: CSPF без зміни порядку LSP

- CSPF-IB-EO: CSPF з точним порядком за збільшенням смуги пропускання

- CSPF-DB-EO: CSPF з точним порядком зі зменшенням смуги пропускання

- CSPF-IB-LR-PO-CSPF: CSPF з лінійним розподілом переважного порядку зі збільшенням смуги пропускання

- CSPF-IB-NLR-PO: CSPF з нелінійним розподілом переважного порядку зі збільшенням смуги пропускання

На рис. 2.11 бачимо середню максимальну завантаженість мережі після забезпечення 840 LSP у випадковому порядку, за зростанням та зі зменшенням смуги пропускання по алгоритму CSPF. З графіку видно, що IB-EO-CSPF перевершує CSPF та DB-EO-CSPF. Це тому, що при сортуванні «зі зменшенням» великі потоки займають коротші шляхи, а згодом маленькі займають усю пропускну спроможність, яка залишилася, тому збільшується максимальне завантаження на зв'язці. При порядку «за збільшенням» маленькі LSP встановлюються першими і в коротших шляхах не вистачає пропускної спроможності для великих, тому вони займають ненайкоротші шляхи, які зазвичай більш ємнісні, тому і максимальне завантаження по зв'язках не таке велике. Можна помітити, що після k=0,7 зростання максимального навантаження стало менш стрімким, це означає, що для декількох запитів почали використовуватися ненайкоротші шляхи. На рисунку 2.12 зображено залежності відношення відмов LSP. Помітно, що метод сортування за зростанням дає кращі результати за спадаючий чи безладний методи. При множнику k=1,8 перевага CSPF-IB-EO становить 50%, що показує значний вплив черговості запитів на кількість відмов у обслуговуванні.



Рисунок 2.11 - Залежність середнього максимального завантаження зв'язку від k для CSPF без переваг в обслуговуванні

Рисунок 2.12 - Залежність середнього відношення відмовлених LSP від k без переваг в обслуговуванні

Переупорядкування на основі переваг в обслуговуванні

Застосовуючи механізм переваг в обслуговуванні отримуємо залежність максимального завантаження зв'язку (рис. 2.13), на якій можна побачити, що продуктивності IB-LR-PO-CSPF та IB-NLR-PO-CSPF майже не відрізняються від IB-EO-CSPF, тобто пропонований перерозподіл дійсно ефективно динамічно пере упорядковує запити. До того ж, у деяких випадках він навіть ближчий за IB-EO-CSPF до оптимального розподілу (при k=0,75)

З рис. 2.14 можна побачити, що лінійний та нелінійний методи майже не відрізняються з огляду на вірогідність відмови в обслуговуванні. При цьому вони набагато кращі за звичайний CSPF та незначно гірші за IB-EO-CSPF. Тобто застосовуючи переваги в обслуговуванні поверх протоколу CSPF ми досягаємо значного виграшу по показнику відмов LSP-запитам.

Рисунок 2.13 - Залежність середнього максимального завантаження зв'язку від k при лінійному та нелінійному методах



Рисунок 2.14 - Залежність середнього відношення відмовлених LSP від k при лінійному та нелінійному методах

Пошкодження в мережі

Для оцінки продуктивності обраного підходу при наявності пошкодження в мережі навантажимо 840 LSP з таким коефіцієнтом шкали трафіку k, щоб завантаження мережі було невеликим та відмови - відсутніми. Потім 100 разів здійснювався «розрив зв'язку» в якомусь з ребер для перерозподілу шляхів. Усереднені показники відмови в обслуговуванні після переадресації потоків, які слідували через пошкоджене ребро, показані в табл. 2.2. Кількість відмов у випадку звичайної CSPF збігається з кількістю потоків через пошкоджене ребро.

Таблиця 2.2 - Усереднена кількість відмов у обслуговуванні при пошкодженні ребра

Зв'язок	CSPF	IB-LR-PO	IB-NLR-PO
		Під |	Без	Під |	Без
14-15	28.42	12.26	12.27
		7.62	4.64	7.66	4.61
12-13	5.78	0.0	0.0
		0.0	0.0	0.0	0.0
8-9	12.02	7.38	7.40
		2.54	4.84	2.54	4.86
2-5	25.78	13.29	13.23
		6.01	7.28	5.62	7.31

При використанні методів, базованих на перевагах в обслуговуванні, деякі LSP, які зазнали шкоди, при переадресації можуть зайняти місце менш пріоритетних LSP, що поміж тим не зазнали прямого пошкодження. Тому окрім кількості відмов у обслуговуванні для IB-LR-PO та IB-NLR-PO позначаються ще кількості потоків, яким відмовлено під впливом пошкодження та без його впливу. В експерименті запити генерувалися з множником k=1,05. Підхід переупорядкування допомагає значно зменшити кількість відмов у обслуговуванні при пошкодженні мережі, або навіть звести до нуля (як у випадку пошкодження зв'язку 12-13)

Висновок

Проведений у розділі аналіз розподілу трафіку за допомогою методів інжинірингу трафіку показав існуючі підходи до функціонування архітектури ТЕ та їхні недоліки і гібридний підхід, який при деякому ускладненні архітектури та функціонування системи (використання протоколу міжагентської комунікації), дозволяє зменшити або нівелювати вплив тих недоліків. Крім того досліджено згубний вплив черговості запитів LSP до системи, а також оцінено переваги використання переважного обслуговування замість звичайної CSPF маршрутизації для збільшення ресурсу виробітки магістралей (зменшення максимального навантаження), а також зменшення відкинутих чи заблокованих потоків у випадку пошкодження мережі.

3. Оптимізація характеристик мереж MPLS

3.1 Обґрунтування критеріїв оптимізації

Для покращення розповсюдження інформації у мережах MPLS, які дедалі більше поширюються в магістральних мережах зв'язку України та іноземних держав (пояснення причин та зазначення переваг мультипротокольних мереж з комутацією за допомогою міток наведені в попередніх розділах), а оптимізація за допомогою трафік інжинірингу не враховує вартість побудови та експлуатації мереж. А в умовах ринку, що розвивається, кількість коштів необхідних для початку експлуатації мережі та надання послуг передачі даних надважлива і задача мінімізації затрат при досягненні пристойної якості зв'язку, який би відповідав потребам користувачів, є завжди актуальною.

Оптимальними особливостями нової технології MPLS, використовуваної в регіональних і глобальних мережах є введення декількох класів сервісу (Class of Service), а також показників якості обслуговування цих класів, зокрема середньої затримки, її варіації і частки втрачених пакетів. Однією з цілей впровадження технології MPLS є забезпечення заданої якості обслуговування потоків різних класів. Висока вартість телекомунікаційного устаткування мереж MPLS - маршрутизаторів і каналів зв'язку, прагнення найкращим чином використовувати комунікаційні ресурси мереж, і в першу чергу пропускні спроможності каналів зв'язку обумовлює як першочергові задачі оптимізації характеристик мереж MPLS. Ці задачі складаються з вибору пропускних спроможностей (ВПС) та розподілу потоків (РП).

Сутність задачі полягає в мінімізації вартості мережі при деяких обмеженнях. Такими обмеженнями можна вважати параметри середньої затримки розповсюдження для окремих класів потоків , середньої ймовірності втрати пакету (Packet Lost Ratio - PLR) та затримки на розповсюдження сигналу між окремими парами вузлів для відповідних класів потоків. Необхідно розглянути 2 останні види обмежень окремо, у вигляді побудованих математичних моделей. Хоча математичний апарат і буде досить схожий, але при об'єднанні в одну задачу всіх обмежень, її формулювання та розв'язання стає вкрай важким та громіздким, тому виходить за рамки даної дипломної роботи [19]

3.2 Оптимізація мережі з обмеженнями на відсоток втрачених пакетів

Задача вирішується за допомогою методів теорії графів та теорії масового обслуговування, тому зробимо математичну модель нашої мережі. Вона може бути задана у вигляді орієнтованого графу , де множина вузлів мережі, - множина каналів зв'язку. Задані пропускні спроможності каналів зв'язку , а також матриця вимог в розподілі каналів усіх класів , , де інтенсивність потоку -го класу, який необхідно передавати з ВЗ у вузол

Необхідно знайти такі маршрути передачі і розподілу потоків всіх класів , при яких забезпечуються обмеження на середню затримку і на частку (ймовірність) втрати пакетів -го класу .

У роботі [16] для потоку -го класу пріоритету і умови, що обслуговування відбувається з відносними пріоритетами отриманий вираз для - середньої затримки повідомлень.

 (3.1)

Ймовірність втрати пакетів класу в КЗ дорівнюватиме ймовірності стану, коли всі тимчасові канали виділені під потік класу в лінії зв'язку будуть зайняті дорівнює:

, (3.2)

де - пропускна спроможність базового каналу (наприклад, );

- число каналів у ЛЗ () виділених для передачі потоку -го класу;

- число пакетів у буфері комутатора під чергу -го класу;

- нормуючий множник.

Тоді ймовірність того, що не відбудеться втрат пакетів -го класу ні в одному з каналів мережі буде рівна:

(3.3)

А ймовірність (частка) втрачених пакетів -го класу буде рівна:

 (3.4)

Потрібно знайти такі маршрути передачі всіх вимог і розподіл потоків всіх класів при якому б виконувалися умови:

(3.5)

, (3.6)

Цю задачу можна вважати узагальненою задачею РП [2]. Вона є комбінованою задачею, що складається з пари задач ВПС та РП. Алгоритм її розв'язання містить декілька етапів, що складаються з кінцевої кількості однотипних ітерацій.

Розглянемо алгоритм розв'язання узагальненої задачі РП на прикладі потоків трьох класів . Алгоритм складається з (2k+1) етапів на кожному з яких вирішується певне завдання РП потоків відповідного класу k по відповідному обмеженню.

1 етап. На цьому етапі вирішуємо задачу розподілу потоку класу при обмеженнях .

Етап складається з поетапних ітерацій, на кожній з яких знаходимо розподіл потоків чергової вимоги.

1а ітерація.

1. Знаходимо початкову умовну метрику:

(3.7)

2. Вибираємо першу вимогу з матриці і знаходимо найкоротший шлях .

3. Розподіляємо потік від вимоги і знаходимо:

(3.8)

Кінець першої ітерації.

kта ітерація.

Нехай вже проведені (k-1) ітерацій і знайдений розподіл потоків . Розглянемо кту ітерацію.

1. Знаходимо умовну метрику:

(3.9)

2. Вибираємо чергову вимогу з матриці і знаходимо найкоротший шлях в матриці .

3. Перевіримо можливість передачі вимоги шляхом :

(3.10)

Якщо умова (3.10) виконується, то розподіляємо потік від вимоги по шляху і знаходимо:

(3.11)

І переходимо до 1го кроку наступної (k+1)ї ітерації. В іншому разі продовжуємо поточну ітерацію кроком 4.

4. Шукаємо такий шлях мінімальної довжини між вузлами та , для якого виконується умова , де - резерв шляху по пропускній спроможності, що визначається згідно формули (3.10).

5. Передаємо потік від вимоги і знаходимо новий розподіл потоків:

(3.12)

Вказані ітерації проводимо до повного розподілу потоку вимог класу 1. В результаті отримуємо розподіл потоків РП такий, що .

Переходимо до другого етапу.

Другий етап. На цьому етапі будуємо допустимий потік, який задовольняє обмеженню:

 (3.13)

Перш за все перевіряємо умову (3.13). Якщо вона виконується, то можна відразу ж переходити на етап 3. В іншому разі виконуємо другий етап, починаючи з першої ітерації.

kта ітерація.

1. Знаходимо умовну метрику:

(3.14)

2. Знаходимо найкоротші шляхи в метриці, яку попередньо знайшли (3.14):

3. Знаходимо потік по найкоротших шляхах в метриці .

4. Перевіряємо умову можливої оптимізації розподілу потоків по величині :

(3.15)

Якщо умова (3.15) виконується, то можна переходити на крок 5, інакше зупиняємо виконання задачі. Завдання РП не вирішуване при заданих пропускних спроможностях каналів і матриці вимог на обслуговування .

5. Відшукуємо першу вимогу для якого виконується нерівність (3.16):

(3.16)

де - шлях передачі вимоги , який використовується в поточному розподілі ,

- найкоротший шлях в метриці .

Для вимоги здійснюємо збурювання потоку і перенаправляємо його з шляху на шлях . І знаходимо:

(3.17)

6. Перевіряємо умову . Якщо так, то закінчуємо другий етап, інакше збільшуємо клас і переходимо на крок 4 другого етапу, вибираємо наступну вимогу, що задовольняє умові (3.15).

В результаті обчислення етапу 2 отримаємо допустимий розподіл потоку класу 1, для якого:

(3.18)

Третій етап. На цьому етапі перевіряємо виконання для потоку обмеження на частку (ймовірність) втрати пакетів:

 (3.19)

Якщо (3.19) виконується, то третій етап пропускаємо та переходимо до четвертого. Якщо ж ні, то шукаємо такий розподіл потоку при якому виконуються обидва обмеження (3.18) і (3.19). З цією метою формуємо допоміжне завдання: знайти такий розподіл потоку , для якого б виконувалося:

за умов

Для цієї мети використовуємо комбіновану метрику:

(3.20)

де

1а ітерація.

1. Для потоку обчислюємо метрику

, ,

а вибираємо за умови .

2. Вибираємо найкоротші шляхи в метриці і потік по найкоротших шляхах . Перевіряємо можливість поліпшення потоку:

(3.21)

Якщо вона існує (нерівність виконується), то переходимо до третього крок, в іншому разі - зупиняємо виконання, бо потік не може бути покращений і завдання РП не має розв'язків.

3. Знаходимо першу вимогу для якого:

(3.22)

де - поточний шлях передачі вимоги () для потоку, - найкоротший шлях для вимоги () у метриці . І перенаправляємо потік вимоги зі шляху на шлях і знаходимо новий розподіл потоків:

(3.23)

Перевіряємо умову:

 (3.24)

Якщо умова (3.24) виконується, то закінчуємо третій етап, коли ж ні - переходимо на крок 2 наступної ітерації. Кроки 2-4 повторюваний до тих пір, поки умова (3.24) не почне виконуватися.

Далі переходимо до знаходження розподілу потоку другого класу , до того ж так, щоб не були порушені обмеження (3.18) і (3.19) для потоку . Для цього виконуємо етапи 4, 5 які аналогічні етапам 2 і 3. При цьому, розподіл потоку знаходимо на пропускних спроможностях каналів, що залишилися, а щоб не порушувалися обмеження (3.18) і (3.19) використовуємо бар'єрну або штрафну функцію для потоку . В якості бар'єрної функції використовуємо:

(3.25)

а як штрафна:

(3.26)

Отже, запропонований алгоритм розв'язання задачі розподілу потоків (узагальненої форми) при врахуванні обмежень на середню затримку пакетів відповідних класів та на відсоток втрачених пакетів. Для врахування обмеження на час доставки інформації між двома вузлами необхідно розробити трішки інакший алгоритм.

3.3 Оптимізація мережі з обмеженнями середньої затримки для потоку та між визначеною парою вузлів

Як і попереднє завдання, ця задача вирішується за допомогою методів теорії графів та теорії масового обслуговування, тому зробимо математичну модель мережі [10]. Вона може бути задана у вигляді орграфу , де множина вузлів мережі, - множина каналів зв'язку, - питомих набір пропускних спроможностей (ПС) каналів, вартість .

Матриця вимог вхідних потоків відповідних класів , , , де інтенсивність потоку -го класу, який необхідно передавати з ВЗ у вузол , обмеження на середню затримку для класів потоків , , а також обмеження на часткові затримки між заданими парами вузлів , де

Необхідно обрати такі пропускні спроможності каналів зв'язку і знайти розподіл потоків всіх класів , при яких вартість мережі є мінімальною і при цьому в повному обсязі забезпечуватимуться обмеження на середню затримку. Можна описати математичну модель задачі таким чином:

Знайти

(3.27)

при обмеженнях

 (3.28)

(3.29)

(3.30)

Припущення, що обслуговування потоків окремих класів сервісу (CoS) в каналах пріоритетне, з відносними пріоритетами, що убувають із зростанням номера класу (тобто ) в роботі було отримано за допомогою виразу для

(3.31)

- потік, класу i в КЗ (r,s).

Розглянемо величину затримки між вузлами для потоку класу :

(3.32)

де - маршрут передачі потоку класу від вузла i до j.

3.3.1 Алгоритм ВПСРП

Дане завдання є комбінованим завданням, що складається з пари завдань ВПС і РП. Опишемо алгоритм її розв'язання. Він складається з попереднього етапу і скінченного числа однотипних ітерацій.

На попередньому етапі знаходимо пропускні спроможності каналів зв'язку і початкові розподіли потоків всіх класів . Після того переходимо до виконання першої ітерації.

(+1)итерация

Нехай вже проведено ітерацій і знайдені поточні ПС та розподіл потоків , а також величина загальної вартості .

1. Для заданих пропускних спроможностей вирішуємо задачу РП і знаходимо новий розподіл потоків всіх класів

(3.33)

2. Для знайдених потоків розв'язуємо задачу ВПС і знаходимо нові ПС всіх каналів і вартість мережі .

3. Порівняння. Якщо , де - задана точність, то можна завершувати виконання завдання. Знайдені ПС і розподіл потоків всіх класів - шукані, якщо нерівність не виконується, то збільшуємо і переходимо до наступної ітерації.

3.3.2 Алгоритм розв'язання задачі ВПС

Розглянемо тепер задачу ВПС, що описується моделлю (3.27)-(3.30) при фіксованому РП .

Дане завдання відноситься до задачі дискретного програмування і для її розв'язку пропонується використовувати метод ПАВ. Він складається з двох процедур та .

Процедура (відсів по обмеженням)

Дана процедура складається з відсіву по обмеженням (3.28) і (3.29). Нехай визначена початкові множини допустимих варіантів по кожному каналу .

Здійснюємо відсів нижніх значень пропускних спроможностей.

Процедура відсіву для каналів зв'язку по обмеженню (3.28) має вигляд:

(3.34)

Тут відсіваються всі нижні значення ПС , де - максимальне значення ПС при якому виконується (3.31).

Аналогічний вигляд має процедура відсіву по обмеженнях (3.29). Вона записується для КЗ () так:

 (3.35)

Вказану процедуру повторюємо зі всіма КЗ і всіма потоками В результаті отримуємо зменшення множини варіантів , .

Процедура .

У ній відбувається відсів по величині критерію .

Спочатку задається величина порогу відсіву

(3.36)

Запишемо процедуру відсіву для каналу зв'язку :

(3.37)

Тут відсіваються всі верхні значення ПС: , де - мінімальне значення ПС, з якого починає виконуватися (3.38). Вказану процедуру повторюємо зі всіма КЗ .

Позначимо отриману множину варіантів через .

Можливі 3 випадки:

а) для всіх , тобто відсіву немає, тоді необхідно зробити перехід на процедуру , із звуженою множиною варіантів, для чого обираємо поріг ;

б) , тобто немає допустимих варіантів. Тоді знову перехід на процедуру із розширенням множини варіантів для чого обираємо ;

в) і для всіх . Тоді переходимо на процедуру .

Вказану послідовність процедур , повторюємо доти, доки не отримаємо таку скорочену множину варіантів по всім каналам зв'язку, з яких допустимий варіант можна буде вибрати звичайним перебиранням.

Кінець роботи алгоритму. Отримана мінімальна вартість побудови мережі буде оптимальною для забезпечення потреб споживачів із заданими вимогами до середньої затримки для окремих видів трафіку, пропускної здатності, відсотку втрачених пакетів.

Висновки

В цьому розділі обґрунтовано необхідність оптимізації мереж MPLS за такими критеріями як: середня затримка розповсюдження для окремих класів трафіку, ймовірність втрати пакету визначеного класу, а також середня затримка розповсюдження між парами кореспондуючих вузлів. Побудовано математичну модель та алгоритм знаходження мінімальної вартості мережі при заданих обмеженнях на показники якості обслуговування.

4. Чисельне моделювання та аналіз результатів

4.1 Розробка застосунку для обчислення мінімальної вартості мережі

Для знаходження закономірностей залежності оптимальної вартості мережі при заданих обмеженнях на середню затримку розповсюдження пакетів відповідного класу від цих обмежень та від інтенсивності трафіку, тобто для розв'язання задачі (3.27) - (3.30), на мові програмування C# напишемо програму, яка відповідно заданій структурі мережі телекомунікаційної мережі України (рис. 4.1) знаходитиме мінімальну вартість мережі за умов виконання (3.28) та (3.30).

Рисунок 4.1 - Структура транспортної мережі України

4.1.1 Опис програми

Для опису програми зазначимо основні класи та функції, використовувані у тексті та при написанні застосовання:

Math.Sqrt - має параметр-змінну типу double та повертає квадратний корінь числа, яке в ній перебуває

Convert.ToDouble - має параметр-змінну типу string, int, long, bool або іншого та перетворює значення у змінну типу double.

Convert.ToInt32 - конвертує параметр строкового або іншого типу в int.

Convert.ToDecimal - має параметр-змінну типу double, string, int, long, bool бо іншого та перетворює значення у змінну типу decimal

Convert.ToString - має параметр-змінну типу double, in, long, bool або іншого та перетворює значення у змінну типу decimal

radioButton#.Checked - визначає (або задає) властивість вибран/не вибран елемент «Перемикач вибору»

this.textBox#.Text - повертає у змінну типу string вміст текстового вікна # даного класу (або встанавлює його)

MessageBox.Show - параметрами є: текст та назва вікна, що спливає

mu.Show - де mu - об'єкт класу Mu: Form, відображає форму Mu