Понятие маршрутизации

ОглавлениеTOC \o "1-1" \h \u HYPERLINK \l _Toc29857 1 Задание на курсовую работу PAGEREF _Toc29857 \h 3 HYPERLINK \l _Toc1070 2 Теоретические сведения PAGEREF _Toc1070 \h 5 HYPERLINK \l _Toc20634 2.1 Понятие маршрутизации PAGEREF _Toc20634 \h 5 HYPERLINK \l _Toc4880 2.2 Алгоритм Флойда-Уоршелла. PAGEREF _Toc4880 \h 6 HYPERLINK \l _Toc18861 3 Маршрутизация на основе алгоритма Флойда-Уоршелла PAGEREF _Toc18861 \h 7 HYPERLINK \l _Toc3148 4 Выводы PAGEREF _Toc3148 \h 161 Задание на курсовую работу Главными задачами данной курсовой работы являлись:- выполнение расчетов стоимостей канальных участков;- осуществление выбора наилучшего маршрута продвижения пакета в сети в соответствии с одним из предложенных алгоритмов. Исходные данные в соответствии с вариантом представлены в таблице 1.1.Таблица 1.1 - Исходные данные ВариантТрафикАлгоритмТопология123443РечьФлойда-Уоршелла2Топология сети в соответствии с вариантом №43 представлена на рисунке 1.1. Рисунок 1.1 – Топология сети Таблица 1.2 содержит параметры канальных участков сети для разных типов трафика, необходимые для дальнейших расчетов. Таблица 1.2 – Параметры канальных участков сети № каналаРечь1215210312475568716859810211119121013171423151216917122 Теоретические сведения2.1 Понятие маршрутизацииМаршрутизация - процесс определения маршрута данных в сетях связи. Задачу выбора маршрута из нескольких возможных решают маршрутизаторы, а также конечны узлы. Маршрут выбирается на основании имеющейся у этих устройств информации о текущей конфигурации сети, а также на основании указанного критерия выбора маршрута. Обычно в качестве критерия выступает задержка прохождения маршрута отдельным пакетом или средняя пропускная способность маршрута для последовательности пакетов. Часто также используется весьма простой критерий, учитывающий только количество пройденных в маршруте промежуточных маршрутизаторов (хопов).Чтобы по адресу сети назначения можно было бы выбрать рациональный маршрут дальнейшего следования пакета, каждый конечный узел и маршрутизатор анализируют специальную информационную структуру, которая называется таблицей маршрутизации.Таблица маршрутизации — таблица, состоящая из сетевых маршрутов и предназначенная для определения наилучшего пути передачи сетевого пакета. Каждая запись в таблице маршрутизации состоит, как правило, из следующих полей:- адрес сети или узла назначения, либо указание, что маршрут является маршрутом по умолчанию;- маску сети назначения ;- шлюз, обозначающий адрес маршрутизатора в сети, на который необходимо отправить пакет, следующий до указанного адреса;- интерфейс, через который доступен шлюз (это может быть порядковый номер, GUID или символьное имя устройства);- метрику - числовой показатель, задающий предпочтительность маршрута; чем меньше, тем предпочтительнее маршрут.К наиболее распространенным алгоритмам выбора кратчайшего пути относятся алгоритмы Дейкстры, Беллмана-Форда и Флойда-Уоршелла. Результаты работы данных алгоритмов в равной степени могут использоваться для формирования таблиц маршрутов как для централизованного, так и для распределенного алгоритмов маршрутизации.Эти алгоритмы послужили основой для создания множества современных алгоритмов маршрутизации. В данной работе выбор кратчайших путей основан на использовании алгоритма Флойда-Уоршелла и целесообразно рассмотреть его реализацию подробно. 2.2 Алгоритм Флойда-Уоршелла.Алгоритм Флойда - Уоршелла - динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Сущность алгоритма состоит в построении весовой матрицы, на основе которой производится добавление промежуточных узлов и дальнейшее определение кратчайших маршрутов от узла к узлу.. 3 Маршрутизация на основе алгоритма Флойда-УоршеллаРассмотрим сеть с топологией, представленной на рисунке 3.1 с указанными стоимостями каналов.Рисунок 3.1 - Текущая топология сети со стоимостями каналовЗадача заключается в том, чтобы определить маршруты с наименьшей стоимостью для всех хостов сети. Поскольку каждый хост подключен к одному роутеру через единственный канал, имеет смысл сначала определить стоимости маршрутов для маршрутизаторов (R1, R2, R3, R6, R7, R8), а затем добавить к ним стоимости каналов к хостам. Таким образом, будем использовать топологию на рисунке 3.2. Рисунок 3.2 – Вспомогательная топология сети Таблицы 3.1 –3.9 содержат реализацию алгоритма Флойда-Уоршелла при построении кратчайших путей для маршрутизаторов R1, R2, R3, R6, R7, R8.Построим весовую матрицу, которая содержит стоимости канальных участков между всеми парами узлов сети. При k=0 таблица стоимостей маршрутов полностью соответствует весовой матрице. D=051608170923589021210101916100190121723120На основе весовой матрицы заполним таблицу 3.1.Таблица 3.1 – Маршруты W(0) с промежуточным узлом k=0УзелR1R2R3R4R5R6R7R8L(R1)0516Путь---4-1-6-1--L(R2)0817Путь---4-2---8-2L(R3)0923Путь---4-3---8-3L(R4)589021Путь1-42-43-4-5-4---L(R5)2101019Путь---4-5-6-57-5-Продолжение таблицы 3.1L(R6)16100Путь1-6---5-6---L(R7)19012Путь----5-7--8-7L(R8)1723120Путь-2-83-8---7-8-Таблица 3.2 – Маршруты W(1) с промежуточным узлом k=1УзелR1R2R3R4R5R6R7R8L(R1)0516Путь---4-1-6-1--L(R2)0817Путь---4-2---8-2L(R3)0923Путь---4-3---8-3L(R4)58902121Путь1-42-43-4-5-46-1-4--L(R5)2101019Путь---4-5-6-57-5-L(R6)1621100Путь1-6--4-1-65-6---L(R7)19012Путь----5-7--8-7L(R8)1723120Путь-2-83-8---7-8-Таблица 3.3 – Маршруты W(2) с промежуточным узлом k=2УзелR1R2R3R4R5R6R7R8L(R1)0516Путь---4-1-6-1--L(R2)0817Путь---4-2---8-2L(R3)0923Путь---4-3---8-3L(R4)5890212125Путь1-42-43-4-5-46-1-4-8-2-4L(R5)2101019Путь---4-5-6-57-5-L(R6)1621100Путь1-6--4-1-65-6---L(R7)19012Путь----5-7--8-7L(R8)172325120Путь-2-83-84-2-8--7-8-Маршруты W(3) с промежуточным узлом k=3 не изменились по сравнению с таблицей 3.3, поэтому данные не поменялись.Таблица 3.4 – Маршруты W(4) с промежуточным узлом k=4УзелR1R2R3R4R5R6R7R8L(R1)013145261630Путь-2-4-13-4-14-15-4-16-1-8-2-4-1L(R2)130178292917Путь1-4-2-3-4-24-25-4-26-1-4-2-8-2L(R3)141709303023Путь1-4-32-4-3-4-35-4-36-1-4-3-8-3L(R4)5890212125Путь1-42-43-4-5-46-1-4-8-2-4L(R5)262930210101946Путь1-4-52-4-53-4-54-5-6-57-58-2-4-5L(R6)1629302110046Путь1-62-4-1-63-4-1-64-1-65-6--8-3-4-1-6L(R7)19012Путь----5-7--8-7L(R8)301723254646120Путь1-4-2-82-83-84-2-85-4-2-86-1-4-3-87-8-Таблица 3.5 – Маршруты W(5) с промежуточным узлом k=5УзелR1R2R3R4R5R6R7R8L(R1)01314526164530Путь-2-4-13-4-14-15-4-16-17-5-4-18-2-4-1L(R2)13017829294817Путь1-4-2-3-4-24-25-4-26-1-4-27-5-4-28-2L(R3)14170930304923Путь1-4-32-4-3-4-35-4-36-1-4-37-5-4-38-3L(R4)589021214025Путь1-42-43-4-5-46-1-47-5-48-2-4L(R5)262930210101946Путь1-4-52-4-53-4-54-5-6-57-58-2-4-5L(R6)162930211002946Путь1-62-4-1-63-4-1-64-1-65-6-7-5-68-3-4-1-6L(R7)454849401929012Путь1-4-5-72-4-5-73-4-5-74-5-75-76-5-7-8-7L(R8)301723254646120Путь1-4-2-82-83-84-2-85-4-2-86-1-4-3-87-8-Маршруты W(6) с промежуточным узлом k=6 не изменились по сравнению с таблицей 3.5, поэтому данные не поменялись.Таблица 3.6 – Маршруты W(7) с промежуточным узлом k=7УзелR1R2R3R4R5R6R7R8L(R1)01314526164530Путь-2-4-13-4-14-15-4-16-17-5-4-18-2-4-1L(R2)13017829294817Путь1-4-2-3-4-24-25-4-26-1-4-27-5-4-28-2L(R3)14170930304923Путь1-4-32-4-3-4-35-4-36-1-4-37-5-4-38-3L(R4)589021214025Путь1-42-43-4-5-46-1-47-5-48-2-4L(R5)262930210101931Путь1-4-52-4-53-4-54-5-6-57-58-7-5L(R6)162930211002941Путь1-62-4-1-63-4-1-64-1-65-6-7-5-68-7-5-6L(R7)454849401929012Путь1-4-5-72-4-5-73-4-5-74-5-75-76-5-7-8-7L(R8)301723253141120Путь1-4-2-82-83-84-2-85-7-86-5-7-87-8-Таблица 3.7 – Маршруты W(8) с промежуточным узлом k=8УзелR1R2R3R4R5R6R7R8L(R1)01314526164230Путь-2-4-13-4-14-15-4-16-17-8-2-4-18-2-4-1L(R2)13017829292917Путь1-4-2-3-4-24-25-4-26-1-4-27-8-28-2L(R3)14170930303523Путь1-4-32-4-3-4-35-4-36-1-4-37-8-38-3L(R4)589021213725Путь1-42-43-4-5-46-1-47-8-2-48-2-4L(R5)262930210101931Путь1-4-52-4-53-4-54-5-6-57-58-7-5L(R6)162930211002941Путь1-62-4-1-63-4-1-64-1-65-6-7-5-68-7-5-6L(R7)422935371929012Путь1-4-2-8-72-8-73-8-74-2-8-75-76-5-7-8-7L(R8)301723253141120Путь1-4-2-82-83-84-2-85-7-86-5-7-87-8-Таким образом, таблица 3.7 содержит кратчайшие пути между маршрутизаторами. Добавляем стоимости каналов, через которые хосты подключены к маршрутизаторам. Кратчайшие пути между хостами следующие: - от А до В: А-R1-R4-R2-В. Стоимость: 28 (13 + 5+10);- от А до С: А-R1-R4-R3-С. Стоимость: 31 (14+ 5+12);- от А до D: А-R1-R6-D. Стоимость: 28 (16+ 5+7);- от А до Е: А-R1-R4-R2-R8-R7-Е. Стоимость: 52 (42 + 5+5);- от А до F: А-R1-R4-R2-R8-F. Стоимость: 43 (30 + 5+8);- от В до А: В-R2-R4-R1-А. Стоимость: 28 (13 + 5+10);- от В до С: В-R2-R4-R3-С. Стоимость: 39 (17+ 10+12);- от В до D: В-R2-R4-R1-R6-D. Стоимость: 46 (29 + 10+7);- от В до Е: В-R2-R8-R7-Е. Стоимость: 44 (29 + 10+5);- от В до F: В-R2-R8-F. Стоимость: 35 (17 + 10+8);- от С до А: С-R3-R4-R1-А. Стоимость: 31 (14+ 12+5);- от С до В: С-R3-R4-R2-В. Стоимость: 39 (17+ 12+10);- от С до D: С-R3-R4-R1-R6-D. Стоимость: 49 (30+ 12+7);- от С до Е: С-R3-R8-R7-Е. Стоимость: 52 (35+ 12+5);- от С до F: С-R3-R8-F. Стоимость: 43 (23+ 12+8);- от D до А: D-R6-R1-А. Стоимость: 28 (16+ 7+5);- от D до В: D-R6-R1-R4-R2-В. Стоимость: 46 (29+ 10+7);- от D до С: D-R6-R1-R4-R3-С. Стоимость: 49 (30+ 7+12);- от D до Е: D-R6-R5-R7-Е. Стоимость: 41 (29+ 7+5);- от D до F: D-R6-R5-R7-R8-F. Стоимость: 56 (41+ 7+8);- от Е до А: Е-R7-R8-R2-R4-R1-А. Стоимость: 52 (42 + 5+5);- от Е до В: Е-R7-R8-R2-В. Стоимость: 44 (29 + 5+10);- от Е до С: Е-R7-R8-R3-С. Стоимость: 52 (35+ 12+5);- от Е до D: Е-R7-R5-R6-D. Стоимость: 41 (29+ 5+7);- от Е до F: Е-R7-R5-R6-F. Стоимость: 25 (12+ 5+8);- от F до А: F-R8-R2-R4-R1-А. Стоимость: 43 (30 + 8+5);- от F до B: F-R8-R2-B. Стоимость: 35 (17 + 8+10);- от F до C: F-R8-R3-C. Стоимость: 43 (23+ 8+12);- от F до D: F-R8-R7-R5-R6-D. Стоимость: 56 (41+ 8+7);- от F до E: F-R8-R7-E. Стоимость: 25 (12+ 8+5).4 ВыводыВ результате проделанной курсовой работы для заданной топологии на основе алгоритма Флойда-Уоршелла (принцип данного алгоритма состоит в построении весовой матрицы и постепенном добавлении промежуточных узлов) были разработаны маршруты кратчайшего пути от хоста к хосту при передаче речевого трафика, т.е. маршруты с наименьшей стоимостью.