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

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

УДК 004.7:519.87(043.3)

Автореферат

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

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

05.13.05 - комп'ютерні системи та компоненти

ЧУБА Ірина Вікторівна

Київ - 2008

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

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

Науковий керівник: доктор технічних наук, професор Жуков Ігор Анатолійович, Національний авіаційний університет, директор Інституту комп'ютерних технологій.

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

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

кандидат технічних наук Скуйбіда Вадим Юрійович, відкрите акціонерне товариство “Укртелеком”, начальник відділу.

Захист відбудеться " 24 " квітня 2008 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.062.07 Національного авіаційного університету за адресою: 03680, м. Київ, просп. Космонавта Комарова,1.

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

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

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

маршрутизація гетерогенний мережа математичний

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

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

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

Широке коло питань, пов'язаних з дослідженням методів та процесів маршрутизації в комп'ютерних мережах, розглядаються в роботах вітчизняних та зарубіжних вчених В.Г. Оліфера, Н.О. Оліфер, В.М. Вишневського, Ю.М. Мінаєва, М.В. Кульгіна, Andrew S. Tanenbaum, William Stallings, Craig Zaker та ін.

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Виконання роботи пов'язано з реальними потребами галузі комп'ютеризації як на національному, так і міжнародному рівнях. Питання, які розглядаються в дисертаційній роботі, безпосередньо випливають із задач у сфері науки і техніки, сформульованих у “Концепції розвитку зв'язку та інформатизації України до 2010 року”, затвердженої Постановою Кабінету Міністрів України № 223/8 від 09.12.99р.; науково-дослідних робіт відповідної цільової державної науково-технічної програми “Телекомунікаційні системи та інвестиційні ресурси”.

Результати дисертаційних досліджень були використані при проведенні науково-дослідних робіт, що проводилися в Національному авіаційному університеті:

- “Методи та засоби визначення атак на комп'ютерні системи на базі аналізу та прогнозування трафіка як динамічної хаотичної послідовності в тензорному нейромережевому базисі” (389-ДБ07) (номер державної реєстрації №0107U002816);

- “Формування та міжнародно-правове забезпечення національних супутникових мереж. Пошук шляхів та аналіз способів забезпечення частотно-орбітальним ресурсом (ЧОР) українського телекомунікаційного геостаціонарного супутника” (шифр “Либідь-ГСО/НАУ”) на підставі державного контракту №5/2006 (331-Х06) від 27.04.2006 р. між НАУ та ДП “Укркосмос”; - “Розробка пропозицій щодо організації системи технічного захисту інформації телекомунікаційної мережі космічного ракетного комплексу “Циклон-4” на підставі державного контракту № 355-Х06 від 12.09.2006 р. між НАУ та ДКБ „Південне”.

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

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

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

- аналіз принципів і методів моніторингу сучасних мереж;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Одержані результати роботи впроваджені в науково-дослідних та дослідницько-конструкторських розробках Українського науково-дослідного інституту зв'язку, а також застосовуються в навчальній дисципліні «Комп`ютерні мережі», що викладається на кафедрі комп'ютерних інформаційних технологій Інституту комп'ютерних технологій Національного авіаційного університету, що підтверджено відповідними актами впровадження. Особистий внесок здобувача. Всі результати, що складають основний зміст дисертаційної роботи, отримані автором самостійно. По результатам наукових досліджень опубліковано дві статті без співавторів. В роботах, виконаних у співавторстві, здобувачеві належить: [2] - порівняльний аналіз та методика оптимізації топологій мереж доступу для застосування у складених комп'ютерних мережах; [3] - результати системного аналізу прикладних задач застосування методу аналізу ієрархій у комп'ютерних системах та мережах; [6] - результати використання сучасних технологій в учбовому процесі ; [7] - аналіз організації системи керування мережними процесами в комп'ютерних мережах.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались та обговорювались на наукових семінарах кафедри комп'ютерних систем та мереж Інституту комп`ютерних технологій Національного авіаційного університету (м. Київ, Україна, 2003-2007 рр.), на міжнародних конференціях, а саме: ІІІ, VI Міжнародних наукових конференціях студентів та молодих учених «ПОЛІТ» (Національний авіаційний університет, м. Київ, Україна, 2003 р., 2006 р.), VIII Міжнародна науково-практична конференція «Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики та освіти» (Європейський університет, м. Київ, Україна, 2002 р.). Публікації. Основні результати дисертаційної роботи опубліковані в 7 наукових працях, серед яких 4 - у фахових виданнях за переліком, затвердженим ВАК України [1-4] і 3 - у матеріалах конференцій [5-7].

