Исследование процессов маршрутизации

Содержание

Введение

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

· Матрица смежности

V1 V2 V3 V4 V5 V6

V1 0 0 5 0 1 5

V2 0 0 0 3 2 4

V3 2 0 0 6 4 0

V4 0 6 2 0 0 0

<

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать