НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ“

КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Нежуренко Олександр Григорович

УДК 621.394/396:520.6.04

ЗАДАЧІ МАРШРУТИЗАЦІЇ В ГІБРИДНІЙ МЕРЕЖІ ПЕРЕДАЧІ ДАНИХ ЄДИНОЇ СУПУТНИКОВОЇ СИСТЕМИ ПЕРЕДАЧІ ІНФОРМАЦІЇ УКРАЇНИ

05.12.02 – Телекомунікаційні системи та мережі

АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня

кандидата технічних наук

Київ – 2004

Дисертацією є рукопис

Робота виконана в Національному технічному університеті України “Київський політехнічний інститут” на кафедрі телекомунікаційних систем та мереж

Науковий керівник:

доктор технічних наук, професор

Сундучков Костянтин Станіславович,

Національний технічний університет України
“Київський політехнічний інститут”,

професор кафедри телекомунікаційних систем та мереж

Офіційні опоненти:

доктор технічних наук, професор

Беркман Любов Наумівна,
Державний університет інформаційно-комунікаційних технологій,
завідувач кафедри телекомунікаційних систем

кандидат технічних наук

Дзюба Юрій Володимирович,

ТОВ “Телеком-АТЕЛ”, технічний директор

Провідна установа:

Український науково-дослідний інститут зв'язку (м. Київ)

Державного комітету зв’язку та інформатизації та України

Захист дисертації відбудеться “ 9 ” квітня 2004 р. о 15-00 годині на засіданні спеціалізованої вченої ради Д 26.002.14 Національного технічного університету України “Київський політехнічний інститут” за адресою:

256056, Київ, проспект Перемоги , 37, навчальний корпус № 1 , аудиторія 163

З дисертацією можна ознайомитися у бібліотеці Національного технічного університету України “Київський політехнічний інститут” за адресою:

256056, Київ, проспект Перемоги , 37

Автореферат розісланий “__4__”_березня____2004 р.

Вчений секретар спеціалізованої

вченої ради __________ Уривський Л.О.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

Специфіка створення мережі передачі даних ЄССПІ, а саме включення її до складу, як наземних вузлів комутації пакетів, так і супутникової мережі, обумовлює виділення її в особливий клас — гібридних мереж зв'язку (ГМЗ).

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках наукового напрямку, що досліджується на кафедрі засобів телекомунікацій Національного технічного університету України „Київський політехнічний інститут”, а також у рамках науково-дослідної роботи „Сигнал-2” (номер державної реєстрації № 0197U013058), що виконувалася ДП “Укркосмос” в рамках Національної космічної програми України.

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

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

Методи дослідження. Вирішення задачі оптимальної розподілу повідомлень в ГМЗ базується на чисельному розв’язані проблеми оптимізації середньої затримки повідомлень, що знайдена аналітично з застосуванням основних результатів теорії телетрафіку та урахуванням наближення Клейнрока, в припустимій області змінних методом послідовного квадратичного програмування (Feasible Sequential Quadratic Programming). Розроблено прикладний пакет програм на мові програмування С++, що дозволяє вирішувати проблему знаходження оптимального плану розподілу потоків повідомлень для широкого класу гібридних мереж різної розмірності.

Наукова новизна отриманих результатів в роботі конкретно полягає у наступному:

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

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

3. Використовуючи отримані в попередніх двох пунктах результати отримані нові вирази для визначення імовірнісно-часових характеристик ГМЗ.

4. Запропоновано розподілений алгоритм маршрутизації для МПД ЄССПІ, що володіє ефективністю близькою до оптимальної.

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

Достовірність наукових результатів, висновків та рекомендацій, викладених в дисертаційній роботі, обґрунтована результатами експериментальних досліджень, коректним використанням математичного апарату та моделюванням на ЕОМ.

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

Результати дисертаційної роботи знайшли також практичне застосування в науково-дослідній роботі “Сигнал-2”— дозволили при проектуванні підвищить ефективність функціонування мережі передачі даних ЄССПІ.

Особистий внесок здобувача. У роботах, виконаних у співавторстві і надрукованих у виданнях, що ввійшли в список ВАК України, авторові належить: у спільній публікації [1] автор виконав аналіз варіантів побудови МПД ЄССПІ; у роботі [2] запропонував агрегативну модель МПД ЄССПІ; у роботі [3] розробив алгоритм і програму імітаційного моделювання МПД ЄССПІ.