Структура та обсяг дисертації. Дисертація складається зі вступу, чотирьох розділів, висновків та списку використаних джерел з 58 найменувань, одного додатку, 2 актів впровадження, 11 рисунків, 21 таблиць - всього на 144 сторінках. Основний текст дисертації викладено на 116 сторінках.

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

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

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

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

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

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

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

– всі лінії зв'язку на інтервалі спостереження працюють безвідмовно;

– завадостійкість ліній зв'язку достатньо висока, так що помилки, спотворення і повторні передачі розглядаються як рідкісні явища на інтервалі спостереження;

– вузли комутації мають нескінченну пам'ять;

– час обробки у вузлах комутації значно менше інтервалу спостереження;

– довжини всіх повідомлень незалежні і розподілені по показовому закону з середнім значенням 1/[байт];

– трафік, що поступає у мережу, має однаковий пріоритет.

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

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

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

Таблиця 1. Таблиця маршрутизації

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

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

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

У цій моделі в метриці альтернативних маршрутів використовується додатковий компонент функції адміністративної відстані

,

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

Оскільки адміністративна відстань лежить в межах від 0 до 255, то значення, відповідно, змінюватимуться від 1 до 9. Інформаційна цінність параметра залежить від його величини: при інформація про стан маршруту вважається абсолютно достовірною; при інформація про стан маршруту вважається абсолютно недостовірною і відкидається. Тому у якості кількісної оцінки достовірності інформації про адміністративну відстань можна вибрати ентропійну міру Шеннона або співставити з достовірністю значення (у загальному випадку - вибрану деяким чином функцію) вагового коефіцієнта .

У якості функції вибрано функцію виду

,

де - коефіцієнт нормування.

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

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

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

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

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

- адміністратори мережі (сегментів мережі);

- користувачі - замовники послуг;

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

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

Якщо k експертів порівнюють n об'єктів і якщо f_ij - емпірична частота, відповідна числу переваг експертами об'єкту i над об'єктом j, то частка p_ij, з якою i більш придатне, ніж j, p=f_ij / k.

Розподіл всіх процесів, що розрізняються, які визначаються стимулом i, нормально щодо модального розрізняючого процесу (або середнього). Середній розрізняючий процес , що асоціюється із стимулом i, називається значенням в шкалі стимулу, а дисперсія розрізняючого процесу позначається через _i. У припущенні про нормальність p_ij може бути виражено як стандартне нормальне відхилення z_ij =s_i - s_j . Тому p_ij =0,5, коли z_ij = 0, і це має місце у випадку . Якщо z_ij > 0, то вважається, що розрізняючий процес j вищий, ніж i. Маємо

Розподіл різниць s_i - s_j є нормальним з середньоквадратичним відхиленням

де - кореляція між та

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

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

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

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

1. Формулювання задачі.

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

3. Ідентифікація критеріїв, що впливають на задачу.

4. Побудова ієрархії загальних критеріїв, приватних критеріїв, властивостей альтернатив і самих альтернатив.

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

6. Щоб усунути неясність, ретельно визначається кожен елемент в ієрархії.

7. Встановлення пріоритетів первинних критеріїв щодо їх дії на загальну мету, звану фокусом.

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

9. Установка пріоритетів приватних критеріїв щодо своїх загальних критеріїв.

10. Введення суджень про парні порівняння і їх зворотні величини.

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

12. У разі сценаріїв калібрування їх змінних стану за шкалою від -8 до +8 залежно від того, наскільки вони відрізняються від існуючого стану, позначеного 0.

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

14. У разі вибору серед альтернатив пошук альтернативи з найбільшим пріоритетом.

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

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

У табл. 2 наведені глобальні пріоритети для логічних топологій мереж доступу, які були взяті як найбільш характерні варіанти сегментів мережі, та відповідні типи маршрутів. Де КТ - кільцева топологія, ТТ - топологія “точка - точка”, ТБТ - топологія “точка - багато точок”, ПЗТ - повнозв'язна топологія.

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

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

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

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

- від адміністратора мережі (статичні записи без обмеження терміну життя, що зберігаються при перезавантаженні, а іноді - після виключення і повторного включення маршрутизатора);

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

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

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

Випадкова узгодженість. xi - один з елементів матриці парних порівнянь.

Фундаментальна проблема застосовності методу полягає в пошуку і обґрунтуванні відповіді на питання: яку речовинну функцію комплексного власного значення і власного вектора вибрати як однозначний параметр рішення?

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

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

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

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

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

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

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

2. В даний час використовується не більш 1% сумарної «міжнародної» смуги пропускання. У теж час регулярні втрати пакетів на внутрішніх і транзитних мережах досягають 30%. Втрата вже 10% пакетів помітно позначається на продуктивності мережі, а при втраті 50% пакетів мережна служба стає фактично даремною. Це означає, що управління мережею в цілому і розподіл потоків трафіку залежно від завантаження маршрутів є вельми недосконалими. Тому актуальність задач покращення методів і алгоритмів маршрутизації, особливо стосовно складових гетерогенних мереж, не викликає сумнівів.

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

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

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

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

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

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

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

