Задачі маршрутизації в гібридній мережі передачі даних Єдиної супутникової системи передачі інформації України

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

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

Третій розділ присвячений побудові математичної моделі ГМЗ і методики визначення оптимально плану розподілу навантаження в таких мережах, а також оцінки імовірнісно-часових характеристик ГМЗ. Приведено чисельні результати розрахунків на прикладі МПД ЄССПІ.

Розглянемо гібридну мережу передачі даних складає з N вузлів, об'єднаних L наземними каналами зв'язку ємністю С_gdl (біт/с), l = 1,2,…,L, по заданій топології. Мережа розділена на M регіонів, кожний з яких має супутниковий вузол зв'язку (СУ).

Супутникові вузли об'єднані через транспондер космічного апарата ємністю С_s (біт/с). Матриця вхідних потоків [_ij] визначає в пакетах/с інтенсивність потоків повідомлень між будь-якими парами вузлів мережі i і j , де i,j = 1,2,…,N.

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

, (1)

,

де T_l - затримка даних у l-каналі, _gdl - інтенсивність потоку даних у l-каналі, 1/_d - середня довжина пакета.

Аналіз супутникової мережі значною мірою залежить від використовуваного методу багатостанційного доступу до супутникового ретранслятора. Стандартні методи багатостанційного доступу містять у собі частотний поділ з жорстко закріпленими каналами (FDMA) і наданням їх за вимогою (DAMA), часовий поділ (TDMA), і кодовий поділ (CDMA). Детальне обговорення і розгляд схем роботи і переваг кожного з перерахованих вище методів не є метою даної роботи і може бути знайдене в цілому ряді джерел.

Найбільш простим і широко використовуваним протоколом випадкового доступу є ALOHA (синхронна або “чиста”), вона не вимагає ні спеціального резервування, ні виділення каналів. Максимальна ефективність синхронної ALOHA складає 0,38, даний протокол є найбільш розповсюдженим для передачі даних у супутникових системах зв'язку.

У випадку передачі мовного трафіку потрібне виділення каналів зв'язку з заданою пропускною здатністю (2,4; 4,8; 8; 16 Кбіт/с) у залежності від типу використовуваного мовного кодеку, для чого використовується алгоритм DAMA.

При встановленні мовних з'єднань їм виділяється необхідна кількість ресурсів, за рахунок зменшення ресурсів доступних для передачі даних, при розриві мовних з'єднань усі ресурси ретранслятора знову виділяються для передачі даних.

Далі ми будемо розглядати супутникову мережу МПД ЄССПІ виходячи з наступних припущень:

1. Усі СУ сумарно генерують пуасонівський потік даних інтенсивністю _d пакетів/с і пуасонівський потік мовних викликів інтенсивністю _v викликів/с (без врахування повторних передач через колізії). Повні потоки (вхідні потоки плюс потоки повторних передач) даних і мовних викликів позначимо як _d¹ і _v¹ відповідно.

2. Пакети даних мають фіксований розмір. Тривалість мовних викликів має експоненціальний розподіл із середньою тривалістю 1/_s секунд.

3. Використовувані супутникові канали розділені на часові слоти, з довжиною кожного слоту T, що рівна часу передачі одного пакета. S - затримка на передачу в супутниковому каналі, що вимірюється в довжинах слотів.

4. Затримка на повторну передачу при виявленні колізії рівномірно розподілена в діапазоні 0… K слотів.

Припустимо що супутниковий канал має ємність С_s , що розділена на дві частин: С_sd для передачі даних і С_sv - для мови, що утворює N_s каналів для повідомлень, що підрозділяються на N_d каналів для даних і N_v каналів для мови.

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

, (2)

, ,

де t_rx - середній час на повторні передачі, а експоненціальний множник у круглих дужках - середнє число повторних передач, m - число каналів з N_s виділених для передачі даних. В (2) зневажається часом перебування пакетів у черзі СУ, оскільки імовірність очікування на передачу повідомлення в такій системі дуже низька.

Розглянемо окремо випадок, коли для передачі даних можуть використовуватися вільні мовні канали, і припустимо, що затримка даних досягає свого стаціонарного значення при активності k (0<k<N_v) мовних викликів, тоді середня затримка пакетів даних у супутниковому каналі може бути представлена наступним виразом:

(3)

де d_data визначається виразом (2).

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

(4)

де _d - інтенсивність потоку викликів від -того СУ, D_d визначається (3).

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

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

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

У методиці рішення задачі оптимальної маршрутизації в гібридній мережі зв'язку, ми будемо дотримувати даної гіпотези.

