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

1.4.Расчет пути с минимальным количеством переходов

Преобразуем исходный граф в неориентированный невзвешенный граф.

Рисунок.9 Неориентированный, невзвешенный граф

V2

V1 V3

Произведем поиск кратчайшего пути по алгоритму Дейкстры.

Таблица№3

L(2)

Путь

L(3)

Путь

L(4)

Путь

L(5)

Путь

L(6)

Путь

1

-

5

1-3

-

1

1-5

5

1-6

2

6

12

1-5-2

1-6-2

5

6

1-3

1-5-3

11

1-3-4  

1

9

1-5

1-3-5

5

1-6

3

6

12

17

14

1-5-2

1-6-2

1-3-4-2

1-3-5-2

5

6

1-4-3

1-5-3

11

12

14

9

1-4

1-6-2-4

1-6-2-4

1

9

13  

1-5

1-3-5

1-6-2-5  

5

9

1-6

1-5-2-6

4

6

18

1-5-2

1-5-3-4-2

5

6

18

15

10  

1-3

1-5-3

1-6-2-5-3

1-6-2-4-3

1-5-2-4-3

9

17

1-5-2-4

1-3-5-2-4

10

20

1-6-2-5

1-3-4-2-5

1

23

1-6

1-3-5-2-6

1.5 Выводы

В итоге оба алгоритма поиска кратчайшего пути привели нас к одинаковому результату. Но по алгоритму Беллмана-Форда результата мы достигли быстрее.

Достоинством алгоритма Дейсктры является то, что на каждом шаге мы находим кратчайшее расстояние еще до одной вершины, а по алгоритму Беллмана- Форда кратчайшее расстояние до любой вершины определяется только после прохождения всего алгоритма.

Расчет пути с минимальным количеством переходов привел к другим результатам, так как исходный граф был преобразован в неориентированный невзвешанный граф.

2. Маршрутизация

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

2.1 Основы маршрутизации

Алгоритмы маршрутизации можно дифференцировать, основываясь на нескольких ключевых характеристиках. Во-первых, на работу результирующего протокола маршрутизации влияют конкретные задачи, которые решает разработчик алгоритма. Во-вторых, существуют различные типы алгоритмов маршрутизации, и каждый из них по-разному влияет на сеть и ресурсы маршрутизации. И наконец, алгоритмы маршрутизации используют разнообразные показатели, которые влияют на расчет оптимальных маршрутов.

Алгоритмы маршрутизации включают процедуры:

- измерение и оценивание параметров сети;

- принятие решения о рассылке служебной информации;

- расчет таблиц маршрутизации (ТМ);

- реализация принятых маршрутных решений.

В зависимости от того, используется ли при выборе направления информация о состоянии только данного узла или всей сети, различают алгоритмы изолированные и глобальные. Если ТМ реагирует на изменения состояния сети, то алгоритм адаптивный (динамический), иначе фиксированный (статический), а при редких корректировках - квазистатический. В статических маршрутизаторах изменения в ТМ вносит администратор сети.

Простейший алгоритм - изолированный, статический. Алгоритм кратчайшей очереди в отличие от простейшего является адаптивным, пакет посылается по направлению, в котором наименьшая очередь в данном узле. Лавинный алгоритм - многопутевой, основан на рассылке копий пакета по всем направлениям, пакеты сбрасываются, если в данном узле другая копия уже проходила. Очевидно, что лавинный алгоритм обеспечивает надежную доставку, но порождает значительный трафик и потому используется только для отдельных пакетов большой ценности.

Наиболее широко используемые адаптивные протоколы (методы) маршрутизации - RIP (Routing Information Protocol) и OSPF (Open Shortest Path First). Метод RIP иначе называется методом рельефов. Он основан на алгоритме Беллмана-Форда и используется преимущественно на нижних уровнях иерархии сети. В сетях, работающих в соответствии с методом OSPF, информация о любом изменении в сети рассылается лавинообразно.

Страница:  1  2  3  4  5  6  7  8  9  10 


Другие рефераты на тему «Программирование, компьютеры и кибернетика»:

Поиск рефератов

Последние рефераты раздела

Copyright © 2010-2024 - www.refsru.com - рефераты, курсовые и дипломные работы