1. Лисовая (Чуба) И.В. Метод оптимальной маршрутизации в составных вычислительных сетях // Проблеми інформатизації та управління: Зб. наук. пр. - К.: НАУ, 2006. - Вип. 3(18). - С. 93-98.

2. Жуков И.А., Лисовая (Чуба) И.В. Оптимизация класса топологии сетей доступа // Проблеми інформатизації та управління: Зб. наук. пр. - К.: НАУ, 2007. - Вип. 1(19). - С. 68-74.

3. Лисовая (Чуба) И.В., Мишарин И.В., Черныш О.А. Системный анализ прикладных задач многокритериальной оптимизации методом анализа иерархий // Проблеми інформатизації та управління: Зб. наук. пр. - К.: НАУ, 2007. - Вип. 3(21). - С. 116-120.

4. Лисовая (Чуба) И.В. Асимптотические оценки эффективности алгоритма многокритериального выбора маршрутов в гетерогенной сети // Проблеми інформатизації та управління: Зб. наук. пр. - К.: НАУ, 2007. - Вип. 4(22). - С. 4-8.

5. Лисовая (Чуба) И.В. Совершенствование методологии обеспечения безопасности компьютерных сетей // Наука і молодь: Зб. наук. пр.: Матеріали Міжнародної наукової конференції студентів та молодих учених «ПОЛІТ-2003». - К.: НАУ, 2003. - Вип. № 3. - С. 130-134.

6. Мартынова О.П., Лисовая (Чуба) И.В. Применение современных мультимедийных технологий в учебном процессе // Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики та освіти: VIII Міжнародна науково-практична конференція. Київ, 12-13 грудня 2002 р. - К.: Європейський університет, 2003. - Ч. 2. - С. 44-47.

7. Лісова (Чуба) І.В., Альтман І.Є., Кудзіновська І.П. Організація системи керування мережними процесами в комп'ютерних мережах // «ПОЛІТ-2006»: VI Міжнародна наукова конференція студентів та молодих учених. Київ, 11-12 квітня 2006 р. - К.: НАУ, 2006. - С. 128.

АНОТАЦІЇ

ЧУБА І. В. Метод маршрутизації у гетерогенних комп'ютерних мережах на основі аналізу ієрархій. - Рукопис.

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

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

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

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

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

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

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

ЧУБА И. В. Метод маршрутизации в гетерогенных компьютерных сетях на основе анализа иерархий. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - Национальный авиационный университет, Киев, 2008. Защищаются метод маршрутизации по нескольким критериям качества маршрутов и методика оценивания чувствительности решений к отклонениям исходных данных от точных значений.

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

Проведено исследование характерных свойств таблиц маршрутизации, которые необходимо учитывать при выборе параметров коммутационного оборудования и структуры компьютерной сети. Для повышения достоверности данных о состоянии маршрута в математическую модель введена количественная (функциональная) мера административного расстояния. Качественные различия значимы на практике и обладают элементом точности, когда величина сравниваемых предметов одного порядка или предметы близки относительно свойства, использованного для сравнения. Психологический предел 7 ± 2 градаций при одновременном сравнении объясняется тем фактом, что если взять 7± 2 отдельных объектов с близкими свойствами, то понадобится не более 9 точек, чтобы различить их.

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

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

Даны рекомендации относительно выбора разных параметров сети (типы коммутационных узлов, логическая топология сетей доступа и т.д.) в зависимости от интенсивности потоков данных, их временных характеристик и структуры сети.

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

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

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

CHUBA I. V. The method of routing in heterogeneous computer networks on the basis of analysis hierarchies. - Manuscript.

Dissertation on competition of scientific degree of candidate of technical sciences on specialty 05.13.05. - Computer systems and components. - National aviation university, Kiev, 2008.

The method of routing on a few criteria of quality of routes and method of evaluation of sensitiveness of decisions to declinations of initial data is defended.

The mathematical models of computer networks, including models of processes of routing, are analyzed.

Research of characteristic properties of routing tables which it is necessary to take into account at the choice of parameters of switching equipment and computer network structure is conducted.

The recommendations are given in relation to the choice of different parameters of network (types of commutation nodes, logical topology of access networks etc.) depending on intensity of data flows, their temporal parameters and network structure.

The function of sensitivity of decision of the choice of route to random perturbations of initial data is explored. It is shown that declinations of decision are the sizes of the second infinitesimal order in relation to the spectral radius of matrix of priorities.

Keywords: computer network, heterogeneity, routing, analysis of hierarchies, function of sensitiveness.

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

...