Інтенсивність потоків у гілках наземної мережі (_gdl) і в супутниковому каналі (_d, _v) є функціями від вхідних інтенсивностей потоків даних та мовних викликів (_ij, Г_ij) та коефіцієнтів їх розподілу між наземною та супутниковою мережами g_{ij ,}і зв'язані лінійно наступними співвідношеннями:

, (5)

де n_ij (n_i) - число шляхів між джерелом i і одержувачем j (), () - номер СУ регіону в якому розташований вузол i (j);

p^k_ij (p^k_i) - коефіцієнт, що визначає частину потоку між парою ij() для k-того маршруту;

(^k_ij)_l - індикаторна функція вона дорівнює одиниці якщо k-тий маршрут між вузлами ij проходить через l-ту гілку наземної мережі, і дорівнює нулеві в протилежному випадку;

g_ij - коефіцієнт, що визначає частину потоку між парами вузлів i та j, що проходить по наземні мережі.

Для супутникового каналу, повна інтенсивність вхідного потоку даних _d, є сумою інтенсивностей потоків від кожного супутникового вузла з M супутникових вузлів:

(6)

Інтенсивності _d є лінійною комбінацією g_ij і _ij:

,

де R - регіон, що містить СУ , R - регіон, що не містить СУ .

Утворимо вектор x = {(g_ij, p^k_ij), i,j,k} з коефіцієнтів розподілу потоків між супутниковими і наземними мережами та коефіцієнтів розподілу потоків між маршрутами в наземній мережі, тоді задача формування плану розподілу потоків зводиться до мінімізації цільової функції f(x) при наступних граничних умовах:

min_(x) f(x),

0 < g_ij, p^k_ij < 1,

_gdl < С_gdl, _d < C_sd,, _v < C_{sv ,}l (8)

, i,j

Задача оптимізації (8) може бути вирішена різними способами, наприклад, методами лінійного і нелінійного програмування, а також методом послідовного квадратичного програмування (Sequential Quadratic Programming - SQP). Ми використовували метод послідовного квадратичного програмування в припустимій області (FSQP). Основна перевага даного методу перед іншими існуючими методами - висока швидкість збіжності, так називана “надзбіжність”, зручність алгоритмічної реалізації.

Для мінімізації загальної затримки у випадку передачі в мережі тільки даних сконструюємо наступну цільову функцію:

, (9)

де - сумарна інтенсивність потоку даних, що надходить у мережу, _d - інтенсивність потоку даних у супутникової мережі. Дана цільова функція являє собою середню затримку пакетів даних у мережі.

Якщо для передачі даних можуть використовуватися вільні мовні канали, то тоді цільова функція f₁ приймає наступний вигляд:

, (10)

де D_MB - затримка в супутниковому каналі визначається виразом (4).

Задача (10) у цьому випадку зводиться до мінімізації середньої затримки даних у мережі (9), при нормованій якості обслуговування мовних викликів.

Далі розглядається використання описаної вище методики на прикладі Відомчої телекомунікаційної мережі (ВТМ) Національного космічного агентства України (НКАУ) - складової частини МПД ЄССПІ. Дана мережа містить 8 вузлів і 20 каналів зв'язку, мережа розділена на два регіони по чотири вузла в кожному, у кожному з регіонів розташована по одному СУ (вузли 1, 7).

Розглядається спочатку випадок передачі тільки даних в зазначеній мережі. Матриця інтенсивностей вхідних потоків _ij однорідна, середня довжина пакета складає 512 біт для наземної мережі, і для супутникової мережі вона фіксована і дорівнює 1024 біт. Ємність усіх наземних каналів зв'язку складає 64 Кбіт/с (C_l), супутникового каналу C_s - 1,5 Мбіт/с.

При цьому у наземній мережі існує наступний алгоритм маршрутизації: для передачі пакетів даних використовуються найкоротші по числу транзитів маршрути, а при існуванні двох або більш маршрутів від даного вузла з рівною довжиною мінімального шляху до вузла призначення, потік розподіляється між усіма маршрутами, відповідно до значень коефіцієнтів p^k_ij (6).

Розглянемо, наприклад, передачу пакетів по наземної мережі між вузлами 1 і 8. Мінімальне число транзитів між цими вузлами дорівнює 4, і в мережі існує 4 альтернативних маршрути в мережі з даним числом транзитів:

(1) 1 3 5 7 8,

(2) 1 3 5 6 8,

(3) 1 3 4 6 8,

(4 ) 1 2 4 6 8.

Після визначення всіх маршрутів для кожної пари вузлів, ми зможемо одержати значення потоків _gdl для кожного каналу в мережі l = 1,2,…20...

Значення маршрутних коефіцієнтів g_ij і p^k_ij можуть бути отримані в результаті рішення задачі (8) з цільовою функцією (9).

Результати розрахунку коефіцієнтів g_ij приведені в табл. 1, а і їхня залежність від інтенсивності вхідного навантаження.

