Размещено на http://www.allbest.ru/

Исследование алгоритма Дейкстры для маршрутизации пакетов в компьютерной сети

Краснодар-2015

РЕФЕРАТ

Ключевые слова: ПРИЛОЖЕНИЕ, РАЗРАБОТКА, ДЕЙКСТРА, КОМПЬЮТЕРНЫЕ СЕТИ, МАРШРУТИЗАЦИЯ, АЛГОРИТМ, C#.

Целью работы является разработка приложения «Алгоритм Дейкстры для поиска кратчайшего пути» для выполнения вычислений в среде VisualStudioC#.

Объект исследования - поиск кратчайшего расстояния между точками.

Предмет исследования - объектно-ориентированные и машинно-ориентированные средства языков программирования для реализации поиска кратчайшего расстояния.

Разработанная программа позволяет находить оптимальныйкратчайшеепуть от заданной до конечной точки.

программирование расстояние кратчайший дейкстра



ВВЕДЕНИЕ

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

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

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



1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 Сведения из теории

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

Обычно маршрутизатор использует адрес получателя, указанный в заголовке пакета, и определяет по таблице маршрутизации путь, по которому следует передать данные. Если в таблице маршрутизации для адреса нет описанного маршрута, пакет отбрасывается.

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

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

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

Каждой вершине сопоставляется метка - минимальное известное расстояние от этой вершины до а. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

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

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

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U - массив булевых переменных.

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

На каждом шаге цикла мы ищем вершину  с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины . Если в них (в ) расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 . Последний случай возможен тогда и только тогда, когда граф G не связан.

Рисунок 1. Блок-схема алгоритма



1.3 Область применения

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

Также, он применяется в протоколе маршрутизации OSPF-динамическом протоколе, основанном на технологии отслеживания состояния канала(link-statetechnology) и использующий для нахождения кратчайшего пути алгоритм Дейкстры.

Протокол OSPF был разработан IETF в 1988 году. Последняя версия протокола представлена в RFC 2328. Протокол OSPF представляет собой протокол внутреннего шлюза (InteriorGatewayProtocol - IGP). Протокол OSPF распространяет информацию о доступных маршрутах между маршрутизаторами одной автономной системы.

OSPF имеет следующие преимущества:

· Высокая скорость сходимости по сравнению с дистанционно-векторными протоколами маршрутизации;

· Поддержка сетевых масок переменной длины (VLSM);

· Оптимальное использование пропускной способности с построением дерева кратчайших путей;

Как работает этот протокол:

1. Маршрутизаторы обмениваются hello-пакетами через все интерфейсы, на которых активирован OSPF. Маршрутизаторы, разделяющие общий канал передачи данных, становятся соседями, когда они приходят к договоренности об определённых параметрах, указанных вихhello-пакетах.

2. На следующем этапе работы протокола маршрутизаторы будут пытаться перейти в состояние смежности со своими соседями. Переход в состояние смежности определяется типом маршрутизаторов, обменивающихсяhello-пакетами, и типом сети, по которой передаются hello-пакеты. OSPF определяет несколько типов сетей и несколько типов маршрутизаторов. Пара маршрутизаторов, находящихся в состоянии смежности, синхронизирует между собой базу данных состояния каналов.

3. Каждый маршрутизатор посылает объявления о состоянии канала маршрутизаторам, с которыми он находится в состоянии смежности.

4. Каждый маршрутизатор, получивший объявление от смежного маршрутизатора, записывает передаваемую в нём информацию в базу данных состояния каналов маршрутизатора и рассылает копию объявления всем другим смежным с ним маршрутизаторам.

5. Рассылая объявления внутри одной OSPF-зоны, все маршрутизаторы строят идентичную базу данных состояния каналов маршрутизатора.

