ВВЕДЕНИЕ 4
1. Анализ проблем построения маршрутов в программно-конфигурируемых сетях 7
1.1. Актуальность проблемы построения маршрутов в программно-
конфигурируемых сетей 7
1.2. Общие сведения о программно-конфигурируемых сетях 7
1.2.1. Архитектура программно-конфигурируемых сетей 10
1.2.2. Протокол OpenFlow 15
1.2.3. Сетевые операционные системы в ПКС 16
1.3. Общие сведения о построении путей 19
1.4. Выбор инструментальных средств реализации для реализации
алгоритма, эмуляции сложного сегмента программно-конфигурируемой сети 22
1.4.1. Обзор сетевых ОС 22
1.4.2. Обзор средств для эмуляции программно-конфигурируемой сети26
1.4.3. Обзор сред разработки 30
2. Проектирование и реализация 38
2.1. Проектирование структуры эффективного алгоритма оптимизации трафика 38
2.1.1. Проектирование и реализация алгоритма построения маршрутов на
базе простых структур данных 39
2.1.2. Оптимизация работы алгоритма построения маршрутов на базе
простых структур данных с помощью OpenMP 49
2.1.3. Эмуляция тестовых сегментов сети 50
3. Тестирование и апробация 54
ЗАКЛЮЧЕНИЕ 57
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 58
ПРИЛОЖЕНИЕ
В XXI веке постоянный рост подключенных устройств к сети «Интернет» повлёк за собой экспоненциальный рост общемирового трафика. Этот резкий скачок стимулировал развитие новых более быстрых и инновационных компьютерных сетей под названием «Программно- конфигурируемые сети». Новое поколение коммуникационных сетей имело важное преимущество в виде увеличенной пропускной способности каждого передающего устройства, однако главным минусом данных сетей стало время создания нового соединения, она увеличилась в более чем два раза. [4]
Проблемы вызваны сложностью построения маршрутов на крупных сегментах подконтрольных сетей, в которых количество подключенных передающих устройств больше 300 штук.
Теория построения кратчайших путей на графах имеет огромное влияние на современный мир. Благодаря своему широкому спектру предоставляемых возможностей, она в последнее время интенсивно развивается: вместе с улучшением уже разработанных методов изобретаются принципиально новые.
Поиск путей является важной задачей, которую используют в различных областях и сферах. Правильно рассчитанный маршрут, может сэкономить средства на единичную или групповую доставку, большой объём данных будет быстрее доставлен пользователю, искусственный интеллект в компьютерных играх покажет более интересное поведение и маршрут для вашего автомобиля будет построен эффективно с точки зрения затраченного времени на путь.
Проблемой поиском путей начали заниматься ещё в XIX веке. Тогда появилась первая задача по поиску путей - задача Коммивояжёра. Сегодня эта задача является классической для комбинаторики и поиска маршрутов.
Начиная с 1969 года компьютерные сети начали развиваться. Изначально в самой первой сети под название ARPANET было соединено 4 суперкомпьютера того времени. Благодаря этой сети была опробована маршрутизация пакетов с помощью протокола IP, который используется и по сей день. Начиная с 1990 года появилась всемирная паутина, которая соединила между собой самые удалённые уголки мира. [2]
Начиная с 1990 года сложность компьютерных сетей растёт в геометрической прогрессии становясь всё более объёмными и запутанными. В современных компьютерных сетях поиск пути осуществляется на два шага вперёд, потому что полный поиск пути может занять огромное количество времени, однако такой «быстрый» поиск не позволяет всегда построить самый оптимальный и быстрый маршрут [17]. Из-за возросшей сложности современных сетей им на смену разрабатывают программно- конфигурируемые сети суть, которых заключается в том, чтобы вынести логику построения маршрутов из передающих устройств и оставить устройствам только саму передачу данных. Для того, чтобы это реализовать необходимо использовать быстрый и эффективный алгоритм построения маршрута, который будет учитывать нагрузку на каждое отдельное устройство, чтобы добиться максимальной производительности сети.
Актуальность разработки эффективного алгоритма оптимизации трафика для программно-конфигурируемых сетей обусловлена нежеланием части игроков ИТ рынка переходить на новое поколение сетей в связи с большими задержками при создании соединений. Поэтому сейчас очень важно разработать быстрый и эффективный алгоритм для построения маршрута с помощью которого задержки при создании нового соединения существенно снизятся.
Исходя из вышесказанного, целью выпускной квалификационной работы является исследование алгоритмов построения маршрутов, разработка и оптимизация их скорости выполнения для программно-конфигурируемых сетей.
В ходе работы были поставлены следующие задачи:
1) Анализ проблем построения маршрутов в программно- конфигурируемых сетях;
2) Выбор инструментальных средств для реализации алгоритма, эмуляции и тестирования реализованного алгоритма на базе программно- конфигурируемых сетей;
3) Разработка и реализация алгоритма, тестирование на
эмулированном сегменте программно-конфигурируемой сети;
4) Апробация алгоритма;
В 1 главе «Анализ проблем построения маршрутов в программно- конфигурируемых сетях» будет произведён анализ программно- конфигурируемых сетей, их слабые места и недостатки построения маршрутов внутри сложных сегментов сети. Также будет произведено обоснование выбора среды разработки, эмулятора программно-конфигурируемой сети для отладки и сетевой операционной системы.
Во 2 главе «Проектирование и реализация» будет произведено проектирование и реализация алгоритма.
В 3 главе «Апробация алгоритма» приведены данные о результатах проведённых испытаний относительно производительности разработанного алгоритма и сравнения с его аналогами.
В заключении сделан вывод о степени достижения поставленных целей и задач.
Целью выпускной квалификационной работы является исследование алгоритмов построения маршрутов, разработка и оптимизация их скорости выполнения для программно-конфигурируемых сетей. Для достижения указанной цели перед работой был поставлен ряд задач.
При решении задачи «Анализ проблем построения маршрутов в программно-конфигурируемых сетях» в работе была изучена проблема, важность и актуальность данного направления. В ходе изучения было установлено, что такая задача является проблемной и её необходимо решать.
При решении задачи «Выбор инструментальных средств для реализации алгоритма, эмуляции и тестирования реализованного алгоритма на базе программно-конфигурируемых сетей» был произведён подробный анализ различных сред для разработки программного обеспечения, сетевых операционных систем для ПКС, различных систем эмуляции. В результате подробного анализа было выявлено, что для использования в работе подходит среда разработки Eclipse CDT, сетевая ОС RUNOS и эмулятор Mininet.
При решении задачи «Разработка и реализация алгоритма, тестирование на эмулированном сегменте программно-конфигурируемой сети» была произведена разработка оптимизированного алгоритма Дейкстры, с помощью упрощённых структур хранения и усечения лишних шагов алгоритма в рамках ПКС. После этого была произведена настройка эмулятора Mininet и настройка RUNOS для взаимодействия с эмулированным сегментом сети, для отладки и тестирования корректности работы.
При решении задачи «Апробация алгоритма» были произведены исследования работоспособности алгоритма на базе эмулированных сегментов сети различного размера, для выявления преимуществ и недостатков разработанного оптимизированного алгоритма.
Таким образом, задачи были решены полностью, цель была достигнута.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
