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

Разработка приложения «Алгоритм Дейкстры для поиска кратчайшего пути» для выполнения вычислений в среде VisualStudioC#. Изучение методов объектно-ориентированные и машинно-ориентированные программирования для реализации поиска кратчайшего расстояния.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

РЕФЕРАТ

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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 или более поздние версии;

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

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

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

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

Источник

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

Разработка приложения «Алгоритм Дейкстры для поиска кратчайшего пути» для выполнения вычислений в среде VisualStudioC#. Изучение методов объектно-ориентированные и машинно-ориентированные программирования для реализации поиска кратчайшего расстояния.

Нажав на кнопку «Скачать архив», вы скачаете нужный вам файл совершенно бесплатно.
Перед скачиванием данного файла вспомните о тех хороших рефератах, контрольных, курсовых, дипломных работах, статьях и других документах, которые лежат невостребованными в вашем компьютере. Это ваш труд, он должен участвовать в развитии общества и приносить пользу людям. Найдите эти работы и отправьте в базу знаний.
Мы и все студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будем вам очень благодарны.

Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку «Скачать архив»

Подобные документы

Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Проверка работоспособности программы на тестовых примерах.

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

Графы: определения, примеры, способы изображения. Смежные вершины и рёбра. Путь в ориентированном и взвешенном графе. Матрица смежности и иерархический список. Алгоритм Дейкстры — алгоритм поиска кратчайших путей в графе. Работа в программе «ProGraph».

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

История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7.

Источник