Розглянемо отримані чисельні результати. При незначному навантаженні на гібридну мережу всі потоки проходять по наземної мережі, тому що затримка в ній мала (порядку 0,02 с) у порівнянні із супутникової мережею, де тільки затримка на поширення складає близько 0,3 с.

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

Аналітичні результати показують, що пари вузлів, що знаходяться на максимальній відстані (по числу транзитів), починають першими передавати навантаження в супутникову мережу (наприклад, вузли 1і 8), потім вузли, що знаходяться на відстані на одиницю менше (1 і 7), і т.д. Це так звана маршрутизація “від самого далекого вузлу”.

Таблиця 1. Значення коефіцієнтів g_ij для мережі передачі даних (_ij = 10 пакетів/с)

Розглянемо далі зміну маршрутних коефіцієнтів p^k_ij у наземній мережі. Тут спостерігається наступна тенденція: при збільшенні навантаження на мережу відбувається концентрація потоку між парами вузлів на одному із шляхів рівної довжини (по числу транзитів), на інших же інтенсивність потоку падає до нуля.

Це пояснюються тим, що при досягненні граничного значення навантаження в 10 пакетів/с, частина вхідного потоку починає передаватися через супутникової канал. У результаті чого порушується симетрія розподілу потоків у наземної мережі, і затримка пакетів стає різної для шляхів рівної довжини по числу транзитів, а весь потік концентрується на шляху з мінімальною величиною затримки.

Можна сказати, що відбувається “зняття виродження”. Причому, чим ближче розташовані вузли, тим при меншій інтенсивності вхідного навантаження відбувається концентрація потоку на одному із шляхів рівної довжини.

Таблиця 2. Значення коефіцієнтів g_ij при нормі втрат мовних викликів не більше 5%

Далі розглянуто одночасну передачу мовних викликів і даних у мережі. Параметри системи наступні - супутниковий канал має 50 дуплексних каналів по 30 Кбіт/с які використовуються при передачі мовних повідомлень і даних, причому мовні виклики мають вищий пріоритет.

Матриця вхідних інтенсивностей потоків однорідна _ij = 10 пакетів/з, _ii = 0, середня довжина пакета складає 512 біт для наземної мережі, а для супутникової мережі вона фіксована і складає 1024 біт. Ємність усіх наземних каналів зв'язку складає 64 Кбіт/с (C_l). Інтенсивність мовних викликів у супутниковому каналі складає 6 викликів на хвилину, із середньою тривалістю 4 хв.

Результати розрахунку маршрутних коефіцієнтів g_jj при нормі втрат мовних викликів у мережі не більше 5% приведені в таблиці 2.

Отримані результати досить схожі з розглянутими вище випадками, тому до них застосовні аналогічні висновки. Але затримка даних у цьому випадку на 50% вище, ніж у випадку монопольного використання супутникового каналу для передачі даних, що легко пояснити.

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

Для оцінки часу доставки пакетів даних по гібридній мережі використано математичну модель, що представляє собою L послідовно з'єднаних однолінійних систем масового обслуговування типу M/M/1.

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

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

При включенні в тракт передачі даних одного супутникового каналу зв'язку , що додається до L наземних ланок передачі, функція розподілу часу доставки по такому тракту може бути записана в наступний спосіб:

, (11)

Де

,

- відповідні параметри для наземних та супутникової ланок передачі.

В четвертому розділі проведене імітаційне моделювання ВТМ НКАУ. При моделюванні використовувався, запропонований оригінальний алгоритм маршрутизації. Він заключається в тому, що усі пакети передаються вузлами по найкоротших шляхах, але якщо пакет не може бути переданий вузлом в даний момент часу по найкоротшому шляху (наприклад, в результаті переповнення FIFO-буфера передавача/приймача), то вузол намагається його передати по наступному найкоротшому шляху і т.д. Тільки якщо всі такі спроби є безуспішними, то вибирається шлях через супутникову мережу.

Результати визначення на ЕОМ для ВТМ НКАУ середнього часу затримки пакетів даних для інтенсивності вхідного потоку = 0 - 12 пакетів/с приведені на рис. 6. Крапками показані експериментальні результати, суцільною лінією - інтерполяційна крива, поруч же приведені аналітичні результати рішення задачі оптимальної маршрутизації.

Розглянемо результати імітаційного моделювання ВТМ НКАУ. Результати моделювання ВТМ показують, що при заданій точності моделювання запропонований алгоритм динамічного керування розподілом пакетів дозволяє дуже близько наблизитися до результатів аналітичного рішення задачі оптимальної маршрутизації.

