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

Національна академія наук України

Інститут проблем моделювання в енергетиці ім. Г.Є.Пухова

Автореферат

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

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

Спеціальність 05.13.05 - Комп'ютерні системи та компоненти

Моделі та методи аналІзу маршрутів трафіку

в об'єднаних комп'ютерних мережах

Корольков Ігор Владиславович

Київ - 2010

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

Робота виконана в Запорізькому національному технічному університеті на кафедрі комп'ютерних систем та мереж.

Науковий керівник: кандидат технічних наук, доцент

Кудерметов Равіль Камілович,

Запорізький національний технічний університет,

завідувач кафедри комп'ютерних систем та мереж

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

Святний Володимир Андрійович,

Донецький національний технічний університет, завідувач кафедри комп'ютерної інженерії

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

старший науковий співробітник

Ролік Олександр Іванович,

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

Захист відбудеться “ 22 ” квітня 20 10 р. о 14 годині на засіданні Спеціалізованої вченої ради Д26.185.01 Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України за адресою: 03164, м. Київ, вул. Генерала Наумова, 15.

З дисертацією можна ознайомитися у бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України за адресою: 03164, м. Київ, вул. Генерала Наумова, 15.

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

Вчений секретар

спеціалізованої вченої ради Д 26.185.01,

кандидат технічних наук Е.П. Семагіна

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

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

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

Проблемі вивчення трафіку комп'ютерних мереж присвячено багато наукових праць. Значний внесок у розвиток основ аналізу та моделювання мереж зробили зарубіжні вчені, такі як: Д. Никола, Г. Рілей, Р. Фуджимото, П. Хонг, Дж. Хайдеманн. Серед дослідників близького зарубіжжя слід відзначити таких російських науковців: В.М. Вишневського, В.В. Крилова, С.С. Самохвалову. Питанням моделювання комп'ютерних мереж присвячені публікації вітчизняних вчених: Н.І. Алішова, Л.Н. Беркман, Н.А. Виноградова, І.А. Жукова, Ю.П. Зайченка.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Основні дослідження з теми дисертації проводились на кафедрі “Комп'ютерні системи та мережі” Запорізького національного технічного університету в рамках науково-дослідної роботи за держбюджетною НТР № ІТ/506-2007 “Створення національної Grid інфраструктури для забезпечення наукових досліджень” (номер державної реєстрації 0107U007931).

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

Для досягнення поставленої мети необхідно вирішити такі завдання:

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

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

3. Дослідити й розробити методи підвищення адекватності імітаційних моделей комп'ютерних мереж, побудованих на основі маршрутних дерев;

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

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

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

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

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

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

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

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

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

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

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

1. Розроблено математичне забезпечення оцінювання якості маршрутних дерев для реалізації методу алгоритмічної маршрутизації по одному або декільком деревам;

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

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

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

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

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

? другий і третій міжнародні молодіжні форуми “Інформаційні технології у ХХІ сторіччі” (2004 і 2005 рр., м. Дніпропетровськ);

? сьомий, дев'ятий і десятий міжнародні молодіжні форуми “Радіоелектроніка і молодь у XXI сторіччі” (2003, 2005 і 2006 рр., м. Харків);

? третя міжнародна науково-технічна конференція студентства й молоді “Світ інформації і телекомунікацій - 2006” (2006 р., м. Київ);

? четверта міжнародна конференція “Сучасні проблеми й досягнення у сфері радіотехніки, телекомунікацій та інформаційних технологій” (2006 р., м. Запоріжжя);

? п'ята міжнародна конференція “Інтернет - Освіта - Наука - 2006” (2006 р., м. Вінниця);

? четверта міжнародна науково-практична конференція “Єдиний інформаційний простір” (2006 р., м. Дніпропетровськ).

Публікації. За темою дисертації опубліковано 15 друкованих праць, з них 5 статей у наукових виданнях, внесених до переліку ВАК України, 10 публікацій в матеріалах науково-технічних конференцій, 11 наукових праць написані без співавторів.

Структура дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, двох додатків і списку літературних джерел (107 найменувань). Загальний обсяг роботи становить 188 сторінок, з них 167 основного тексту. Робота містить 64 рисунки і 6 таблиць.

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

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

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

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

У дисертації розроблено модифікований метод алгоритмічної маршрутизації з фіксованою обчислювальною складністю (ФАМ). Замість використання одного числа для адресації вузла метод передбачає використання двох чисел: перша частина адреси є унікальною серед усіх інших вузлів, які знаходяться на тій самій глибині у дереві; друга частина адреси відповідає глибині вузла в дереві. При цьому кореневий вузол має адресу (0, 0). Як і в методі ПАМ, список сусідніх вузлів сортується на кожному вузлі таким чином, щоб вузол-предок знаходився у кінці списку.