Апробація результатів дисертації. Основні теоретичні положення та практичні результати роботи доповідалися й обговорювалися на 10-тій міжнародній кримський конференції по мікрохвильовій техніці “НВЧ-техніка та телекомунікаційні технології” КРИМІКО (Україна, м. Севастополь, 2000 р.), на 2 і 3 всеукраїнській конференції “Людина і Космос” (Україна, м. Дніпропетровськ, 2000, 2001 р.), та науково-технічних семінарах в Національному технічному університеті України
“Київський політехнічний інститут”.

Публікації. За результатами дисертації опубліковано 6 наукових праць, у тому числі 3 статті в провідних фахових виданнях.

Структура та обсяг роботи. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаних літературних джерел та додатків. Загальний об’їм роботи становить 111 сторінок, у тому числі 25 рисунків і 6 таблиць. Список використовуваних джерел містить 68 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі розглянуті загальні закономірності і специфічні особливості побудови і функціонування МПД ЄССПІ. Існуюча в даний час класифікація поділяє мережі зв'язку по ознаці їхнього призначення на дві великі групи: мережі загального і спеціального призначення. Саме до другої групи і відноситься об'єкт дослідження в даній дисертаційній роботі.

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

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

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

Однак МПД ЄССПІ відноситься до так називаних гібридних мереж зв'язку, у яких присутні як наземні, так і супутникові мережі. Крім того, у МПД ЄССПІ крім пакетів даних можуть передаватися і мовні виклики.

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

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

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

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

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

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

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

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

, (1)

,

де Tl — затримка даних у l-каналі, gdl – інтенсивність потоку даних у l-каналі, 1/d — середня довжина пакета.

Рис. 1. Структура ГМЗ

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

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

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

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

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

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

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

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

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

Припустимо що супутниковий канал має ємність Сs , що розділена на дві частин: Сsd для передачі даних і Сsv — для мови, що утворює Ns каналів для повідомлень, що підрозділяються на Nd каналів для даних і Nv каналів для мови.

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

, (2)

, ,

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

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

(3)

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

Рис. 2. Схема розподілу супутникового каналу для даних і мови

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

(4)

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

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

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

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

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

Інтенсивність потоків у гілках наземної мережі (gdl) і в супутниковому каналі (d, v) є функціями від вхідних інтенсивностей потоків даних та мовних викликів (ij, Гij) та коефіцієнтів їх розподілу між наземною та супутниковою мережами gij ,і зв'язані лінійно наступними співвідношеннями:

, (5)

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

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

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

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

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

(6)

Інтенсивності d є лінійною комбінацією gij і ij:

,

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

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

min(x) f(x),

0 < gij, pkij < 1,

gdl < Сgdl, d < Csd,, v < Csv ,l (8)

, i,j

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

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

, (9)

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

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

, (10)

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

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

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

Рис. 3. ВТМ НКАУ

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

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

Розглянемо, наприклад, передачу пакетів по наземної мережі між вузлами 1 і 8 на рис. 3. Мінімальне число транзитів між цими вузлами дорівнює 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...

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

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

Рис. 4 Результати розрахунку маршрутних коефіцієнтів gij

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

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

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

Таблиця 1

Значення коефіцієнтів gij для мережі передачі даних (ij = 10 пакетів/с)

gi j | 5 | 6 | 7 | 8

1 | 1 | 1 | 1 | 0,61

2 | 1 | 1 | 0,61 | 1

3 | 1 | 1 | 1 | 1

4 | 1 | 1 | 1 | 1

Цільова функція = 0,082 с

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

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

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

Таблиця 2

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

gi j | 5 | 6 | 7 | 8

1 | 1 | 1 | 1 | 0,225

2 | 1 | 1 | 0,225 | 1

3 | 1 | 1 | 1 | 1

4 | 1 | 1 | 1 | 1

Цільова функція = 0,132 с

Рис. 5. Результати розрахунку маршрутних коефіцієнтів pkij

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

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

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

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

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

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

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

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

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

, (11)

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

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

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

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

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

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

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

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

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

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

Рис. 6. Залежність середньої затримки в мережі Т від інтенсивності вхідного потоку

ВИСНОВКИ

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

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

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

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

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1.

Нежуренко О.Г. виконав аналіз варіантів побудови МПД ЄССПІ.

2.

Нежуренко О.Г. запропонував агрегативну модель МПД ЄССПІ.

3.

Нежуренко О.Г. розробив алгоритм і програму імітаційного моделювання МПД ЄССПІ.

4.

