 |
|
ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
по дисциплине: Архитектура и ЭВМ __________________________________
на тему: Исследование алгоритма Дейкстры для маршрутизации пакетов в компьютерной сети_________________________________________________
выполнил студент группы ИТ 1301____________________________________
Елисеенко Дмитрий Игоревич________________________________________
Допущен к защите
Руководитель проекта Параскевов Александр Владимирович_____________
Защищен__________________ Оценка______________________
(дата)
Члены комиссии________________________________________________
_______________________________________________________________
_______________________________________________________________
_______________________________________________________________
(подпись, дата, расшифровка подписи)
Краснодар
ФГБОУ
КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ
Факультет прикладной информатики
Кафедра компьютерных технологий и систем
УТВЕРЖДАЮ:
Зав. кафедрой____________________
________________________________
ЗАДАНИЕ
На курсовую работу
Студенту: ИТ1301 группы 2 курса
Факультета Прикладная информатика
Направление подготовки: 230400.62 Информационные системы и технологии
(шифр) .
(Ф.И.О.)
Тема проекта: Исследование алгоритма Дейкстры для маршрутизации пакетов в компьютерной сети
_________________________________________________________________
Содержание задания:____________________________________________
_______________________________________________________________
_______________________________________________________________
Объем работы:
а) пояснительная записка к работе___________________листа формата А4
б) графическая часть______________________________лист формата А4
Рекомендуемая литература: ______________________________________
_______________________________________________________________
Срок выполнения проекта: с “___”___________ по “___”________20__ г.
Срок защиты: “___”________20__ г.
Дата выдачи задания: “___”________20__ г.
Дата сдачи проекта на кафедру: “___”________20__ г.
Руководитель проекта ___________________________________________.
(подпись, Ф.И.О., звание, степень)
Задание принял студент _________________________________________
(подпись, дата)
Краснодар
РЕФЕРАТ
Ключевые слова: ПРИЛОЖЕНИЕ, РАЗРАБОТКА, ДЕЙКСТРА, КОМПЬЮТЕРНЫЕ СЕТИ, МАРШРУТИЗАЦИЯ, АЛГОРИТМ, C#.
Целью работы является разработка приложения «Алгоритм Дейкстры для поиска кратчайшего пути» для выполнения вычислений в среде Visual Studio C#.
Объект исследования – поиск кратчайшего расстояния между точками.
Предмет исследования – объектно-ориентированные и машинно-ориентированные средства языков программирования для реализации поиска кратчайшего расстояния.
Разработанная программа позволяет находить оптимальный кратчайшее путь от заданной до конечной точки.
Содержание
РЕФЕРАТ. 3
ВВЕДЕНИЕ. 5
1 ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ.. 6
1.1 Сведения из теории. 6
1.2 Алгоритм Дейкстры.. 6
2 ТЕХНОЛОГИЯ РАЗРАБОТКИ ПРИЛОЖЕНИЯ.. 9
2.1 Алгоритм решения. 9
2.2 Макет приложения. 9
2.3 Описание программы.. 10
3 РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ.. 12
3.1 Результат работы программ. 12
3.2 Руководство пользователя. 13
ЗАКЛЮЧЕНИЕ. 14
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 15
ПРИЛОЖЕНИЯ.. 16
ВВЕДЕНИЕ
Цель маршрутизации - доставка пакетов по назначению с максимизацией эффективности. Чаще всего эффективность выражена взвешенной суммой времен доставки сообщений при ограничении снизу на вероятность доставки. Маршрутизация сводится к определению направлений движения пакетов в маршрутизаторах. Выбор одного из возможных в маршрутизаторе направлений зависит от текущей топологии сети (она может меняться хотя бы из-за временного выхода некоторых узлов из строя), длин очередей в узлах коммутации, интенсивности входных потоков и т.п.
Большинство (если не все) маршрутизаторов работают по алгоритму кратчайшего пути Дейкстры. Для реализации алгоритма он нуждается в плане сети с обозначенными длинами каналов. У каждого маршрутизатора есть собственный адрес, который был введен в его родной прошивке, который обращается к остальным при поиске сетевых адресов. В работающей сети маршрутизатор может рассчитать метрику каждого исходящего канала.
Маршрутизаторы могут также выполнять алгоритм Дейкстры с несколькими различными наборами метрик. Например, метрики могут учитывать порознь надежность, пропускную способность и задержку. В результате выполнения алгоритма Дейкстры для каждого из трех наборов метрик, все маршрутизаторы сети знают самый надежный путь, путь с наибольшей пропускной способностью и путь с минимальной задержкой до любого другого маршрутизатора. В пакете может быть указано, по какому критерию маршрутизаторам следует выбирать путь.
ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ
Сведения из теории
Маршрутизатор – специализированный сетевой компьютер, имеющий два или более сетевых интерфейса и пересылающий пакеты данных между различными сегментами сети. Маршрутизатор может связывать разнородные сети различных архитектур. Для принятия решений о пересылке пакетов используется информация о топологии сети и определённые правила, заданные администратором.
Обычно маршрутизатор использует адрес получателя, указанный в заголовке пакета, и определяет по таблице маршрутизации путь, по которому следует передать данные. Если в таблице маршрутизации для адреса нет описанного маршрута, пакет отбрасывается.
Существуют и другие способы определения маршрута пересылки пакетов, когда, например, используется адрес отправителя, используемые протоколы верхних уровней и другая информация, содержащаяся в заголовках пакетов сетевого уровня. Нередко маршрутизаторы могут осуществлять трансляцию адресов отправителя и получателя, фильтрацию транзитного потока данных на основе определённых правил с целью ограничения доступа, шифрование/расшифрование передаваемых данных и т. д.
Алгоритм Дейкстры
Алгоритм Дейкстры – алгоритм на графах, изобретенный нидерландским ученым Э.Дейкстрой в 1959 году. Алгоритм находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса. Широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.
Каждой вершине сопоставляется метка – минимальное известное расстояние от этой вершины до а. Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как не посещённые.
Если все вершины посещены, алгоритм завершается. В противном случае, из еще не посещенных вершин выбирается вершина, имеющая минимальную метку. Вершины, в которые ведут ребра называются «соседями» этой вершины. Для каждого соседа вершины, кроме отмеченных как посещенные, рассмотрим новую длину пути, равную сумме значений текущей метки и длины ребра, соединяющего вершину с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, п, пометим вершину как посещенную и повторим шаг алгоритма.
В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных.
В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (большим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.
На каждом шаге цикла мы ищем вершину 
с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины 
. Если в них (в ) расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 
. Последний случай возможен тогда и только тогда, когда граф G не связан.
Приложение «Алгоритм Дейкстры для поиска кратчайшего пути» имеет расширение .exe и, следовательно, работает только в ОС Windows.
Требования к системе:
1) ОС Windows XP или более поздние версии;
2) Direct X 9;
3) 10 Мб свободного места на жестком диске;
4) Видеоускоритель;
5) Устройства ввода (мышь, клавиатура).