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

Содержание

 

 Введение           3

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

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

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

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

1.4. Сравнение алгоритмов       10

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

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

2.2. Характеристики протокола RIP      12

2.3. Построение таблиц маршрутизации     14

2.4. Адаптация к изменению состояния  сети    17

2.4.1. Проблема адаптации RIP     17

2.4.2. Отключение тупиковой сети     22

2.4.3. Отключение канала      25

2.4.4. Отключение  маршрутизатора     29

Заключение          33

Список  литературы         34

 

Введение.

 

Процессы маршрутизации являются основополагающими в работе любой сети. Так как обмен информацией должен проходить по каким-то, строго заданным, алгоритмам. По этому изучение данной темы является очень важным. Для изучения процессов маршрутизации дана сеть из 6 узлов, которые определенным образом связаны между собой сетями (по матрице смежности). Требуется объяснить по шагам процесс выбора маршрута с минимальной стоимостью с помощью алгоритмов Дейкстры  и Беллмана-Форда и изучить процесс создания маршрутных таблиц в данной сети.  А так же рассмотреть процесс их изменения при различных изменениях сети (отключение тупиковой сети, канала, маршрутизатора). 
Задание:

 

Вариант№ 757

 

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

 

V1 V2 V3 V4 V5 V6

V1   0    6    0    3    1    1

V2   6    0    0    8    1    0

V3   0    0    0    6    0    3

V4   1    8    6    0    3    0

V5   5    8    0    5    0    5

V6   7    0    8    0    6    0

    

 

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

 

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

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

    Пусть  имеется сеть, состоящая из узлов, соединенных двунаправленными линиями  связи, и каждой линии поставлена  в соответствие стоимость пересылки  данных в каждом направлении.

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

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

 

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

 

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

Для моего задания алгоритм будет выглядеть следующим образом:

В первый момент времени во множестве вершин, уже обработанных алгоритмом находится только вершина V1. Соответственно от нее можно достичь вершин V4,V2,V5 и V6. На втором шаге добавляется вершина V2, однако это не влияет на стоимости путей от вершины V1. При добавлении во множество обработанных вершин вершины V4 появляется путь до вершины V3, через V4. При добавлении вершины V3, ничего в таблице не изменяется. Но когда во множество Т добавляется вершина V5, то алгоритм находит более короткий путь от V1 до V6. Это путь 1-5-6. Таким образом, на этом шаге происходит изменение связующего дерева, которое приобретает окончательный вид (при добавлении V6 изменений не происходит).

 

h	T	L(2)	Путь	L(3)	Путь	L(4)	Путь	L(5)	Путь	L(5)	Путь
1	{1}	6	1-2	∞	-	3	1-4	1	1-5	1	1-6
2	{1,2}	6	1-2	∞	-	3	1-4	1	1-5	1	1-6
3	{1,2,4}	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
4	{1,2,3,4}	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
5	{1,2,3,4,5}	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
6	{1,2,3,4,5,6}	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6

 

T= {1}

 

T= {1,2}

 

T= {1,2,4}

T= {1,2,3,4}

 

T= {1,2,3,4,5}

 

T= {1,2,3,4,5,6}

 

 

     Алгоритм завершает работу, когда все вершины добавлены к множеству Т. Таким образом, для работы алгоритма требуется 6 итераций. К моменту окончания работы алгоритма значение L(x), поставленное в соответствие каждой вершине Х представляет собой минимальную стоимость (длину) пути от вершины V1 до вершины Х. Кроме того, дерево представляет собой связующее дерево исходного ориентированного графа, определяющее пути с минимальной стоимостью от вершины S до всех остальных вершин.

 

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

 

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

Этот алгоритм также работает поэтапно: на каждом шаге алгоритм находит путь с минимальной стоимостью, максимальное число ретрансляционных участков в котором равно h. То есть на первом шаге, когда h=0 можно сказать только о существовании узла V1, так как количество переходов равно 0. При h=1, алгоритм находит кратчайшие пути до всех узлов в пределах одного перехода. То есть до узлов V4,V2,V5,V6. При h=2 , алгоритм находит кратчайшие пути до всех узлов в пределах двух переходов. На данном этапе “открывается” узел V3,  и изменяется путь к узлу V6 (с учетом стоимости путей). При дальнейшем увеличении количества переходов, полученные значения не изменяются.

 

h	L(2)	Путь	L(3)	Путь	L(4)	Путь	L(5)	Путь	L(6)	Путь
0	∞	-	∞	-	∞	-	∞	-	∞	-
1	6	1-2	∞	-	3	1-4	1	1-5	1	1-6
2	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
3	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
4	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6

 

h=1

 

 

h=2

 

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

 

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

 

Для выполнения данного расчета следует преобразовать граф в неориентированный и не взвешенный. То есть стоимость каждого ребра приравнивается 1.

Произведем расчет полученного графа с помощью алгоритма Беллмана-Форда.

h	L(2)	Путь	L(3)	Путь	L(4)	Путь	L(5)	Путь	L(6)	Путь
0	∞	-	∞	-	∞	-	∞	-	∞	-
1	1	1-2	∞	-	1	1-4	1	1-5	1	1-6
2	1	1-2	2	1-4-3	1	1-4	1	1-5	1	1-6
3	1	1-2	2	1-4-3	1	1-4	1	1-5	1	1-6
4	1	1-2	2	1-4-3	1	1-4	1	1-5	1	1-6

 

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

 

 

 

1.4 Сравнение  алгоритмов 

 

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

Результаты расчета невзвешенного и взвешенного графов различны. Это объясняется тем, что при расчете взвешенного графа большое значение имеет вес перехода(сеть может быть кратчайшим путем, но очень загружена). Поэтому алгоритм находит путь с наименьшим весом. Тогда, как при расчете невзвешенного графа вес любого ребра равен 1. Следовательно, путь с наименьшим количеством переходов будет кратчайшим.

 

 

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

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

В общественном значении слово маршутизация означает передвижение информации от источника к пункту назначения через объединенную сеть. Маршрутизация отличается от объединения сетей с помощью моста, тем, что объединение с помощью моста имеет место на уровне 2 эталонной модели ISO, в то время как маршрутизация встречается на уровне 3. Эта разница объясняется тем, что маршрутизация и объединение по мостовой схеме используют различную информацию в процессе ее перемещения от источника к месту назначения и выполняют свои задачи разными способами.  Маршрутизация включает в себя два основных компонента: определение оптимальных трактов маршрутизации и транспортировка информационных групп через объединенную сеть (коммутация). Для облегчения процесса определения маршрута алгоритмы маршрутизации инициализируют и поддерживают таблицы маршрутизации, в которых содержится маршрутная информация. Маршрутная информация изменяется в зависимости от используемого алгоритма маршрутизации. Алгоритм маршрутизации заполняют маршрутные таблицы неким множеством информации. “Показатели” обеспечивают информацию о желательности какого-либо канала или тракта.

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