Читать курсовая по Отсутствует: "Исследование процессов маршрутизации" Страница 1

(Назад) (Cкачать работу)

Федеральное агентство железнодорожного транспорта

Уральский государственный университет путей сообщения

Кафедра Автоматики, телемеханики и связи на ж. д. транспорте Курсовой проект

по дисциплине: "Передача дискретной информации"

на тему: "Исследование процессов маршрутизации" Екатеринбург Содержание

1. Алгоритм поиска кратчайшего пути

. Исходные данные

. Алгоритм Дейкстры

. Алгоритм Белмана-Форда

. Компоненты маршрутизации

. Алгоритмы маршрутизации

. Протоколы обмена маршрутной информацией

. Протокол RIP

Список использованной литературы . Алгоритмы поиска кратчайшего пути Компьютерные сети, как правило, представляются в виде графов, при этом коммутаторы и маршрутизаторы сетей являются узлами графа, а линии связи представляют собой ребра графа. Ряд понятий из теории графов оказываются полезными при разработке сетей и алгоритмов маршрутизации.

Граф состоит из объектов двух типов: вершин (vertices) или узлов (nodes) и ребер (edges) или связей (links), при этом каждое ребро графа определяется как неупорядоченная пара вершин. При изображении графов вершины представляются точками или кружками, а ребра - линиями, соединяющими вершины. Величина графа характеризуется количеством вершин |V|, называемым порядком (order) графа, а число ребер называется размером (size) графа. Граф также часто представляется в виде матрицы смежности (adjacency matrix). Вершины нумеруются произвольным образом от 1 до |V|.

Два ребра, инцидентные одной и той же паре вершин, называются параллельными (parallel). Ребро, инцидентное всего одной вершине, называется петлей (loop). Граф, в котором отсутствуют петли и параллельные ребра, называется простым графом (simple graph).

Ориентированный граф (digraph) состоит из множества вершин V и множества ребер, при этом каждое ребро определяется как упорядоченная пара вершин. Вершины ориентированных графов также обозначаются точками или кружками, а ребра - стрелками, соединяющими вершины. Как правило, в ориентированных графах допускается наличие параллельных ребер при условии, что параллельные ребра ориентированы в противоположном направлении. Такие ориентированные графы хорошо подходят для представления компьютерных сетей, в которых каждое ребро обозначает поток данных в одном направлении между узлами сети.

Сеть с коммутацией пакетов (или сеть ретрансляции кадров, или сеть ATM) но рассматривать как ориентированный граф, в котором каждая вершина соответствует узлу коммутации пакетов, а линии связи между узлами соответствует пара параллельных ребер, по каждому из которых данные передаются в одном направлении. В такой сети для передачи пакета от узла-источника узлу-получателя по разным линиям через несколько коммутаторов пакетов требуется принять решение о выборе маршрута. Эта задача эквивалентна поиску пути в графе. Если два маршрутизатора напрямую соединены к одной и той же локальной или глобальной сети, тогда это двусторонне соединение соответствует паре параллельных ребер, соединяющих соответствующие вершины. Если к сети напрямую присоединены более двух маршрутизаторов, тогда эта сеть представляется в виде множества пар параллельных ребер, каждая из которых соединяет два маршрутизатора. В объединенной сети для передачи IP-дейтаграммы от маршрутизатора-источника к

Похожие работы