Нехай k - максимальна кількість сусідів будь-якого вузла у мережі. Вузол-предок позначимо як P, а вузол-потомок - як C, тоді (X_P, Y_P) - адреса P, а (X_C, Y_C) - адреса C. Нехай C буде i-им вузлом у списку сусідів вузла P, де i {0, …, (k _ 1)}. Тоді адреси вузлів P і C пов'язані таким чином:

Y_C = Y_P + 1, (1)

X_C = X_P Ч k + i. (2)

Далі нехай S і D позначають відповідно джерело та пункт призначення пакета. Тільки на основі адреси вузол D може бути зарахований до однієї з трьох ділянок. Ділянка A містить усі вузли, що знаходяться у дереві вище, ніж S: Y_D < Y_S. Ділянка Б містить усі вузли, що знаходяться у дереві безпосередньо нижче, ніж вузол S: Y_D > Y_S. З виразу (2) випливає - якщо вузол D знаходиться на цій ділянці, то:

(3)

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

Якщо вузол призначення знаходиться на ділянці A чи В, то наступним пересиланням з вузла-джерела S буде пересилання до вузла-предка S. Якщо вузол призначення знаходиться на ділянці Б, то може існувати більше ніж один вузол-потомок, який може бути використаний для наступного пересилання. Нехай

(4)

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

(5)

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

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

У третьому розділі розроблено методи підвищення адекватності маршрутів, які отримуються за допомогою методів алгоритмічної маршрутизації:

? ефективні ітераційні методи підвищення якості маршрутних дерев;

? схема застосування методу алгоритмічної маршрутизації з використанням декількох дерев;

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

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

(6)

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

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

Нехай G(V, E) - граф топології мережі, а (T, r) - маршрутне дерево, в якому Т - зв'язне дерево, а r - кореневий вузол. S(T, a) - множина вузлів у піддереві Т з коренем в а. Нехай x, y, z V, а y - потомок х.

Позначимо модифікацію дерева як:

(7)

де: z S(T, x). Позначимо значення Н для дерев T і T_new, як H(T) і H(T_new) відповідно.

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

Для вироблення рішення щодо прийняття або відкидання кожної модифікації дерева необхідно визначати зміну величини Н. Нехай d(x, y) - відстань між вузлами x та y вздовж маршруту, обраного методом АМ. Для двох множин вузлів Х та Y нехай D(X, Y) - сума довжин маршрутів, які з'єднують кожну пару вузлів x, y (x X, y Y, x ? y):

(8)

Нехай S(a, T) - множина вузлів у піддереві дерева Т з коренем в а. Нехай Sґ(a, T) = V\S(a, T). Нехай Т₁ - маршрутне дерево мережі. Для стислості запишемо: S₁ = S(a, T₁) і Sґ₁ = Sґ(a, T₁). Нехай а - вузол з предком b у дереві Т₁, тоді:

(9)

Оскільки S₁ і Sґ₁ є неперетинними множинами, якщо x S₁ і y Sґ₁, тоді:

(10)

. (11)

Використовуючи вирази (8), (9) і (11), отримаємо:

(12)

Нехай Т₂ - така модифікація дерева Т₁, що с є предком а, де c S₁. Передбачається, що S₂ = S(a, T₂) = S₁. Позначимо функції відстаней мереж для дерев Т₁ і Т₂ як H(T₁) і H(T₂) відповідно. Тоді H(T₂) може бути виведений аналогічно (12):

(13)

Враховуючи (12) і (13), отримаємо:

(14)

де:

(15)

(16)

Таким чином, отримаємо: маршрут трафік комп'ютерний мережа

(17)

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

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

? кожне дерево повинне мати унікальний корінь для максимальної різноманітності структур дерев;

? модифікація дерева має викликати залучення ліній зв'язку, що раніше не використовувалися;

? модифікації, які мають додатні значення H, інколи мають прийматися для збільшення різноманітності дерев.

Вираз (17) може бути поданий таким чином:

. (18)

Для прийняття рішення про збереження модифікації з додатним H необхідно враховувати цю різницю: якщо H₂ < H₁, то зміна буде спричиняти погіршення якості дерева; якщо H₂ > H₁ - покращення. Якщо відношення H₂ / H₁ наближається до 1, слід розглянути, чи викликає така модифікація використання раніше не задіяних ліній зв'язку.

Ще одна метрика якості маршрутних дерев u_ij - кількісний показник наявності ліній зв'язку між вузлами i та j у множині всіх маршрутів, які зв'язують невпорядковані пари вузлів, що відрізняються один від одного. Ця метрика відображає рівень використання ліній зв'язку. Оскільки u_ij = u_ji, то:

(19)

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

