МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ

КУЙБІДА ВАДИМ ЮРІЙОВИЧ

УДК 004.724.4

МЕТОД МАРШРУТИЗАЦІЇ ПАКЕТІВ ЗА КРИТЕРІЄМ РІВНОМІРНОГО ЗАВАНТАЖЕННЯ МЕРЕЖІ

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

Автореферат

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

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

Київ-2005

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

Робота виконана в Державному університеті інформаційно-комунікаційних технологій Міністерства освіти і науки України.

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

доктор технічних наук, професор Віноградов Микола Анатолійович, Інститут комп’ютерних технологій Національного авіаційного університету МОН України, професор кафедри комп’ютерних інформаційних технологій.

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

доктор технічних наук, професор Печурін Микола Капітонович, Інститут комп’ютерних технологій Національного авіаційного університету МОН України, професор кафедри обчислювальної техніки;

кандидат технічних наук Домарєв Валерій Валентинович, Апарат Ради національної безпеки і оборони України, завідувач сектором технічного захисту інформації.

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

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

Захист відбудеться 22.12.2005 р. о 12 годині на засіданні спеціалізованої вченої ради Д 26.062.07 Національного авіаційного університету за адресою: 03058, м. Київ, просп. Космонавта Комарова, 1.

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

Автореферат розісланий 18.11.2005 р.

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

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

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

Мартинова О.П.

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

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

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

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

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

Основою для рішення поставлених задач стали роботи видатних учених: Г.Є. Пухова, В.В. Васильева, В.Л. Баранова, О.Г. Додонова, І.А. Жукова, В.А. Веннікова , І.М. Мінаєва і їх учнів.

Зв'язок роботи з науковими програмами, планами, темами Робота виконувалась в рамках наукових досліджень ДУІКТ та НАУ, результати яких були впроваджені у ВАТ „Укртелеком” та ТОВ “Інтелектуальні комунікації”.

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

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

1)

2)

3)

4)

5)

6)

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

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

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

1.

2.

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

· постійно контролювати ступінь завантаження визначеної зони.

3.

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

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

1.

2.

Отримані результати дисертаційної роботи були впроваджені у ВАТ „Укртелеком” та ТОВ “Інтелектуальні комунікації”.

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

Апробація роботи Основні положення роботи доповідалися та обговорювалися на Міжнародній конференції студентів, аспірантів та молодих спеціалістів „Світ інформації та телекомунікацій" (Україна, м. Київ, 2002), на наукових семінарах та засіданнях кафедр ДУІКТ та НАУ.

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

Структура та обсяг роботи Дисертація складається зі вступу, чотирьох розділів, висновків, що містять основні результати, списку використаної літератури з 92 найменувань, двох актів впровадження, 26 рисунків та 4 таблиць, додатків – всього на 142 сторінках. Основний текст дисертації викладено на 126 сторінках.

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

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

