Практическая работа №9 СТвИСиС
.docxМинистерство цифрового развития, связи и массовых коммуникаций
Российской Федерации
Ордена Трудового Красного Знамени
федеральное государственное бюджетное образовательное учреждение
высшего образования
Московский технический университет связи и информатики
Кафедра «Сетевые Информационные Технологии и Сервисы»
«Утверждаю»
Зав.кафедрой
__________________________
__________________________
Отчёт о практической работе №9
«Поиск кратчайшего маршрута с помощью алгоритма Дейкстры»
Выполнил:
Проверил: Гадасин Д.В. Вариант №00
Москва ****
Содержание
Задание…………………………………………………………………………….3
Введение…………………………………………………………………………...6
Основная часть…………………………………………………………………….7
Заключение……………………………………………………………….............16
Список использованных источников…………………………………………...17
Задание
Задание №9. Поиск кратчайшего маршрута с помощью алгоритма Дейкстры.
В соответствии с вариантом (табл. 8) необходимо найти маршрут самого быстрого прохождения пакета от маршрутизатора с номером 1 до маршрутизатора с номером 25 (рис. 1), применяя алгоритм Дейкстры.
При прохождении через сеть Интернет пакеты обрабатываются на интерфейсах маршрутизаторов со скоростью 170 пакетов/с.
Пакеты всегда идут от маршрутизатора с меньшим номером к маршрутизатору с большим номером. Например, с маршрутизатора 9 пакеты могут быть переданы на маршрутизаторы 12, 13, 18, 21, 24 и не могут быть переданы на маршрутизатор 2.
Если маршрутизатор имеет прямое подключение к сети Интернет, то он может как посылать пакеты в сеть Интернет, так и получать их из сети Интернет
Таблица №8 – Варианты Задания №9
Скорость обработки пакетов Пакет/с |
Маршрутизатор № |
Скорость обработки пакетов (Пакет/с) |
1 |
23950 |
|
2 |
28200 |
|
3 |
26200 |
|
4 |
27700 |
|
5 |
26700 |
|
6 |
27200 |
|
7 |
24450 |
|
8 |
25200 |
|
9 |
28700 |
|
10 |
23200 |
|
11 |
22950 |
|
12 |
25700 |
|
13 |
23700 |
|
14 |
22700 |
|
15 |
28450 |
|
16 |
26450 |
|
17 |
25450 |
|
18 |
25950 |
|
19 |
27450 |
|
20 |
24700 |
|
21 |
23450 |
|
22 |
26950 |
|
23 |
24200 |
|
24 |
24950 |
|
25 |
27950 |
Рисунок 1 - Схема сети
Введение
Маршрутизация (Routing) — это процесс по определению/вычислению лучшего маршрута движения для данных в сетях связи. Есть еще второе определение — это передача пакетов данных от отправителя к получателю.
Сами маршруты могут быть статическими — задаются административно, или динамическими, т.е. рассчитываться по специальным алгоритмам-протоколам, которые базируются на данных о топологии и состоянии сети. [1]
Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS. [2]
Основная часть
Вариант №19
По условию задания нам дана скорость обработки пакетов от каждого узла, чтобы найти вес ребер зададимся некоторым количеством пакетов, которые передаются по сети, и поделим это число на скорость. Например, от узла 1 к узлу 25 передаются данные размером 100 000 пакетов. Тогда найдем вес ребер (время обработки) от каждого маршрутизатора:
Таблица №1 - Варианты Задания №9
Для вариант №19
Маршрутизатор № |
Скорость обработки пакетов (u), (Пакет/с) |
Обработка, с (100000/u) |
1 |
23950 |
4,17 |
2 |
28200 |
3,54 |
3 |
26200 |
3,81 |
4 |
27700 |
3,61 |
5 |
26700 |
3,74 |
6 |
27200 |
3,67 |
7 |
24450 |
4,08 |
8 |
25200 |
3,96 |
9 |
28700 |
3,48 |
10 |
23200 |
4,31 |
11 |
22950 |
4,35 |
12 |
25700 |
3,89 |
13 |
23700 |
4,21 |
14 |
22700 |
4,40 |
15 |
28450 |
3,51 |
16 |
26450 |
3,78 |
17 |
25450 |
3,92 |
18 |
25950 |
3,85 |
19 |
27450 |
3,64 |
20 |
24700 |
4,04 |
21 |
23450 |
4,26 |
22 |
26950 |
3,71 |
23 |
24200 |
4,13 |
24 |
24950 |
4,01 |
25 |
27950 |
3,57 |
Internet |
170 |
588,23 |
Для поиска кратчайшего маршрута будем использовать алгоритм Дейкстры. Будем использовать табличное представление. Идея алгоритма: сначала выберем путь до начальной вершины равным нулю и заносим эту вершину во множество уже выбранных, расстояние от которых до оставшихся невыбранных вершин определено. На каждом следующем этапе находим следующую выбранную вершину, расстояние до которой наименьшее, и соединенную ребром с какой-нибудь вершиной из множества невыбранных (это расстояние будет равно расстоянию до выбранной вершины плюс длина ребра).
Рисунок 2 – Граф с обозначением всех вершин и путей
Теперь воспользуемся алгоритмом Дейкстры для нахождения кратчайшего маршрута от вершины 1 до вершины 25.
Квадратные скобки - от какой вершины представленное значение, выделение - та вершина, которая в дальнейшем будет рассмотрена на одном из шагов.
Шаг 1 (определение начальных значений):
Вершина 1 = 0
Вершина 2 – 25 = бесконечность
Шаг 2 (пути от вершины 1 = 0):
Вершина 2 = Вершина 1 + 4,17 = 0 + 4,17 = 4,17 [1]
Вершина 3 = Вершина 1 + 4,17 = 0 + 4,17 = 4,17 [1]
Вершина 4 = Вершина 1 + 4,17 = 0 + 4,17 = 4,17 [1]
Вершина 6 = Вершина 1 + 4,17 = 0 + 4,17 = 4,17 [1]
Вершина 8 = Вершина 1 + 4,17 = 0 + 4,17 = 4,17 [1]
Шаг 3 (пути от вершины 2 = 4,17 [1])
Вершина 3 = Вершина 2 + 3,54 = 4,17 + 3,54 = 7,71 > 4,17 = > 4,17 [1]
Вершина 4 = Вершина 2 + 3,54 = 4,17 + 3,54 = 7,71 > 4,17 = > 4,17 [1]
Вершина 6 = Вершина 2 + 3,54 = 4,17 + 3,54 = 7,71 > 4,17 = > 4,17 [1]
Вершина 8 = Вершина 2 + 3,54 = 4,17 + 3,54 = 7,71 > 4,17 = > 4,17 [1]
Вершина 9 = Вершина 2 + 3,54 = 4,17 + 3,54 = 7,71 [2]
Вершина 13 = Вершина 2 + 3,54 = 4,17 + 3,54 = 7,71 [2]
Вершина 24 = Вершина 2 + 3,54 = 4,17 + 3,54 = 7,71 [2]
Шаг 4 (пути от вершины 3 = 4,17 [1])
Вершина 4 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 > 4,17 = > 4,17 [1]
Вершина 5 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 [3]
Вершина 6 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 > 4,17 = > 4,17 [1]
Вершина 7 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 [3]
Вершина 8 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 > 4,17 = > 4,17 [1]
Вершина 11 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 [3]
Вершина 14 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 [3]
Вершина 15 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 [3]
Вершина 16 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 [3]
Вершина 17 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 [3]
Вершина 22 = Вершина 3 + 3,81= 4,17 + 3,81= 7,98 [3]
Шаг 5 (пути от вершины 4 = 4,17 [1])
Вершина 5 = Вершина 4 + 3,61= 4,17 + 3,61= 7,78 < 7,89 = >7,78 [4]
Вершина 6 = Вершина 4 + 3,61= 4,17 + 3,61= 7,78 > 4,17 = > 4,17 [1]
Вершина 7 = Вершина 4 + 3,61= 4,17 + 3,61= 7,78 < 7,89 = >7,78 [4]
Вершина 8 = Вершина 4 + 3,61= 4,17 + 3,61= 7,78 > 4,17 = > 4,17 [1]
Вершина 11 = Вершина 4 + 3,61= 4,17 + 3,61= 7,78 < 7,89 = >7,78 [4]
Вершина 16 = Вершина 4 + 3,61= 4,17 + 3,61= 7,78 < 7,89 = >7,78 [4]
Вершина 17 = Вершина 4 + 3,61= 4,17 + 3,61= 7,78 < 7,89 = >7,78 [4]
Вершина 22 = Вершина 4 + 3,61= 4,17 + 3,61= 7,78 < 7,89 = >7,78 [4]
Шаг 6 (пути от вершины 6 = 4,17 [1])
Вершина 8 = Вершина 6 + 3,67= 4,17 + 3,67= 7,84 > 4,17 = > 4,17 [1]
Вершина 14 = Вершина 6 + 3,67= 4,17 + 3,67= 7,84 [6]
Вершина 15 = Вершина 6 + 3,67= 4,17 + 3,67= 7,84 [6]
Шаг 7 (пути от вершины 8 = 4,17 [1])
Вершина 12 = Вершина 6 + 3,67= 4,17 + 3,96= 8,13 [8]
Вершина 14 = Вершина 6 + 3,67= 4,17 + 3,96= 8,13 > 7,84 =>7,84 [6]
Вершина 19 = Вершина 6 + 3,67= 4,17 + 3,96= 8,13 [8]
Вершина 21 = Вершина 6 + 3,67= 4,17 + 3,96= 8,13 [8]
Вершина 23 = Вершина 6 + 3,67= 4,17 + 3,96= 8,13 [8]
На данном шаге значения путей получились больше, чем есть в предыдущих шагах. Поэтому следующий шаг будет исходить из вершины, значение которой получено на шаге 3 – вершина 9.
Шаг 8 (пути от вершины 9 = 7,71 [2])
Вершина 12 = Вершина 9 + 3,48= 7,71 + 3,48 = 11,19 > 8,13 => 8,13 [8]
Вершина 13 = Вершина 9 + 3,48= 7,71 + 3,48 = 11,19 >7,71 => 7,71 [2]
Вершина 18 = Вершина 9 + 3,48= 7,71 + 3,48 = 11,19 [9]
Вершина 21 = Вершина 9 + 3,48= 7,71 + 3,48 = 11,19 > 8,13 => 8,13 [8]
Вершина 24 = Вершина 9 + 3,48= 7,71 + 3,48 = 11,19 >7,71 => 7,71 [2]
Шаг 9 (пути от вершины 13 = 7,71 [2])
Вершина 24 = Вершина 13 + 4,21= 7,71 + 4,21= 11,92 > 7,71 => 7,71 [2]
Шаг 10 (пути от вершины 24 = 7,71 [2])
Internet = Вершина 24 + 588.2 = 11,92 + 588.2 = 600.15 [24]
На данном шаге значения путей получились больше, чем есть в предыдущих шагах. Поэтому следующий шаг будет исходить из вершины, значение которой получено на шаге 5 – вершина 5.
Шаг 11 (пути от вершины 5 = 7,78 [4])
Вершина 7 = Вершина 5 + 3,74= 7,78 + 3,74 = 11,52 > 7,78 =>7,78 [4]
Вершина 11 = Вершина 5 + 3,74= 7,78 + 3,74 = 11,52 > 7,78 =>7,78 [4]
Вершина 14 = Вершина 5 + 3,74= 7,78 + 3,74 = 11,52 >7,84 =>7,84 [6]
Вершина 15 = Вершина 5 + 3,74= 7,78 + 3,74 = 11,52 > 7,84 =>7,84 [6]
Вершина 16 = Вершина 5 + 3,74= 7,78 + 3,74 = 11,52 > 7,78 =>7,78 [4]
Вершина 17 = Вершина 5 + 3,74= 7,78 + 3,74 = 11,52 > 7,78 =>7,78 [4]
Вершина 22 = Вершина 5 + 3,74= 7,78 + 3,74 = 11,52 > 7,78 =>7,78 [4]
Шаг 12 (пути от вершины 7 = 7,78 [4])
Вершина 10 = Вершина 7 + 4,08= 7,78 + 4,08= 11,86 [7]
Вершина 11 = Вершина 7 + 4,08= 7,78 + 4,08= 11,86 > 7,78 =>7,78 [4]
Вершина 15 = Вершина 7 + 4,08= 7,78 + 4,08= 11,86 > 7,84 =>7,84 [6]
Вершина 16 = Вершина 7 + 4,08= 7,78 + 4,08= 11,86> 7,78 =>7,78 [4]
Вершина 17 = Вершина 7 + 4,08= 7,78 + 4,08= 11,86> 7,78 =>7,78 [4]
Вершина 20 = Вершина 7 + 4,08= 7,78 + 4,08= 11,86 [7]
Вершина 22 = Вершина 7 + 4,08= 7,78 + 4,08= 11,86 > 7,78 =>7,78 [4]
Шаг 13 (пути от вершины 11 = 7,78 [4])
Вершина 16 = Вершина 11 + 4,35= 7,78 + 4,35= 12,13 > 7,78 =>7,78 [4]
Вершина 17 = Вершина 11 + 4,35= 7,78 + 4,35= 12,13 > 7,78 =>7,78 [4]
Вершина 22 = Вершина 11 + 4,35= 7,78 + 4,35= 12,13 > 7,78 =>7,78 [4]
Шаг 14 (пути от вершины 16 = 7,78 [4])
Вершина 17 = Вершина 16 + 3,78= 7,78 +3,78=11,56 > 7,78 =>7,78 [4]
Вершина 20 = Вершина 16 + 3,78= 7,78 +3,78=11,56 <11,86 => 11,56 [16]
Вершина 22 = Вершина 16 + 3,78= 7,78 +3,78=11,56 > 7,78 =>7,78 [4]
Вершина 25= Вершина 16 + 3,78= 7,78 +3,78=11,56 [16]
На данном шаге был получен маршрут от 1 до 25 с временем прохождения 11,56 c. Для того, чтобы удостовериться, что нет других более коротких маршрутов продолжим выполнять алгоритм для оставшихся вершин.
Шаг 15 (пути от вершины 17 =7,78 [4])
Вершина 20 = Вершина 17 + 3,92= 7,78 +3,92=11,7 > 11,56 => 11,56 [16]
Вершина 22 = Вершина 17 + 3,92= 7,78 +3,92=11,7 > 7,78 =>7,78 [4]
Вершина 25 = Вершина 17 + 3,92= 7,78 +3,92=11,7 > 11,56 => 11,56 [16]
На данном шаге был получен маршрут от 1 до 25 с временем прохождения 11,7 c. Для того, чтобы удостовериться, что нет других более коротких маршрутов продолжим выполнять алгоритм для оставшихся вершин.
Шаг 16 (пути от вершины 22 =7,78 [4])
Вершина 25 = Вершина 22 + 3,71= 7,78 +3,71=11,49 < 11,56 => 11,49 [22]
На данном шаге был получен маршрут от 1 до 25 с временем прохождения 11,49 c. Для того, чтобы удостовериться, что нет других более коротких маршрутов продолжим выполнять алгоритм для оставшихся вершин.
Шаг 17 (пути от вершины 14 =7,98 [3])
Вершина 15 = Вершина 14 + 4,40 = 7,98+4,40=12,38 > 7,84 =>7,84 [6]
Вершина 21 = Вершина 14 + 4,40 = 7,98+4,40=12,38 > 8,13 =>8,13 [8]
Вершина 23 = Вершина 14 + 4,40 = 7,98 + 4,40 =12,38 > 8,13 =>8,13 [8]
Вершина 19 = Вершина 14 + 4,40 = 7,98 + 4,40 =12,38 > 8,13 =>8,13 [8]
Вершина 25 = Вершина 14 + 4,40 = 7,98 + 4,40 =12,38 >11,49 =>11,49 [22]
Вершина 20 = Вершина 14 + 4,40 = 7,98 + 4,40 =12,38 >11,56 =>11,56 [16]
Вершина 16 = Вершина 14 + 4,40 = 7,98 + 4,40 =12,38 > 7,78 =>7,78 [4]
Вершина 17 = Вершина 14 + 4,40 = 7,98 + 4,40 =12,38 > 7,78 =>7,78 [4]
Вершина 22 = Вершина 14 + 4,40 = 7,98 + 4,40 =12,38 > 7,78 =>7,78 [4]
На данном шаге была рассмотрена последняя вершина, от которой идут пути к вершине, не рассмотренной ранее. Это означает то, что дальнейшее рассмотрение не будет иметь смысла, т.к. значения заведомо будет получаться больше, чем они есть на данный момент. Также не имеет смысла рассматривать пути от вершины «Internet», поскольку полученный вес пути будет значительно больше, по сравнению с другими вершинами. Таким образом получили следующий маршрут от «1» до «25»: 1-4-22-25 = 11,49 с.
Графический путь изображён на рисунке 3. Вершины 5, 10, 11, 13, 18 и 19 были убраны, исходя из рисунка 1. Маршрутизатор 5 – проходной, у него нет индивидуальных путей, всё, что проходит через него проходит через маршрутизатор 3. Остальные вершины были убраны, так как имеют только один вход, и приходится возвращаться. Также, вершины 23 и 24 имеют доступ только в Интернет, использовать их нерационально, так как скорость гораздо ниже.
Рисунок 3 - Кратчайший путь от 1 до 25
Заключение
В результате выполнения данной работы были получены теоретические и практические навыки работы с алгоритмом Дейкстры, применяемым в протоколе динамической маршрутизации OSPF и IS-IS.