У четвертому розділі розроблено систему паралельного імітаційного моделювання трафіку комп'ютерних мереж - PNSS (Parallel Network Simulation System). Як паралельний інтерфейс застосовано стандарт Message Passing Interface (MPI). Запропонований алгоритм синхронізації модельного часу частково комбінує протоколи на основі вікон і нульових повідомлень. При цьому усувається необхідність у проведенні глобальної мінімізації на кожному кроці віконної синхронізації та знижується кількість нульових посилань.

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

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

До складу системи моделювання входять п'ять основних модулів пристроїв:

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

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

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

4. Модуль TCP реалізує протокол TCP, що відповідає RFC 793, включаючи такі доповнення, як “повільний старт” і “запобігання перенавантаженням”.

5. Модуль пристрою формування топології (ПФТ) автоматизує задачу побудови топології мережі. ПФТ є віртуальним пристроєм та не відображає частину фізичної структури мережі. ПФТ зчитує топологічну карту, генерує вузли та зв'язує їх у топологію мережі. ПФТ може виконувати поділ топології на ділянки з мінімальним розривом ребер за допомогою бібліотеки поділу графів METIS.

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

Для дослідження ефективності балансування було виконано моделювання 100 різних мереж і проведено порівняння часу виконання з використанням і без використання балансування, виявлене зниження розбалансування обробки при використанні зваженого поділу мережі на ділянки.

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

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

Висновки

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

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

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

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

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

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

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

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

1. Корольков И.В. Принципы организации распределенных вычислений в гетерогенной метакомпьютерной среде / И.В. Корольков // Седьмой международный молодежный форум “Радиоэлектроника и молодежь в XXI веке” : сб. матер. форума. - Харьков : ХНУРЭ, 2003. - С. 346.

2. Корольков И.В. Адаптивная система управления трафиком в

3. IP-сетях / И.В. Корольков // Информационные технологии в XXI веке : сб. докладов и тезисов II Молодежного науч.-практич. форума [г. Днепропетровск, 27-28 апреля 2004 г.] / под ред. акад. НАНУ В.В. Пилипенко, д.х.н. М.В. Бурмистра, к.ф.-м.н. Н.Ф. Огданского, к.ф.-м.н. Ю.А. Прокопчука. - Днепропетровск : ИПК ИнКомЦентра УГХТУ, 2004. - С. 84.

4. Корольков І.В. Математичні моделі алгоритмів маршрутизації в пакетних комунікаційних мережах / І.В. Корольков // Информационные технологии в XXI веке : сб. докладов и тезисов III Молодежного науч.-практич. форума. [г. Днепропетровск, 27-28 апреля 2005 г.] / под ред. акад. НАНУ В.В. Пилипенко, д.х.н. М.В. Бурмистра, к.ф.-м.н. Н.Ф. Огданского, к.ф.-м.н. Ю.А. Прокопчука. - Днепропетровск : ИПК ИнКомЦентра УГХТУ, 2005. - С. 106.

5. Корольков И.В. Анализ моделей маршрутизации в пакетных коммуникационных сетях / И.В. Корольков // Дев'ятий міжнародний молодіжний форум “Радіоелектроніка і молодь в XXI ст.” : зб. матер. форуму. - Харків : ХНУРЕ, 2005. - С. 62.

6. Корольков И.В. Параллельное моделирование вычислительных сетей с пакетной коммутацией / И.В. Корольков // Десятий ювілейний міжнародний молодіжний форум “Радіоелектроніка і молодь в XXI ст.” : зб. матер. форуму. - Харків : ХНУРЕ, 2006. - С. 133.

7. Корольков І.В. Особливості моделювання та аналізу складних телекомунікаційних мереж з пакетною комутацією / І.В. Корольков // Світ інформації та телекомунікацій-2006 : матер. ІІІ Міжнар. наук.-техніч. конфер. студентства та молоді [м. Київ, 26-27 квітня 2006 р.] - К. : ДУІКТ, 2006. - С. 30.

8. Корольков И.В. О самоподобных свойствах пакетного трафика в сетях телекоммуникационных операторов / И.В. Корольков, Р.К. Кудерметов // Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій : тези доповідей Міжнародної науково-практичної конференції [м. Запоріжжя, 13-15 квітня 2006 р.] / під заг. ред. Д.М. Пізи. - Запоріжжя : ЗНТУ, 2006. - С. 82-83.

9. Корольков И.В. Повышение производительности моделирования маршрутизации в больших вычислительных сетях / И.В. Корольков // Радіоелектронні і комп'ютерні системи. - 2007. - № 7 (26). - С. 20_26.

10. Корольков И.В. О применении самоподобных процессов для моделирования трафика в телекоммуникационных сетях с пакетной коммутацией / И.В. Корольков, Р.К. Кудерметов // Вестник Херсонского национального технического университета. - 2006. - № 3 (26). - С. 62-68.

