Материал: Алгоритмы маршрутизации

Рис. 18. Иллюстрация алгоритма Флойда

После реализации n шагов алгоритма определение по матрицам D_n и S_n кратчайшего пути между узлами i и j выполняется по следующим правилам.

Расстояние между узлами i и j равно элементу d_ij в матрице D_n.

Промежуточные узлы пути от узла i к узлу j определяем по матрице S_n. Пусть s_ij = k, тогда имеем путь i ->k ->j. Если далее s_ik = k и s_kj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

Пример. Найдем для сети, показанной на рисунке 4, кратчайшие пути между любыми двумя узлами. Расстояние между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3, 5) ориентированно, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны:

Рис. 19. Пример сети

Шаг 0. Начальные матрицы D₀ и S₀ строятся непосредственно по заданной схеме сети. Матрица D₀ симметрична, за исключением пары элементов d₃₅ и d₅₃, где d₅₃ равно бесконечности, поскольку невозможен переход от узла 5 к узлу 3:

Рис.20. Начальное состояние

Шаг 1. В матрице D₀ выделены ведущие строка и столбец (k = 1). Двойной рамкой представлены элементы d₂₃ и d₃₂, единственные среди элементов матрицы D₀, значения которых можно улучшить с помощью треугольного оператора. Таким образом, чтобы на основе матриц D₀ и S₀ получить матрицы D₁ и S₁, выполняем следующие действия.

Заменяем d₂₃ на d₂₁ + d₁₃ = 3 + 10 = 13 и устанавливаем s₂₃ = 1.

Заменяем d₃₂ на d₃₁ + d₁₂ = 10 + 3 = 13 и устанавливаем s₃₂ = 1.

Матрицы D₁ и S₁ имеют следующий вид:

Рис.21. Матрицы D₁ и S₁

Шаг 2. Полагаем k = 2; в матрице D₁ выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D₁ и S₁, выделенным двойной рамкой. В результате получаем матрицы D₂ и S₂:

Рис.22. Матрицы D₂ и S₂

Шаг 3. Полагаем k = 3; в матрице D₂ выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D₂ и S₂, выделенным двойной рамкой. В результате получаем матрицы D₃ и S₃:

Рис.23. Матрицы D₃ и S₃

Шаг 4. Полагаем k = 4, ведущие строка и столбец в матрице D₃ выделены. Получаем новые матрицы D₄ и S₄:

Рис.24. Матрицы D₄ и S₄

Шаг 5. Полагаем k = 5, ведущие строка и столбец в матрице D₄ выделены. Никаких действий на этом шаге не выполняем; вычисления закончены.

Конечные матрицы D₄ и S₄ содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя узлами сети. Например, кратчайшее расстояние между узлами 1 и 5 равно d₁₅ = 12.

Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i, j) состоит из ребра (i, j) только в том случае, когда s_ij = j. В противном случае узлы i и jсвязаны, по крайней мере, через один промежуточный узел. Например, поскольку s₁₅ = 4 и s₄₅ = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1->4->5. Но так как s₁₄ не равно 4, узлы 1 и 4 в определенном пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s₁₄ = 2 и s₂₄ = 4, поэтому маршрут 1->4 заменяем 1->2->4. Поскольку s₁₂ = 2 и s₂₄ = 4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5: 1->2->4->5. Длина этого пути равна 12 километрам.

Глава 3. Разработка алгоритмов маршрутизации

.1 Разработка алгоритма маршрутизации Дейкстры

Рис.25. Блок схема Алгори́тма Де́йкстры

Алгори́тм Де́йкстры реализован на языке программирования C#

using System;.Collections.Generic;.Linq;.Text;ConsoleApplication18