У першому розділі проведено аналіз стану та перспектив розвитку протоколів маршрутизації ІР-пакетів. Встановлено, що найбільш перспективним напрямком розвитку є мережі на основі стеку протоколів TCP/IP та його модифікацій. Встановлено, що швидкий ріст пропускної здатності каналів і, як наслідок, збільшення трафіку в мережах потребує підвищення продуктивності маршрутизаторів. Однак просте підвищення їхньої швидкодії не дозволяє вирішити цю задачу, що змушує уважніше придивитися до алгоритмів роботи маршрутизаторів. Визначено, що найбільшою проблемою сучасних комп’ютерних мереж є недосконалість існуючих протоколів маршрутизації. Визначено, що існує потреба у вдосконаленні механізмів маршрутизації пакетів у мережах на основі стеку протоколів TCP/IP в напрямку скорочення часу реакції маршрутизаторів на зникнення каналів у мережі та більш рівномірного розподілу трафіку між окремими ланками мережі. За результатами аналізу стану існуючих протоколів встановлено, що головними причинами недосконалості протоколів маршрутизації є нерівномірність затримок та відсутність механізму швидкого встановлення факту перевантаження або виключення маршрутизатора. Однією з головних причин виникнення нерівномірності у часі доставки пакетів є перевантаження окремих ланок мережі. Перевантаження окремих ланок мережі приводить не тільки до збільшення затримок, але й до збоїв окремих маршрутизаторів або груп маршрутизаторів. До факту зникнення маршрутизаторів існуючі протоколи майже не пристосовані. Інформація про зникнення маршрутизатора з мережі може розповсюджуватися протягом кількох годин, а у випадку зникнення груп маршрутизаторів проблеми можливі протягом кількох діб. Це пов’язано з тим, що існуючі протоколи маршрутизації передбачають методи інформування сусідніх маршрутизаторів про свою появу, але мають дуже повільну систему сповіщення про зникнення маршрутизатора. Система сповіщення базується на інформуванні сусідніх маршрутизаторів про зникнення маршрутизатора при обміні таблицями маршрутизації. Ця процедура відбувається, як правило, один раз за півгодини. Сучасні протоколи маршрутизації передбачають реакцію на перевантаження каналів з сусідніми маршрутизаторами. Це відбувається за рахунок використання метрик каналів, тобто використання інформації про стан каналів з сусідніми маршрутизаторами для прийняття рішення про маршрутизацію. Врахування тільки інформації про канали на сусідні маршрутизатори не завжди може виправити становище, особливо при зникненні кількох маршрутизаторів. Можливості існуючих протоколів маршрутизації пакетів майже вичерпали свій ресурс щодо забезпечення надійності функціонування мережі та забезпечення вимог, які виникають при передачі потокової інформації.

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

У другому розділі розроблено адаптивну модель комп’ютерної мережі на основі стеку протоколів ТСР/ІР.

