Факультет: Обчислювальної техніки та інформатики
Спеціальність: Комп'ютерні системи та мережі
В комп'ютерних мережах застосовується велика кількість алгоритмів маршрутизації. Саме мережевий рівень моделі OSI займається розробкою маршрутів доставки пакетів від відправника до одержувача. Щоб дістатися до пункту призначення, пакету потрібно здолати декілька транзитних ділянок між маршрутизаторами. Мережевий рівень є найнижчим рівнем, який має справу з передачею даних на всьому шляху від одного кінця до іншого.
Зазвичай у складних мережах практично завжди існує декілька альтернативних маршрутів, за якими можлива передача даних між двома вузлами. Крім того, великі складені мережі можуть включати мережі різних масштабів – від локальних до територіально-розподілених глобальних мереж.
Маршрутом передачи пакету з одного вузла складеної мережі на іншій є порядок проходження цим пакетом транзитних мереж, що сполучають мережі, в яких розташовано джерело і адресат даного пакету.
Складені мережі, в яких потрібна маршрутизація пакету на мережевому рівні, мають бути об'єднані між собою за допомогою маршрутизаторів. Тому маршрутом пересилки пакету по мережі можна назвати послідовність маршрутизаторів, через які цей пакет буде перенаправлений в процесі дотримання до свого адресата.
Маршрутизація пакетів включає два основні завдання: визначення оптимального маршруту пересилки пакету по складеній мережі; власне пересилку пакету по мережі [1].
Для реалізації завдання передачі даних мережевий рівень повинен володіти інформацією про топологію підмережі зв'язку (тобто про безліч всіх маршрутизаторів) і вибирати потрібний шлях у цій підмережі. Досить важливо стежити за тим, щоб навантаження на маршрутизатори і лінії зв'язку були, за можливістю, більш рівномірними.
Алгоритм маршрутизації реалізується тією частиною програмного забезпечення мережевого рівня, яка відповідає за вибір вихідної лінії для відправки пакету, що прийшов. При сучасному рівні розвитку мережевих технологій особливі вимоги пред'являються до того, щоб алгоритм вибору маршруту володів певними властивостями – коректністю, простотою, надійністю, стійкістю, справедливістю і оптимальністю. Під час роботи великої мережі постійно відбуваються певні відмови апаратури і зміни топології [2].
Магістерська робота виконується впродовж 2008-2009 рр. відповідно до наукового напрямку кафедри «Електронні обчислювальні машини» Донецького національного технічного університету.
Мета роботи. Дослідження і аналіз роботи алгоритму маршрутизації у мережевій топології.
Ідея роботи. Розгляд часткового використання методу централізованої маршрутизації в комп'ютерній мережі, при якому певний головний роутер є центром, а всі сусідні, безпосередньо приєднані до нього – другорядними вузлами. У такому разі для аналізу роботи мережі зручно розташувати маршрутизатори у порядку послідовного чергування.
Основні завдання розробки і дослідження. Для досягнення поставленої мети в процесі дослідження необхідно:
Предмет розробки і дослідження. Комп'ютерна мережа.
Об'єкт розробки і дослідження. Пристрої мережевого рівня – роутери (маршрутизатори).
Методологія і методи дослідження. В процесі дослідження застосовується формальний апарат теорії графів і алгоритмів маршрутизації.
Новизна отриманих результатів полягає у використанні у якості моделі дослідження конкретної розробленої топології мережі і механізму роботи алгоритму маршрутизації для надання послуг обміну даними між вузлами.
Полягає у використанні вибору алгоритму роботи роутера в конкретній топології.
Основні результати докладалися і обгрунтовувалися на четвертій міжнародній науково-технічній конференції студентів, аспірантів і молодих вчених по «Інформатиці і комп'ютерним технологіям».
При розробці алгоритмів маршрутизації часто переслідують одну або декілька з перерахованих нижче цілей: оптимальність, простота і низькі непродуктивні витрати, живучість і стабільність, швидка збіжність, гнучкість, оптимальність [3].
Альтернативна маршрутизація. Завдання вибору оптимальних маршрутів відноситься до класу багатопродуктових задач з цільовою функцією і безліччю обмежень. Отже, існує єдиний локальний мінімум даного завдання, що є глобальним мінімумом, для знаходження якого розроблено чимале число обчислювальних методів [4].
Необхідно пам'ятати, що абсолютно надійних протоколів маршрутизації не існує. При надмірному навантаженні відмовити може будь-який протокол. Певних загальноприйнятих стандартів налаштування протоколів стану каналу немає [5].
Ip-маршрутізація — простий процес, який однаковий в мережах будь-якого розміру. Наприклад, на рис. 1 показаний процес покрокової взаємодії хоста А з хостом В в іншій мережі [6].
Рис. 1. Приклад ip-маршрутізації для двох хостів і одного маршрутизатора.
Адаптивна маршрутизація – це основний вигляд алгоритмів маршрутизації, що застосовуються маршрутизаторами в сучасних мережах із складною топологією. Грунтується на тому, що маршрутизатори періодично обмінюються спеціальною топологічною інформацією про наявні в інтермережі мережі, а також про зв'язки між маршрутизаторами. Зазвичай враховується не лише топологія зв'язків, але і їх пропускна спроможність і стан [7].
Пристрій маршрутизатора: вхідні порти; комутаційний блок; вихідні порти; маршрутний процесор [8].
Провідні лідери в розробці роутер-технологій [9]: Cisco; Juniper; Huawei; Fujitsu; Foundry; NEC.
Моделюванням є потужним методом наукового пізнання, при використанні якого досліджуваний об'єкт замінюється простішим об'єктом, ща називається моделлю. Основними різновидами процесу моделювання можна вважати два його види - математичне і фізичне моделювання. При фізичному (натурному) моделюванні досліджувана система замінюється відповідною їй іншою матеріальною системою, яка відтворює властивості системи, що вивчається, із збереженням їх фізичної природи.
Можливості фізичного моделювання досить обмежені. Воно дозволяє вирішувати окремі завдання при завданні невеликої кількості поєднань досліджуваних параметрів системи. Дійсно, при натурному моделюванні обчислювальної мережі практично неможливо перевірити її роботу для варіантів з використанням різних типів комунікаційних пристроїв - маршрутизаторів, комутаторів і тому подібне. Перевірка на практиці близько десятка різних типів маршрутізатров пов'язана не лише з великими зусиллями і тимчасовими витратами, але і з чималими матеріальними витратами [10].
Розглядається метод дослідження алгоритму маршрутизації. Виробляється диференціювання алгоритмів маршрутизації, що грунтується на декількох ключових характеристиках. По-перше, на роботу результуючого протоколу маршрутизації впливають конкретні задачі. По-друге, вплив різних типів алгоритмів маршрутизації на мережу і ресурси. І нарешті, алгоритми маршрутизації використовують конкретні показники, які впливають на розрахунок оптимальних маршрутів.
У загальному випадку принцип роботи маршрутизатора можна представити наступною послідовністю дій (рис. 2):
Рис. 2 – Алгоритм роботи роутера (анiмацiя: 6 кадрiв, 6 циклiв, 31 Кб).
У деякий початковий момент часу роботи мережі прийнято, що другорядні маршрутизатори (на рис. 3 позначені номерами, починаючи з №14) мають інформацію лише про безпосередньо підключені до них роутери. Центральні роутери з номерами від 1 до 13 містять в своїх таблицях інформацію не лише про безпосередні сусідні маршрутизатори, але і маршрутизатори, що розташовані через один (тобто на відстані з метрикою проходження шляху рівної двум). Надалі при функціонуванні мережі і при пошуку нових необхідних шляхів працюють за алгоритмами маршрутизації лише головні, складніші в реалізації, маршрутизатори. Інформацію про знайдені маршрути вони можуть вказувати другорядним роутерам для можливості роботи мережі і коректної відправки пакетів. Самі ж роутери простої реалізації пошуком маршрутних шляхів не займаються, а - лише відправкою пакетів за даними про топологію мережі у власних таблицях маршрутизації.
Рис. 3 – Топологія экспериментальної мережі.
Алгоритм починає займатися пошуком маршрутів лише тоді, коли вони дійсно потрібні. Нехай необхідно знайти щлях між маршрутизаторами №1 і №8. Вузол №1 генерує спеціальний запит маршруту Route Request і поширює його по мережі широкомовним засобом. У великих мережах алгоритмом генерується багато широкомовних пакетів, тому для уникнення зайвого завантаження і для виявлення адресата відправник розсилає пакет запиту маршруту з кроком, рівним 1. Тобто запит формується для роутеров №14 і №16 (у прикладі). Якщо відповідь не приходить і маршрут як і раніше невизначений, то посилається ще один запит, але з кроком, рівним 2, і так далі. Таким чином, пошук, що почався в певній локальній області, все більше розширює свій обсяг.
Коли після конкретного числа кроків запиту маршруту, знаходиться необхідна інформація, то формується відповідь про наявність шляху Route Reply. Останній вирушає у зворотньому напрямку до джерела запиту. При цьому вузли, що стоять на вказаному маршруті, абсолютно «безкоштовно» отримують інформацію про маршрут до роутеру №8.
Розглядаються проблеми перевантаження ліній передачі даних. З кожною лінією може бути зв'язана речова змінна u, значення якої в межах від 0.0 до 1.0 відображає є використання лінії за останній час. Таку усереднену оцінку завантаженості лінії можна отримати за допомогою нескладних обчислень, періодично визначаючи миттєву завантаженість лінії f (0 або 1) і розраховуючи нове значення змінної u за вираженням:
uнов=auст+(1-a)f,
де константа а визначає, наскільки часто маршрутизатор аналізує завантаженість лінії.
Коли значення змінної u починає перевищувати якийсь пороговий рівень, це означає, що лінія переходить в небезпечний стан. Кожен пакет, що приходить, підлягає перевірці: якщо йому належить слідувати по лінії, що знаходиться в близькому до перевантаження стані, то необхідно вибрати альтернативний маршрут.
Коли число пакетів, що посилаються хостами у мережу, не перевищує її пропускної спроможності, всі вони доставляються адресатам. При цьому кількість доставлених пакетів пропорційна кількості відправлених. Проте по мірі зростання трафіку маршрутизатори перестають встигати обробляти всі пакети і починають їх втрачати. Коли кількість пакетів досягає максимального рівня, продуктивність мережі падає до низького рівня.
У магістерській роботі для досягнення поставленої мети в процесі дослідження виконані наступні завдання:
При написанні даного автореферату магістерська робота ще не завершена. Остаточне завершення: грудень 2009 р. Повний текст роботи і матеріали по темі можуть бути отримані у автора або його керівника після вказаної дати.