6. Когда база данных построена, каждый маршрутизатор использует алгоритм «кратчайший путь первым» для вычисления графа без петель, который будет описывать кратчайший путь к каждому известному пункту назначения с собой в качестве корня. Этот граф - дерево кратчайших путей.

7. Каждый маршрутизатор строит таблицу маршрутизации из своего дерева кратчайших путей.

Также, алгоритм Дейкстры применяется в протоколе маршрутизации промежуточных систем (IS-IS) - протокол внутренних шлюзов (IGP), стандартизированный ISO и использующийся в основном в крупных сетях провайдеров услуг. IS-IS может также использоваться в корпоративных сетях особо крупного масштаба. IS-IS - это протокол маршрутизации на основе состояния соединений. Он обеспечивает быструю сходимость и отличнуюмасштабируемость. Как и все протоколы на основе состояния соединений, IS-IS очень экономно использует пропускную способность сетей.

Приложение «Алгоритм Дейкстры для поиска кратчайшего пути» имеет расширение .exe и, следовательно, работает только в ОС Windows.

Требования к системе:

1) ОС WindowsXP или более поздние версии;

2) Direct X 9;

3) 10 Мб свободного места на жестком диске;

4) Видеоускоритель;

5) Устройства ввода(мышь, клавиатура).

1.4 Алгоритм решения

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

Работает программа очень просто: пользователю нужно рандомно указать 11 точек, после чего нажать кнопку «Построить граф» а затем отметить начальную и конечную точку. Начальная точка будет отображаться зеленым цветом, а конечная - красным. После этого пользователю нужно нажать кнопку «Показать кратчайший путь» и программ прорисует жирной линией путь от начальной до конечной точки.

После прорисовки пути данные передаются в С++ и результаты выводятся в специально отведенное поле, а выполнение программы прекращается.

1.5 Макет приложения

На рисунке 1 показан макет приложения

Рисунок 1 - Макет приложения

- Button1Click- кнопка необходимая для вызова функции построения графика. Имеет название «Построить граф»

- Button2Click -кнопка необходимая для вызова функции поиска кратчайшего пути между точками. Имеет название «Показать кратчайший путь»

- Button3Click - кнопка необходимая для вызова очистки рабочей области. Имеет название «Очистить PictureBox1 - рабочая область, в которой задаются вершины, строится граф и вычисляется кратчайший путь.

1.6 Описание программы

Используемые библиотеки

usingSystem;

usingSystem.Collections.Generic;

usingSystem.ComponentModel;

usingSystem.Data;

usingSystem.Drawing;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Threading.Tasks;

usingSystem.Windows.Forms;

Используемыеэлементы

button

picturebox1

label

Обработчикисобытий

private void picturebox1_mousedown;

private void button1_click;

private void button2_click;

private void button3_click;

Файлыклассов

Graph.cs

GraphMethods.cs

NodeGraph.cs

После старта программы, пользователю предлагается нажатием кнопки мышки выбрать 11 произвольных вершин в окне. При этом вызывается обработчик picturebox_mousedown. Все вершины 11 вершин, которые построил пользователь окрашиваются в черный цвет с помощью функции draw_node. После того, как вершины построены, вызывается построение графа, задание ребер и веса для каждой из вершин. Далее пользователь выбирает начальную точку, которую функция draw_nodeокрашивает в зеленый цвет, и конечную, которую эта же функция окрашивает в красный цвет. После этого пользователь нажимает на кнопку «Поиск кратчайшего пути» и программа в качестве результата строит жирную линию пути от указанных точек с помощью функции DoDijkstra.

Если пользователь построил указал вершины и построил граф, но не выбрал конечную и начальную точки то программа производить операции не будет.



2.РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

2.1 Результат работы программ

Входные данные представлены на рисунке 3:

Рисунок 3 - входные данные

Выходные данные(по нажатию на кнопку «Показать кратчайший путь») представлены на рисунке 4:

Рисунок 4 - выходные данные

2.2 Руководство пользователя