{Program

{public class Node

{List<Link> Links { get; set; }Node()

{= new List<Link>();

}

}public class Link

{double Distance { get; set; }string Node { get; set; }

}public class Description

{Visited { get; set; }double Distance { get; set; }Description()

{= false;= double.PositiveInfinity;//+8

}

}public class Graph

{Dictionary<string, Node> nodes;Graph()

{= new Dictionary<string, Node>();

}void AddNode(string name)

{.Add(name, new Node());

}void AddLinkToNode(string start, string end, double distance, boolisOriented)

{[start].Links.Add(new Link { Node = end, Distance = distance });(!isOriented)[end].Links.Add(new Link { Node = start, Distance = distance });

}double FindShortestDistance(string start, string end)

{

// АлгоритмДейкстры<string, Description> info = new Dictionary<string, Description>(this.nodes.Count);(string current in this.nodes.Keys).Add(current, new Description());//visited, distance

info[start].Distance = 0;

// Пока все вершины непосещенные

while (!info.Select(x =>x.Value.Visited).Aggregate((x, y) => x & y))

{

// Находим непосещенную вершину с минимальной меткой

string current = info.Where(x => !x.Value.Visited

&&x.Value.Distance == info.Where(y => !y.Value.Visited).Min(y =>y.Value.Distance))

.First().Key;

// Находим все непосещенные соседние вершины для текущей вершины

List<Link> neighbors = nodes[current].Links.Where(x => !info[x.Node].Visited).ToList();

// Рассматриваем новую длину пути для каждой соседней вершины

foreach (Link link in neighbors)

{distance = info[current].Distance + link.Distance;(info[link.Node].Distance > distance)[link.Node].Distance = distance;

}

// Отмечаем текущую вершину как посещенная.

info[current].Visited = true;

}info[end].Distance;

}

}void Main()

{count = 10;[] names = { "1", "2", "3", "4", "5", "6", "7", "8", "9", "10" };= newGraph();

// Заполнениеграфавершинами.(inti = 0; i< count; ++i)

graph.AddNode(names[i]);

// Создание у вершин связей.

// Последнее значение говорит о том, что эта связь двунаправленная.

graph.AddLinkToNode("1", "2", 7, false);

graph.AddLinkToNode("1", "3", 9, false);

graph.AddLinkToNode("1", "6", 14, false);

graph.AddLinkToNode("2", "3", 10, false);

graph.AddLinkToNode("2", "4", 15, false);

graph.AddLinkToNode("3", "4", 11, false);

graph.AddLinkToNode("3", "6", 2, false);

graph.AddLinkToNode("4", "5", 6, false);

graph.AddLinkToNode("5", "6", 9, false);

graph.AddLinkToNode("6", "7", 11, false);

graph.AddLinkToNode("7", "9", 9, false);

graph.AddLinkToNode("8", "5", 6, false);

graph.AddLinkToNode("9", "5", 14, false);

graph.AddLinkToNode("9", "6", 16, false);

graph.AddLinkToNode("9", "10", 15, false);.AddLinkToNode("10", "5", 18, false);.Write("Маршрутиз 1 в 2 = ");.WriteLine(graph.FindShortestDistance("1", "2")); .Write("Маршрутиз 1 в 3 = ");.WriteLine(graph.FindShortestDistance("1", "3")); .Write("Маршрутиз 1 в 4 = ");.WriteLine(graph.FindShortestDistance("1", "4")); .Write("Маршрутиз 1 в 5 = ");.WriteLine(graph.FindShortestDistance("1", "5")); .Write("Маршрутиз 1 в 6 = ");.WriteLine(graph.FindShortestDistance("1", "6")); .Write("Маршрутиз 1 в 7 = ");.WriteLine(graph.FindShortestDistance("1", "7"));.Write("Маршрутиз 1 в 8 = ");.WriteLine(graph.FindShortestDistance("1", "8"));.Write("Маршрутиз 1 в 9 = ");.WriteLine(graph.FindShortestDistance("1", "9"));.Write("Маршрутиз 1 в 10 = ");.WriteLine(graph.FindShortestDistance("1", "10"));.ReadKey();

}

}

}

.1.1 Таблица кратчайших путей и маршрутов

Маршрут из 1 в 2 = 7

Маршрут из 1 в 3 = 9

Маршрут из 1 в 4 = 20

Маршрут из 1 в 5 = 20

Маршрут из 1 в 6 = 11

Маршрут из 1 в 7 = 22

Маршрут из 1 в 8 = 24

Маршрут из 1 в 9 = 27

Маршрут из 1 в 10 = 38

Рис. 26. Граф. Пример сети для алгоритма Дейкстры.

.2 Разработка алгоритма маршрутизации Флойда

Рис. 27.Блок схема алгоритма Флойда.

Алгоритма Флойда реализован на языке программирования C#.

using System;Алгоритм_Флойда

{Program

{void Main()

{[,] array = new int[6, 6]

{ // 1 2 3 4 5 6

/*1*/{0, 2, 9999, 3, 6, 9999},

/*2*/{9999, 0, 4, 7, 9999, 4 },

/*3*/{3, 9, 0, 5, 9999, 2 },

/*4*/{9999, 6, 9999, 0, 2, 9999},

/*5*/{7, 9999, 2, 4, 0, 7 },

/*6*/{5, 2, 9999, 9999, 2, 0 }

};, j, k;(i= 0; i< 6; i++)(j = 0; j < 6; j++)(k = 0; k < 6; k++)(array[i, k] > array[i, j] + array[j, k])[i, k] = array[i, j] + array[j, k];

// Вывод измененной матрицы смежности

Console.WriteLine("Алгоритм Флойда : \n");

for (i = 0; i< 6; i++)

{(j = 0; j < 6; j++).Write(array[i, j] + " ");.WriteLine();

} Console.ReadLine();

}}}

.2.1 Таблица кратчайших путей и маршрутов

Таблица 1

Рис. 28. Граф. Пример сети для алгоритма Флойда.

.3 Сравнительный анализ алгоритмов маршрутизации

Проведя анализ трех алгоритмов, можно сделать выводы о целесообразности использовании данных алгоритмов.

Алгоритм Дейкстры Этот алгоритм является самым простым алгоритмом из исследуемых. Он хорошо выполняется в графах с небольшим количеством вершин, компьютерные сети не является таковыми. Учитывая структуры больших схем, программа, написанная с использованием алгоритма Дейкстры будет выполняться медленно.

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

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

В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе. Конечно эта задача может быть решена и многократным применением алгоритма Дейкстры (каждый раз последовательно выбираем вершину от первой до N-ной, пока не получим кратчайшие пути от всех вершин графа), однако реализация подобной процедуры потребовала бы значительных вычислительных затрат.

В заключение отметим общие недостатки рассматриваемых методов: оба метода требуют полного перебора всех вершин графа. Требуется большой объем памяти и время расчета.

Заключение

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

В результате были получены таблицы кратчайших путей и маршрутов методом Дейкстры и Флойда.

Программы готовы к эксплуатации и могут с успехом использоваться для демонстрации работы с алгоритмом Дейкстры и Флойда.

алгоритм маршрутизация сеть граф

Список использованной литературы

1. Столлингс В. Современные компьютерные сети. - 2003

2.      Автоматические системы коммутации: Учебник для вузов / Иванова О.П., Копп М.Ф., Кохонова З.С., Метельский Г.Б.; Под ред. О.Н Ивановой 2-е изд., доп. и перераб. М.: Связь, 1978. - 624с., ил.

.        Семенов Ю.А. Протоколы и ресурсы Internet. Радио и связь, 1996 г.

.        Владимир Плешаков, CISCO Internetworking Technology Overview.

5.      Электронная энциклопедия Wikipedia.