11. Корольков И.В. Алгоритмическая маршрутизация как механизм абстракции для моделирования больших пакетных сетей / И.В. Корольков // Единое информационное пространство : сб. докладов IV Международной научно-практической конференции [г. Днепропетровск, 7-8 декабря 2006 г.] - Днепропетровск : ИТМ, 2006. - С. 50.

12. Корольков І.В. Актуальні проблеми паралельного моделювання великих обчислювальних мереж із пакетною комутацією / І.В. Корольков, Р.К. Кудерметов // Інтернет-Освіта-Наука-2006 : зб. матеріалів V Міжнародної конференції ІОН-2006 [м. Вінниця, 10-14 жовтня, 2006 р.] : в 2 т. - Вінниця : УНІВЕРСУМ-Вінниця, 2006. - Т. 2. - С. 413-416.

13. Корольков І.В. Паралельне моделювання великих обчислювальних мереж: актуальні підходи та проблеми / І.В. Корольков, Р.К. Кудерметов // Інформаційні технології та комп'ютерна інженерія. - 2007. - № 1 (8). -

14. С. 45-51.

15. Корольков И.В. Адаптированный метод алгоритмической маршрутизации для моделирования больших вычислительных сетей / И.В. Корольков // Дні науки : зб. тез доповідей : в 3 т. [м. Запоріжжя,

16. 11-12 жовтня 2007 р.] / Гуманітарний університет “ЗІДМУ” ; [ред. кол. В.М. Огаренко та ін.]. - Запоріжжя : ГУ “ЗІДМУ”, 2006. - Т. 3. - С. 187-189.

17. Корольков І.В. Скорочення довжин маршрутів, отриманих методом алгоритмічної маршрутизації, шляхом модифікації топологічних дерев / І.В. Корольков // Вісник Національного технічного університету України “КПІ”. Серія: Інформатика, управління та обчислювальна техніка. - 2007. - № 47. _ С. 86-97.

18. Корольков И.В. Особенности реализации системы параллельного моделирования маршрутизации в больших вычислительных сетях / И.В. Корольков // Радіоелектроніка. Інформатика. Управління. - 2009. -

19. № 1 (20). - С. 98_105.

У публікаціях, написаних у співавторстві, здобувачу належать: аналіз і виявлення самоподібних властивостей трафіку в мережі Інтернет-провайдера [7]; розробка алгоритму генерування пакетного трафіку з самоподібними властивостями [9]; аналіз проблем синхронізації паралельного моделювання обчислювальних мереж [11]; дослідження особливостей організації паралельного дискретно-подієвого моделювання, виявлення проблем і шляхів їх вирішення [12]. Роботи [1-6, 8, 10, 13-15] написані без співавторів.

Анотація

Корольков І.В. Моделі та методи аналізу маршрутів трафіку в об'єднаних комп'ютерних мережах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи та компоненти. - Інститут проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України, Київ, 2010.

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

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

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

Аннотация

Корольков И.В. Модели и методы анализа маршрутов трафика в объединенных компьютерных сетях. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. - Институт проблем моделирования в энергетике им. Г.Е. Пухова, Киев, 2010.

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

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

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

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

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

Материалы диссертации использовались в учебном процессе при выполнении научно-исследовательских, дипломных и магистерских работ, при подготовке лекционных курсов “Компьютерные сети” и “Параллельное программирование” на кафедре компьютерных систем и сетей ЗНТУ.

Ключевые слова: моделирование трафика, объединенная компьютерная сеть, оптимизация использования линий связи, имитационное моделирование, параллельные вычисления.

Annotation

Korolkov I.V. Models and methods of traffic routes analisys in interconnected networks. - Manuscript.

Thesis for candidate's degree in technical science by speciality 05.13.05 - Computer systems and components. - Pukhov Institute for Modelling in Energy Engineering, Kiev, 2010.

Dissertation is devoted to development of methods and models for traffic routes analysis in interconnected computer networks. To solve the tasks of large-scale computer networks simulations the combined approach based on abstract routing method and parallel computing is proposed.

In dissertation two modified methods for traffic routing simulation are developed on the basis of algorithmic routing method. Additional methods for improving accuracy of routes generated by algorithmic routing method are developed. Multy-tree scheme for algorithmic routing method is proposed for reducing route lengths and improving communication links utilization. Method of low overlap multy-tree generation for improving links utilization rate and model adequacy with acceptable trees quality is developed. Parallel simulation system for interconnected computer networks traffic modelling is completed based on proposed methods and algorithms.

Key words: traffic simulation, interconnected computer network, communication links optimization, simulation modelling, parallel computations.

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

...