МАРШРУТИЗАЦІЯ В МЕРЕЖАХ ПЕРЕДАЧІ ДАНИХ.. Курсова робота з Інші. Робота № 202272

Перехід до торгівельного партнера Binance

МАРШРУТИЗАЦІЯ В МЕРЕЖАХ ПЕРЕДАЧІ ДАНИХ.

Інформація про навчальний заклад

ВУЗ:

Чернівецький національний університет імені Юрія Федьковича

Інститут:

Не вказано

Факультет:

Математичний факультет

Кафедра:

Кафедра математичних проблем управління і кібернетики

Інформація про роботу

Рік:

2002

Тип роботи:

Курсова робота

Предмет:

Інші

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Чернівецький національний університет ім. Ю. Федьковича Математичний факультет Кафедра математичних проблем управління і кібернетики МАРШРУТИЗАЦІЯ В МЕРЕЖАХ ПЕРЕДАЧІ ДАНИХ курсова робота Науковий керівник: Ассистент кафедри МПУіК Коцур М.П. Чернівці 2002 Зміст Вступ 3 1. Основні поняття, що використовуються при маршрутизації в мережах 3 2. Використання графів в мережевих алгоритмах 6 2.1. Основні поняття теорії графів 6 2.2. Постановка задачі вибору найкоротшого шляху 7 2.3. Способи представлення графів у пам'яті ЕОМ. 8 2.3.1. Вимоги до представлення графів 9 2.3.2. Матриця суміжності 9 2.3.3. Матриця інциденцій 10 2.3.4. Списки суміжності 10 2.3.5. Масив дуг 11 3. Алгоритми пошуку найкоротшого шляху 12 3.1. Алгоритм Беллмана-Форда 12 3.2. Алгоритм Дейкстра 14 3.3. Алгоритм Флойда-Уоршалла 17 4. Сучасні протоколи маршрутизації на основі алгоритма Беллмана-Форда 18 4.1. Протокол RIP 18 4.2. Протокол маршрутизації OSPF 20 5. Опис програми 21 6. Контрольні приклади 22 Висновки 23 Література 24 Вступ Під алгоритмом маршрутизації ми часто розуміємо протокол мережевого рівня, котрий керує пакетами при їхньому русі по мережі зв'язку до потрібного місця призначення. Моменти часу, коли приймаються рішення про вибір маршруту, залежать від того, використовує мережа дейтаграмну передачу чи віртуальні з'єднання. У дейтаграмній мережі два послідовних пакети однієї і тієї ж пари користувачів можуть проходити по різних маршрутах і вибирати маршрут необхідно індивідуально для кожного пакета. У мережі з віртуальними з'єднаннями маршрут вибирається при встановленні кожного віртуального з'єднання. Всі пакети віртуального з'єднання послідовно використовують цей шлях впритул до моменту, коли або дане віртуальне з'єднання закінчує своє існування, або коли для даного з'єднання по яким-небудь причинам вибирається інший маршрут. Звичайно для вибору маршруту використовується достатньо складний набір алгоритмів, які працюють більш менш незалежно, хоча і обмінюються інформацією. Його складність обумовлена рядом причин. По-перше, маршрутизація потребує координації роботи усіх вузлів підмережі, а не тільки однієї пари модулів. По-друге, система маршрутизації повинна справлятися із виходами з ладу ліній чи вузлів шляхом перенаправлення графіка і обновлення баз даних, що використовуються системою. По-третє, для досягнення найкращих характеристик алгоритм маршрутизації може змінити маршрути у випадку коли деякі області мережі стають перевантаженими. В курсовій роботі розглядаються алгоритми вибору найкоротшого шляху в мережі. Розділ 1 містить опис основних понять, що використовуються при маршрутизації в мережах, а також класифікацію методів маршрутизації. У розділі 2 є інформація про використання графів у мережевих алгоритмах, постановка задачі вибору найкоротшого шляху і способи представлення графів у пам'яті ЕОМ. Розділ 3 містить опис алгоритмів Беллмана-Форда, Дейкстра і Флойда-Уоршалла. Розділ 4 присвячений опису сучасних протоколів маршрутизації в мережі RIP і OSPF. У 5 розділі дається опис програми пошуку найкоротшого шляху в мережі, в розділі 6 – контрольний приклад. 1. Основні поняття, що використовуються при маршрутизації в мережах Двома головними функціями, які виконує алгоритм маршрутизації, є вибір маршрутів для різноманітних пар відправник - адресат і забезпечення правильної доставки повідомлень їх адресатам після того, як вибрані маршрути. Друга функція забезпечується шляхом використання різних протоколів і структур даних, що називаються маршрутними таблицями. Основна увага буде приділена першій функції (вибору маршрутів) і тому, як це впливає на характеристики мережі. Існують дві основні характеристики, на які вагомий вплив здійснює алгоритм маршрутизації - пропускна здатність (кількість обслуговувань) і середня затримка пакету (якість обслуговування). Маршрутизація взаємодіє з керуванням потоками у визначенні характеристик через механізм оберненого зв'язку (рис. 1). Рис. 1. Схема маршрутизації. Якщо трафік, що надійшов у підмережу від зовнішніх джерел, відносно малий, він повністю буде прийнятий мережею і тоді Пропускна здатність = Поступаючому навантаженню. Якщо поступаюче навантаження надзвичайно велике, частина цього навантаження буде відхилятися алгоритмом керування потоками і тоді Пропускна здатність= Поступаюче навантаження-Знехтуване навантаження Трафік, прийнятий у мережу, буде мати середню затримку пакетів, яка залежить від того, які маршрути були вибрані алгоритмом маршрутизації. Однак на пропускну здатність вагомий вплив має також алгоритм маршрутизації, оскільки алгоритм керування потоками звичайно діє на основі підтримки балансу між пропускною здатністю і середньою затримкою, наприклад, навантаження, що поступає, не приймається, як тільки затримка стає занадто великою. Тому, якщо алгоритму маршрутизації вдається більш успішно підтримувати малу затримку, то алгоритм керування потоками дозволяє приймати у мережу більше трофіка.. Хоча точний баланс між затримкою і пропускною здатністю встановлюється алгоритмом керування потоками, хороша маршрутизація в умовах великого трафіка, що пропонується, дає найкращу криву типу затримка - пропускна здатність, за якою діє алгоритм керування потоками (рис. 2). Рис.2. Крива типу затримка - пропускна здатність. Рис. 2 Існує декілька способів класифікації алгоритмів маршрутизації. Один із них полягає у розподілі всіх алгоритмів на централізовані і розподілені. У централізованих алгоритмах вибір всіх маршрутів здійснюється у центральному вузлі, а у розподілених - у вузлах мережі. При цьому вузли обмінюються інформацією, якщо це необхідно. Відмітимо, однак, що така класифікація відноситься до реалізації, а не до математичного опису алгоритму. Можливо, що на деякому рівні математичної абстракції розподілений і централізований алгоритми стають еквівалентними. Інша класифікація алгоритмів маршрутизації основується на тому, чи змінюються маршрути в залежності від інтенсивності вхідних потоків. В статичних алгоритмах маршрутизації шлях, що використовується кожною парою відправник-адресат, фіксований і не залежить від коливань графіка. Він може змінюватись лише у вилажу виходу із ладу якого-небудь вузла чи лінії. При використанні алгоритмів цього типу не може досягатися велика пропускна здатність при значній варіації вхідного графіка. Такий спосіб маршрутизації рекомендується застосовувати або для дуже простих мереж, або коли ефективність роботи мережі несуттєва. Для більшості основних мереж з комутацією пакетів використовуються різновиди адаптивної маршрутизації, при якій шляхи від відправників до адресатів для нового графіка змінюються у відповідь на перевантаження. Справа в тому, що у результаті змін статистики вхідного графіка на окремих ділянках мережі можуть виникати перевантаження. У цьому випадку алгоритм маршрутизації повинен намагатися змінити маршрути і направити потоки в обхід місць накопичення пакетів. Застосовується багато алгоритмів маршрутизації, що відрізняються за ступенем складності і ефективності. Це пояснюється історичними причинами і різноманітністю призначення мереж. 2. Використання графів в мережевих алгоритмах 2.1. Основні поняття теорії графів Граф - непорожня множина V і X- деякий набір пар елементів з V. Елементи множини V називаються вершинами, а елементи набору X- ребрами. Підграф - підграфом графа G називається граф, усі вершини і ребра якого містяться серед вершин і ребер графа G. Головний підграф містить усі вершини графа G. Зв'язний граф - граф, у якого для будь-яких двох різних вершин існує ланцюг (послідовність суміжних вершин), що з'єднує їх. Зважений зв'язний граф - зв'язний граф, із заданою ваговою функцією (кожному елементу набору X ставиться у відповідність деяке число - вага ребра). Дерево- зв'язний граф, що не містить циклів. Орієнтований граф або діаграф G=(V,X) - скінчена непорожня множина вузлів V і набір X впорядкованих пар різних вузлів із V; кожна впорядкована пара вузлів із X називається орієнтованою дугою (або просто дугою). Графічно діаграф зображається так само як і граф, але дуга представляється у вигляді стрілки, що йде від першого вузла впорядкованої пари до другого вузла (рис. 3). N={1,2,3,4}, А={(1,2),(2,3),(2,4),(4,2),(4,1),} Рис.3. Зображення діаграфа. Відмітимо, що на рис.3 дуги (2,4) і (4,2) різні. Кожному діграфу G=(Ш) відповідає асоційований (неорієнтований) граф G’=(V’,X’), де V/=V і (i,j)  X’, якщо або (i,j)  X, або (j,i)  X, або одночасно і те, і інше. Будемо говорити, що (n1, n2, … nl) - перехід, шлях або цикл у діаграфі, якщо це перехід, шлях або цикл у асоційованому графі. Крім того, (n1, n2, … nl) називається орієнтованим переходом у діаграфі G, якщо (ni, ni+1) є орієнтованою дугою в G для всіх 1.і l-1. Орієнтований шлях - це орієнтований перехід із вузлами без повторень, а орієнтований цикл - це орієнтований перехід (n1, n2, … nl) із вузлами без повторень, такий, що n1=nl і l > 2. Відмітимо, що (n1, n2, … nl) є орієнтованим циклом, якщо (n1, n2) і (n1, nl) є орієнтованими дугами, але (n1, n2, nl) не може бути неорієнтованим циклом, якщо (n1, n2) - неорієнтована дуга. 2.2. Постановка задачі вибору найкоротшого шляху Методи маршрутизації використовують ряд простих графових алгоритмів. Розглянемо, наприклад, задачу знаходження найкоротшого шляху, у якій є відомими довжини всіх ліній мережі і вимагається знайти шлях, що з'єднує два даних вузла і має мінімальну сумарну довжину. Якщо довжина лінії у деякій мірі відображає степінь її навантаження, то пошук найкоротшого шляху еквівалентний пошуку найменш навантаженого шляху між двома вузлами, а це має відношення до задачі маршрутизації. Розглянемо орієнтований граф G={V, X} із числом вузлів V і числом дуг X, в якому кожній дузі (і, j) приписане деяке дійсне число dij , яке називається довжиною або відстанню дуги. Довжина будь-якого орієнтованого шляху р=(і, j, k, ...., l, m) визначається як dij+djk+…+dlm.. Довжина орієнтованого переходу або циклу визначається аналогічно. Для будь-яких вузлів i і т графа задача найкоротшого шляху полягає у відшуканні такого шляху від i до т, який би мав мінімальну довжину. Задача пошуку найкоротшого шляху виникає надзвичайно часто і має стільки практичних застосувань і інтерпретацій, що любий фахівець, без сумніву, може сам легко привести безліч прикладів. Якщо dij - вартість використання даної лінії (і,j) у мережі передачі даних, то найкоротший шлях від і до m буде маршрутом, по якому дані будуть передаватись із найменшими затратами. Таким чином, якщо вартість використання лінії дорівнює середній затримці пакету при проходженні по цій лінії, то маршрут з найменшими затратами буде маршрутом із найменшою затримкою. На жаль, в мережах передачі даних середня затримка у лінії залежить від інтенсивності навантаження на цій лінії, яка у свою чергу залежить від тих маршрутів, які вибрав алгоритм маршрутизації. Через цей ефект оберненого зв'язку задача маршрутизації набагато складніша від задачі вибору найкоротшого шляху, однак задача знаходження найкоротшого шляху є складовою частиною задачі маршрутизації у всіх постановках, які будуть розглядатися. Задача знаходження найкоротшого шляху виникає також у мережевому плануванні, що використовується керівництвом підприємств при виконанні складних проектів. Вузли мережі відповідають етапам, а дуга від етапу i до етапу j вказує на те, що виконання етапу у залежить від виконання етапу i. Якщо tij - час, необхідний для виконання етапу j, після того як виконаний етап i, то у якості відстані для (і,j) береться dij= -tij . Найкоротший шлях від початку виконання всього проекту до його завершення потребує найбільшого часу, і найкоротший шлях вказує на ті критичні етапи, час виконання яких, по суті, визначає час виконання усього проекту. Ще одним прикладом є деякі задачі динамічного програмування, які можна розглядати як задачі знаходження найкоротшого шляху. І, накінець, багато більш складних задач теорії графів вимагають розв'язання задач знаходження найкоротшого шляху. 2.3. Способи представлення графів у пам'яті ЕОМ. Варто ще раз підкреслити, що конструювання структур даних для представлення в програмі об'єктів математичної моделі — це основа мистецтва практичного програмування. Розглянемо чотири різних базових представлення графів. Вибір найкращого представлення визначається вимогами конкретної задачі та типами структур даних, які допускаються алгоритмічною мовою, що використовується і типом ЕОМ. Більш того, при рішенні конкретних задач використовуються, як правило, деякі комбінації чи модифікації зазначених представлень, загальне число яких неозоро. Але усі вони так чи інакше засновані на тих базових ідеях, що описані в цьому розділі. 2.3.1. Вимоги до представлення графів Відомі різні способи представлення графів у пам'яті комп'ютера, що розрізняються обсягом займаної пам'яті і швидкістю виконання операцій над графами. Представлення вибирається, виходячи з потреб конкретної задачі. Далі приведені чотири найбільш часто використовуваних представлень з вказівкою характеристики n(p,q) — обсяг пам'яті для кожного представлення. Тут р — число вершин, a q — число ребер. ЗАУВАЖЕННЯ Зазначені представлення придатні для графів і орграфів. Представлення ілюструються на конкретних прикладах графа G і орграфа D, діаграми яких представлені на рис. 4. Рис. 4. Діаграми графа (ліворуч) і орграфа (праворуч), що використовуються як приклади. 2.3.2. Матриця суміжності Представлення за допомогою матриці суміжності - одне з найпоширеніших. Воно бере свій початок від зручності ручної роботи з матрицею суміжності та зручності опису алгоритмів на графах, заданих в такий спосіб. Для графів з великим числом дуг це досить компактне представлення, особливо якщо є можливість працювати з двійковими бітами в машинному слові. До недоліків варто віднести велику витрату пам'яті при роботі з графами, що мають невелике число дуг (матриця суміжності при цьому виходить дуже розрідженою), а також неможливість зменшення трудомісткості алгоритмів у тому випадку, коли вона пропорційна числу дуг, а не числу вершин. Представлення графа за допомогою квадратної булевої матриці М: array [l..p, l..p] of 0...1, що відображає суміжність вершин, називається матрицею суміжності, де EMBED Equation.3 Для матриці суміжності n(p,q) = О(р2). Приклад Матриця суміжності неорієнтованого графа симетрична щодо головної діагоналі, тому досить зберігати в пам'яті тільки її половину. Завдання графа за допомогою матриці суміжності зручно ще і тоді, коли граф зважений і елементами матриці є не нулі й одиниці, а ваги дуг. 2.3.3. Матриця інциденцій Представлення за допомогою матриці інциденцій визначає граф однозначно (з точністю до ізоморфізму), але застосовується вкрай рідко в силу великої розрідженості матриці і практичної відсутності алгоритмів, що працюють на такій структурі даних. Матриця Н : array [l..p, l..g] of 0..1 (для орграфів H: array [l..p,l..q] of -1..1), що відображає інцидентність вершин і ребер, називається матрицею інциденцій, де для неорієнтованого графа EMBED Equation.3 а для орієнтованого графа EMBED Equation.3 Для матриці інциденцій n(p,q) = О(pq). Приклад 2.3.4. Списки суміжності Представлення за допомогою списків суміжності є головною альтернативою представленню за допомогою матриці суміжності. Ця структура відображує суміжність вершин і складається з масиву покажчиків Г : array [l..p] off  N на списки суміжних вершин (елемент списку представлений структурою N : record v ..p, п : N endrecord) та називається списком суміжності. У випадку представлення неорієнтованих графів списками суміжності n(р,q) = О(p+2q), а у випадку орієнтованих графів n(p, q) = О(р + q). Приклад Списки суміжності для графа G і орграфа D представлені на рис.5. Рис. 5. Списки суміжності для графа G (ліворуч) і орграфа D (праворуч) Якщо число дуг в орграфі істотньо мале в порівнянні з повним графом, то цей спосіб представлення дуже ефективний. Менш зручний цей спосіб представлення для завдання зважених графів, тому що тоді виникає додаткова задача зберігати десь ваги дуг і встановлювати відповідні зв'язки між дугами і їх вагами. 2.3.5. Масив дуг Представлення графа за допомогою масиву дуг Е : array [l..p] of record b, е: 1..p endrecord, що відбиває список пар суміжних вершин, називається масивом ребер (чи, для орграфів, масивом дуг). Для масиву ребер (чи дуг) n(p,q)=O(2q). Представлення за допомогою масиву дуг застосовується в тих випадках, коли необхідно мати окрему, незалежну нумерацію дуг. При цьому способі кожній дузі зіставляється трійка <u,х z>, де u - дуга, х — її початок, у - її кінець. Цей спосіб представлення легко узагальнюється на випадок зважених графів. Більш того, він найбільш пристосований для збереження різної інформації про дуги. Приклад Представлення за допомогою масиву ребер (дуг) показано в наступній таблиці (для графа G ліворуч, а для орграфа D праворуч). Нехай G — неорієнтований граф, A(G)-його матриця суміжності. Оскільки A(G) симетрична щодо головної діагоналі, будемо розглядати тільки її верхню трикутну частину А'. Запишемо рядки А' послідовно один за одним і розглянемо отриману послідовність з нулів і одиниць як двійкове число. Змінюючи нумерацію вершин, будемо для того самого графа одержувати різні числа. Найбільше з них визначається для графа однозначно і зветься кодом Харарі. Код Харарі визначає граф однозначно, тому, наприклад, задачу визначення ізоморфізму двох графів можна звести до порівняння відповідних кодів Харарі. Правда, цей метод настільки ж неефективний, як і інші методи встановлення ізоморфізму двох довільних графів. Нумерація вершин, що відповідає коду Харарі, зветься канонічною і використовується при перерахуванні (генеруванні) графів із заданими властивостями. 3. Алгоритми пошуку найкоротшого шляху 3.1. Алгоритм Беллмана-Форда Припустимо, що вузол 1 є вузлом-джерелом і треба знайти довжини найкоротших шляхів від вузла до кожного іншого вузла графа. Числа dij>0 позначають завантаженість лінії від вузла i до j. Якщо в графі відсутня дуга (i,j), то dij = . Основна ідея алгоритму Беллмана-Форда полягає у тому, щоб знайти спочатку довжини найкоротших шляхів за умови, що шляхи містять не більше однієї дуги, потім дуги найкоротших шляхів за умови, що шляхи містять не більше двох дуг і т.д. Найкоротший шлях за умови, що шлях містить не більше h дуг, надалі буде називатися найкоротшим (h) шляхом. Нехай Dih– довжина найкоротшого шляху (h) від вузла 1 до вузла і. Будемо вважати, що Dih = 0 для всіх h. Алгоритм Беллмана-Форда має вигляд: Спочатку Di(0) =  для всіх i1. (1) При кожному наступному h  0 EMBED Equation.3 Приклад роботи алгоритму показано на рис.6. Доведемо тепер, що алгоритм 1-2 приводить до правильного результату. Для цього виконаємо доведення індукцією. Зауважимо спочатку, що Di(1)=d1i для і1 i ваги дійсно є довжинами найкоротших (1) шляхів. Далі припустимо, що для даного h: Di(h) є довжинами найкоротших (h) шляхів для всіх і1. Доведемо, що рівність (2) дає довжини найкоротшого (h+1) шляху від вузла 1 до кожного вузла і1. Спочатку покажемо, що ліва частина (2) більша або рівна правої частини, а потім доведемо, що менша або рівна. Припустимо, що (1,...,m,k,i) – найкоротший (h+1) шлях від 1 до і. Тоді його довжина дорівнює довжині шляху (1,...,m,k)+dk. Оскільки (1,...,m,k) містить не більше ніж h дуг, то EMBED Equation.3 Рис.6. Приклад роботи алгоритму Беллмана-Форда Для доведення оберненої нерівності припустимо, що мінімум в правій частині (2) досягається при j=k і що (1,...,m,k) є найкоротшим (h) шляхом, довжина якого за припущенням дорівнює Dk(h). Тоді довжина шляху (1,...,m,k,i) дорівнює правій частині (2). Тому якщо (1,...,m,k,i) – деякий шлях, то EMBED Equation.3 З цих двох нерівностей і випливає необхідний результат. Оскільки оптимальний шлях може містити не більше N-1 дуг, (де N–число вузлів), то Di(N-1) буде довжиною найкоротшого шляху від 1 до і. Також легко помітити, що якщо Di(h-1)=Di(h) для всіх і і певного h, то наступні ітерації з більшим не змінять довжини найкоротших шляхів і Di(h) буде довжиною найкоротшого шляху для кожного і. Число ітерацій алгоритму в найгіршому випадку дорівнює N-1, кожна ітерація повинна бути проведена для N-1, вузла, для кожного вузла мінімізація визначається по N-1 змінній. Таким чином, кількість обчислень приблизно дорівнює O(N3) . Популярність алгоритму Беллмана-Форда полягає у тому, що ітерації у (2) можна виконувати паралельно для різних вузлів, в довільному порядку, що має велике значення для розподілених алгоритмів. 3.2. Алгоритм Дейкстра Перевага цього алгоритму в порівнянні з алгоритмом Беллмана-Форда полягає у значно меншій кількості обчислень. Формальний опис алгоритму: Спочатку P={1}, D1=0, Dj=d1j для j1. Крок 1 (пошук наступного найближчого вузла). Нехай iP, такий, що EMBED Equation.3 . Покласти P: P{i}. Якщо P містить усі вузли, то на цьому робота алгоритму завершується. Крок 2 (поповнення міток). Для всіх jP покласти Dj:=min[Dj, Di+dij] Перейти до кроку 1. Формальна реалізація алгоритму Дейкстра: Вхід: орграф G(V,E), заданий матрицею довжин дуг C: array [l..p,l..p] of real; s і t -вершини графа. Вихід: вектори T: array [l..p] of real; і Н : array [l..p] of 0..p. Якщо вершина v лежить на найкоротшому шляху від s до t, те T[v] — довжина найкоротшого шляху від s до v; H[v] — вершина, безпосередньо попередня v на найкоротшому шляху. for v from 1 to р do T[v]: ==  { найкоротший шлях невідомий } X[v]: =0 { усі вершини не відзначені } end for H[s}: = 0 { s нічого не передує } T[s]: = 0 { найкоротший шлях має довжину 0 ... } X [s]:= 1 { ... і він відомий } v: = s { поточна вершина } М: { відновлення позначок } for u (v) do if X[u] = 0 & Т[і] > T[v] + C[v, і] then Т[і]: =T[v] + C[v,u] { знайдений більш короткий шлях з s в і через v } Н[і]: = v { запам'ятовуємо його } end if end for t=; v: = 0 { пошук кінця найкоротшого шляху } for і from 1 to p do if X[u]=0 & T[u] <t then v: = і; t: == T[u] { вершина v закінчує найкоротший шлях з S} end if end for if v = 0 then stop { немає шляху з s у t} end if if v = t then stop { знайдений найкоротший шлях з s в t} end if X[v]: = 1 { знайдений найкоротший шлях з s в v} goto M Основна ідея алгоритму Дейкстра: на i-ому кроці є множина P з k найближчих вузлів до вузла 1, Di - найкоротші відстані від вузла 1 до кожного вузла з P. Серед усіх шляхів, що з’єднують вузол 1 з деяким вузлом не з P, найкоротший шлях має пройти по вузлам з P. Тому (k+1)–й найближчий вузол, а значить і відповідна найкоротша відстань отримуються мінімізацією по jP величини EMBED Equation.3 . Ці обчислення можна провести ефективно, як описано вище, в результаті чого обчислювальна складність буде порядка O(N2). Приклад: порівняння алгоритму Беллмана-Форда і Дейкстра. dij = dji  i, j Беллман-Форд Дейкстра 3.3. Алгоритм Флойда-Уоршалла Як і в попередніх алгоритмах, остаточний розв’язок знаходиться методом ітерацій, але в різних алгоритмах ітеруються різні величини. Якщо в методі Беллмана Форда ітерується число дуг у шляху, в алгоритмі Дейкстра – довжина шляху, то в алгоритмі Флойда-Уортела ітерується множина вузлів, які допускається мати в якості проміжних вузлів на шляхах. Для більш строгого опису алгоритму позначимо через Dij(n) довжину найкоротшого шляху від вузла і до вузла j при обмеженні, що лише вузли 1,2,...,n можуть використовуватись в якості проміжних вузлів на шляху. Алгоритм при цьому працює так: Спочатку Dij(0)=dij для всіх i, j, ij. Для n=0,1,…,N-1: Dij(n+1)=min[Dij(n), Di(n+1)(n) + D(n+1)j(n)] для ij. У цьому алгоритмі для збереження інформації про шляхи використовується матриця H[1..р, 1..р], де EMBED Equation.3 Алгоритм Флойда: Вхід: матриця C[1..р, 1..р] довжин дуг. Вихід: матриця T[1..р, 1..р] довжин шляхів і матриця H[1..р, 1..р] самих шляхів. for i from 1 to p do for j from 1 to p do T[i,j] :=C[i,j] { ініціалізація } if C[i,j] =  then H[i,j]: = 0 { немає дуги з i в j } else H[i,j]: =j { є дуга з i в j } end if end for end for for i from 1 to p do for j from 1 to p do for k from 1 to p do if ij &:T[j,i] & ik & T[i,k] & (T[j,k]= V T[,j,k]>T[j,i]+T[i,k]) then H[j,k]: =H[j,i] { запам'ятати новий шлях } T[j, k]: = T[j, i]+ Т[i, k] { і його довжину } end if end for end for for j from 1 to p do if T[j,j] <0 then stop { немає розв’язку: вершина j входить у цикл негативної довжини } end if end for end for Перевага цього алгоритму – найкоротші шляхи знаходяться зразу для всіх вузлів, тому алгоритм Флойда приблизно на 50% менш трудомісткий, ніж застосування алгоритму Дейкстра для всіх пар вершин. Обсяг операцій: O(N3). 4. Сучасні протоколи маршрутизації на основі алгоритма Беллмана-Форда 4.1. Протокол RIP RIP є проколом, що містить маршрутну інформацію про мережу (Routing Information Protocol). RIP відноситься до широко відомого класу протоколів маршрутизації, заснованих на так називаному алгоритмі векторів відстаней (алгоритм Беллмана–Форда). Протокол RIP найбільше підходить для маршрутизації повідомлень усередині автономної системи, що працює на єдиних принципах. RIP призначений для роботи в мережах помірних розмірів, що використовують досить однорідну технологію, це може бути, наприклад, мережа деякого наукового чи навчального закладу, що використовує послідовні лінії передачі даних, причому бажано, щоб пропускні здатності таких ліній у межах мережі мінялися незначно. Алгоритми векторів відстаней заснований на обміні між маршрутизаторами тільки інформацією про "відстані" між ними (про відповідні метрики). При цьому вважається, що самі мережі є точковими об'єктами, тобто відстані між двома вузлами однієї мережі дорівнюють нулю, тому відстані між двома маршрутизаторами двох різних мереж дорівнюють відстані між цими мережами. Кожен маршрутизатор має таблицю з переліком всіх інших мереж даного домена маршрутизації з вказівкою тих своїх сусідів, через які проходять шляхи до цих мереж, і відповідних метрик - відстаней до цих мереж від мережі даного маршрутизатора. Таким чином, ці таблиці відстаней індивідуальні в кожного маршрутизатора і відрізняються від таблиць інших маршрутизаторів. Такі таблиці повинні відповідати дійсності, і складаються маршрутизатором по алгоритму Беллмана - Форда. Алгоритм Беллмана - Форда діє в такий спосіб. Кожен маршрутизатор розсилає свою таблицю відстаней усім маршрутизаторам - його безпосереднім сусідам. Фактично це означає, що маршрутизатор повідомляє усім своїм сусідам, як від нього добиратися до різних мереж і які при цьому довжини шляхів. Сусіди приймають це за достовірну інформацію і починають корегувати з урахуванням цієї інформації свої власні таблиці відстаней. А саме, якщо маршрутизатор, покладемо для визначеності C, бачить, що його сусід, нехай це буде A, знає більш короткий шлях до деякої мережі, наприклад до мережі T, ніж він сам, маршрутизатор враховує шлях від нього до сусіда, просто додаючи ці шляхи, тобто якщо виявляється, що через сусіда A шлях до мережі T коротший, то він змінює запис у своїй таблиці відстаней, відповідний мережі T, записуючи туди, що до мережі T шлях лежить через сусіда A і має довжину: (довжина шляху, повідомлена сусідом A)+(довжина шляху до сусіда A). Якщо ж маршрутизатор C бачить, що той його сусід (A), через який проходить шлях від нього (C) до мережі T, говорить, що шлях від A до цієї самої мережі T, виявляється, довший, ніж A думав раніше, то C змінює в записі у своїй таблиці, що відповідає мережі T, стару відстань на нову, яку він обчислює тим же чином: (довжина шляху, повідомлена сусідом)+(довжина шляху до сусіда). Очевидно, що відстані між сусідами повинні бути відомі заздалегідь - це власне і є метрика, що задається. І такі обміни інформацією повторюються до виникнення стану рівноваги. Якщо зміни топології мережі досить рідкі, то процес маршрутизації буде встигати сходитися і хоч якийсь час буде здійснюватися коректна робота мережі. А якщо зміни топології будуть занадто частими, то алгоритм утратить свою дієздатність і маршрутизація в мережі припиниться. Алгоритм Беллмана - Форда не передбачає випадку, коли деяка мережа чи її маршрутизатор стають зовсім недоступні, тому що це фактично відповідає тому, що цей маршрутизатор припиняє розсилати повідомлення. У такому випадку теорема про збіжність не застосовна, а процес, зовсім очевидно, ніколи не зійдеться. Тому RIP розвиває алгоритм Беллмана - Форда, додаючи в нього різні додаткові умови. Наприклад, RIP може розпізнавати обрив лінії, що не передбачалося в первісному алгоритмі. Діагностика виконується просто: якщо мережа не відповідає сусіду занадто довго, вважається, що лінія зв'язку обірвана. Цієї лінії привласнюється метрика, називана "нескінченністю". У дійсності, це просто число, що реальною метрикою бути не може, і просто служить ознакою такої нескінченності. Маршрутизатор не буде намагатися користатися зламаною лінією, тому що "нескінченність" при додаванні з іншим числом також дає "нескінченність", і "нескінченність" завжди більше будь-якого іншого числа. При такім трактуванні "нескінченності", якщо між двома маршрутизаторами обірветься лінія, то вони будуть кивати один на одного доти, поки не дійдуть до довжини шляху, що буде дорівнює "нескінченність"+1, тоді вони зрозуміють, що лінія між ними обірвана і припинять спроби виявлення маршруту по цій лінії. 4.2. Протокол маршрутизації OSPF OSPF (Open Shortest Path First) - протокол наступного в порівнянні з RIP покоління. Крім основної функції - маршрутизації - він надає послуги, відсутні в RIP. Він оперативно розподіляє трафік між рівноцінними маршрутами, оптимізуючи в такий спосіб використання ліній зв'язку. Забезпечує аутентифікацію маршрутів і адміністративний контроль, роблячи маршрутизацію областей. Також він надає можливості маршрутизації по типі трафіка. OSPF використовує інші механізми збору і використання маршрутної інформації. Для складання таблиць маршрутизації він може використовувати будь-які методи, у тому числі алгоритм Беллмана - Форда. У OSPF збір інформації здійснюється в явному вигляді, причому кожен маршрутизатор має повну інформацію про стан мережі, що він одержує в інформаційному обміні зі своїми сусідами, тому він сам може зробити всі необхідні для складання таблиці маршрутизації обчислення в явному виді (по тим алгоритмам, що йому підходять). Як тільки в мережі відбувається яка-небудь зміна лінії, відповідальний за неї маршрутизатор розсилає всім іншим інформацію про свої підопічні лінії зв'язку, про їх поточний стан (про пропускну здатність, про затримки, про завантаженість і т.д.). Розсилання інформації відбувається методом лавинної маршрутизації, тобто кожен маршрутизатор відразу розсилає отриману їм інформацію усім своїм сусідам, що ще не встигли одержати її. При цьому кожен маршрутизатор повинний підтвердити одержання цієї інформації. Маршрутизатори, виходячи з отриманої інформації, обчислюють відповідні таблиці маршрутизації незалежно і самостійно. Таке обчислення відбувається практично миттєво. OSPF також робить простим здійснення маршрутизації по типу трафіка. Така маршрутизація дозволяє розподіляти весь трафік на класи (до восьми класів) і надавати різні маршрути для різних класів. Наприклад, передача файлів може здійснюватися по супутниковій лінії з великою пропускною здатністю, що володіє, однак, значними затримками, і одночасно здійснюватися передача трафіка Telnet по наземній орендованій лінії з малою пропускною здатністю, але з малими затримками. 5. Опис програми У ході виконання курсової роботи була розроблена програма, яка реалізує алгоритми Беллмана-Форда, Дейкстра та Флойда-Уоршалла пошуку найкоротшого шляху у орієнтовному графі. В програмі зроблена спроба графічного задання вхідних даних і наочного представлення результатів. Основне вікно програми має вигляд, показаний на рис.7. 3 1 1 4 2 3 Рис.7. Основне вікно програми Елементи інтерфейсу програми: Перемикач вибору алгоритму (Беллман-Форд, Дейкстра, Флойд-Уоршалл). Область для задання графу у вигляді матриці суміжності (В якості позначення суміжності двох вершин використовується число, що дорівнює вазі ребра, яке з’єднує дані суміжні вершини. Якщо вершини не суміжні, то у відповідній клітинці ставиться “–1”). Область для графічного задання графа. Щоб графічно задати граф, треба, використовуючи ліву кнопку миші, нанести необхідну кількість вершин, а потім з допомогою правої кнопки з’єднати ребрами суміжні вершини. При цьому по замовчуванню вага ребра буде рівною 1, але користувач може змінити це значення в матриці суміжності (див.п.2). В алгоритмах Беллмана-Форда і Дейкстра є додаткове вікно для введення початкової вершини (по замовчуванню за початкову береться перша вершина ). Вікно виводу результату. Як результат виводиться список величин, які визначають найкоротший шлях з фіксованої вершини до всіх інших вершин графа. В алгоритмі Флойда-Уоршалла результат виводиться у вигляді списку величин найкоротшого шляху з кожної вершини графа в усі інші. В алгоритмі Дейкстра вивід результату можливий і графічно у вигляді дерева найкоротших шляхів в разі графічного задання вхідного графу. 6. Контрольні приклади Алгоритм БелманаФорда: Алгоритм Дейкстра: Алгоритм Флойда-Уоршалла: Висновки При виконанні курсової роботи було вивчено елементи теорії графів і їх використання в мережених алгоритмах. Розглянуто способи представлення графів в пам’яті ЕОМ і алгоритми пошуку найкоротшого шляху в графі: Беллмана-Форда, Дейкстра, Флойда-Уоршалла. Розглянуто особливості сучасних протоколів маршрутизації в мережах RIP і OSPF, що працюють на основі алгоритму Беллмана-Форда. Алгоритми Беллмана-Форда, Дейкстра, Флойда-Уоршалла реалізовані в комп’ютерній програмі, написаній на мові DELPHY 5.0. Результатом роботи програми є список найкоротших шляхів з даної вершини в усі інші. В результаті роботи алгоритму Дейкстра виводиться графічно дерево найкоротших шляхів з даної вершини в усі інші. Література Новиков Ф.А. Дискретна математика для програмістів. Питер, 2001, с.304. Бертсекас Д., Галлер Р. Сети передачи данных, Мир, 1989, с.344. Евстигнеев В.А. Применение теории графов в программировании, Москва, Наука, 1985, с.352. Проценко В.С. Техніка програмування мовою С, Либідь, 1999, с.224. Оре О. Теория графов, Москва, Наука, 1985, с.134.

Курсова робота Інші

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись