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

СодержаниеTOC \o "1-1" \h \u HYPERLINK \l _Toc28753 1 Задание на курсовую работу PAGEREF _Toc28753 \h 3 HYPERLINK \l _Toc492 2 Теоретические сведения. PAGEREF _Toc492 \h 5 HYPERLINK \l _Toc2216 2.1 Маршрутизация. PAGEREF _Toc2216 \h 5 HYPERLINK \l _Toc3070 2.1 Алгоритм Дейкстры PAGEREF _Toc3070 \h 6 HYPERLINK \l _Toc7374 3 Маршрутизация на основе алгоритма Дейкстры PAGEREF _Toc7374 \h 8 HYPERLINK \l _Toc13717 4 Выводы PAGEREF _Toc13717 \h 171 Задание на курсовую работу Главными задачами данной курсовой работы являлись:- выполнение расчетов стоимостей канальных участков;- осуществление выбора наилучшего маршрута продвижения пакета в сети в соответствии с одним из предложенных алгоритмов. Исходные данные в соответствии с вариантом представлены в таблице 1.1.Таблица 1.1 - Исходные данные ВариантТрафикАлгоритмТопология123421ВидеоДейкстры1Топология сети в соответствии с вариантом №21 представлена на рисунке 1.1. Рисунок 1.1 – Топология сети Таблица 1.2 содержит параметры канальных участков сети для разных типов трафика, необходимые для дальнейших расчетов. Таблица 1.2 – Параметры канальных участков сети № каналаВидео121152213174185226137883392110171191222131314311516162217342 Теоретические сведения.2.1 Маршрутизация.Маршрутизация - процесс определения маршрута данных в сетях связи. Задачу выбора маршрута из нескольких возможных решают маршрутизаторы, а также конечны узлы. Маршрут выбирается на основании имеющейся у этих устройств информации о текущей конфигурации сети, а также на основании указанного критерия выбора маршрута. Обычно в качестве критерия выступает задержка прохождения маршрута отдельным пакетом или средняя пропускная способность маршрута для последовательности пакетов. Часто также используется весьма простой критерий, учитывающий только количество пройденных в маршруте промежуточных маршрутизаторов (хопов).Чтобы по адресу сети назначения можно было бы выбрать рациональный маршрут дальнейшего следования пакета, каждый конечный узел и маршрутизатор анализируют специальную информационную структуру, которая называется таблицей маршрутизации.Таблица маршрутизации — таблица, состоящая из сетевых маршрутов и предназначенная для определения наилучшего пути передачи сетевого пакета. Каждая запись в таблице маршрутизации состоит, как правило, из следующих полей:- адрес сети или узла назначения, либо указание, что маршрут является маршрутом по умолчанию;- маску сети назначения ;- шлюз, обозначающий адрес маршрутизатора в сети, на который необходимо отправить пакет, следующий до указанного адреса;- интерфейс, через который доступен шлюз (это может быть порядковый номер, GUID или символьное имя устройства);- метрику - числовой показатель, задающий предпочтительность маршрута; чем меньше, тем предпочтительнее маршрут.К наиболее распространенным алгоритмам выбора кратчайшего пути относятся алгоритмы Дейкстры, Беллмана-Форда и Флойда-Уоршелла. Результаты работы данных алгоритмов в равной степени могут использоваться для формирования таблиц маршрутов как для централизованного, так и для распределенного алгоритмов маршрутизации.Эти алгоритмы послужили основой для создания множества современных алгоритмов маршрутизации. В данной работе выбор кратчайших путей основан на использовании алгоритма Дейкстры и целесообразно рассмотреть его реализацию подробно. 2.1 Алгоритм ДейкстрыАлгоритм Дейкстры назван в честь голландского ученого Эдсгера Дейкстры. Алгоритм был предложен для нахождения кратчайших путей от одной вершины до всех остальных в ориентированном взвешенном графе, при условии, что все ребра в графе имеют неотрицательные веса. Алгоритм Дейкстры относится к так называемым «жадным» алгоритмам, т.е. алгоритмам, заключающимся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.Сам алгоритм Дейкстры состоит из n итераций. На очередной итерации выбирается вершина с наименьшей величиной среди ещё не помеченных. Алгоритм выполняется до тех пор, пока все узлы не будут добавлены в множество узлов Т.3 Маршрутизация на основе алгоритма ДейкстрыРассмотрим сеть с топологией, представленной на рисунке 3.1 с указанными стоимостями каналов.Рисунок 3.1 - Текущая топология сети со стоимостями каналовЗадача заключается в том, чтобы определить маршруты с наименьшей стоимостью для всех хостов сети. Поскольку каждый хост подключен к одному роутеру через единственный канал, имеет смысл сначала определить стоимости маршрутов для маршрутизаторов (R1, R2, R3, R5, R6, R8), а затем добавить к ним стоимости каналов к хостам. Таким образом, будем использовать топологию на рисунке 3.2. Рисунок 3.2 – Вспомогательная топология сетиТаблицы 3.1 –3.6 содержат реализацию алгоритма Дейкстры при построении кратчайших путей для маршрутизаторов R1, R2, R3, R5, R6, R8.Таблица 3.1 - Кратчайшие пути для R1ШагТL (R2)ПутьL (R3)ПутьL (R4)ПутьL (R5)ПутьL (R6)ПутьL (R7)ПутьL (R8)Путь1{R1}81-2331-3∞-∞-91-6∞-∞-2{R1}{R2}81-2291-2-3251-2-4∞-91-6∞-∞-3{R1}{R2}{R6}81-2291-2-3251-2-4∞-91-6431-6-7∞-4{R1}{R2}{R6}{R4}81-2291-2-3251-2-4561-2-4-591-6381-2-4-7∞-Продолжение таблицы 3.15{R1}{R2}{R6}{R4}{R3}81-2291-2-3251-2-4561-2-4-591-6381-2-4-7∞-6{R1}{R2}{R6}{R4}{R3}{R7}81-2291-2-3251-2-4561-2-4-591-6381-2-4-7601-2-4-7-87{R1}{R2}{R6}{R4}{R3}{R7}{R5}81-2291-2-3251-2-4561-2-4-591-6381-2-4-7601-2-4-7-88{R1}{R2}{R6}{R4}{R3}{R7}{R5}{R8}81-2291-2-3251-2-4561-2-4-591-6381-2-4-7601-2-4-7-8Кратчайшие пути:От А до В: А-R1-R2-R3-В, стоимость - 65 (29+15+21);От А до С: А-R1-R6-С, стоимость - 41 (9+15+17);От А до D: А-R1-R2-R4-R7-R8-D, стоимость - 93 (60+15+18);От А до E: А-R1-R2-R4-R5-E, стоимость - 93 (56+15+22);От А до F: А-R1-R2-F, стоимость - 36 (8+15+13).Таблица 3.2 - Кратчайшие пути для R2ШагТL (R1)ПутьL (R3)ПутьL (R4)ПутьL (R5)ПутьL (R6)ПутьL (R7)ПутьL (R8)Путь1{R2}82-1212-3172-4∞-∞-∞-∞-2{R2}{R1}82-1212-3172-4∞-172-1-6∞-∞-Продолжение таблицы 3.23{R1}{R1}{R4}82-1212-3172-4482-4-5172-1-6302-4-7∞-4{R1}{R2}{R4}{R6}82-1212-3172-4482-4-5172-1-6302-4-7∞-5{R1}{R2}{R4}{R6}{R3}82-1212-3172-4482-4-5172-1-6302-4-7∞-6{R1}{R2}{R4}{R6}{R3}{R7}82-1212-3172-4482-4-5172-1-6302-4-7522-4-7-87{R1}{R2}{R4}{R6}{R3}{R7}{R5}82-1212-3172-4482-4-5172-1-6302-4-7522-4-7-88{R1}{R2}{R4}{R6}{R3}{R7}{R5}{R8}82-1212-3172-4482-4-5172-1-6302-4-7522-4-7-8Кратчайшие пути:От F до A: F-R2-R1-A, стоимость - 36 (8+13+15)От F до B: F-R2-R3-B, стоимость - 55 (21+13+21);От F до C: F-R2-R1-R6-C, стоимость - 47 (17+13+17).От F до D: F-R2-R4-R7-R8-D, стоимость - 83 (52+13+18);От F до E: F-R2-R4-R5-E, стоимость - 83 (48+13+22).Таблица 3.3 - Кратчайшие пути для R3ШагТL (R1)ПутьL (R2)ПутьL (R4)ПутьL (R5)ПутьL (R6)ПутьL (R7)ПутьL (R8)Путь1{R3}333-1213-2∞-∞-∞-223-7∞-2{R3}{R2}293-2-1213-2383-2-4∞-∞-223-7∞-3{R3}{R2}{R7}293-2-1213-2353-7-4∞-563-7-6223-7443-7-84{R3}{R2}{R7}{R1}293-2-1213-2353-7-4∞-383-2-1-6223-7443-7-85{R3}{R2}{R7}{R1}{R4}293-2-1213-2353-7-4663-7-4-5383-2-1-6223-7443-7-86{R3}{R2}{R7}{R1}{R4}{R6}293-2-1213-2353-7-4663-7-4-5383-2-1-6223-7443-7-87{R3}{R2}{R7}{R1}{R4}{R6}{R8}293-2-1213-2353-7-4603-7-8-5383-2-1-6223-7443-7-88{R3}{R2}{R7}{R1}{R4}{R6}{R8}{R5}293-2-1213-2353-7-4603-7-8-5383-2-1-6223-7443-7-8Кратчайшие пути:От B до A: B-R3-R1-A, стоимость - 65 (29+21+15);От B до C: B-R3-R2-R1-R6-C, стоимость -76 (38+21+17).От B до D: B-R3-R7-R8-D, стоимость - 83 (44+21+18);От B до E: B-R3-R7-R8-R5-E, стоимость - 103 (60+21+22);От B до F: B-R3-R2-F, стоимость - 55 (21+21+13).Таблица 3.4 - Кратчайшие пути для R5ШагТL (R1)ПутьL (R2)ПутьL (R3)ПутьL (R4)ПутьL (R6)ПутьL (R7)ПутьL (R8)Путь1{R5}∞-∞-∞-315-4∞-∞-165-82{R5}{R8}∞-∞-∞-315-4∞-385-8-7165-83{R5}{R8}{R4}∞-485-4-2∞-315-4∞-385-8-7165-84{R5}{R8}{R4}{R7}∞-485-4-2605-8-7-3315-4725-8-7-6385-8-7165-85{R5}{R8}{R4}{R7}{R2}565-4-2-1485-4-2605-8-7-3315-4725-8-7-6385-8-7165-86{R5}{R8}{R4}{R7}{R2}{R1}565-4-2-1485-4-2605-8-7-3315-4655-4-2-1-6385-8-7165-87{R5}{R8}{R4}{R7}{R2}{R1}{R3}565-4-2-1485-4-2605-8-7-3315-4655-4-2-1-6385-8-7165-88{R5}{R8}{R4}{R7}{R2}{R1}{R3}{R6}565-4-2-1485-4-2605-8-7-3315-4655-4-2-1-6385-8-7165-8От E до A: B-R5-R4-R2-R1-A, стоимость - 93 (56+22+15);От E до B: E-R5-R8-R7-R3-B, стоимость - 103 (60+22+21);От E до C: E-R5-R4-R2-R1-R6-C, стоимость -104 (65+22+17).От E до D: E-R5-R8-D, стоимость - 56 (16+22+18);От E до F: E-R5-R4-R2-F, стоимость - 83 (48+22+13).Таблица 3.5 - Кратчайшие пути для R6ШагТL (R1)ПутьL (R2)ПутьL (R3)ПутьL (R4)ПутьL (R5)ПутьL (R7)ПутьL (R8)Путь1{R6}96-1∞-∞-∞-∞-346-7∞-2{R6}{R1}96-1176-1-2426-1-3∞-∞-346-7∞-3{R6}{R1}{R2}96-1176-1-2386-1-2-3346-1-2-4∞-346-7∞-4{R6}{R1}{R2}{R7}96-1176-1-2386-1-2-3346-1-2-4∞-346-7566-7-85{R6}{R1}{R2}{R7}{R4}96-1176-1-2386-1-2-3346-1-2-4656-1-2-4-5346-7566-7-86{R6}{R1}{R2}{R7}{R4}{R3}96-1176-1-2386-1-2-3346-1-2-4656-1-2-4-5346-7566-7-87{R6}{R1}{R2}{R7}{R4}{R3}{R8}96-1176-1-2386-1-2-3346-1-2-4656-1-2-4-5346-7566-7-8Продолжение таблицы 3.58{R6}{R1}{R2}{R7}{R4}{R3}{R8}{R5}96-1176-1-2386-1-2-3346-1-2-4656-1-2-4-5346-7566-7-8Кратчайшие пути:От C до A: C-R6-R1-A, стоимость - 41 (9+17+15);От C до B: C-R6-R1-R2-R3-B, стоимость - 76 (38+17+21);От C до D: C-R6-R7-R8-D, стоимость - 91 (56+17+18);От C до F: C-R6-R1-R2-F, стоимость - 47 (17+17+13);От C до E: C-R6-R1-R2-R4-R5-E, стоимость -104 (65+17+22).Таблица 3.6 - Кратчайшие пути для R8ШагТL (R1)ПутьL (R2)ПутьL (R3)ПутьL (R4)ПутьL (R5)ПутьL (R6)ПутьL (R7)Путь1{R8}∞-∞-∞-∞-168-5∞-228-72{R8}{R5}∞-∞-∞-478-5-4168-5∞-228-73{R8}{R5}{R7}∞-∞-448-7-3358-7-4168-5568-7-6228-74{R8}{R5}{R7}{R4}∞-528-7-4-2448-7-3358-7-4168-5568-7-6228-75{R8}{R5}{R7}{R4}{R3}778-7-3-1528-7-4-2448-7-3358-7-4168-5568-7-6228-7Продолжение таблицы 3.66{R8}{R5}{R7}{R4}{R3}{R2}608-7-4-2-1528-7-4-2448-7-3358-7-4168-5568-7-6228-77{R8}{R5}{R7}{R4}{R3}{R2}{R6}608-7-4-2-1528-7-4-2448-7-3358-7-4168-5568-7-6228-78{R8}{R5}{R7}{R4}{R3}{R2}{R6}{R1}608-7-4-2-1528-7-4-2448-7-3358-7-4168-5568-7-6228-7Кратчайшие пути:От D до A: D-R8-R7-R4-R2-R1-A, стоимость - 93 (60+18+15);От D до B: D-R8-R7-R3-B, стоимость - 83 (44+18+21);От D до C: D-R8-R7-R6-C, стоимость - 91 (56+18+17);От D до F: D-R8-R7-R4-R2-F, стоимость - 83 (52+18+13);От D до E: D-R8-R5-E, стоимость -56 (16+18+22).4 Выводы В результате выполненной курсовой работы была рассмотрена реализации алгоритма Дейкстры для поиска кратчайшего пути при передачи видео трафика. В ходе выполнения курсовой работы было выявлено, что принцип алгоритма Дейкстры следующий: от узла, соединенного с одним из хостов по одному каналу, мы находим канал с наименьшей стоимостью к одному из соседних узлов. На каждом из этапов добавляется новый узел, до этого не входящий в текущее множество Т, до которого существует самый короткий маршрут от исходного узла.