Різниця між результатами при високому навантаженні (8-12 пакетів/с) не перевищує 5%, що показує практичну цінність, як результатів моделювання, так і аналітично отриманих результатів рішення задачі оптимальної маршрутизації.

При низькому навантаженню (менш 8 пакетів), запропонований алгоритм динамічної маршрутизації дає вже на 30% відсотків гірші результати. Це зв'язано з тим, що аналітичне рішення задачі показує, що в цьому випадку весь трафік повинний проходити по наземній мережі.

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

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

Також результати моделювання показали, що при навантаженні в 12 пакетів/с імовірність доставки повідомлень за час 0,6 с складає більш 99%. Якщо супутниковий канал не використовується, то цей показник складає всього 78%, що набагато нижче норми - 95%.

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

ВИСНОВКИ

У процесі проведених досліджень отримані наступні результати:

1. Розроблено нову математичну модель функціонування ГМЗ, що дозволяє на основі запропонованих коефіцієнтів поділу потоків знаходити затримку повідомлень в гілках наземної мережі і супутниковому каналі в залежності від вхідного навантаження, а також імовірність відмов у встановленні з'єднання для мовних викликів. При побудові моделі використані наступні наближення для розрахунки затримки повідомлень в наземній мережі: потоки повідомлень, що поступають у вузли мережі, є пуасонівськими, довжини повідомлень в наземній мережі мають експоненціальний розподіл, потоки на різних вузлах незалежні і часи обслуговування повідомлень також незалежні на сусідніх вузлах. Аналіз супутникової мережі проведено в випадку використання протоколів випадкового доступу типа ALOHA до ресурсів супутникового ретранслятора, але модель цілком є інваріантною до вибору методу та протоколу багатостанційного доступу до супутникового ретранслятора. Додатково розглянуто випадок передачі поряд з даними мовних викликів в супутниковому каналі. При цьому при встановленні мовних з'єднань їм виділяється необхідна кількість ресурсів, за рахунок зменшення ресурсів доступних для передачі даних, при розриві мовних з'єднань усі ресурси ретранслятора знову виділяються для передачі даних.

2. На основі запропонованої математичної моделі вперше розроблена методика визначення оптимального плану розподілу потоків у всій гібридній мережі зв'язку, включаючи наземну і супутникову мережі. Ціль оптимального плану розподілу потоків при цьому полягає в тому, щоб розділити повну інтенсивність потоків між кожною парою адресатів у мережі між декількома шляхами від відправника до адресата так, щоб загальний результуючий потік по лініях мережі мінімізував задану вартісну функцію. За таку функцію використовується значення середньої затримки передачі повідомлень у мережі з урахуванням наближення Клейнрока. Цей вибір заснований на гіпотезі, що оптимальний розподіл потоків можна одержати, оптимізуючи інтенсивність потоків по гілках мережі, і зневажаючи іншими імовірнісними характеристиками потоків, оскільки в цьому випадку функція вартості не залежить від вищих моментів потоків. Вирішення зазначеної проблеми базується на чисельному рішенні задачі оптимізації середньої затримки повідомлень в ГМЗ в припустимій області перемінних методом послідовного квадратичного програмування (Feasible Sequential Quadratic Programming). Основна перевага даного методу перед іншими існуючими методами - висока швидкість збіжності, так звана “надзбіжність”, зручність алгоритмічної реалізації. Розроблений прикладний пакет програм на мові програмування С++, що дозволяє вирішувати проблему знаходження оптимального плану розподілу потоків повідомлень для широкого класу гібридних мереж різної розмірності. Отриманні чисельні результати використання зазначеної вище методики на прикладі ВТМ НКАУ.

3. Використовуючи отримані в попередніх двох пунктах результати розроблена методика визначення імовірнісно-часових характеристик ГМЗ. Для оцінки часу доставки пакетів даних по гібридній мережі використано математичну модель, що представляє собою L послідовно з'єднаних однолінійних систем масового обслуговування типу M/M/1. Отримана функція розподілу часу доставки повідомлень при включенні в тракт передачі даних одного супутникового каналу зв'язку , що додається до L наземних ланок передачі. За допомогою даної методики проведена чисельна оцінка імовірнісно-часових характеристик ВТМ НКАУ.

4. На базі агрегативного підходу розроблений імітаційний алгоритм функціонування розглянутої системи. Для програмної реалізації зазначеного алгоритму використана мова програмування С++. Запропонований оригінальний алгоритм динамічного перерозподілу потоків для гібридної мережі на прикладі ВТМ НКАУ.

5. В результаті проведеного імітаційного моделювання на прикладі функціонування ВТМ НКАУ отримані чисельні дані, які підтвердили коректність запропонованих математичних моделей, та ефективність запропонованого алгоритму динамічного перерозподілу потоків в ВТМ НКАУ.