Зміст
Введення
1. Алгоритми пошуку найкоротшого шляху
1.1 Вихідні дані
1.2 Алгоритм Дейкстри
1.3 Алгоритм Беллмана-Форда
1.4 Розрахунок шляху з мінімальною кількістю переходів
1.5 Висновки
2. Маршрутизація
2.1 Основи маршрутизації
2.2 Характеристика пртокола RIP
2.3 Побудова маршрутних таблиць
Висновок
Список використаної літератури
Введення
Мета маршрутизації - доставка пакетів за призначенням з максимізацією ефективності. Найчастіше ефективність виражена зваженою сумою часів доставки повідомлень при обмеженні знизу на імовірність доставки. Маршрутизація зводиться до визначення напрямків руху пакетів в маршрутизаторах. Вибір одного з можливих в маршрутизаторі напрямків залежить від поточної топології мережі (вона може змінюватися хоча б через тимчасове виходу деяких вузлів з ладу), довжин черг у вузлах комутації, інтенсивності вхідних потоків і т.п.
Метою курсового проекту є дослідження процесів маршрутизації. У курсовому пректе будуть розглянуті алгоритми пошуку найкоротшого шляху, проведений розрахунок шляху з мінімальною кількістю переходів. Також розглянемо характеристики протоколу RIP і побудуємо маршрутні таблиці.
1.Краткая огляд постановки завдання і шляхів її вирішення
Комп'ютерні мережі, як правило, представляються у вигляді графів, при цьому комутатори і маршрутизатори мереж є вузлами графа, а лінії зв'язку є р алгоритм Белмана-Форда), ребра графа. Ряд понять з теорії графів виявляються корисними при розробці мереж і алгоритмів маршрутизації. Для об'єднаної мережі, такий як Інтернет або інтранет, подання її у вигляді орієнтованого графа також є прийнятним. У цьому випадку кожній вершині відповідає маршрутизатор. Якщо два маршрутизатора безпосередньо сполучені до однієї і тієї ж локальної або глобальної мережі, тоді це двосторонньо з'єднання відповідає парі паралельних ребер, що з'єднують відповідні вершини. Якщо до мережі прямо приєднані більше двох маршрутизаторів, тоді ця мережа представляється у вигляді безлічі пар паралельних ребер, кожна з яких сполучає два маршрутизатора. В об'єднаній мережі для передачі IP-дейтаграми від маршрутизатора - джерела до маршрутизатора - приймачу по різних лініях через різні мережі та маршрутизатори пакетів потрібно прийняти рішення про вибір маршруту. Це завдання також еквівалентна пошуку шляху у графі.
Мережа з комутацією пакетів (або мережа ретрансляції кадрів, або мережу ATM) але розглядати як орієнтований граф, в якому кожна вершина відповідає вузлу комутації пакетів, а лінії зв'язку між вузлами відповідає пара паралельних ребер, по кожному з яких дані передаються в одному напрямку. У такій мережі для передачі пакета від вузла-джерела вузлу - одержувача по різних лініях через кілька комутаторів пакетів потрібно прийняти рішення про вибір маршруту. Це завдання еквівалентна пошуку шляху у графі.
Практично у всіх мережах з комутацією пакетів і у всіх об'єднаних мережах рішення про вибір маршруту приймається на основі однієї з різновидів критерію мінімальної вартості. Якщо вибирається маршрут з мінімальною кількістю ретрансляційних ділянок (хопов), тоді кожному ребру, відповідному ретрансляційної ділянці, призначається одиничний вагу. Таке завдання відповідає пошуку найкоротшого шляху в звичайному (не зважене) графі. Але частіше за все кожному ретрансляційної ділянці у відповідність ставиться певна величина, яка називається вартістю (cost) передачі. Ця величина може бути обернено пропорційній пропускної здатності лінії, прямо пропорційною поточної навантаженні на цю лінію або представляти собою якусь комбінацію подібних параметрів. При розрахунку вартості можуть враховуватися також такі критерії, як фінансова вартість використання ретрансляційного ділянки. У будь-якому випадку, вартості використання ретрансляційних ділянок є вхідними даними для алгоритму пошуку шляху з мінімальною вартістю, який може бути сформульовано таким чином.
Нехай є мережа, що складається з вузлів, з'єднаних двонаправленими лініями зв'язку, і кожній лінії поставлена у відповідність вартість пересилки даних в кожному напрямку. Вартість шляху між двома вузлами визначаєте як сума вартостей усіх ліній, які входять у даний шлях. Завдання полягає в тому, щоб знайти шлях з найменшою вартістю для кожної пари вузлів.
Зверніть увагу на те, що вартість використання ретрансляційного ділянки може бути різною в різних напрямках. Наприклад, це справедливо у випадку, якщо вартість використання ретрансляційного ділянки пропорційна довжині черги дейтаграм, що чекають передачі. У теорії графів завданню знаходження шляху з найменшою вартістю відповідає завдання пошуку шляху з найменшою довжиною у зваженому орієнтованому графі.
Більшість алгоритмів пошуку маршруту з найменшою вартістю, що застосовуються в мережах з комутацією пакетів і об'єднаних мережах, є варіації одного з двох загальних алгоритмів, відомих як алгоритм Дейкстри (Dijkstra) і алгоритм Беллмана - Форда (Bellman - Ford). У цьому розділі обговорюються обидва алгоритму.
1.1 Вихідні дані
Номер варіанта-6
Матриця суміжності
V 1 V 2 V 3 V 4 V 5 V 6
V 1 0 0 5 0 1 5
V 2 0 0 0 3 2 4
V 3 2 0 0 6 4 0
V 4 0 6 2 0 0 0
V 5 1 5 5 0 0 0
V 6 6 6 0 0 0 0
Малюнок 1. Зважений орієнтований граф, побудований за матрицею суміжності
V 2
V 1 V 3
1.2 Алгоритм Дейкстри
Алгоритм Дейкстри може бути сформульовано таким чином. Алгоритм знаходить найкоротші шляхи від даної вершини-джерела до всіх інших вершин, перебираючи шляху в порядку збільшення їх довжин. Робота алгоритму проходить поетапно. До k - му кроці алгоритм знаходить k найкоротших (з найменшою вартістю) шляхів до k вершин, найближчим до вершини-джерела. Ці вершини утворюють безліч Т. На кроці (k + 1) до безлічі Т додається вершина, найближча до вершини-джерела серед вершин, що не входять в безліч Т. При додаванні кожної нової вершини до безлічі Т визначається шлях до неї від джерела. Формально цей алгоритм може бути визначений таким чином. Введемо позначення:
N - множина вершин мережі;
s - Вершина-джерело;
Т - множина вершин, вже оброблених алгоритмом;
Дерево - Сполучна дерево для вершин, що належать безлічі Т, включаючи ребра, що входять в дорозі з найменшою вартістю від вершини s до кожної вершини безлічі Т;
w (i, j) - вартість лінії від вершини i до вершини j, причому w (i, j) = 0 або w (i, j) = ¥, якщо дві вершини не з'єднані безпосередньо, і w (i, j) => 0, якщо дві вершини з'єднані безпосередньо;
L (n) - мінімальна вартість шляху від вершини s до вершини п, відомого на даний момент алгоритмом (по завершенні роботи алгоритму це мінімальна вартість шляху від вершини s до вершини п).
Алгоритм складається з трьох кроків. Кроки 2 і 3 повторюються до тих пір, поки безліч T не співпаде з безліччю N. Це означає, що кроки 2 і 3 повторюються, поки для всіх вершин мережі не будуть знайдені остаточні шляху.
1. Ініціалізація. Т = Дерево = {s},
то є безліч досліджених вершин складається поки що тільки з вершини-джерела.
L (n) = w (s, п) для п ¹ s,
тобто вартості початкових шляхів до сусідніх вершин являють собою просто вартості ліній зв'язку.
2. Отримати наступну вершину.
Знайти наступну вершину, не належить безлічі T і має шлях від вершини s з мінімальною вартістю, і включити цю вершину в безліч T і в Дерево. Крім того, до дерева додається ребро, Інцидентне цій вершині і вершині множини T, входить в дорогу з мінімальною вартістю. Це може бути сформульовано таким чином. Знайти вершину x Ï Т таку, що
L (x) = min L (j)
j Ï T
Додати вершину х до безлічі T і до дерева; додати до дерева ребро, Інцидентне вершині х, що становить компонент шляху L (x) з мінімальною вартістю, тобто останній ретрансляційних ділянку шляху.
3. Оновити шлях з мінімальною вартістю.
L (n) = min [L (n), L (x) + w (x, п)] для всіх п Ï Т.
Якщо остання величина мінімальна, то з цього моменту шлях від вершини до вершини п являє собою конкатенацію шляху від вершини s до вершини х та шляхи від вершини х до вершини п.
Алгоритм завершує роботу, коли всі вершини додані до безлічі Т. Таким чином, для роботи алгоритму потрібно | V | ітерацій. До моменту закінчення роботи алгоритму значення L (x), поставлене у відповідність кожній вершині x являє собою мінімальну вартість (довжину) шляху від вершини s до вершини х. Крім того, Дерево являє собою сполучну дерево вихідного орієнтованого графа, що визначає шляхи з мінімальною вартістю від вершини s до всіх інших вершин.
На кожній ітерації при виконанні кроків 2 і 3 до безлічі T додається одна нова вершина, а також знаходиться шлях з мінімальною вартістю вершини s до цієї вершини. Іншими словами, на кожній ітерації до безлічі додається вершина х, а значення L (x) на цей момент часу представляє собою мінімальну вартість шляху від вершини s до вершини х. Більш того, шлях з мінімальною вартістю визначається унікальним шляхом від вершини s, вершини х в безлічі Т. Цей шлях проходить тільки по вершинах, що належить безлічі Т. Щоб зрозуміти це, розглянемо наступний ланцюжок міркувань. Вершина х, додається на першій ітерації, повинна бути суміжною з вершиною і не повинно існувати іншого шляху до вершини х з меншою вартістю. Якщо вершина х не є суміжною з вершиною s, тоді повинна існувати інша вершина, суміжна з вершиною s, що представляє собою перший транзитний ділянку шляху з мінімальною вартістю до вершини х. У цьому випадку при виборі вершини, що додається, до безлічі Т, перевагу буде віддано цій вершині, а не вершини х. Якщо вершина х є суміжною з вершиною s, але шлях s - х не є шляхом з найменшою вартістю від вершини s до вершини х, то це значить, що існує інша суміжна з вершиною s вершина у, що знаходиться на шляху з мінімальною вартістю, і при виборі додається до безлічі Т вершини перевагу буде віддано вершині у, а не вершині х. Після виконання k ітерацій у безліч T увійдуть k вершин і буде знайдено шлях з мінімальною вартістю від вершини s до кожної з цих вершин. Тепер розглянемо всі можливі шляхи від вершини s до вершин, що не входять в безліч Т. Серед цих шляхів суті один шлях з мінімальною вартістю, що проходить виключно по вершинах, що належить безлічі Т, що закінчується лінією, безпосередньо зв'язує якусь вершину безлічі Т з вершиною, яка не належить безлічі Т. Ця вершина додається до безлічі Т, а відповідний шлях вважається шляхом з найменшою вартістю до даної вершини.
У табл. 1 показаний результат застосування даного алгоритму до графа, представленому на рис.1.
№ | Т | L (2) | Шлях | L (3) | Шлях | L (4) | Шлях | L (5) | Шлях | L (6) | Шлях |
1 | {1} | ∞ | - | 5 | 1-3 | ∞ | - | 1 | 1-5 | 5 | 1-6 |
2 | {1; 5} | 6 | 1-5-2 | 5
| 1-3 1-5-3 | ∞ | - | 1 | 1-5 | 5 | 1-6 |
3 | {1; 5; 2} | 6 | 1 - 5 -2 | 5
| 1-3 |
1-5-3