1.Запускаем программу

2. Указываем произвольно 11 вершин в Рабочей Области

3. Нажимаем на кнопку «Построить граф»

4. Выбираем начальную и конечную вершины. Сначала будет выбрана начальная точка (зеленым), а потом конечная(красным).

5. Для вычисления кратчайшего пути от заданных точек нажмите кнопку «Показать кратчайший путь»

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



ЗАКЛЮЧЕНИЕ

В ходе выполнения курсовой работы были выполнены все поставленные задачи, а так же был получен дополнительный опыт разработки приложений на языке C# с применением алгоритма Дейкстры.

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

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

Программа не требует больших ресурсных затрат, интерфейс рассчитан на простого пользователя.



СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1) Герберт Шилдт. «Полный справочник по C#» [Текст] / Герберт Шилдт. - ООО «И.Д. Вильямс», 2010. - 780 с.

2) CLR via C#. Программирование на платформе Microsoft .NET Framework 4.5 на языке C#. 4-е изд. [Текст] / Дж.Рихтер - Москва: Дом Книги, 2011.

3) Бьёрн Страуструп «Язык программирования C#». [Текст] / Бьёрн Страуструп - Специальное издание. Москва: Бином-Пресс, 2010. - 1104 с.

4) Язык программирования C#. Классика ComputersScience. 4-е изд.[Текст] / А. Хейлсерберг, М. Торгерсен- БХВ-Петербург, 2011. - С. 336.

5) Изучаем C#. 3-е изд.[Текст] / Э. Стиллмен- М.: ДМК Пресс, 2011. - С. 304.



ПРИЛОЖЕНИЯ

Приложение 1.

Кодпрограммы«Алгоритм Дейкстры для поиска кратчайшего пути»

КодForm1.cs

using System;

usingSystem.Collections.Generic;

usingSystem.ComponentModel;

usingSystem.Data;

usingSystem.Drawing;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Threading.Tasks;

usingSystem.Windows.Forms;

namespacedeikstra