Проведено аналіз існуючих моделей мереж, які використовуються існуючими протоколами маршрутизації, показано, що оптимальною моделлю була б модель, яка враховує інформацію про стан всіє мережі, але це вимагає надто великих витрат ресурсу мережі та маршрутизаторів. Запропоновано використовувати модель з частковим врахуванням інформації про стан мережі. Зона охоплення моделлю – вузли, вибрані по одному з критеріїв (перевищення кількості пакетів, які проходять через активний маршрутизатор та мають пройти через дані вузли, встановленого відсотку або вибір N вузлів із максимальними значеннями статистики проходження через них пакетів та інші). Вибір критерію або модифікація критерію виконує оператор системи. Маємо орієнтований граф G (рис. 1), тому що дані при проходженні в одному напрямку посилаються по одному віртуальному каналу. Дані в іншому напрямку посилаються по іншому віртуальному каналу. В даному випадку віртуальними каналами назвемо сесії організовані протоколами транспортного рівня еталонної 7-ми рівневої моделі. Вузли даного орієнтованого графу xi - це маршрутизатори. Ребра - це канали мережі, що їх з`єднують. Вага ребра Qi - це величина пропускної здатності каналу. Wi – це пропускна здатність вершини, в нашому випадку розмір буфера маршрутизатору. В вузлах не задані розміри полоси пропускання для користувачів окремо, ребра – мають постійну вагу, яка відповідає полосі пропускання на виходах вузлів і розміру буфера вузла. Вага ребра відповідає найменшому значенню, яке регулюється на вих/вх між парою сусідніх вузлів. Вузли призначення пакетів – Кi.

Рис.1. Модель комп’ютерної мережі для визначення ступеня завантаженості каналів мережі

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

пираючись на роботи інших авторів зроблено висновок, що трафік даних, який циркулює в цифрових мережах, і, зокрема, у мережах з комутацією пакетів, має самоподібні, або фрактальні, властивості. “Самоподібність” являє собою властивість процесу зберігати своє поводження і зовнішні ознаки при розгляді в різному масштабі. Для тимчасових послідовностей масштабуємою величиною є час. Виходячи з визначення самоподібності, можна стверджувати, що тимчасові і спектральні характеристики випадкового процесу (у нашому випадку – трафіку) при зміні масштабу будуть описуватися тими самими рівняннями, функціями, але з відповідними масштабними коефіцієнтами. Іншими словами, самоподібність якого-небудь процесу (явища) можна трактувати як інваріантість до змін масштабу або розміру.

Якщо всі канали обслуговування зайняті і мається черга заявок, то потік обслуговуємих заявок можна вважати найпростішим. Зробимо також припущення про найпростіший характер потоку “нетерплячих” заявок у загальному потоці. Відносна пропускна здатність системи q обчислюється з припущення, що будуть обслуговані всі заявки, крім тих, котрі підуть з черги достроково. Тому для перебування середнього числа заявок, що залишають чергу достроково, обчислимо середнє число заявок у черзі:

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

Відносна пропускна здатність СМО буде , середнє число зайнятих каналів (із загального числа ) , середнє число заявок у черзі . Тут інтенсивності потоку заявок і обслуговування відповідно;

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

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

. (1)

ри H=0,5 ця формула спрощується:

, (2)

о являє собою класичний результат СМО з найпростішим вхідним потоком і експоненціально розподіленим часом обслуговування (М/М/1). Для системи з детермінованим часом обслуговування (М/D/1) класичний результат виглядає в такий спосіб:

. (3)

а формулами (1 – 3) проведено розрахунки, результати яких зображені на рис. 2.

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

Рис. 2. Залежність довжини черги заявок (потрібної пам’яті буфера )

від коефіцієнту використання для різних моделей вхідного трафіку

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

Рис 3. Залежність часу затримки від полоси пропускання, %

Ці результати добре збігаються з теоретичними результатами, отриманими вище.

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

Кmax=atвимekn/N, (4)

де tвим - виміряний час затримки пакету;

n - кількість пакетів, яким відмовлено в обслуговуванні;

N - загальна кількість посланих пакетів;

а та k - позитивні константи.

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

д2a,k = (Кmax теор - Кmax вим)2. (5)

Оскільки розмірність цільової функції Q(a,k) дорівнює 2, досить ефективним, простим і швидкодіючим є, наприклад, метод покоординатного спуску. Початкові значення змінних a0, k0 виберемо, виходячи з аналізу діапазону результатів вимірів (рис. 3). Алгоритм апроксимації (4-5) реалізується у циклічній формі з незаданим числом повторень. Результати обчислень використовуються для аналізу та прогнозу завантаження окремих маршрутів.

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

· маршрутизувати пакети по каналу, який є менш завантаженим;

· будувати схему мережі;

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

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

Nt~ 90%, при Tm/Te = 5, (6)

де, Nt – ступінь завантаження каналу;

Tm – виміряна затримка;

Te – затримка у незавантаженому каналі.

Для визначення завантаженості каналу потрібно оцінювати помилку вимірів. Чим більша вона буде, тим більша завантаженість каналу. Це дозволяє уникнути необхідності визначати час затримки в “порожньому” каналі і вірно реагувати при зміні характеристик каналу (наприклад, перехід від оптоволоконого до супутникового каналу і т.і.).

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

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

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

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

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

Маршрутизатор n1 повинен прийняти рішення про вибір наступного маршрутизатора для пакета, який повинен попасти у вузол n5. Канал між вузлами n2 та n3 завантажений повністю, але визначити це можливо у випадку, якщо маршрутизатори мають можливість обмінюватися інформацією про стан завантаженості каналу (на малюнку завантаження каналів написана над ребрами у відсотках). Гіпотетично це можливо, але це мало б позитивний ефект лише при невеликій кількості маршрутизаторів, коли ресурси на передачу цієї інформації не перевищували прийнятний відсоток. Для глобальної мережі це не прийнятно. Оцінку можна отримати лише за допомогою експерименту: направити пакет по обом шляхам і визначити, на скільки час на проходження пакету по кожному з шляхів буде більшим за час, потрібний на проходження кожним зі шляхів при повній відсутності завантаження. Ця затримка буде викликана наступними чинниками:

· часом находження пакету у буфері кожного маршрутизатору на шляху;

· станом завантаження апаратних ресурсів маршрутизатору.

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

· шляхом обміну метриками між маршрутизаторами;

· за допомогою власних вимірювань маршрутизатора.

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

У практичній реалізації потрібно враховувати:

· можливість зациклення маршруту проходження пакетів;

· можливість витрачання надто великих мережевих ресурсів на доставку пакету (перевищення часу життя пакету);

· можливість надмірного витрачання ресурсів на прийняття рішень про зміни маршрутів на короткостроковому періоді;

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

Методика складається з двох розділів:

1) підготовка до маршрутизації;

2) маршрутизація пакетів.

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

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

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

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

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

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

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

У четвертому розділі розглянуто існуючі програмні маршрутизатори, і, в якості типового, взято програмний маршрутизатор Zebra, для якого програми написані на мові програмування С. Програмний маршрутизатор Zebra оснований на протоколі TCP/IP і підтримує протоколи маршрутизації: RIPv1, RIPv2, RIPng, OSPFv2, OSPFv3, BGP-4 та BGP-4+. Zebra підтримує традиційний протокол IPv4 та новий протокол IРv6. Zebra має інтерактивний інтерфейс користувача для кожного протоколу маршрутизації і підтримує введення команд користувачем з командної строки.

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

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

Створено програму, яка написана мовою програмування Delphi. У коді були використані додаткові модулі деяких програмістів, які вільно поширюються через Internet (TrayIcon, Ping), системні модулі інсталяційного пакету Delphi 6.0. (Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls, Psock, NMHttp, ComCtrls, Menus, Grids, Spin, AppEvnts) та модулі додаткових вікон, які використовує головна програма (OpenPath, Halp).

Система може складатися з трьох підсистем:

· модуль - маршрутизатор Zebra;

· підсистема збору статистики;

· підсистема маршрутизації при перевантаженнях.

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

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

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

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

Рис.4. Залежність відносної завантаженості комп’ютерної мережі від відносної кількості пакетів

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

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

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

ВИСНОВКИ

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

1.

2.

3.

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

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

1. Кривошеєв Є.А., Климович О.К., Скуйбіда В.Ю. Модель гібридної маршрутизації в мережах з комутацією пакетів // Електроніка та зв’язок: Зб. наук. пр. – К.: ВІТІ НТУУ “КПІ”, 2004. – Вип. №4. – С. 81-88.

2. Скуйбіда О.Ю., Скуйбіда В.Ю. Аналіз протоколів маршрутизації ІР - пакетів // Вісник Державного університету інформаційно-комунікаційних технологій. – К.: ДУІКТ, 2005. – Т3. №1. – С. 34-41.

3. Скуйбіда В.Ю. Методика маршрутизації ІР - пакетів по критерію рівномірного завантаження мережі // Вісник Державного університету інформаційно-комунікаційних технологій. – К.: ДУІКТ, 2005. – Т.3. №2. – С. 105-111.

4. Віноградов М.А., Скуйбіда О.Ю., Скуйбіда В.Ю. Оцінка продуктивності вузлів доступу в Інтернет/інтранет мережі // Вісник українського будинку економічних та науково-технічних знань. – К.: Тов. ”Знання” України, 2003. – Вип.1. – С. 131-137.

5. Скуйбіда В.Ю. Дослідження впливу часу затримки пакету на пропускну здатність мережі // Вісник українського будинку економічних та науково-технічних знань. – К.: Тов. ”Знання” України, 2004. – Вип.1. – С. 95-100.

АНОТАЦІЇ

Скуйбіда В.Ю. Метод маршрутизації пакетів за критерієм рівномірного завантаження мережі. – Рукопис.

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

Дисертацію присвячено питанням маршрутизації пакетів за критерієм рівномірного завантаження мережі. Ідея методики маршрутизації ІР-пакетів полягає у наділенні маршрутизатора функціями моніторингу мережі для встановлення перевантажених ланок мережі і прийняття рішення про маршрутизацію на основі цієї інформації. Для реалізації методики було створено адаптивну модель комп’ютерної мережі. Новизна створеної моделі полягає у формування зони „інтересу”, в рамках якої визначається ступінь завантаження каналів. Для визначення ступеня завантаження каналів запропоновано використовувати метод розрахунку помилки апроксимації за критерієм мінімуму середнього квадрату помилки на інтервалі вимірів. Запропонована модель адаптується спочатку до пакетів (тобто до вузлів їх призначення, які мають найбільшу статистику), а потім до мережі (тобто до каналів, які поєднують визначені вузли). Створено методику збору та аналізу інформації. Ідея методики полягає у постійному моніторингу пакетів, які проходять через маршрутизатор з метою визначення найбільш актуальних вузлів та постійного моніторингу ступеня завантаженості каналів в межах цієї зони. Ідея методики прийняття рішення про оптимальний маршрут полягає у поступовому переносі трафіку з більш низьким пріоритетом на альтернативні шляхи у випадку перевантаження якогось з каналів в межах зони „інтересу”. Новизна полягає у децентралізації контролю стану завантаження комп’ютерної мережі та можливості оперативно реагувати на перевантаження ланок мережі. Створено метод маршрутизації ІР-пакетів за критерієм рівномірного завантаження мережі, який дозволяє збільшити коефіцієнт використання комп’ютерної мережі та не потребує модернізації існуючого на інших маршрутизоторах програмного забезпечення.

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

Скуйбида В.Ю. Метод маршрутизации пакетов по критерию равномерной загрузки сети. – Рукопись.

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

Диссертация посвящена вопросам маршрутизации пакетов по критерию равномерной загрузки сети. Популярность компьютерных сетей стала движущей силой многих информационных технологий. Передача голоса и видеоконференции занимают все большую часть пропускной способности компьютерных сетей. Влияние на функционирование сети также оказывает постоянно увеличивающееся количество пользователей компьютерных сетей, которые используют в работе мультимедийные приложения. Идея методики маршрутизации ІР-пакетов состоит в наделении маршрутизатора функциями мониторинга сети для установления перегруженных звеньев сети и принятия решения о маршрутизации на основе этой информации. Для реализации методики была создана адаптивная модель компьютерной сети. Новизна созданной модели состоит в формирование зоны „интереса”, в рамках которой определяется степень загрузки каналов. Зона „интереса” представляет собой набор узлов назначения пакетов, статистика обращений к которым является набольшей. Для определения степени загрузки каналов предложено использовать метод расчета ошибок аппроксимации по критерию минимума среднего квадрата ошибки на интервале измерений. Предложенная модель адаптируется сначала к пакетам (то есть к узлам их назначения, которые имеют наибольшую статистику), а потом к компьютерной сети (то есть к каналам, которые объединяют определенные узлы). Создана методика сбора и анализа информации. Идея методики состоит в постоянном мониторинге пакетов, которые проходят через маршрутизатор с целью определения наиболее актуальных узлов и постоянного мониторинга степени загруженности каналов в границах этой зоны. Основное преимущество данной методики заключается в быстрой реакции на изменения топологии и перегрузки в компьютерной сети. С помощью данной методики можно определять наиболее загруженный канал; строить схему сети; на основании полученных данных планировать расширение компьютерной сети и определять наиболее проблемные места.

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

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

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

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

Skuybida V.Yu. Method of routing of packets on the criterion of uniform load of network. – Manuscript.

The dissertation on competition of a scientific degree of Candidate Technical Science by a speciality 05.13.13 – Computers, systems and networks. – National aviation university Ministry of Education and Science of Ukraine, Kiev, 2005.

Dissertation is devoted to the packets routing by the criterion of network uniform loading. The concept of IP-packets routing method consists of assigning the router task of the network monitoring, detecting the overloaded links and choice the route based on this data. For realization of the method the adaptive model of computer network was created. The novelty of the developed model consists of the formation of „ interest ” area, which determines the channel loading degree. In order to determine the channel loading degree the method of approximation faults computation by criterion of minimum mean-square-error on the measuring interval is offered to use. At the beginning the offered model fits to the packets (to the setting junctions that have the greatest statistics), and then to the network (to the channels that join the defined junctions). The method of data collection and analysis was created. The idea of method consists of the permanent monitoring of packets, which pass through the router in order to determine the most important junctions and to permanently monitor channel-loading degree within this area. The idea of the decision-making methodology, concerning the determination of optimal route, consists of gradual transfer of traffic with lower priority to the alternative routes in case the channel of “interest” zone is overloaded. A novelty lays decentralization of control of computer network loading status and possibility to operatively react on the network links overloads. The method of route of the ІP-packets on the criterion of uniforms load of network which multiplies the coefficient of the use of network and does not require modernization of existing software is created, on other route.

Key words: route, host of setting of package, adaptive model of computer network, method of collection and analysis of information, method of acceptance of decision about an optimum route, computer network.