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

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

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"

УДК 621.391

АВТОРЕФЕРАТ

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

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

ДОСЛІДЖЕННЯ МЕТРИК МАРШРУТИЗАТОРІВ ГЛОБАЛЬНИХ МЕРЕЖ ПЕРЕДАЧІ ДАНИХ

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

МОХАММАД АБДЕЛХАДІ (АЛХАЖ МОХ'Д) АЛХІХІ

Львів - 2011

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

Робота виконана в Національному університеті "Львівська політехніка".

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

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

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

Ложковський Анатолій Григорович, доктор технічних наук, професор, Одеська національна академія зв'язку ім. О.С. Попова, завідувач кафедри комутаційних систем;

Турупалов Віктор Володимирович, кандидат технічних наук, доцент, Донецький національний технічний університет, декан факультету комп'ютерних інформаційних технологій і автоматики.

Захист відбудеться 21 жовтня 2011 р. о 15:00 годині на засіданні спеціалізованої вченої ради Д 35.052.10 в Національному університеті "Львівська політехніка" (вул. С. Бандери,12, м. Львів, 79013, Україна).

З дисертацією можна ознайомитися в бібліотеці Національного університету "Львівська політехніка" (вул. Професорська 1, м. Львів, 79013).

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

Вчений секретар спеціалізованої вченої ради, д.т.н., доцент Бондарєв А.П.

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

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

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

При цьому існує два основні протоколи визначення найбільш вигідного шляху і способу доставки даних: RIP і OSPF. При використанні протоколу маршрутизації RIР основним критерієм вибору найбільш ефективного шляху є мінімальне число "хопів" (hops), тобто мережевих пристроїв між вузлами. Цей протокол мінімально завантажує процесор маршрутизатора і гранично спрощує процес конфігурації, але він нераціонально управляє трафіком. При використанні OSPF якнайкращий шлях вибирається не тільки з погляду мінімізації числа хопів, але і з урахуванням інших критеріїв: продуктивності мережі, затримки при передачі пакету і т. д. Мережі великого розміру, що чутливі до перевантаження трафіку і базуються на складній маршрутизуючій апаратурі, вимагають використання протоколу ОSРF. Реалізації цього протоколу можлива тільки на маршрутизаторах з достатньо потужним процесором, оскільки його реалізація вимагає значних обчислювальних витрат.

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

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

Відоме велике число відомих зарубіжних і вітчизняних учених, які вирішували окремі завдання в цій області: L. Kleinrock, S. Blake, D. Grossman, Z. Wang, Стєклов В.К., Захарченко М.В., Беркман Л.Н., Іванов А.Б., Шехтман Л.І., Вишневський В.М., Оліфер Н.А, Оліфер В.Г., Башарін Г.П., Безрук В.М., Климаш М.М., Тимченко О.В. і ін. Проте завдання отримання оптимальної метрики маршрутизації для об'єднаних мереж, не дивлячись на величезне число публікацій і зусилля фірм-виробників комунікаційного устаткування, остаточно не вирішена.

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

Зв'язок роботи з науковими програмами планами і темами. Тематика дисертаційної роботи безпосередньо пов'язана з пріоритетними напрямками розвитку науки і техніки Кабінету Міністрів України "Перспективні інформаційні технології, прилади комплексної автоматизації, систем зв'язку". Робота виконувалась в рамках держбюджетної теми кафедри "Телекомунікації" Національного університету "Львівська політехніка" "Підвищення ефективності оптичних мереж доступу з використанням кодового мультиплексування каналів", номер державної реєстрації 0109U001147, 2009-2010 рр.

Результати дисертаційних досліджень впроваджено в навчальний процес кафедри "Телекомунікації" в лекційному курсі та лабораторному практикумі з дисципліни "Канали та системи передавання", та при проведенні курсів "Телекомунікаційні системи та мережі". Окремі наукові результати дисертаційної роботи впроваджено в центрі № 6 дирекції первинних мереж України ВАТ "Укртелеком" та ПП "Цифрові технології".

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

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

1. Системний аналіз алгоритмів маршрутизації.

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

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

4. Розробка моделі маршрутизатора з протоколом RIP для IP в системі Simulink, що дозволяє відстежувати поведінку маршрутизатора при різних параметрах обслуговування черг.

• Наукова новизна отриманих результатів полягає в наступному:
• 1. Вперше розроблено математичну модель маршрутизатора за протоколом RIP, що складається з інтерфейсів маршрутизатора, функціонує в активному і пасивному режимах та дозволяє врахувати рівні мережевого протоколу і рівні протоколів маршрутизації.
• 2. Отримала подальший розвиток узагальнена метрика маршрутизації, що дозволяє оптимізувати вибір маршруту передачі даних на основі врахування: часу затримки; пропускної здатності каналу; стійкості маршруту, дозволяє отримання адитивної, мультиплікативної і увігнутої метрики.
• 3. Вперше запропонований і досліджений метод маршрутизації в системі зі змінними параметрами, що дозволяє мінімізувати число помилок маршрутизації.
• 4. Запропонована і досліджена модель маршрутизатора в системі Simulink, що дозволяє відстежувати поведінку маршрутизатора при різних параметрах обслуговування черг та враховувати окремі складові метрики маршрутизації.

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

Предмет дослідження: методи маршрутизації трафіку телекомунікаційних мереж для заданої якості послуг.

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

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

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

Внесок претендента в опублікованих роботах полягає в наступному: в [1] - запропонував методику визначення метрики маршрутизації; в [2] - запропонував враховувати в метриках якість послуги; в [3] - запропонував методику моделювання маршрутизатора; в [4] - провів імітаційне моделювання; в [5] - розробив архітектуру мережі і провів імітаційне моделювання моделі маршрутизатора; в [6] - запропонував методику моделювання маршрутизатора; в [7] - провів дослідження методів і протоколів для забезпечення передачі потокове мультимедіа.

• Апробація результатів дисертації. Основні результати досліджень були представлені і всебічно обговорені на наступних науково-технічних конференціях:
• ХХVIIІ Науково-технічна конференція "Моделювання". ІПМЕ НАН України. 15-16 січня 2009 року. м. Київ.
• Науково-практична конференція "Сучасні проблеми телекомунікацій - 2009", 29-31 жовтня 2009 р., м. Львів.
• Науково-методична конференція "Сучасні проблеми телекомунікацій і підготовка фахівців в галузі телекомунікацій". 28-30 жовтня 2009 р., м. Львів.
• Публікації за темою дисертації. Матеріали дисертації опубліковано в 7 наукових працях, з них 5 статей у фахових виданнях згідно переліку ВАК України, 2 - у матеріалах науково-технічних конференцій.
• Структура і обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, списку використаних джерел (124 найменування) та додатків. Загальний обсяг роботи 172 сторінки, з яких основний текст 139 сторінок.
• ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі "Аналіз протоколів міжмережевої взаємодії TCP/IP. Класифікація і аналіз параметрів алгоритмів маршрутизації" проведено системний аналіз поняття маршрутизації стосовно вибору шляхів передачі даних в глобальних мережах.

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

Проаналізована структура стека протоколів TCP/IP (рис. 1), використовуваних при передачі даних, стек протоколів TCP і стек протоколів при роботі через транспортний протокол UDP. Показано, що в цих протоколах вся інформація про шлях, по якому повинен пройти пакет, береться з самої мережі у момент проходження пакету.

Рис. 1. Зіставлення архітектури протоколів сімейства TCP/IP та еталонної моделі OSI

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

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

· оптимальність;

· простота і низькі непродуктивні витрати;

· живучість і стабільність;

· швидка збіжність;

· гнучкість.

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

Алгоритми, що приймають рішення про маршрут (алгоритми маршрутизації) можуть бути:

1. Статичними або динамічними;

2. Одномаршрутними або багатомаршрутними;

3. Однорівневими або ієрархічними;

4. З інтелектом в головній обчислювальній машині або в маршрутизаторі;

5. Внутрідоменними і міждоменними;

6. Алгоритмами стану каналу або вектору відстаней.

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

У метриках маршрутизації використовуються наступні показники:

· довжина маршруту;

· надійність;

· затримка;

· ширина смуги пропускання;

· навантаження каналів і вузлів;

· вартість зв'язку.

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

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

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

· Алгоритм Дейкстри. Використовується для знаходження оптимального маршруту між двома вершинами.

· Алгоритм Флойда. Використовується для знаходження оптимального маршруту між всіма парами вершин.

· Алгоритм Йена. Використовується для знаходження k-оптимальних маршрутів між двома вершинами.

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

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

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

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

Протокол IGRP дозволяє великому числу маршрутизаторів координувати свою роботу. Його основні переваги:

· стабільність маршрутів навіть в дуже великих і складних мережах;

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

· мінімальна надмірність;

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

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

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

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

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

, (1)

де: - константи; B_e - пропускна здатність каналу (у відсутності завантаження) * (1 - завантаження каналу); D_c - топологічна затримка; r - відносна надійність, (% пакетів, успішно переданих по даному сегменту шляху). Тут завантаження вимірюється як частка від 1.

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

Рис. 2. Функціонування протоколу EGP

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

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

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

Створена і досліджена модель маршрутизатора за протоколом RIP для IP, що функціонує в активному і пасивному режимах. Для цього реалізована функціональна схема маршрутизатора (рис. 3), що складається з інтерфейсів маршрутизатора, рівня мережевого протоколу і рівня протоколів маршрутизації. маршрутизація мережа метрика оптимальний

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

Якщо заявка спрямована на k-ий сервер, що має вільний канал, то заявка обробляється і індикатор I_k =1. У разі відсутності вільних каналів запит перенаправляється на інший сервер. Якщо у нього є вільний канал, то заявка обробляється і індикатор J_1-k =1. Ця ситуація є помилкою маршрутизації. При неможливості обробки заявки ні на одному з серверів відбувається відмова в обслуговуванні і заявка покидає систему.

Рис. 3. Модель маршрутизатора за протоколом RIP

Завдання оптимізації алгоритму полягає в розподілі заявок по серверах таким чином, щоб мінімізувати кількість помилок. Результати експерименту показують, що при малій кількості каналів на серверах (2/4) ефективнішим є алгоритм почергового оброблення заявок (21,2 % помилок), при більшій кількості каналів (10/20) кращим є метод перенаправлення заявки на наступний сервер при виникнення помилки маршрутизації (11,7 % помилок), При малій кількості каналів на серверах кількість помилок цього алгоритму зростає до 31,0 %.

Рис. Алгоритм "-J - -I"

Рис. Алгоритм "-J + -I"

Рис. Алгоритм "-J згладжений"



Рис. Кількість помилок маршрутизації

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

Проаналізовані та показані методи отримання адитивної, мультиплікативної, увігнутої метрик маршрутизації:

Ш Адитивна метрика:

met(p) = meti j +metjk +:::+metqr. (2)

Очевидно що затримка (del), зміна затримки - джитер (dej), кількість стрибків і вартість (ціна) мають адитивний характер.

Ш Мультипликативна метрика:

met(p) = met i j Ч met j k Ч…Ч met q r. (3)

Достовірність успішної передачі (pst) має мультиплікативний характер. Залежність для імовірності втрат (Lp):

met(p) = 1-((1-met i j)Ч(1-met j k)Ч…Ч(1-met q r)). (4)

Ш Увігнута метрика:

met(p) = min{met i j; met j k; …; met q r}. (5)

Пропускна здатність (ширина смуги частот) має увігнутий характер.

ь Метрика затримки передачі даних D(v, и) рівна:

. (5)

ь Метрика пропускної здатності

Якщо b(i, j) - пропускна спроможність каналу e(v, и) Е, де {і, j} V, то для любого маршруту P(v, и) G метрика пропускної здатності B(v, u) дорівнюватиме мінімальній пропускній здатності каналів на шляху між двома вузлами v і и, де {v, u} V:

. (6)

ь Метрика стійкості маршруту

Стійкість л(і, j) каналу між двома суміжними вершинами і і j, рівна:

, (7)

де - імовірність видалення ребра e(v, и) Е з графу G. Стійкість маршруту P(v, и) G між двома вузлами v і и, де {v, u} V, є функцією стійкості всіх каналів даного маршруту:

(8)

Тоді метрика стійкості маршруту P(v, и) G між двома вузлами v і и, де {v, u} V, визначається таким чином:

. (9)

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

· час затримки;

· пропускна здатність каналу;

· стійкість маршруту.

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

Складена метрика маршрутизації M(v, и), що використовується для пошуку оптимального маршруту P(v, и) G між двома вузлами v і и, де {v, u} V, визначається таким чином:

. (10)

Складові метрики маршрутизації M(v, и) (10) визначаються за виразами (2)-(9). Коефіцієнти враховують ступінь впливу характеристик каналів на складену метрику маршрутизації, де:

- ваговий коефіцієнт пропускної спроможності;

- ваговий коефіцієнт завантаження;

- ваговий коефіцієнт затримки;

і - відповідно первинний і вторинний вагові коефіцієнти стійкості маршруту.

Створена і досліджена модель маршрутизатора в системі Matlab Simulink (рис. 4), що містить вхідний буфер, блок комутації пакетів і вихідні буфери. Модель пакету даних (джерела трафіку, рис. 5) представлена у вигляді вектора, який містить: <адреса одержувача>, <адреса відправника>, <довжина пакету>.

Рис. 4. Схема моделі маршрутизатора

Рис. 5. Моделі джерела трафіку

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

Рис. 6. Результати моделювання

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ І ВИСНОВКИ

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

При цьому можна зробити наступні виводи:

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

2. Проведений порівняльний аналіз протоколів маршрутизації RIP, OSPF, IGRP, BGP-4 і EGP. У протоколі RIP маршрут характеризується вектором відстані до місця призначення. Протокол OSPF використовується як внутрішній протокол маршрутизації і характеризується станом маршруту. Протокол IGRP, використовуючи вагові коефіцієнти, адаптує вибір маршрутів до завдань кінцевого користувача. Зовнішній протокол маршрутизації BGP-4 дозволяє реалізувати маршрутну політику, визначену адміністратором AS. Маршрутна політика визначає рішення, коли місце призначення досяжне декількома шляхами, міркування безпеки, економічні інтереси і ін. Протокол зовнішніх маршрутизаторів EGP є протоколом міждоменної досяжності, який застосовується в Internet, не використовує показники і тому містить інформацію тільки про досяжність мереж.

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

4. Досліджений метод здійснення маршрутизації в системі зі змінними параметрами, показано, що існує можливість його оптимізації шляхом розподілу заявок по серверах так, щоб мінімізувати кількість помилок. Показано, що в багатосерверній системі (кількість серверів 20) оптимальним за мінімумом помилок (11,7 %) є метод направлення заявок на наступний сервер після виникнення помилки маршрутизації, в той час як метод почергового оброблення заявок дає 21.8 % помилок. При малій кількості каналів на серверах (2) кількість помилок цього методу зростає до 31,0 %.

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

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

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

1. Тимченко О.В. Дослідження метрик маршрутизації мобільних комп'ютерних мереж / О.В. Тимченко, Алхіхі Мухамад, Фрейхат Ахмад // Зб. наук. пр. ІПМЕ НАН України. - Вип.47. - К.: 2008. - С. 147-151.

2. Тимченко О.В. Дослідження механізмів забезпечення якості обслуговування в мультисервісних мережах / О.В. Тимченко, Самі Аскар, Алхіхі Мухамад, Аль-бдур Нашат // Моделювання та інформаційні технології. Зб. наук. пр. ІПМЕ НАН України. - Вип.47. - К.: 2008. - С. 133-142.

3. Зеляновський М.Ю. Засоби для моделювання спеціалізованих та сенсорних мереж бездротового доступу: симулятори роботи комп'ютерних мереж NS-2 та NS-3 / М.Ю. Зеляновський, Алхіхі Мухамад, Аль-бдур Нашат, Самі Аскар // Зб. наук. пр. ІПМЕ НАН України. - Вип.51. - К.: 2009. - С. 203-210.

4. Верхола Б.М. Розробка архітектури для передачі відеотрафіку MPEG-4 в домені MPLS / Б.М. Верхола, А.Т. Ратич, Алхіхі Мухамад, Фрейхат Ахмад // Зб. наук. пр. ІПМЕ НАН України. - Вип.53. - К.: 2009. - С. 216-221.

5. Верхола Б.М. Аналіз методів і протоколів для забезпечення потокового мультимедіа / Б.М. Верхола, А.Т. Ратич, Алхіхі Мухамад, Фрейхат Ахмад // Моделювання та інформаційні технології. Зб. наук. пр. ІПМЕ НАН України. - Вип.54. - К.: 2009. - С. 237-247.

6. Зеляновський М.Ю. Методика застосування симуляторів комп'ютерних мереж NS-2 та NS-3 / М.Ю. Зеляновський, Алхіхі Мухамад, Аль-бдур Нашат, Самі Аскар // ХХVIIІ Науково-технічна конференція "Моделювання". ІПМЕ НАН України. Тези конференції. 15-16 січня 2009 року. - К.: 2009. - 62 с. - С. 53-54.

7. Верхола Б.М. Особливості методів і протоколів для забезпечення потокового мультимедіа / Б.М. Верхола, А.Т. Ратич, Алхіхі Мухамад, Фрейхат Ахмад // Науково-практична конференція "Сучасні проблеми телекомунікацій - 2009". Матеріали конференції. 29-31 жовтня 2009 р. - Львів: 2009. - С. 63-65.

АНОТАЦІЯ

Мохаммад Абделхаді (Алхаж Мох'д) Алхіхі. Дослідження метрик маршрутизаторів глобальних мереж передачі даних. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.12.02 - телекомунікаційні системи та мережі. Національний університет "Львівська політехніка", Львів, 2010.

Роботу присвячено розробці та дослідженню математичних моделей і методів для аналізу і розробки метрик маршрутизаторів глобальних мереж передачі даних. У метриках маршрутизації використовуються наступні показники: довжина маршруту; надійність; затримка; ширина смуги пропускання; навантаження каналів і вузлів; вартість зв'язку. В результаті їх комбінації отримують один окремий (гібридний) показник, який називається метрикою і є визначальним параметром при виборі маршруту з таблиць маршрутизації. Проведений аналіз протоколів маршрутизації (RIP, OSPF, IGRP, BGP-4 і EGP). Показано, що у всіх протоколах найкращий шлях вибирається з використанням комбінованих метрик (крім протоколу міждоменної досяжності EGP). Досліджений алгоритм маршрутизації в системі зі змінними параметрами, проведена його оптимізація. В багатосерверній системі (кількість серверів 20) оптимальним за мінімумом помилок (11,7 %) є алгоритм направлення заявок на наступний сервер після виникнення помилки маршрутизації, в той час як алгоритм почергового оброблення заявок дає 21.8 % помилок. При малій кількості каналів на серверах (2) кількість помилок цього алгоритму зростає до 31,0 %.

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

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

АННОТАЦИЯ

Мохаммад Абделхади (Алхаж Мох'д) Алхихи. Исследование метрик маршрутизаторов глобальных сетей передачи данных. - Рукопись.

Диссертация на получение научной степени кандидата технических наук по специальности 05.12.02 - телекоммуникационные системы и сети. Национальный университет "Львовская политехника", Львов, 2010.

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

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

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

Проанализированы алгоритмы нахождения кратчайшего пути (Дейкстры, Флойда, Йена). Показано, что известные алгоритмы требуют значительных вычислительных ресурсов - приблизительно О(n²) операций, где n - число узлов сети. Проведен анализ протоколов маршрутизации (RIP, OSPF, IGRP, BGP-4 и EGP). В протоколе RIP маршрут характеризуется вектором расстояния к месту назначения. Протокол OSPF используется в качестве внутренний протокол маршрутизации и характеризуется состоянием маршрута. Протокол IGRP, используя взвешивающие коэффициенты, адаптирует выбор маршрутов к требованиям конечного пользователя. Внешний протокол маршрутизации BGP-4 позволяет реализовать маршрутную политику, определенную администратором AS. Маршрутная политика определяет решение, когда место назначения достигается несколькими путями, требования безопасности, экономические интересы и др. Показано, что во всех алгоритмах выбирается наилучший путь с использованием комбинированных метрик. Протокол внешних маршрутизаторов EGP является протоколом междоменной досягаемости, который применяется в Internet, не использует показатели и потому содержит информацию только о досягаемости сетей.

Исследован алгоритм, который осуществляет маршрутизацию в системе с переменными параметрами, проведена его оптимизация, которая заключается в распределении заявок по серверам так, чтобы минимизировать количество ошибок. Показано, что в многосерверной системе (количество серверов 20) оптимальным по минимуму ошибок (11,7 %) является алгоритм направления заявок на следующий сервер после возникновения ошибки маршрутизации, в то время как алгоритм поочередной обработки заявок дает 21,8 % ошибок. При малом количестве каналов на серверах (2) количество ошибок этого алгоритма возрастает до 31,0 %.

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

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

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

ANNOTATION

Mohammad abdelhadi (ALHAJ MOH'D) AlHIHI. Research of birth-certificates of routers of global networks of telecommunications. - Manuscript.

Dissertation for the scientific degree of candidate of technical sciences in telecommunication systems and networks, specialty 05.12.02. Lviv polytechnic National University, Lviv, 2010.

Work is devoted development and research of mathematical models and methods for an analysis and development of metric routers of global networks transmissions data. The followings indexes are utilized in the metrics of routing: length of route; reliability; delay; B. key-in; loading of ductings and knots; cost of connection. As a result of their combination get one separate (hybrid) index which is named a birth-certificate and is a determining parameter at the choice of route from routing directories. The analysis protocols of routing (RIP, OSPF, IGRP, BGP-4 and EGP) is conducted. It is rotined that in all of protocols the best way gets out with the use of the combined birth-certificates (except for protocol of interblast-furnace reach of EGP). The algorithm of routing is investigational in the system with in-out parameters, his optimization is conducted. In the multiserver system (number of servers 20) optimum after a minimum of errors (11,7 %) is an algorithm of direction of requests on a next server after the origin of error of routing, in that time as an algorithm of by turn treatment of requests gives 21.8 % errors. At a few of number on servers (2) the amount of errors of this algorithm grows to 31,0 %.

A method is offered of receipt of the generalized birth-certificate of routing at the choice of optimum route which takes into account transmissions given of: time of delay; carrying capacity of channel; firmness of route. The methods of receipt of aditivnoy, multiplicative, concave birth-certificate are rotined. Coefficients which take into account the degree of influence of descriptions of ductings on the made birth-certificate are specified. The mathematical model of router, and also model of router, is offered and investigational in the system of Matlab Simulink, which allows to probe the conduct of router at different speeds entrance-output, different disciplines of maintenance of turns in entrance and initial buffers, to change intensity of receipt of packages, determine the volume of the lost information.

Keywords: telecommunication network, routing, metric of routing.

СПИСОК СКОРОЧЕНЬ

AS - Autonomous System. Автономна система

BGP - Border Gateway Protocol. Протокол зовнішньої маршрутизації

EGP - Exterior Gateway Protocol. Протокол зовнішнього шлюзу

IGRP - Exterior Gateway Routing Protocol. Протокол внутрішніх роутерів з вектором відстані

IP - Internet Protocol. Протокол міжмережевої взаємодії

ISO/OSI - International Standards Organization / Open System Interconnection. Міжнародна організація по стандартизації / Модель взаємодії відкритих систем

MPLS - Multiprotocol Label Switching. Багатопротокольна комутація за міткама

OSPF - Open Shortest Pass First. Протокол найкоротшого шляху. Протокол динамічної маршрутизації, що базується на відслідковуванні стану каналу (link-state technology) і використовує для знаходження найкоротшого шляху алгоритм Дейкстри.

RIP - Routing Information Protocol. Протокол маршрутизації.

RTP - Real Time Protocol. Протокол реального часу

SNMP - Simple Network Management Protocol. Протокол мережного управління

TCP - Transmission Control Protocol. Протокол керування передачею

TCP/IP - Transmission Control Protocol/Internet Protocol. Протокол керування передачею даних/Протокол Internet)

UDP - User Data Protocol. Протокол датаграмм користувача

TKС - Телекомунікаційна система.

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