{

public partial class Form1 : Form

{

/// <summary>

/// Матрица смежености, по которой буде строиться граф

/// </summary>

privateint[,] matrixAdjacency = new int[,]

{

//1 2 3 4 5 6 7 8 9 10 11

{0, 6, 3, 2, 8, 0, 0, 0, 0, 0, 0},

{6, 0, 2, 0, 0, 0, 7, 8, 0, 0, 0},

{3, 2, 0, 0, 0, 6, 0, 12, 0, 0, 0},

{2, 0, 0, 0, 5, 0, 0, 0, 3, 0, 0},

{8, 0, 0, 5, 0, 14, 0, 0, 5, 0, 0},

{0, 0, 6, 0, 14, 0, 11, 6, 10, 0, 9},

{0, 0, 0, 0, 0, 11, 0, 0, 4, 12, 7},

{0, 8, 12, 0, 0, 6, 0, 0, 0, 0, 3},

{0, 0, 0, 3, 5, 10, 4, 0, 0, 2, 0},

{0, 0, 0, 0, 0, 0, 12, 0, 2, 0, 5},

{0, 0, 0, 0, 0, 9, 7, 3, 0, 5, 0}

};

/// <summary>

/// Списоквершинграфа

/// </summary>

private List<EdgeGraph>listEdgeG = new List<EdgeGraph>();

/// <summary>

/// Списокреберграфа

/// </summary>

private List<NodeGraph>listNodeG = new List<NodeGraph>();

privateintcnt = 1;

/// <summary>

/// Индексначальнойвершины

/// </summary>

privateintsrc_index;

/// <summary>

/// Индексконечнойвершины

/// </summary>

privateintdest_index;

public Form1()

{

InitializeComponent();

}

private void button1_Click(object sender, EventArgs e)

{

for (inti = 0; i<matrixAdjacency.GetLength(0); ++i)

{

for (int j = 0; j <matrixAdjacency.GetLength(1); ++j)

{

if (i > j &&matrixAdjacency[i, j] != 0)

{

EdgeGraph edge = new EdgeGraph(listNodeG[i].point, listNodeG[j].point,

matrixAdjacency[i, j].ToString());

edge.draw_edge(pictureBox1.CreateGraphics(), 1);

listEdgeG.Add(edge);

}

}

}

foreach (var x in listNodeG)

{

x.draw_number(pictureBox1.CreateGraphics());

}

}

private void pictureBox1_Click(object sender, EventArgs e)

{

}

private void Form1_Load(object sender, EventArgs e)

{

label1.Text = "Напоминание: Разместите на форме " + (matrixAdjacency.GetLength(0)) + " вершин...";

}

privateintcheckCnt = 1;

privateint checkCnt1 = 1;

privatebool flag = true;

} /// <summary>

/// рисует вершини и выделяет зеленым цветом начальну и красным конечню вершину

/// </summary>

/// <param name="sender"></param>

/// <param name="e"></param>

private void pictureBox1_MouseDown(object sender, MouseEventArgs e)

{

//Рисуемсначаланашивершины

if (checkCnt<= matrixAdjacency.GetLength(0))

{

NodeGraphng = new NodeGraph(e.X, e.Y, (cnt++).ToString());

ng.draw_node(pictureBox1.CreateGraphics(), Color.Black); // черныеточки - вершины

listNodeG.Add(ng);

++checkCnt;

}

//фикисруем начальную и конечную вершины

else

{

for (inti = 0; i<listNodeG.Count; ++i)

{

if (checkCnt1 <= 2)

{

if (e.X>= listNodeG[i].point.X - 15 &&e.X<= listNodeG[i].point.X + 15

&&e.Y>= listNodeG[i].point.Y - 15 &&e.Y<= listNodeG[i].point.Y + 15)

{

if (flag == true)

{

src_index = i;

listNodeG[i].draw_node(pictureBox1.CreateGraphics(), Color.Chartreuse); // выделяемначальнуювершину

flag = false;

++checkCnt1;

}

else

{

dest_index = i;

listNodeG[i].draw_node(pictureBox1.CreateGraphics(), Color.Red); // выделяемконечнуювершину

++checkCnt1;

}

}

}

}

}

}

privatevoidbutton2_Click(objectsender, EventArgse) // Ищемивыделяемжирнымкратчайшийпутьотначальнойвершиныдоконечной

{

try

{

var list = GraphMethods.DoDijkstra(matrixAdjacency, src_index, dest_index);

for(inti = 0; i<list.Count - 1; ++i)

{

EdgeGraphedg = new EdgeGraph(listNodeG[list[i]].point, listNodeG[list[i + 1]].point);

edg.draw_edge(pictureBox1.CreateGraphics(), 4);

foreach (var x in listNodeG)

{

x.draw_number(pictureBox1.CreateGraphics());

}

}

}

catch (Exception ex)

{

MessageBox.Show(ex.Message);

}

}

private void button3_Click(object sender, EventArgs e) // вызываемперерисовкуэлементаиперезапускаем

{

pictureBox1.Image = null;

pictureBox1.Invalidate();

Application.Restart();

}

Код Graph.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

using System.Threading.Tasks;

namespacedeikstra

{

/// <summary>

/// Класс "граф"

/// </summary>

class Graph

{

/// <summary>

/// Списокребер

/// </summary>

Dictionary<int, Dictionary<int, int>> vertices = new Dictionary<int, Dictionary<int, int>>();

/// <summary>

/// Метод додавания вершины в список

/// </summary>

/// <param name="name"></param>

/// <param name="edges"></param>

public void add_vertex(int name, Dictionary<int, int> edges)

{

vertices[name] = edges;

}

/// <summary>

/// Нахождениекратчайшегопутимежду start и finish

/// </summary>

/// <param name="start"></param>

/// <param name="finish"></param>

/// <returns></returns>

public List<int>shortest_path(int start, int finish) // кратчайшийпуть

{

var previous = new Dictionary<int, int>();

var distances = new Dictionary<int, int>();

var nodes = new List<int>();

List<int> path = null;

foreach (var vertex in vertices)

{

if (vertex.Key == start)

{

distances[vertex.Key] = 0;

}

else

{

distances[vertex.Key] = int.MaxValue;

}

nodes.Add(vertex.Key);

}

while (nodes.Count != 0)

{

nodes.Sort((x, y) => distances[x] - distances[y]);

var smallest = nodes[0];

nodes.Remove(smallest);

if (smallest == finish)

{

path = new List<int>();

while (previous.ContainsKey(smallest))

{

path.Add(smallest);

smallest = previous[smallest];

}

break;

}

if (distances[smallest] == int.MaxValue)

{

break;

}

foreach (var neighbor in vertices[smallest])

{

var alt = distances[smallest] + neighbor.Value;

if (alt < distances[neighbor.Key])

{

distances[neighbor.Key] = alt;

previous[neighbor.Key] = smallest;

}

}

}

returnpath;

}

}

}

Код GraphMethods.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

using System.Threading.Tasks;

namespacedeikstra

{

/// <summary>

/// Класс "методыграфа"

/// </summary>

internal static class GraphMethods

{

/// <summary>

/// Метод преобразования матрицы смежености в список ребер и поиск кратчайшего пути

/// </summary>

/// <param name="m"></param>

/// <param name="s"></param>

/// <param name="e"></param>

/// <returns></returns>

static public List<int>DoDijkstra(int[,] m, int s, int e)

{

Graph g = new Graph();

for (inti = 0; i<m.GetLength(0); ++i)

{

Dictionary<int, int>buf = new Dictionary<int, int>();

for (int j = 0; j <m.GetLength(1); ++j)

if (m[i, j] != 0)

buf.Add(j, m[i, j]);

g.add_vertex(i, buf);

}

var l = g.shortest_path(s, e);

l.Add(s);

l.Reverse();

return l;

}

}

}

Код NodeGraph.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Drawing;

usingSystem.Linq;

usingSystem.Security.AccessControl;

using System.Security.Cryptography.X509Certificates;

usingSystem.Text;

usingSystem.Threading.Tasks;

using System.Windows.Forms;

namespacedeikstra

{

/// <summary>

/// Класс "Узелграфа"

/// </summary>

classNodeGraph

{

/// <summary>

/// Описываетузелграфакакточкунапикчербоксе

/// </summary>

public Point point { get; set; }

/// <summary>

/// Текствузле

/// </summary>

public string number { get; set; }

//перегрузкаконструкторов

publicNodeGraph()

{

point = new Point();

}

publicNodeGraph(int _X, int _Y, string _num)

{

point = new Point(_X, _Y);

number = _num;

}

publicNodeGraph(Point _p, string _num)

{

point = _p;

number = _num;

}

/// <summary>

/// Рисует узел по заданум цвету

/// </summary>

/// <param name="g"></param>

/// <param name="color"></param>

public void draw_node(Graphics g, Color color)

{

g.DrawEllipse(new Pen(Color.Black), point.X - 13, point.Y - 12, 30, 30);

g.FillEllipse(new SolidBrush(color), point.X - 13, point.Y - 12, 30, 30);

draw_number(g);

g.Dispose();

}

/// <summary>

/// Рисует текст в узле, в даном случае число

/// </summary>

/// <param name="g"></param>

public void draw_number(Graphics g)

{

Font font = new Font("Times New Roman", 12, FontStyle.Bold);

g.DrawString(number, font, new SolidBrush(Color.Blue), point.X - 4, point.Y - 5);

g.Dispose();

}

}

Размещено на Allbest.ru

...