Размещено на http://www.allbest.ru/

Національний авіаційний університет

Автореферат

дисертації на здобуття наукового ступеня

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

05.13.13 - Обчислювальні машини, системи та мережі

Методи аналізу трафіку гетерогенних комп'ютерних мереж

Даниліна Галина Володимирівна

Київ 2007

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

Робота виконана на кафедрі комп'ютерних систем та мереж Інституту комп'ютерних технологій Національного авіаційного університету Міністерства освіти і науки України.

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

кандидат технічних наук, доцент Гузій Микола Миколайович ,Національний авіаційний університет, ,заступник директора з наукової роботи Інституту комп'ютерних технологій.

Офіційні опоненти: доктор технічних наук, доцент

Дичка Іван Андрійович Національний технічний університет України “Київський політехнічний інститут”, професор кафедри спеціалізованих комп'ютерних систем,

кандидат технічних наук, доцент Прокудін Георгій Семенович Національний транспортний університет України, доцент кафедри інформаційних систем і технологій.

Провідна установа: Інститут проблем реєстрації інформації НАН України, відділ 102, м. Київ.

Захист відбудеться “05” липня 2007 р. о 14 годині на засіданні

спеціалізованої вченої ради Д 26.062.07 в Національному авіаційному університеті за адресою: 03680, м. Київ, проспект Космонавта Комарова, 1.

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

Автореферат розісланий “02” червня 2007 р.

Вчений секретар спеціалізованої вченої ради, кандидат техн. наук, доцент О.П. Мартинова

1. Загальна характеристика роботи

алгоритм трафік мережа гетерогенний

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

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

Дослідженнями тих чи інших проблем аналізу, синтезу і оптимізації мережних систем трафіку займається багато наукових колективів і окремих вчених як в Україні, так і за її межами. Значний внесок у розвиток цього наукового напряму внесли: Лівшиц Б. С., Пшеничніков А. П., Харкевич А. Д., Клейнрок Д.В., Ігнатов В.О., Паук С.М.,Оліфер Н.А., Оліфер В.Г., Вишневський В.М.,Стєклов В.К., W.E.Leland, M.S.Taqqu, W.Willinger, D.V.Wilson, D.Wischik, Цибаков Б.С., T. Gneiting, M. Schlather, Заборовський В.С., Городецький А.Я., Шелухін О.И., Мінаєв Ю.М., Тенякішев А.М., Осін А.В., Криштофович А.Ю., Veres A., Boda M., Зайченко Ю.П., Kaplan I., Park K., Зайченко О.Ю., Додонов О.Г., Miloucheva I., Mыller E., Anzaloni A., Trajkovic L., Neidhardt A., Уайндер С., Gripenberg G., Norros I. та багато інших вчених.

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

Зв'язок роботи з науковими програмами, планами, темами. Результати дисертаційної роботи використані при виконанні НДР в №139-ДБ04 “Дослідження принципів побудови паралельних обчислювальних структур для розв'язання задач великої розмірності”.

Автор брав участь у виконанні робіт як співвиконавець.

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

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

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

- розробка моделей аналізу динаміки трафіку в гетерогенних комп'ютерних мережах;

- розробка метода оптимізації параметрів моделей аналізу динаміки трафіку;

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

Об'єкт дослідження - трафік гетерогенних комп'ютерних мереж.

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

Методи дослідження. Автором вибрані методи, що відповідають змісту і характеру поставлених задач. Серед головних методів слід вказати: метод диференційних рівнянь Колмогорова-Чепмена, метод дискретизації, квантування трафіку і марковської неоднорідної апроксимації зміни станів трафіку, класичний метод складання систем рівнянь оптимізації, метод невизначених множників Лагранжу для врахування обмежень реального характеру, метод лінеаризації і гаусовської апроксимації розподілу нелінійних функцій випадкових аргументів, метод мінімізації середнього ризику, метод найменших квадратів, методи теорії ймовірностей і математичної статистики, імітаційне комп'ютерне моделювання трафіку.

Наукова новизна одержаних результатів:

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

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

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

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

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

Практичне значення одержаних результатів. Практичне значення мають:

1. Рандомізовані моделі динаміки трафіку для аналізу точності і достовірності інтегральних характеристик трафіку.

2. Логіко-математичні моделі випадкового стаціонарного, нестаціонарного і періодичного режимів трафіку.

