на пара елементів з V називається дугою.
Якщо ребра мають напрямок, то граф називається орієнтованим (Орграф); в іншому випадку він неорієнтовний. Якщо в графі є ребро C з вершини A в вершину B, то кажуть, що ребро C інцидентне вершин A і B, а також що вершина A суміжно з вершиною B.
Рис 1. Приклади графів
Рис 2. Приклад повного і двудольного графа.
Глава 2. Аналіз алгоритмів маршрутизації
Алгоритми маршрутизації класифікуються на статичні і динамічні (рис. 3). Т.е алгоритми, які явно не зараховуються до цих типів, визначають стратегію маршрутизації, не визначаючи конкретні принципи побудови протоколів.
Рис. 3. Класифікація алгоритмів маршрутизації.
Статичні алгоритми маршрутизації, на відміну від динамічних, не враховують постійно змінюється топологію мережі. Це робить її непридатною для використання в більшості мереж.
Всі алгоритми використовують одну з трьох математичних моделей - Дійкстра, Беллмана-Форда, Флойда-Уоршелла. Вичерпне їх опис наведено далі. Але якщо статичні алгоритми поширюють їх на всю описувану підмережа, то динамічні тільки локально, використовуючи розвинені метрики оптимальності.
Алгоритм заливки є самим надійним і швидким з усіх існуючих алгоритмів. Принцип функціонування полягає в розсилці пакету, що прийшов в усі лінії, окрім тієї, за якою він прийшов. Але його єдиний і головний мінус - неприпустимо велике значення трафіку. Даний алгоритм є оціночним при тестуванні нових розробок і все ще використовується в спеціалізованих мережах (наприклад, військових).
Алгоритм маршрутизації на підставі потоку грунтується на припущенні про те, що трафік усередині мережі можна описати якимось статістіческіму закону, на підставі якого і вибираються оптимальні схеми маршруту. Повний опис дивися в.
Динамічні алгоритми для оцінки оптимальності шляху використовують механізм метрик. Метрикою для дистанційно-векторної маршрутизації є число відрізків мережі (хопов) між отруйником і одержувачем. На підставі даної метрики вибирається оптимальний маршрут, локально використовуючи алгоритм Дійкстра. Даний метод глобально використовувався в комерційних мережах і мережах загального призначення до початку 80х років XX століття. Даний алгоритм має ряд недоліків, головним з яких є проблема рахунки до нескінченності. Практична реалізація алгоритму виконана в. вигляді протоколу RIP. Зараз же даний метод поступився місцем більш досконалим, але його ще підтримує переважний відсоток устаткування, що випускається, операційних систем (MVS, Unix, сімейство MSWindowsServer).
Одним з найбільш досконалих на сьогоднішній момент алгоритмів в маршрутизації є маршрутизація з обліків стану ліній. Метрикою для даного алгоритму є середня величина затримки для тестового пакета, що відображає не тільки довжину маршруту, а й завантаження каналу. Практичною реалізацією даного алгоритму є протокол OSPF.
2.1 Аналіз алгоритму Дейкстри
алгоритми? тм Де? йкстри - алгоритм на графах, винайдений нідерландським ученим Е. Дейкстрой в 1959 році. Знаходить найкоротші шляхи від однієї з вершин графа до всіх інших. Алгоритм працює тільки для графів без ребер негативного ваги. Алгоритм широко застосовується в програмуванні і технологіях, наприклад, його використовують протоколи маршрутизації OSPF і IS-IS.
Кожній вершині з V зіставимо мітку - мінімальне відоме відстань від цієї вершини до a. Алгоритм працює покроково - на кожному кроці він «відвідує» одну вершину і намагається зменшувати мітки. Робота алгоритму завершується, коли всі вершини відвідані.
Ініціалізація. Мітка самої вершини a покладається рівною 0, мітки інших вершин - нескінченності. Це відображає те, що відстані від a до інших вершин поки невідомі. Всі вершини графа позначаються як невідвіданих.
Алгоритм Де? йкстри покроково.
Якщо всі вершини відвідані, алгоритм завершується. В іншому випадку, з ще не відвіданих вершин вибирається вершина u, що має мінімальну мітку. Ми розглядаємо всілякі маршрути, в яких u є передостаннім пунктом. Вершини, в які ведуть ребра з u, назвемо сусідами цієї вершини. Для кожного сусіда вершини u, крім зазначених як відвідані, розглянемо нову довжину шляху, що дорівнює сумі значень поточної мітки u і довжини ребра, що з'єднує u з цим сусідом. Якщо отримане значення довжини менше значення мітки сусіда, замінимо значення мітки отриманим значенням довжини. Розглянувши всіх сусідів, пометим вершину u як відвіданих і повторимо крок алгоритму.
Розглянемо виконання алгоритму на при...
