Федеральне агентство залізничного транспорту
Уральський державний університет шляхів сполучення
Кафедра Автоматики, телемеханіки та зв'язку на ж. д. транспорті
Курсовий проект
з дисципліни: "Передача дискретної інформації"
на тему: "Дослідження процесів маршрутизації"
Єкатеринбург
Зміст
1. Алгоритм пошуку найкоротшого шляху
. Вихідні дані
. Алгоритм Дейкстри
. Алгоритм Белмана-Форда
. Компоненти маршрутизації
. Алгоритми маршрутизації
. Протоколи обміну маршрутною інформацією
. Протокол RIP
Список використаної літератури
. Алгоритми пошуку найкоротшого шляху
Комп'ютерні мережі, як правило, подаються у вигляді графів, при цьому комутатори і маршрутизатори мереж є вузлами графа, а лінії зв'язку являють собою ребра графа. Ряд понять з теорії графів виявляються корисними при розробці мереж і алгоритмів маршрутизації. p align="justify"> Граф складається з об'єктів двох типів: вершин (vertices) або вузлів (nodes) і ребер (edges) або зв'язків (links), при цьому кожне ребро графа визначається як невпорядкована пара вершин. При зображенні графів вершини представляються точками або гуртками, а ребра - лініями, що з'єднують вершини. Величина графа характеризується кількістю вершин | V |, званим порядком (order) графа, а число ребер називається розміром (size) графа. Граф також часто представляється у вигляді матриці суміжності (adjacency matrix). Вершини нумеруються довільним чином від 1 до | V |. p align="justify"> Два ребра, інцідентние однієї і тієї ж парі вершин, називаються паралельними (parallel). Ребро, інцідентное всього однієї вершині, називається петлею (loop). Граф, у якому відсутні петлі і паралельні ребра, називається простим графом (simple graph). p align="justify"> Орієнтований граф (digraph) складається з безлічі вершин V і безлічі ребер, при цьому кожне ребро визначається як впорядкована пара вершин. Вершини орієнтованих графів також позначаються крапками або гуртками, а ребра - стрілками, що з'єднують вершини. Як правило, в орієнтованих графах допускається наявність паралельних ребер за умови, що паралельні ребра орієнтовані в протилежному напрямку. Такі орієнтовані графи добре підходять для представлення комп'ютерних мереж, в яких кожне ребро позначає потік даних в одному напрямку між вузлами мережі. p align="justify"> Мережа з комутацією пакетів (або мережа ретрансляції кадрів, або мережа ATM) але розглядати як орієнтований граф, в якому кожна вершина відповідає вузлу комутації пакетів, а лінії зв'язку між вузлами відп...