3. Метод оптимізації трафіку в гетерогенних комп'ютерних мережах.

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

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

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

Особистий внесок здобувача. У роботах, написаних у співавторстві, автору належать: моделювання перехідних режимів трафіку [1]; розробка марковської рандомізованої моделі [2,7]; розробка методу і алгоритмів оптимізації трафіку обчислювальної мережі [3]; створення методики оцінювання ефективності використання мереж [4,5]; створення методу оцінювання ефективності обчислювальних систем [8].

Апробація результатів роботи. Основні результати проведених досліджень доповідалися й обговорювалися на міжнародних науково-технічних конференціях, зокрема на ІІ міжнародній науковій конференції “Інтелектуальні системи ухвалення рішень і прикладні аспекти інформаційних технологій” (ISDMIT', Київ, Україна, 2006р.); VI Міжнародній науковій конференції студентів та молодих вчених “Політ” (Київ, 2006 р.); VIІ Міжнародній науковій конференції студентів та молодих вчених “Політ” (Київ, 2007 р.); Міжнародній науково-технічній конференції “АВІА - 2006” (Київ, 2006 р.); Міжнародній науково-технічній конференції “АВІА - 2007” (Київ, 2007 р.);Науково-практичній конференції “Комп'ютерні системи і мережні технології” (Київ, 2007р.)

Публікації. За результатами дослідження опубліковано 5 статей у фахових наукових журналах; 4 тезисів виступів на наукових конференціях та зроблено 6 доповідей. Підготовлено 2 заявки на винаходи.

Структура і обсяг дисертаційної роботи. Дисертаційна робота складається зі вступу, чотирьох розділів основного тексту, висновків та 6 додатків. Загальний обсяг дисертаційної роботи складає 153 сторінки, 30 рисунків, 6 таблиць. Шість додатків до основних результатів досліджень займають 74 сторінки. Список використаних джерел складається з 82 найменувань на 7 сторінках.

2. Основний зміст роботи

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

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

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

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

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

Прийняті наступні позначення: Si , i=1,...,n, i-ий стан трафіку, n-загальне число станів, стрілками показані напрямки переходів, через aij і aji позначені випадкові інтенсивності прямих і зворотних переходів зі стану Si в стан Sj , i?j, i,j=1,...,n. Через Pi(t) позначена ймовірність перебування трафіку в момент часу t у стані Si , i=1,...n, через Pi' (t) позначена похідна цієї ймовірності.

Передбачається, що випадкові інтенсивності aij і aji зв'язані з відповідними випадковими тривалостями Ti і Tj перебування трафіку в станах Si і Sj до відповідних переходів наступними співвідношеннями:

 (1)

де величини Ti і Tj мають гаусові розподіли з параметрами:

, , , (2)

через M і D позначені операції визначення математичного сподівання й дисперсії. Моменти (2) передбачаються заданими для всіх станів трафіку.

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

Теорема 1. Якщо для всіх інтенсивностей aij і aji прямих і зворотних переходів випадкового процесу:

1. Справедливі співвідношення (1).

2. Для всіх Ti і Tj відомі моменти (2).

3. Коефіцієнти варіації випадкових тривалостей станів задовольняють умовам:

(3)

тоді коефіцієнти варіації Vij і Vji інтенсивностей переходів збігаються з відповідними коефіцієнтами варіацій Vi і Vj тривалостей Ti і Tj.

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

Показано, як враховуються числові характеристики випадкових інтенсивностей aij і aji у наступних розрахунках. Динаміку процесу описують системою диференціальних рівнянь Колмогорова-Чепмена, які складають за допомогою графу як і відомі рівняння Кірхгофа:

(4)

і які вирішують при заданих початкових умовах:

(5)

У результаті рішення диференціальних рівнянь (4) одержують нелінійні функції випадкових аргументів aij і aji, а також початкових значень ймовірностей (5). Ці функції є основою для визначення всіх інтегральних характеристик випадкового процесу як для перехідних, так і для сталих режимів статистичної рівноваги, якщо вона існує. Вони дозволяють врахувати вплив випадкових аргументів Ti і Tj на інтегральні характеристики. Застосування методу лінеаризації інтегральних характеристик і гаусової апроксимації їхніх розподілів дозволяє одержати математичні сподівання й дисперсії інтегральних характеристик по заданим математичним сподіванням і дисперсіям гаусових змінних Ti і Tj, i,j=1,...,n. Розкладання щільностей розподілу в ряд Грама-Шарлье дозволяє узагальнити одержувані результати на той випадок, коли необхідно враховувати моменти вищих порядків, наприклад, коефіцієнти асиметрії й ексцесу розподілів. Як приклад використано марковську рандомізовану модель для аналізу поводження трафіку комп'ютерної мережі протягом доби й визначення годин найбільшого навантаження.

У третьому параграфі розроблені дві логіко-математичні моделі нестаціонарних режимів трафіку при n=4. Через лі, і=1,...,3 позначена інтенсивність зміни Sі-го стану трафіку. Ймовірність перебування трафіку у стані Sі в момент часу t позначено як Pi(t), i=1,...,4. Усі стани трафіку складають повну групу подій, тому для ймовірностей станів трафіку діє умова нормування

(6)

Перша модель основана на припущенні, що Це означає, що доба розбивається на чотири однакових інтервали, у межах яких вимірюється трафік. Використовуючи цю модель, запишемо систему диференційних рівнянь Колмогорова-Чепмена, що описують динаміку перехідних режимів трафіку відносно ймовірностей станів трафіку. Застосовуючи пряме та зворотнє перетворення Лапласа, отримаємо рішення системи диференціальних рівнянь при начальних умовах: Pi(0) = Pi0, i = 1,…,4.

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

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

У шостому параграфі розроблено метод оптимізації параметрів логіко-математичних моделей динаміки трафіку. В ролі керованих змінних обрані квантовані значення та інтенсивності зміни станів трафіку. Оптимізація виконується для нестаціонарного режиму трафіку як найбільш складного і такого, що представляє найбільший практичний інтерес. Нижче показано розв'язання задачі оптимізації параметрів логіко-математичних моделей трафіку для одного класу задач. Припущено, що по результатах спостереження реального трафіку отримані відліки середнього фрейму трафіку Х0 (tk) = x0k, k=1,...,m, де m-загальне число відліків, взятих за середній період (цикл) зміни трафіку. Необхідно так обрати квантовані значення xі*, і=1,...,n трафіку при обчисленні його математичного сподівання, щоб значення суми квадратів відхилень математичного сподівання трафіку від відліків, що спостерігались, було б мінімальним. В ролі цільової функції оптимізації квантованих значень обирається сума квадратів

, (6)

яка залежить від вибору квантованих значень х*1,..., х*n.

Систему рівнянь оптимізації квантованих значень трафіку (6) отримано стандартним методом: взяттям похідної від (5) по х*і та прирівнянням результату нулю.

, (7)

де і=1,...,n. Оскільки друга похідна має позитивне значення, за умови, що ,система рівнянь оптимізації, що отримана з (6),

, і=1,...,n, (8)

дозволяє визначити xj*opt, які забезпечують функції (5) мінімальне значення

Системи лінійних алгебраїчних рівнянь типу (7) розв'язуються стандартними методами, тому принципових труднощів у визначені xі *opt не виникає. За результатами досліджень цього параграфу зроблені наступні висновки: для найкращого відображення даних реальних спостережень за трафіком комп'ютерних мереж доцільно застосувати оптимізацію параметрів логіко-математичних моделей динаміки трафіку; в ролі керованих змінних доцільно вибирати квантовані значення трафіку та інтенсивності змін станів трафіку; керування за допомогою квантованих значень трафіку приводить до відносно простих обчислювальних процедур розв'язання лінійних алгебраїчних рівнянь, які виконуються добре відпрацьованими методами лінійної алгебри; керування за допомогою інтенсивності зміну станів трафіку приводить до необхідності розв'язувати нелінійні трансцендентні рівняння, що пов'язано із застосуванням досить складних ітераційних процедур.

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

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

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

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

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

Теорема 2. Якщо в комп'ютерній мережі мають місце наступні необхідні умови:

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

 ? C (9)

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

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

D1(С) = a/С, (10)

де параметр моделі (10) .

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

< С (11)

виникають втрати D2(С), що обумовлені неповним використанням пропускної здатності лінії зв'язку, які можна апроксимувати залежністю

D2(С) = bСc, (12)

де параметр моделі (12) .

3. Ймовірності виконання умов (9), (11) визначаються системою рівнянь, що складається з диференціального рівняння Колмогорова-Чепмена (3) і умови нормування .

4. Існує усталений режим статистичної рівноваги трафіку і для ймовірностей станів трафіку справедливі рівняння (4), (5).

5. Математичне сподівання втрат від використання лінії зв'язку з середньою пропускною здатністю С0 апроксимоване залежністю

де середній коефіцієнт використання пропускної здатності лінії зв'язку

середня швидкість передачі повідомлень

середня пропускна здатність

де Т0 -- середній період трафіку, тоді і тільки тоді існує оптимальне значення пропускної здатності лінії зв'язку, що визначається формулою

(13)

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

(14)

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

(15)

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

Крива 1 ілюструє втрати від чекання пакетів у черзі при відмові в обслуговуванні, вони обернено пропорційні пропускній здатності лінії зв'язку. Чим більше значення пропускної здатності лінії, тим менші втрати. Крива 2 ілюструє витрати на створення і підтримку пропускної здатності лінії, вони прямо пропорційні значенню пропускній здатності лінії. Чим більше значення пропускної здатності лінії, тим більше витрат на забезпечення роботи лінії. Крива 3 ілюструє середнє значення критерію середнього ризику - сумарні середні витрати в залежності від пропускної здатності одноканальної лінії зв'язку. Наочно ілюструє те, що значення координат екстремуму критерію середнього ризику (13) - (15) залежать від середнього значення коефіцієнта використання пропускної здатності лінії зв'язку і параметрів функцій витрат.

Доведені ствердження теорем відносно взаємозв'язків середньої тривалості Т0 обслуговування повідомлень і ймовірності Р0 того, що лінія буде зайнята, відносно взаємозв'язків обсягів пам'яті n* i n0 буферних пристроїв ліній зв'язку, що функціонують в оптимальному і неоптимальному режимах, щодо впливу коефіцієнта варіації V розподілу тривалості обслуговування на середню тривалість обслуговування Т0 повідомлення в оптимальному і неоптимальному режимах, а також на середню затримку Т01 повідомлення в черзі на обслуговування. Доведення цих теорем надано в Додатку Б.

Теорема 3. Середня тривалість Т0 обслуговування пакету даних одноканальною лінією зв'язку і ймовірність P0 того, що лінія буде зайнята обслуговуванням повідомлення, пов'язані прямим і зворотнім перетворенням такого виду:

де -- середня тривалість очікування пакетом даних обслуговування в черзі;

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

Теорема 4. Обсяги пам'яті буферних пристроїв при роботі лінії зв'язку в оптимальному і неоптимальному режимах пов'язані співвідношенням

,

де - обсяг пам'яті буферного пристрою в оптимальному режимі,

- обсяг пам'яті буферного пристрою в неоптимальному режимі,

- середній коефіцієнт використання пропускної здатності лінії зв'язку в неоптимальному режимі,

-

коефіцієнт збільшення обсягів пам'яті буферного пристрою в оптимальному режимі.

Теорема 5 .Якщо коефіцієнт варіації

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

тоді для середньої тривалості обслуговування пакету даних в неоптимальному режимі справедлива складна нерівність

Теорема 6. Якщо коефіцієнт варіації

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

тоді для середньої тривалості обслуговування повідомлення в оптимальному режимі обслуговування повідомлення справедлива складна нерівність

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

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

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

Теорема 7. Якщо справедлива апроксимація (16) середніх сумарних витрат

(16)

де aN і bN -- параметри функцій витрат для N канального центру,

n - число пакетів даних,

-- сумарна пропускна здатність телекомунікаційного центру,

- ймовірність того, що центр буде зайнятий

- ймовірність того, що центр буде вільний (доступний)

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

яке забезпечує мінімум критерію якості (16)

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

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

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

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

де ,- вагові коефіціенти,

тоді значення допоміжного невизначеного множника знаходиться за допомогою співвідношення.

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

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

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

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

Висновки

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

В результаті дослідження:

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

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

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

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

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

6. Практичне значення мають:

· рандомізовані моделі динаміки трафіку для аналізу точності і достовірності інтегральних характеристик трафіку;

· логіко-математичні моделі випадкового стаціонарного, нестаціонарного і періодичного режимів трафіку;

· метод оптимізації пропускної здатності ліній зв'язку, комунікаційних центрів гетерогенних комп'ютерних мереж;

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

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

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

1. Ігнатов В.О., Жуков І А., Гузій М.М., Даниліна Г.В. Моделювання перехідних режимів трафіку комп`ютерної мережі // Информационные технологии и безопасность: Сборник научных трудов. - К.: Национальная академия наук Украины, Институт проблем регистрации информации, 2006. - Вып.9. - С. 84 - 87.

2. Ігнатов В.О., Мачалін І.О., Гузій М.М., Даниліна Г.В.. Марковські рандомізовані моделі // Вісник Житомирського державного технологічного університету. - Житомир, 2006. - Вип. ІV (39). - С. 179-184.

3. . Гузій М.М., Ігнатов В.О., Даниліна Г.В., Милокум Я.В. Методи і алгоритми оптимального управління трафіком в обчислювальних мережах // Проблеми інформатизації та управління. - К.: НАУ, 2006.- Вип.17. - С. 32-37.

4. Гузій М.М., Ігнатов В.О., Даниліна Г.В. Оцінювання ефективності використання ліній зв'язку в обчислювальних мережах // Проблеми інформатизації та управління. - К.: НАУ, 2006.- Вип.18. - С.54-59.

5. Мартынова О.П., Даниліна Г.В., Клименко И.А. Оценка эффективности системоаналоговых вычислительных структур // Проблеми інформатизації та управління.- К.: НАУ, 2006.- Вип.1(16). - С. 107-110.

6. Данилина Г.В. Алгоритм многоадресной маршрутизации ориентированный на передачу информации различного типа // Наука і молодь: Матеріали міжнародної наукової конференції студентів та молодих учених “Політ-2006”. - К.: НАУ, 2006.- С. 118.

7. Игнатов В.А., Мачалин И.А., Гузий Н.Н., Данилина Г.В. Рандомизированные модели марковских процессов: Матеріали VІІ Міжнародної науково-технічної конференції “АВІА-2006”. - К.: НАУ, 2006.- Т. 1. - C. 13. 101-13.104.

8. Ігнатов В.О., Гузій М.М., Даниліна Г.В. Оптимізація управління трафіком обчислювальних мереж: VІІІ Міжнародна науково-технічна конференція “АВІА-2007”.- К.: НАУ, 2007. - Т. 1. - С. 13.21-13.24.

Анотація

Даниліна Г.В. Методи аналізу трафіку гетерогенних комп'ютерних мереж. - Рукопис.

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

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

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

Аннотация

Данилина Г.В. Методы анализа трафика гетерогенных компьютерных сетей. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13. - Вычислительные машины, системы и сети. Национальный авиационный университет. Киев. 2007.

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

Ключевые слова: гетерогенная компьютерная сеть, трафик, обслуживание трафика.

Summary

Danilina G. V. Methods of the traffic analysis of heterogeneous computer networks.-The Manuscript of Ph. D. thesis.

The dissertation on competition of a scientific degree of Cand.Tech.Sci. on a specialty 05.13.13. - Computers, systems and networks. National Aviation University. Kiev. 2007.

The Dissertation is devoted to development of methods, algorithms and models of the traffic analysis in heterogeneous computer networks. The Purpose of work consists in development of methods, algorithms and models of the traffic analysis, estimation and optimization of communication lines throughputs and other systems for increase of efficiency of heterogeneous computer networks. Put and solved problems to the analysis of methods and models for the estimation and optimization of the traffic service in computer networks; development of models for the dynamics analysis of the traffic in heterogeneous computer networks; development of a method of parameters optimization of models of the analysis of the traffic dynamics; development of a method of optimization of communication lines throughputs and other systems in heterogeneous computer networks. Practical value have a technique of use randomization models of the traffic dynamics for estimation of accuracy and reliability of the traffic integrated characteristics; the Technique of logical-mathematical modeling of casual stationary, non-stationary and periodic modes of the traffic; a technique of efficiency estimation of use of multichannel communication lines and the comparative analysis optimum and not optimum modes of communication lines operation; a technique of imitating computer modeling of dynamics of the traffic which allows to experimental check models adequacy of the traffic dynamics.

Key words: heterogeneous computer networks, traffic, traffic service.

Размещено на Allbest.ru