Зміст
Введення
Глава 1. Загальні відомості
.1 Маршрутизація
.2 Алгоритми маршрутизації
.3 Теорія графів
Глава 2. Аналіз алгоритмів маршрутизації
.1 Аналіз алгоритму Дейкстри
.2 Аналіз алгоритму Флойда
Глава 3. Розробка алгоритмів маршрутизації
.1 Розробка алгоритму маршрутизації Дейкстри
.1.1 Таблиця найкоротших шляхів і маршрутів
.2 Розробка алгоритму маршрутизації Флойда
.2.1 Таблиця найкоротших шляхів і маршрутів
.3 Порівняльний аналіз алгоритмів маршрутизації
Висновок
Список використаної літератури
Введення
Кожен маршрутизатор діє за алгоритмом найкоротшого шляху. Для реалізації алгоритму він потребує плані мережі з позначеними довжинами каналів. Кожен маршрутизатор знає власну адресу, який був введений в нього при його установці, і звертається до сусідів при пошуку їх мережевих адрес. У працюючої мережі маршрутизатор може розрахувати метрику кожного вихідного каналу. У найпростішому випадку метрика дорівнює 1 для працездатної каналу і нескінченно велика в іншому випадку. Більш точна метрика враховує пропускну здатність каналу і середню затримку при проходженні через його буфер. Метрика вибирається адміністратором мережі, і всі маршрутизатори використовують одну метрику.
Найкоротший шлях можна визначити за допомогою деякого математичного апарату, званого графом. Існують найбільш ефективні алгоритми знаходження найкоротшого шляху:
· алгоритм Дейкстри (використовується для знаходження оптимального маршруту між двома вершинами);
· алгоритм Флойда (для знаходження оптимального маршруту між усіма парами вершин);
Зазначені алгоритми легко виконуються при малій кількості вершин у графі. При збільшенні їх кількості завдання пошуку найкоротшого шляху ускладнюється.
Таким чином, завдання даної роботи можна сформулювати наступним чином:
· Ознайомитися з керуванням процесами маршрутизації пакетів, що передаються через мережу.
· Вивчити теорію вибору найкоротших шляхів і її методів.
· Написати програму, налагодити і вирішити її на ПК.
· Отримати таблицю найкоротших шляхів і маршрутів методом Дейкстри і Флойда.
Глава 1. Загальні відомості
1.1 Маршрутизація
Маршрутизація (англ. Routing) - процес визначення маршруту проходження інформації в мережах зв'язку.
Маршрути можуть задаватися адміністративно (статичні маршрути), або обчислюватися за допомогою алгоритмів маршрутизації, базуючись на інформації про топології і стан мережі, отриманої за допомогою протоколів маршрутизації (динамічні маршрути).
Статичними маршрутами можуть бути:
маршрути, які не змінюються в часі;
маршрути, що змінюються за розкладом;
Маршрутизація в комп'ютерних мережах виконується спеціальними програмно-апаратними засобами - маршрутизаторами; в простих конфігураціях може виконуватися і комп'ютерами загального призначення, відповідно налаштованими.
1.2 Алгоритми маршрутизації
Алгоритми маршрутизації застосовуються для визначення найкращого шляху пакетів від джерела до приймача і є основою будь-якого протоколу маршрутизації. Для формулювання алгоритмів маршрутизації мережу розглядається як граф. При цьому маршрутизатори є вузлами, а фізичні лінії між маршрутизаторами - ребрами відповідного графа. Кожній грані графа присвоюється певне число - вартість, що залежить від фізичної довжини лінії, швидкості передачі даних по лінії або вартості лінії.
1.3 Теорія графів
Теорія графів є важливою частиною обчислювальної математики. За допомогою цієї теорії вирішуються велику кількість завдань з різних областей. Граф складається з безлічі вершин і безлічі ребер, які з'єднують між собою вершини. З погляду теорії графів не має значення, який сенс вкладається в вершини і ребра. Вершинами можуть бути населеними пункти, а ребрами дороги, що з'єднують їх, або вершина є підпрограми, з'єднані вершин ребрами означає взаємодію підпрограм. Часто має значення напрямки дуги в графі. Якщо ребро має напрямок, воно називається дугою, а граф з орієнтованими ребрами називається Орграф.
Дамо тепер більш формально основне визначення теорії графів. Граф G є впорядкована пара (V, E), де V - непорожнє безліч вершин, E - безліч пар елементів множини V, пара елементів з V називається ребром. Упорядкова...