5.

6.

АНОТАЦІЯ

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

Дисертація на здобуття вченого ступеня кандидата технічних наук за спеціальністю 05.12.02 — телекомунікаційний системи та мережі. — Національний технічний університет України “Київський політехнічний інститут”, Київ, 2003.

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

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

На базі агрегативного підходу розроблений імітаційний алгоритм функціонування системи, що розглядається. Для програмної реалізації вказаного алгоритму використана мова програмування C++. Проведене імітаційне моделювання на прикладі функціонування ВТМ НКАУ. Отримані чисельні дані підтвердили коректність запропонованих математичних моделей.

Ключові слова: керування, гібридна мережа, агрегат, моделювання.

ANNOTATION

Nezhurenko O. G. Routing problems in Hybrid data transmission network of Unified Satellite Information Transmission System of Ukraine. Manuscript.

Ph.D. thesis by speciality 05.12.02 — Systems of telecommunication and networks. — National technical university of Ukraine “Kyiv Polytechnic Institute”, Kyiv, 2003.

A new mathematical model of hybrid data network has been developed. It allows on base of offered streams division coefficients to find out a data delay in branches of ground network and satellite channel in dependence on incoming data traffic, and also refusals probability in establishment of connection for voice calls.

A new method of determination of optimum streams distribution plan in whole hybrid data network (including ground and satellite subnet) has been proposed. The method is based on offered mathematical model and numerical optimisation of average data delay in feasible variable domain by mathematical approach of successive quadratic programming (FSQP).

On the basis of aggregate approach it is worked up a imitation functioning algorithm of considered system. For program realisation of stated algorithm is used a programming language С++. The imitation modelling of NSAU private data network has been conducted. Numeral results have bored out the proper behaviour of offered mathematical models.

Key words: management, hybrid network, aggregate, imitation.

АННОТАЦИЯ

Нежуренко А. Г. Задачи маршрутизации в гибридной сети передачи данных Единой спутниковой системы передачи информации Украины. — Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.02 — телекоммуникационные системы и сети. — Национальный технический университет Украины “Киевский политехнический институт”, Киев, 2003.

За последние годы в Украине произошли существенные изменения в социальной и политической сферах жизни об-щества. Одним из результатов таких изменений явилось интен-сификация деловой активности и связанное с этим повышение требований к услугам связи. Наряду с развитием сетей общего пользования значительно увеличилось число разработок систем связи различных ведомств, а также межведомственных сетей, к которым относиться сеть передачи данных Единой Спутниковой Системы Передачи Информации (ЕССПИ).

Наряду с общими закономерностями построения и функциони-рования сетей связи и любого типа ведомственные (межведомственные) сети связи могут существенно отличаться от сетей общего пользования. Это, в первую очередь, обуслов-ливается предъявляемыми со стороны пользователей услугами ведомственных сетей специфических требований и необходи-мостью обеспечения функционирования таких сетей в услови-ях, существенно отличающихся от повседневных условий сетей связи общего применения.

Специфика создания сети передачи данных ЕССПИ, а именно включение ее в состав, как наземных узлов коммутации пакетов, так и спутниковой сети, обусловливает выделение ее в особый класс — гибридных сетей связи (ГСС).

Для обеспечения нормального функционирования ГСС создаются специаль-ные системы управления ими, характеризующиеся определен-ными принципами организационно-технического построения и описывающими их параметрами. В данной работе, прежде всего, будет рассматриваться сетевой уровень управления согласно Эталонной модели взаимодействия открытых систем, т.е. задачи маршрутизации в таких сетях.

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

Однако без этого нельзя говорить ни о построении конкретных ГСС, ни об оценке их соответ-ствия своему предназначению. В связи с этим проведение ис-следований и разработок по созданию соответствующих по-ставленной проблеме методик решения задач маршрутизации в ГСС является актуальным. Решению указанной проблемы и посвящена настоящая диссертационная работа.

Целью данной работы является разработка методики решения задачи оптимальной маршрутизации в ГСС, и в частности в СПД ЕССПИ, что обеспечивает оценку принимаемых при ее создании решений на соответствие предъявляемым к данной системе требованиям.

Научная задача данной работы заключается в разработке математи-ческой модели, раскрывающей происходящие в ГСС про-цессы и используемые принципы организационно-технического построения, методики решения задачи оптимальной маршрутизации и нахождения оптимального плана распределения потоков в СПД ЕССПИ в зависимости от поступающей в сеть нагрузки.

В ходе