Математическое и программное обеспечение адаптивной маршрутизации и балансировки потоков данных в программно-конфигурируемых сетях с обеспечением качества сетевых сервисов Перепелкин Дмитрий Александрович

Содержание к диссертации

Введение

Глава 1 Анализ состояния и перспективы развития программно – конфигурируемых сетей (ПКС) 24

1.1 Основные предпосылки к появлению ПКС и особенности их эволюции.24

1.1.1 Сильные и слабые стороны ранних конфигурируемых сетей 25

1.1.2 Переход к парадигме ПКС .29

1.1.3 Появление современных ПКС 32

1.2 Парадигма и приложения ПКС 34

1.2.1 Архитектура и основные конструктивные блоки ПКС 34

1.2.2 Интерфейсы программирования ПКС 42

1.2.2.1 Южный API-интерфейс контроллера ПКС .42

1.2.2.2 Северный API-интерфейс контроллера ПКС 43

1.2.3 Особенности коммутаторов ПКС 44

1.2.4 Особенности контроллеров ПКС 47

1.2.4.1 Централизация управления в ПКС 47

1.2.4.2 Обзор контроллеров ПКС на основе протокола OpenFlow .50

1.3 Влияние ПКС на научную и производственную сферу 57

1.3.1 Обзор попыток стандартизации ПКС 57

1.3.2 ПКС в промышленности в России и в мире 59

1.3.3 Перспективы развития ПКС 64

1.4 Параметры качества сетевых сервисов 67

1.4.1 Классы качества сетевых сервисов .68

1.4.2 Классификация сетевых механизмов качества сервиса 73

1.5 Архитектуры качества сетевых сервисов 75

1.5.1 Архитектура IntServ .79

1.5.2 Архитектура DiffServ .80

1.6 Основные возможности протокола OpenFlow 83

Основные результаты и выводы 108

Глава 2 Основные принципы маршрутизации в ПКС .110

2.1 Цели и задачи маршрутизации в ПКС .110

2.2 Методы маршрутизации в ПКС 117

2.3 Критерии и метрики качества сетевых сервисов 119

2.4 Алгоритмы адаптивной маршрутизации в ПКС .124

2.4.1 Алгоритм Дейкстры .124

2.4.2 Алгоритм Йена 131

2.5 Алгоритмы многопутевой QoS-маршрутизации в ПКС. 136

2.5.1 MCP QoS-маршрутизация .137

2.5.2 MCOP QoS-маршрутизация 142

2.5.3 CSP QoS-маршрутизация .148

2.5.3.1 Упрощенная задача CSP QoS-маршрутизации 148

2.5.3.2 Двойственная задача CSP QoS-маршрутизации 149

2.5.4 LARAC QoS-маршрутизация 150

2.6 Алгоритмы сегментации структур ПКС для адаптивной маршрутизации 157

2.6.1 Алгоритм бинарного деления .159

2.6.2 «Жадный» алгоритм сегментации 163

2.6.3 Алгоритм Гирвана – Ньюмана 166

Основные результаты и выводы .169

Глава 3 Методы и алгоритмы адаптивной маршрутизации в ПКС .172

3.1 Метод и алгоритм парных переходов в ПКС 175

3.2 Метод и алгоритм парных переходов в условии динамических подключений узлов и каналов связи ПКС 195

3.3 Метод и алгоритм парных переходов в условии динамических отказов узлов и каналов связи ПКС 208

3.4 Метод и алгоритм парных перестановок маршрутов в ПКС 221

3.5 Метод и алгоритм сегментации структур ПКС для адаптивной маршрутизации 236

Основные результаты и выводы 250

Глава 4 Метод и алгоритм балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов .253

4.1 Концептуальная модель и метод балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов 254

4.2 Алгоритм балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов 260

Основные результаты и выводы 277

Глава 5 Программное обеспечение адаптивной маршрутизации и балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов 278

5.1 Программная инфраструктура распределенной обработки и передачи потоков данных в ПКС на основе протокола OpenFlow .278

5.1.1 Пользовательский интерфейс 279

5.1.2 Графический редактор .280

5.1.3 Дополнительные настройки визуальной среды 281

5.1.4 Управление проектом 282

5.1.5 Генератор сценариев на языке Python для запуска топологии в MiniNet 285

5.1.6 Модуль визуализации результатов работы контроллера ПКС 287

5.1.7 Виртуальная среда и эмулятор MiniNet .288

5.2 Программное обеспечение адаптивной маршрутизации в ПКС .289

5.2.1 Исследование алгоритма Дейкстры в ПКС 289

5.2.2 Исследование комбинированного алгоритма Дейкстры и сегментации в ПКС .294

5.2.3 Исследование алгоритма Йена в ПКС 298

5.2.4 Исследование комбинированного алгоритма Йена и сегментации в ПКС 301

5.2.5 Исследование алгоритма парных переходов в ПКС .303

5.2.6 Исследование комбинированного алгоритма парных переходов и сегментации в ПКС 306

5.2.7 Анализ результатов работы алгоритмов адаптивной маршрутизации в ПКС 308

5.3 Программное обеспечение балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов 314

5.3.1 Исследование алгоритма Йена с модулем TE и алгоритма балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов 314

5.3.2 Анализ результатов работы алгоритмов балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов 317

Основные результаты и выводы 323

Заключение 326

Список литературы 334

Приложение 1 Копии актов о внедрении. 360

Приложение 2 Копии свидетельств о регистрации программ для ЭВМ в РОСПАТЕНТ 384

Приложение 3 Копии наград и отраслевых сертификатов .402

Приложение 4 Основные термины протокола OpenFlow .416

Приложение 5 Листинг программного обеспечения .419

• Архитектура и основные конструктивные блоки ПКС
• Метод и алгоритм парных переходов в ПКС
• Алгоритм балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов
• Анализ результатов работы алгоритмов балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов

Введение к работе

Актуальность темы и ее значимость. Развитие современных компьютерных сетей (КС) сопровождается непрерывной сменой сетевых технологий, направленной на повышение быстродействия и надежности сетей, возможностей интегрированной передачи данных, голоса и видеоинформации. Обеспечение высокоскоростного и надежного обмена информацией между узлами КС при жестких требованиях к задержкам передачи информации в условиях возможных всплесков трафика в каналах связи является одной из важнейших проблем. Для повышения качества сетевых сервисов (Quality of Service, QoS) необходимо использовать эффективные модели и алгоритмы адаптивной маршрутизации, которые непосредственно влияют на значения ключевых QoS-параметров: пропускной способности, средней задержки передачи, джиттера, значения отклонения от длины оптимального маршрута. Особую важность имеет эффективная маршрутизация пакетов данных в условиях динамических подключений и отказов отдельных элементов сети, всплесков трафика и локальных перегрузок. В связи с этим особое значение приобретают подходы по внедрению и поддержке решений быстрой перемаршрутизации и балансировки нагрузки, использованию композитных метрик линий связи, максимально учитывающих численные значения различных QoS-параметров, а также обеспечению масштабируемости маршрутных решений, т. е. способности сохранить в заданных пределах свою эффективность в условиях роста территориальной распределенности сети связи, числа и типов обслуживаемых трафиков пользователей.

Традиционная архитектура КС требует больших ресурсов для обеспечения потребностей по передаче растущих объемов трафика для большого числа устройств. Принципы, положенные в основу классической архитектуры, позволили обеспечить функционирование сетей в условиях ограниченной пропускной способности каналов связи и ненадежных соединений. Основным ограничением существующих КС является неполная совместимость сетевых решений и зависимость от производителя телекоммуникационного оборудования. Развитие в последнее время технологии программно-конфигурируемых сетей (ПКС) позволяет устранить данные ограничения и обеспечить гибкость в управлении потоками данных за счет разделения плоскости управления и передачи данных. Основная идея ПКС состоит в том, чтобы, не изменяя существующего сетевого оборудования отделить управление маршрутизаторами и коммутаторами за счет создания специального программного обеспечения, которое находится под контролем администратора сети. Внедрение ПКС упрощает сетевые элементы плоскости передачи данных за счет логической централизации управления сетью. Концепция ПКС позволяет выполнить переход от отдельных сетевых элементов и сети, к платформам в целом. Управление сетевыми потоками происходит с помощью приложений, которыми можно оптимизировать потоки, чтобы найти оптимальный маршрут, а также сконфигурировать сеть для мак-

симального использования связей и числа пользователей. Архитектура ПКС состоит из множества программных приложений и аппаратных коммутаторов, подключенных к общему контроллеру, реализованных в виде обычного сервера со специальным программным обеспечением. Для управления потоками данных между сетевыми устройствами и контроллером применяется протокол OpenFlow. OpenFlow представляет собой интерфейс, который соединяет коммутаторы ПКС с управляющим контроллером. С помощью этого интерфейса контроллер осуществляет конфигурацию и управление коммутаторами, получает от него отчеты и отправляет ему пакеты данных.

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

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

В диссертационной работе предлагается разработка комплексного научно-методического подхода и создание программной инфраструктуры для организации сетевого взаимодействия и глобально распределенной обработки и передачи потоков данных в ПКС на основе протокола OpenFlow. Задача создания гибкой и быстро перепрограммируемой сетевой инфраструктуры является актуальной и может быть решена на основе разработки и создания специализированного математического и программного обеспечения, программных инструментов адаптивной маршрутизации и балансировки потоков данных в ПКС.

Актуальность темы диссертации подтверждается тем, что она выполнялась при финансовой поддержки грантов Президента РФ для молодых российских ученых – кандидатов наук МК-819.2014.9 «Разработка и развитие моделей, алгоритмов и технологии динамического управления маршрутами передачи данных программно-конфигурируемых телекоммуникационных сетей» (2014-2015) и МК-6016.2016.9 «Разработка и развитие методов, алгоритмов и технологии динамического управления сетевыми ресурсами и потоками данных в программно-конфигурируемых телекоммуникационных сетях на основе виртуализации сетевых функций» (2016-2017), гранта РФФИ № 16-47-620300 р_а «Разработка и развитие моделей, методов и алгоритмов многопутевой адаптивной маршрутизации и балансировки потоков данных программно-конфигурируемых компьютерных сетей с обеспечением качества обслуживания сетевых сервисов» (2016-2018) и гранта Фонда содействия инновациям по программе «СТАРТ» № 1586ГС1/24270 «Разработка комплекса программных приложений виртуализации сетевой инфраструктуры и сетевых сервисов IT-компаний» (2016-2018).

Научные результаты диссертационной работы отмечены на региональном и всероссийской уровне различными наградами: дипломом и премией Губернатора Рязанской области № 18 молодым ученым и специалистам в области науки и инноваций за высокие результаты в научно-исследовательской и инновационной деятельности (2013 г.), дипломом за 2 место в номинации «Молодой ученый года» среди молодых ученый и специалистов по направлению физико-технические науки (2014 г.), почетным знаком Губернатора Рязанской области «За усердие» (2014 г.), сертификатом эксперта Российской академии наук (РАН) № 2016-01-7830-0299 (2016 г.).

Современное состояние исследований в данной области. Проблемами совершенствования методов и алгоритмов маршрутизации в КС занимались такие ученые, как D.P. Bertsekas, Д. Филипс, А. Гарсиа-Диас, P. Gupta, А.Б. Гольдштейн, Б.С. Гольдштейн, О.Я. Кравец, Д.В. Куракин, И.П. Норенков, В.А. Трудоношин, S. Floyd, L.R. Ford, D.R. Fulkerson и другие. Задачу нахождения кратчайших путей в транспортной системе рассматривали в своих трудах ученые E.W. Dijkstra, R. Bellman, Г. Габов, С. Гудман, В.А. Евстигнеев, В.Н. Касьянов, Р. Седжвик, Р.Э. Тарьян, S. Floyd, L.R. Ford, D.R. Fulkerson. Подробное описание методов поиска кратчайших путей можно найти в работах Т. Кормена, Ч. Лейзерсона и Р. Ривеста. Заметный вклад в разработку методов, алгоритмов и программного обеспечения управления многопотоковым трафиком в КС внесли В.М. Вишневский, Г.П. Захаров, В.П. Корячко, А.П. Шибанов, Е.В. Никульчев, P. Merindol, В.В. Поповский, А.В. Лемешко, В.В. Кореньков, Я.А. Коган, В.И. Борисов и многие другие ученые. Вопросы разработки и развития технологии ПКС изложены в работах N. McKeown, T. Anderson, G. Parul-kar, L. Peterson, J. Rexford. Результаты разработки и исследования сетевых операционных систем (СОС) для ПКС отражены в работах M. Casado, S. Shenker, A. Tavakoli, T. Koponen. Развитие методов, алгоритмов и программных систем управления потоками данных с обеспечением качества сервиса в ПКС подробно

рассматривается в работах Р.Л. Смелянского, В.Н. Тарасова, Н.Ф. Бахаревой, В.Г. Карташевского, В.А. Соколова, Ю.Л. Леохина, H. Egilmez, Ian F. Akyildiz, Pu Wang и Min Luo.

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

Для достижения поставленной цели необходимо решить следующие

основные задачи:

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

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

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

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

5. Разработать концептуальную модель и эффективный метод и алгоритм балансировки потоков данных в ПКС, которые позволят повысить быстродействие, эффективность и надежность процессов обработки и передачи потоков данных, а также обеспечат требуемое качество сетевых сервисов по сравнению с известными аналогами.

6. Разработать программную инфраструктуру и визуальную среду для глобально распределенной обработки и передачи потоков данных в ПКС на основе

протокола OpenFlow, которая позволит повысить эффективность и надежность функционирования ПКС, а также обеспечит требуемое качество сетевых сервисов.

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

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

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

Научная новизна диссертационной работы заключается в том, что впервые разработаны эффективные модели, методы, алгоритмы, программное обеспечение и программные инструменты адаптивной маршрутизации и балансировки потоков данных в ПКС на основе протокола OpenFlow в условии динамических изменений метрик каналов связи и структуры сети, которые позволяют получить меньшую вычислительную сложность [O(N) и O(N²) соответственно, где N – число узлов или коммутаторов ПКС] построения таблиц коммутации потоков данных по сравнению с известными аналогами и обеспечить требуемое качество сетевых сервисов. Научная новизна сформулирована в положениях, изложенных ниже:

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

2. Метод и алгоритм парных переходов в ПКС на основе протокола OpenFlow в условии динамических изменений метрик каналов связи и структуры сети, позволяющие получить меньшую вычислительную сложность [O(kN), где k – число парных переходов] построения таблиц коммутации потоков данных по сравнению с известными аналогами.

3. Метод и алгоритм парных перестановок маршрутов в ПКС на основе протокола OpenFlow в условии динамических изменений метрик каналов связи, позволяющие получить меньшую вычислительную сложность O(N) построения таблиц коммутации потоков данных по сравнению с известными аналогами.

4. Эффективный метод и алгоритм сегментации структур ПКС на основе протокола OpenFlow с учетом данных о структуре базовой сети и связности каналов связи, позволяющие получить меньшую вычислительную сложность по-

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

5 Концептуальная модель, эффективный метод и алгоритм балансировки
потоков данных в ПКС на основе протокола OpenFlow с вычислительной слож
ностью O(N²), позволяющие повысить быстродействие, эффективность и на
дежность процессов обработки и передачи потоков данных, а также обеспечить
требуемое качество сетевых сервисов по сравнению с известными аналогами.

6. Программная инфраструктура и визуальная среда для организации глобально распределенной обработки и передачи потоков данных в ПКС на основе протокола OpenFlow, позволяющая повысить эффективность и надежность функционирования ПКС, а также обеспечить требуемое качество сетевых сервисов.

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

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

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

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

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

В рамках диссертационной работы разработана программная инфраструктура и визуальная среда SDNTopology для организации сетевого взаимодействия и глобально распределенной обработки и передачи потоков данных в ПКС на основе протокола OpenFlow, реализующая разработанные методы и алгоритмы адаптивной маршрутизации и балансировки потоков данных с обеспечением качества сетевых сервисов. Программная инфраструктура предназначена для динамического конфигурирования сетевых топологий и их маршрутов передачи данных с учетом различных QoS-показателей и QoS-метрик в режиме реального времени. SDNTopology доступна на платформах Linux и Windows и включает ряд полезных и ключевых особенностей:

1. графический редактор;

2. генератор сценариев на языке Python для запуска топологии в MiniNet;

3. модуль визуализации результатов работы контроллера OpenFlow;

4. возможность загрузки и сохранения проектов в формате .xml;

5. панели быстрого доступа;

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

следующих функций:

7. создание и визуальное проектирование графовых моделей ПКС;

8. динамическое конфигурирование ПКС с использованием алгоритмов адаптивной одноадресной маршрутизации (unicast routing) и многоадресной маршрутизации (multicast routing) в ПКС;

9. проведение экспериментов по изменению метрик каналов связи и параметров ПКС (пропускной способности, задержки передачи, проценту потерь пакетов), по подключению и отказу узлов и каналов связи с последующим построением дерева оптимальных маршрутов;

10. проведение экспериментов по сегментации структур ПКС для адаптивной маршрутизации;

11. балансировка потоков данных в ПКС с обеспечением качества сетевых сервисов на основе различных QoS-показателей и QoS-метрик;

12. экспорт данных в среду MiniNet;

7) оценка трудоемкости разработанных алгоритмов.
Основные положения, выносимые на защиту. На защиту выносятся

следующие результаты диссертационной работы:

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

2 Метод и алгоритм парных переходов в ПКС на основе протокола
OpenFlow в условии динамических изменений метрик каналов связи и структу-

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

3. Метод и алгоритм парных перестановок маршрутов в ПКС на основе протокола OpenFlow в условии динамических изменений метрик каналов связи, позволяющий получить меньшую вычислительную сложность O(N) построения таблиц коммутации потоков данных по сравнению с известными аналогами.

4. Метод и алгоритм сегментации структур ПКС на основе протокола OpenFlow с учетом данных о структуре базовой сети и связности каналов связи, позволяющие получить меньшую вычислительную сложность построения таблиц коммутации потоков данных по сравнению с известными аналогами при решении задачи адаптивной маршрутизации.

5. Концептуальная модель, эффективный метод и алгоритм балансировки потоков данных в ПКС на основе протокола OpenFlow с вычислительной сложностью O(N²), позволяющий повысить быстродействие, эффективность и надежность процессов обработки и передачи потоков данных, а также обеспечить требуемое качество сетевых сервисов по сравнению с известными аналогами.

6. Программная инфраструктура и визуальная среда для глобально распределенной обработки и передачи потоков данных в ПКС на основе протокола OpenFlow, позволяющая повысить эффективность и надежность функционирования ПКС, а также обеспечить требуемое качество сетевых сервисов.

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

Соответствие паспорту специальности. Проблематика, исследованная в диссертации, соответствует областям исследований 3, 8 и 9 паспорта специальности 05.13.11 – «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей».

Степень достоверности. Достоверность научных положений и практических результатов, изложенных в диссертационной работе, подтверждена:

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

экспериментальными данными, полученными с привлечением результатов исследований и научных положений, разработанных автором;

разработкой действующего программного обеспечения адаптивной маршрутизации и балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов, подтвержденного соответствующими свидетельствами о регистрации программы для ЭВМ в РОСПАТЕНТ (ФГУ «ФИПС»);

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

фундаментальных и прикладных исследований, проводимых в ФГБОУ ВО «Рязанский государственный радиотехнический университет» по НИР 34-09Г «Доработка и апробация компоненты организационно-методической и информационной поддержки системы качества деятельности образовательного учреждения, ориентированных на кадровое обеспечение высокотехнологичной отрасли экономики» (исполнитель, 2010-2012), НИР 15-09Г «Разработка и развитие моделей, методов и технологии создания открытой информационно-образовательной среды для дистанционной подготовки, переподготовки и повышения квалификации специалистов в области создания ИПИ (CALS) и CASE технологий» (исполнитель, 2009-2011), НИР 1-12Г «Разработка и создание интеллектуального автоматизированного комплекса управления ресурсами в динамических информационно-телекоммуникационных системах» (ответственный исполнитель, 2011-2012), НИР 2-14Г «Разработка и развитие моделей, алгоритмов и технологии динамического управления маршрутами передачи данных программно-конфигурируемых телекоммуникационных сетей» по гранту Президента РФ для государственной поддержки молодых российских ученых – кандидатов наук МК-819.2014.9 (руководитель, 2014-2015), НИР 9-14Г «Разработка методов и прорывных технологий обработки, распространения и использования аэрокосмических изображений в интересах развития экономики регионов Российской Федерации» (исполнитель, 2014-2016), НИР 5-16Г «Разработка и развитие методов, алгоритмов и технологии динамического управления сетевыми ресурсами и потоками данных в программно-конфигурируемых телекоммуникационных сетях на основе виртуализации сетевых функций» по гранту Президента РФ для государственной поддержки молодых российских ученых – кандидатов наук МК-6016.2016.9 (руководитель, 2016-2017), НИР 7-16Г «Разработка и развитие моделей, методов и алгоритмов многопутевой адаптивной маршрутизации и балансировки потоков данных программно-конфигурируемых компьютерных сетей с обеспечением качества обслуживания сетевых сервисов» по гранту РФФИ № 16-47-620300 р_а (руководитель, 2016-2018), НИОКР № 1586ГС1/24270 «Разработка комплекса программных приложений виртуализации сетевой инфраструктуры и сетевых сервисов IT-компаний» по гранту ФГБУ «Фонд содействия развитию малых форм предприятий в научно-технической сфере» по программе «СТАРТ» (руководитель, 2016-2018), НИР 2-17Г «Разработка интеллектуальных методов и технологий передачи, хранения и обработки информации в системах телекоммуникаций, технического зрения и аэрокосмического наблюдения Земли» (исполнитель, 2017-2019).

Результаты, полученные в диссертационной работе, внедрены на следующих предприятиях и в организациях: ФГБОУ ВО «Поволжский государственный университет телекоммуникаций и информатики» (ПГУТИ) (г. Самара); АО «Государственный Рязанский приборный завод» (ГРПЗ) (г. Рязань); ФГБУ Национальный исследовательский центр «Курчатовский институт» (НИЦ КИ) (г. Москва); филиал АО «Ракетно-космический центр «Прогресс» – ОКБ

«СПЕКТР» (г. Рязань); ФГКВОУ ВО «Военная академия связи имени Маршала Советского Союза С.М. Буденного» (г. Санкт-Петербург); ФГКВОУ ВО «Академия Федеральной службы охраны Российской Федерации» (Академия ФСО РФ) (г. Орел); Рязанское отделение ПАО «МЕГАФОН» (г. Рязань); АО «Рязанский радиозавод» (г. Рязань); Муромский институт (филиал) ФГБОУ ВО «Владимирский государственный университет им. А.Г. и Н.Г. Столетовых» (МИ ВлГУ) (г. Муром); ФГБОУ ВО «Рязанский государственный радиотехнический университет» (РГРТУ) (г. Рязань); ФГАОУ ВО «Казанский (Приволжский) федеральный университет» (КФУ) (г. Казань); ООО «НПП ЭТРА-Плюс» (г. Москва); ООО «Энлинк Телекоммуникации» (Nlink) (г. Рязань); ООО «ИнтерТелеком» (WestCall Telecommunications) (г. Рязань).

Использование результатов диссертационной работы на практике подтверждено соответствующими актами о внедрении и использовании. Получено 17 авторских свидетельств о регистрации программ для ЭВМ в ФГБУ «Федеральный институт промышленной собственности» (РОСПАТЕНТ).

Апробация результатов диссертации. Основные результаты диссертационной работы докладывались и обсуждались на следующих всероссийских и международных научных конференциях и семинарах: XII, XV, XVI, XVII, XVIII, XIX, XX, XXI Всероссийских научно-технических конференциях студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях (НИТ)» (г. Рязань, 2007, 2010, 2011, 2012, 2013, 2014,

2015. 2016); XVII, XIX, XX, XXI Всероссийских научно-методических конференциях «Телематика» (г. Санкт-Петербург, 2010, 2012, 2013, 2014); 13 и 14-ой Международных телекоммуникационных конференциях студентов и молодых ученых «Молодежь и наука» (г. Москва, 2010, 2011); 16, 17 и 18-ой Международных научно-технических конференциях «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2010, 2012, 2015); I и II Международных научно-практических конференциях «Стратегия управления: государство, бизнес и образование» (г. Рязань, 2010, 2011); XXI Всероссийском совещании по проблемам управления (ВСПУ) (г. Москва, ИПУ РАН, 2014); XI Международной научно-технической конференции «Новые информационные технологии и системы (НИТиС)» (г. Пенза, 2014); Международной научно-технической конференции «Радиоэлектронные устройства и системы для инфокоммуникационных технологий (REDS)» (г. Москва, 2015); I и II Международных научных форумах молодых ученых «Наука будущего – наука молодых» (г. Севастополь, 2015; г. Казань, 2016); 8-ой Всероссийской мульти-конференции по проблемам управления (г. Ростов-на-Дону, 2015); XXVIII Международной научной конференции «Математические методы в технике и технологиях» (г. Рязань, 2015); Международной научно-технической конференции «Перспективные информационные технологии (ПИТ)» (г. Самара, 2016, 2017); I и II Международных научно-технических и научно-методических конференциях «Современные технологии в науке и образовании (СТНО)» (г. Рязань,

2016. 2017); Всероссийской научно-технической конференции «Интеллекту-

альные и информационные системы (Интеллект)» (г. Тула, 2016); Научном семинаре лаборатории технологий больших данных для проектов в области «МЕГАСАЙНС» (г. Москва, ФГБУ НИЦ «Курчатовский институт», 2016); I Международной молодежной научной школе по распределенным гетерогенным вычислительным инфраструктурам (International School on Heterogeneous Computing Infrastructure) (г. Томск, 2016); 11th IEEE International Conference ELEKTRO (Strbske Pleso, Slovak Republic, 2016); IEEE International Siberian Conference on Control and Communications (SIBCON) (Moscow, Russian Federation, 2016); 5th and 6th IEEE Mediterranean Conference on Embedded Computing (ME-CO) (Bar, Montenegro, 2016, 2017); 1th and 2nd IEEE Conference on Quality Management, Transport and Information Security, Information Technologies (IT&MQ&IS) (Nalchik, Russian Federation, 2016; Saint Petersburg, 2017); 27th IEEE International Conference Radioelektronika (Brno, Czech Republic, 2017); 3-м заседании Консорциума университетов «ПКС – технологии в научно-образовательной среде» (г. Москва, МГУ, 2017).

Публикации. По теме диссертации опубликовано 158 печатных работ, в том числе: 2 монографии; 36 статей в изданиях из Перечня ведущих рецензируемых научных журналов и изданий ВАК; 16 статей в изданиях, входящих в международные базы научного цитирования Web of Science и Scopus; 35 статей в научно-технических журналах и межвузовских сборниках научных трудов; 52 доклада на международных и всероссийских научных конференциях; 17 авторских свидетельств о регистрации программы для ЭВМ в ФГБУ «Федеральный институт промышленной собственности» Федеральной службы по интеллектуальной собственности, патентам и товарным знакам (ФГБУ «ФИПС», РОСПАТЕНТ).

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

Структура и объем диссертации. Диссертационная работа состоит из введения, 5 глав, заключения, списка литературы, 5 приложений, изложенных на 443 страницах (включая 156 рисунков и 22 таблицы). Список литературы содержит 258 наименований.

Архитектура и основные конструктивные блоки ПКС

В настоящее время традиционная архитектура КС требует больших ресурсов для обеспечения потребностей по передаче растущих объемов трафика для большого числа устройств. Она позволяет решать широкий круг задач по организации обмена данными, обеспечивая развитие информационного общества. Принципы, положенные в основу классической архитектуры, позволили обеспечить функционирование сетей в условиях ограниченной пропускной способности каналов связи и ненадежных соединений. Для традиционной архитектуры КС в обычном Интернет-маршрутизаторе одновременно реализуются и управление и передача данных. Уровень управления представлен встроенным контроллером, уровень передачи данных – таблицей маршрутизации и коммутационной матрицей. Маршрутизатор обладает некоторыми интеллектуальными функциями, позволяющими ему самому принимать решения о передаче данных на основе информации о структуре сети. Но непосредственно управлять принятием решения нельзя – можно лишь конфигурировать контроллер, задавая определенные наборы правил и приоритетов. Это значительно ограничивает функциональность маршрутизатора и всей сети. Структура и функции Интернет-маршрутизатора классической архитектуры КС приведены на рис. 1.3 и 1.4.

Также стоит отметить основные недостатки классической архитектуры КС:

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

2. В архитектуре современных сетей имеются, существенные барьеры для экспериментирования и создания новых сервисов.

3. Сети связи сложны в обслуживании, для их функционирования используется более 100 протоколов, и настройка сетевых устройств осуществляется индивидуально, а это не эффективно с точки зрения технической эксплуатации.

Сложность в обслуживании таких сетей сочетается зачастую с неполной совместимостью сетевых решений, что влечет за собой зависимость от производителей оборудования. Несоответствие потребностей клиентов и предлагаемых на рынке решений привело к появлению новых концепций построений и организации работы сетей передачи данных – программно-конфигурируемые сети (Software Defined Networks, SDN) и виртуализация сетевых функций (Network Function Virtualization, NFV) на основе протокола OpenFlow [198]. Основная идея ПКС на основе протокола OpenFlow (OF) состоит в том, чтобы, не изменяя существующего сетевого оборудования отделить управление этим оборудованием (маршрутизаторами и коммутаторами) за счет создания специального программного обеспечения, которое может работать на обычном отдельном компьютере и находится под контролем администратора сети. Вследствие такого подхода становится возможным существенное упрощение сетевых элементов плоскости передачи данных и логическая централизация управления сетью. Заинтересованность IT-компаний в ПКС вызвана тем, что такие технологии позволяют повысить эффективность сетевого оборудования на 25–30%, снизить на 30% затраты на эксплуатацию сетей, повысить безопасность и предоставить пользователям возможность программно создавать новые сервисы и оперативно загружать их в сетевое оборудование, вследствие чего, можно уменьшать нагрузку на отдельные элементы сети. Структура и функции коммутатора ПКС на основе протокола OpenFlow приведены на рис. 1.5 и 1.6.

Интернет-маршрутизатора с поддержкой протокола OpenFlow Теоретически ПКС дает возможность абсолютной гибкости в управлении трафиком, а так же обеспечивает легкую балансировку трафика без использования отдельного специализированного оборудования. Также ПКС обеспечивает независимость функций высокоуровневого управления от аппаратного обеспечения, за счет чего ускоряются процессы передачи и обработки данных. В ПКС вся интеллектуальная часть реализуется на центральном сервере или контроллере, что упрощает выполнение сложных операций. Идея заключается в использовании для управления такими сетями стандартных серверов или контроллеров, работающих отдельно от сетевых устройств, благодаря чему сетевые администраторы могут получать более детализированный контроль над трафиком. Централизация ПКС избавила разработчиков анализаторов конфигураций сети от необходимости самостоятельно собирать комплекс данных о ее состояния – контроллер осуществляет централизованное управление всеми коммутационными устройствами сети, и заведомо способен предоставить всю необходимую для этого информацию. Одновременно с этим явное выделение контура данных позволило получить доступ непосредственно к правилам обработки пакетов, которые в сетях с традиционной архитектурой приходилось выводить на основании настроек служебных протоколов самостоятельно.

Технология ПКС на основе протокола OpenFlow предлагает отказаться от такой тенденции развития КС, выполнив переход от отдельных сетевых элементов и сети, к платформам в целом. Управление сетевыми потоками происходит с помощью приложений, которыми можно оптимизировать потоки, чтобы найти кратчайший путь, как это делают современные распределенные протоколы маршрутизации, а также оптимизировать сеть для максимального использования связей.

Архитектуру ПКС можно представить, как множество простых программ и аппаратных коммутаторов, подключенных к общему контроллеру (Контроллер OpenFlow), реализованных в виде обычного сервера со специальным программным обеспечением (ПО). На рис. 1.8 представлена архитектура ПКС на основе протокола OpenFlow.

Архитектура ПКС на основе протокола OpenFlow состоит из трех уровней:

1. Инфраструктурный уровень (ИУ), состоящий из набора сетевых устройств (коммутаторов и каналов передачи данных);

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

3. Уровень сетевых сервисов (УСС), включающий приложения, позволяющие более гибко и эффективно управлять сетью.

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

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

Далее расположен уровень управления, содержащий объект, называемый контроллером. Этот объект инкапсулирует сетевую логику и отвечает за предоставление программного интерфейса в сети, который используется для реализации новых функций и выполнения различных задач управления. Уровень управления ПКС полностью отделен от сетевого устройства и считается централизованным логически, в то время как физически он может быть либо централизованным, либо децентрализованным, находящимся на одном или нескольких серверах, которые управляют сетевой инфраструктурой в целом. Вся интеллектуальная часть высокоуровневой маршрутизации реализована на контроллере. За счет переноса логики в центральный узел коммутаторы разгружаются и могут более эффективно использовать вычислительные мощности для выполнения низкоуровневых операций с трафиком. Централизованное управление позволяет мониторить состояние компьютерной сети и управлять множеством ее параметров из единого узла. Самой главной возможностью архитектуры ПКС на основе протокола OpenFlow, является возможность программно управлять потоками данных.

Для управления потоками данных между сетевыми устройствами и контроллером применяется управляющий протокол OpenFlow. Протокол OpenFlow реализует независимый от производителя интерфейс между логическим контроллером сети и сетевым транспортом и является одной из реализаций концепции ПКС, а также считается движущей силой ее распространения и популяризации. OpenFlow – протокол управления процессом обработки данных, передающихся по СПД маршрутизаторами и коммутаторами, реализующий технологию ПКС. Протокол используется для управления сетевыми устройствами с центрального устройства – контроллера сети (например, с сервера или даже персонального компьютера). Это управление заменяет или дополняет работающую на коммутаторе (маршрутизаторе) встроенную программу, осуществляющую построение маршрута, создание карты коммутации и т.д. Контроллер используется для управления таблицами потоков коммутатора, на основании которых принимается решение о передаче принятого пакета на конкретный порт коммутатора. Таким образом, в сети формируются прямые сетевые соединения с минимальными задержками передачи данных и необходимыми параметрами.

Метод и алгоритм парных переходов в ПКС

Представим ПКС в виде неориентированного взвешенного связного графа Network = (Nodes, Links, Weights), где Nodes = (Controllers, Switches, Hosts), Controllers - множество контроллеров ПКС, Controllers = С, Switches - множество вершин или коммутаторов ПКС, Switches = N, Hosts -множество хостов или конечных узлов, Hosts = Н, Links - множество ребер или каналов связи, Links = Е, Weights - множество весов и метрик каналов связи (стоимость каналов связи, пропускная способность, задержка передачи, процент потери пакетов или композитная метрика).

Пусть на графе Network в некоторый момент времени уже решена задача поиска оптимальных маршрутов до всех коммутаторов множества N$=N\NS из начальной вершины Ns , т. е. построено дерево оптимальных маршрутов с корнем в вершине Ns. Обозначим это дерево как TN. На рис. 3.1 жирными линиями обозначено построенное дерево оптимальных маршрутов. Рассмотрим множество ребер Links графа Network. По признаку вхождения ребер в дерево TN можно разделить исходное множество Links на два подмножества: LinksTeTN и LinksRTN, LinksTuLinksR = Links.

Множество ребер дерева LinksT - множество ребер дерева TN для графа Network. Для заданного графа Network, согласно свойству дерева, мощность множества Linksi будет равняться мощности множества Switches минус единица Linksi = Switches - 1.

Множество ребер замены для дерева LinksR - множество ребер графа Network, не вошедших в дерево ТN. При соответствующих условиях некоторое ребро e eLinksR, инцидентное вершинам Nt и Nj может перейти в множество ребер дерева LinksT, заменив собой некоторое ребро e eLinksT. При этом инцидентность ребра е р вершине Ni или TV, является обязательным условием. В свою очередь ребро eitj перейдет во множество LinksR.

Будем называть такие переходы парными переходами и обозначать eij - е р.

Парные переходы возможны в двух случаях: при уменьшении веса ребра е р до некоторого порогового значения и при увеличении веса ребра e eLinksT. При этом возможен такой случай, при котором изменение веса ребра eyeLinksT повлечет за собой исключение некоторого ребра eOMeLinksT и включение в это множество ребра e eLinksR. Изменение веса ребра Єк р є Links может привести к одному или нескольким парным переходам, но может и не привести к перестановкам, вследствие чего конфигурация дерева оптимальных маршрутов не изменится. Количество парных переходов зависит от величины изменения и положения ребра в дереве оптимальных мАр 177 шрутов (для ребер ЄуЄLinksT). Любое ребро eyeLinksT может попасть в дерево ТN только посредством срабатывания парного перехода.

Маршрутная степень вершины ms(Nt) - число неповторяющихся ребер бу є Links, инцидентных вершине Nt, через каждое из которых можно построить простой маршрут между вершинами Nt и Ns.

Теорема 1. Для любого ребра e eLinksT, инцидентного некоторым вершинам Ni и TV,, маршрутные степени которых больше единицы, при заданной конфигурации графа, неизменных весах других ребер существует такое значение веса wtJ, что при wtj wtJ ребро е становится ребром замены и переходит во множество LinksR

Доказательство. Пусть riiU - текущий оптимальный маршрут с оценкой di dj. Для вершины Nt, степень которой больше единицы, следовательно, Ri 1, среди raeRi найдется такой оптимальный маршрут гі р, для которого Єц гі р. Длина маршрута rip составляет dip. Тогда при увеличении веса ребра Wij на величину, большую diiP - diiU оптимальный маршрут до вершины Nt изменится на маршрут rip. Т.е. при wtj Wij+(diyP - diu) ребро е становится ребром замены и переходит в множество LinksR В данном случае wtJ = wtj + (dUp - dUu). Теорема доказана.

Величину Wij будем называть точкой вхождения в дерево для ребра еи.

Отношение парного перехода pst - отношение соответствия элемента eitj множества LinksT элементу вк р множества LinksR, такое, что при увеличении веса ребра е так, что wtj wtJ имеет место парный переход е - е р.

Теорема 2. Для любого ребра e eLinksR, находящегося в отношении парного перехода с некоторым ребром gy-eLinksT с заданной точкой вхождения в дерево существует такое значение веса WkJ, что при Wk,p WkJ ребро Єк р становится веткой дерева ТN и переходит в множество LinksT.

Доказательство. Пусть riiU - текущий оптимальный маршрут, содержащий ребро еи. Пусть riiP - оптимальный маршрут, содержащий ребро ек,р. Из доказательства, приведенного выше, следует, что diu + (wj - wtJ) = dip. Т. е. di,u = dlp - (Wij - w ). При dUp diiU ребро eKp станет веткой дерева ТN и перей 178 дет в множество LinksT. В данном случае wkJ = wKp - (wj - wUj). Теорема доказана.

Теорема 3. Для элементов парного отношения pst е -єілпквт и e eLinksR при известной точке вхождения в дерево WiJ и wkJ справедливо, что Доказательство. Пусть ребра eUj и еКр инцидентны некоторой вершине N, т.е. к = і. Пусть оптимальный маршрут между Ns и N, содержащий etJ имеет длину diyk. Известно, что при увеличении веса ребра е до значения, превышающего wj, оптимальный маршрут до вершины Nt изменится таким образом, что будет включать в себя ребро екр и иметь длину, равную da. Т. е. dij - diyk = wj - Wij. С другой стороны, при уменьшении ребра екр до значения, меньшего wkJ оптимальный маршрут до вершины Nt изменится таким образом, что будет включать в себя ребро екр и будет иметь длину, равную diti. Т.е. da - diM = wkp - wkJ Таким образом, wj - wUj = wkp - wkJ Теорема доказана.

Следствие 1. Если для элементов парного отношения/ю,-, Linksi и e eLinksR, соответствующих весов Wij и м при известной точке вхождения в дерево изменился вес ребра е до значения w1, то WkJ = WkJ + (w1 - Wjj).

Следствие 2. Если для элементов парного отношения/ю,-, Linksi и e eLinksR, соответствующих весов Wij и м при известной точке вхождения в дерево изменился вес ребра екр до значения w2, то wj = wj + (w2 - wkp).

Теорема 4. Ребра Linksi и e eLinksR, находящиеся в одном отношении ps, инцидентны одной и той же вершине Ni при условии, что Ni является листом дерева оптимальных маршрутов.

Доказательство. После превышения веса ребра eUj точки вхождения в дерево, оно будет исключено из дерева и вершина Nt окажется не связанной со всеми остальными вершинами в дереве. Чтобы в результате получилось дерево TN с исходным множеством вершин, необходимо в дерево добавить ребро, связывающее вершину Nt с некоторой вершиной Np в дереве. Таким ребром по определению парного отношения является e eLinksR. Это ребро будет инцидентно вершине Nt. Теорема доказана.

Отношение парного перехода/? , в общем случае, может быть не задано. Действительно, оптимальные маршруты до вершины маршрутной степени 1 на заключительном шаге будут содержать одно и то же ребро вне зависимости от веса этого ребра. Т. е. для некоторой вершины ТУ с маршрутной степенью, равной 1 и инцидентного ей ребра е , через которое проходит маршрут между вершинами ТУ и TVs, точка вхождения в дерево для ребра е будет равна бесконечности. Иными словами, изменение веса ребра eUj в данных условиях приведет к изменению оценки длины маршрута до вершин множества SwitchesT(). Конфигурация дерева TN при этом останется неизменной.

Множество оптимальных маршрутов г,- (/ = 1, 2, …, ТУ)до вершин графа Network из исходной вершины TVs определяет множество оценок оптимальных маршрутов до этих вершин di(i = 1, 2, …, TV).

Алгоритм балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов

Для подтверждения правильности и корректности предложенной математической модели разработан алгоритм динамической балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов [128]. Укруп-ненно алгоритм имеет следующий вид.

Шаг 1. Загрузить список коммутаторов, хостов и каналов связи в контроллер OpenFlow. Запустить фоновое приложение измерения сетевых параметров (задержки передачи, пропускной способности, процента потерь пакетов) каналов связи ПКС.

Шаг 2. Вычислить QoS-метрики и выбрать требуемое качество сервиса.

Шаг 3. Сформировать дерево оптимальных маршрутов с учетом выбранного качества сервиса с использованием алгоритма Дейкстры.

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

Шаг 5. Если коммутатор не является листом дерева, то вычислить парные переходы для этого коммутатора и выбирать лучшие значения потенциалов парных переходов для потомков коммутатора и собственных парных переходов. Подобную процедуру выполнить для формирования списков парных переходов в случае увеличения или уменьшения QoS-метрики канала связи.

Шаг 6. Для каждого коммутатора сформировать полный список парных переходов. Число элементов в каждом из этих списков не превышает количества коммутаторов в ПКС. Такое решение позволяет отказаться от предварительной сортировки потенциалов или приращений для парных переходов без значительного усложнения алгоритма обработки изменения.

Шаг 7. Для каждого коммутатора ПКС сформировать полный список возможных маршрутов, проходящий через каналы, состоящие в отношении парного перехода, включая и каналы, входящие в дерево оптимальных маршрутов.

Шаг 8. В ПКС определить коммутатор-источник и коммутатор-получатель z-го потока данных.

Шаг 9. Анализируя полученную от коммутаторов OpenFlow информацию определить, произошло ли изменение QoS-метрики каналов связи в ПКС:

а) если да – перейти к шагу 10;

б) иначе - к шагу 12.

Шаг 10. Используя список парных переходов определить, требуется ли сделать парный переход:

а) если да - перейти к шагу 11;

б) иначе - к шагу 13.

Шаг 11. Для каждого коммутатора, у которого в список возможных маршрутов входит канал с изменившейся QoS-метрикой, определить маршрут минимальной длины и поместить его в дерево оптимальных маршрутов, тем самым, построив новое дерево оптимальных маршрутов и их маршрутов замены в ПКС.

Шаг 12. Используя полученную от контроллера OpenFlow информацию о потоках данных в ПКС, определить, требуется ли выполнить балансировку потоков данных по всем сформированным маршрутам:

а) если да - перейти к шагу 13;

б) иначе - к шагу 14.

Шаг 13. 1) Определить суммарную маршрутную метрику всех имеющихся маршрутов между коммутатором-источником и коммутатором-получателем. Определить долю информации, проходящей по каждому из маршрутов.

2) Определить длины минимального и максимального маршрутов. Если отношение этих длин соответствует заданному параметру J3:

а) Перейти к пункту 3;

б) Иначе - к пункту 12.

3) Определить отклонение длины минимального маршрута от максимального между коммутатором-источником и коммутатором-получателем.

4) Определить среднее значение между вычисленными маршрутами.

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

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

7) Если такие пары каналов найдены:

а) Отсортировать данный список в порядке убывания QoS-метрики и перейти к пункту 8;

б) Иначе - к пункту 12.

8) Найти долю отклонения QoS-метрик, находящихся в вышеуказанном списке.

9) Сформировать дополнительную надбавку на каналы связи с помощью заданного параметра а.

10) Переформировать QoS-метрики каналов связи.

11) а) Если значение надбавки полностью не распределено, то выбрать следующую пару каналов связи, находящихся в отношении парного перехода из сформированного в пункте (6) списка маршрутов и перейти к пункту (8); б) Перейти к пункту 1.

12) Надбавка распределена, маршруты полностью сбалансированы в соответствии с параметрами a, J3иy Перейти к шагу 14.

Шаг 14. Для обеспечения требуемого качества сервиса в ПКС выполнить расчет значения оценки джиттера задержки передачи, тем самым, отбросив маршруты, которые не соответствуют требованию качества сервиса.

Шаг 15. Передать пакеты z-потока данных по всем сформированным маршрутам с обеспечением требуемого QoS. Установить флаг передачи.

Шаг 16. Пересчитать точки вхождения в дерево и переформировать список маршрутов для каждого изменившегося коммутатора.

Шаг 17. Перейти к шагу 8.

Алгоритм реализован на языке Python в виде модуля для контроллера POX. Данный алгоритм реализуется классом LoadBalancingAlgorithm. Метод RunLB является внешним и для запуска алгоритма БПД необходимо вызывать именно его. В данном методе происходит обращение к основному методу алгоритма _ExeLB, вычисление дополнительных данных и вывод результатов выполнения алгоритма. Программный код данного метода приведен ниже.

Анализ результатов работы алгоритмов балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов

В рамках проведенных исследований основное внимание было сосредоточено на сравнительном анализе модуля TE, работающего с маршрутами, вычисленными с помощью алгоритма Йена и алгоритма балансировки потоков данных (АБПД), включающего три коэффициента: а, , (а - коэффицент балансировки нагрузки, - отклонение длины минимального маршрута от длины максимального маршрута, - отклонение метрики канала, находящемся в минимальном маршруте, от метрики канала, находящемся в максимальном маршруте, которые состоят в отношении парного перехода), дающих больше возможностей управления нагрузкой, и основанной на работе алгоритма парных перестановок маршрутов (АППМ с БПД) [4-6]. На рис. 5.56-5.59 приведены графики сравнительного анализа рассмотренных алгоритмов балансировки потоков данных с обеспечением качества сетевых сервисов.

В табл. 5.3 - 5.6 приведены основные параметры топологии ПКС: N количество коммутаторов ПКС, M - количество каналов связи в ПКС, D - диаметр графа ПКС, CD - общая длина, т.е. общая маршрутная метрика всех доступных маршрутов между коммутатором-источником и коммутатором-получателем, P - номер маршрута, Ds - длина маршрута, I - информация, проходящая через маршрут, AV - среднее значение каналов, входящих в машрут, SD - квадратичное отклонение каналов, входящих в маршрут, MxVL - максимальное значение канала в маршруте, MnVL - минимальное значение канала в маршруте, J - отклонение значения длины текущего маршрута от длины оптимального маршрута, а - коэффицент балансировки нагрузки, fi - отклонение длины минимального маршрута от длины максимального маршрута, у - отклонение метрики канала, находящемся в минимальном маршруте, от метрики канала, находящемся в максимальном маршруте, которые состоят в отношении парного перехода. Результаты работы алгоритма Йена совместно с модулем TE и АБПД с обеспечением качества сетевых сервисов на основе различных QoS-параметров и QoS-метрик приведены в табл. 5.3 - 5.6.

Исследования проводились на различных топологиях ПКС, в том числе на топологии, представленной на рис. 5.49. Данная сетевая топология состоит из 14 коммутаторов и 23 каналов связи. В качестве метрик каналов связи использовались: пропускная способность, задержка передачи, процент потери пакетов и композитная метрика. В рамках проведенных исследований выполнялся синтез настроек различных QoS-параметров и QoS-метрик для исследуемых алгоритмов балансировки потоков данных в ПКС с обеспечением качества сетевых сервисов.

В результате проведенных исследований были получены следующие результаты. Для метрики QoS 2 (Delay Metric, задержка) первоначальный джиттер составлял 71% (табл. 5.3). Применив модуль TE, произошло уменьшение джит-тера до 68% (при а = 0.4), а использование АБПД позволило снизить данный показатель до 19% (при а = 0.8, /? = 0.9, у = 0.9J, благодаря чему увеличивается эффективность передачи, и уменьшаются потери пакетов данных при передаче информации по сбалансированным маршрутам.

Метрика QoS 3 (LARAC Metric) вычисляется с учетом параметров пропускной способности и задержки передачи данных, регулируемые коэффициентом X. Этот коэффициент определяет должна ли влиять задержка передачи на результирующую метрику при вычислении оптимального маршрута. Аналитически было выведено, что оптимальным значением коэффициента д является 0.7. Анализ результатов работы алгоритмов с данной QoS-метрикой (табл. 5.4) показывает, что первоначальный джиттер был равен 73%, а после применения алгоритмов балансировки может уменьшиться на 10% (TE-модуль) и на 67% (АБПД).

Метрика QoS 4 (LARAC Cost Metric) вычисляется с учетом параметров задержки передачи и процента потери пакетов, регулируемые коэффициентом д. Этот коэффициент определяет важность одного из двух параметров на результирующую метрику при вычислении оптимального маршрута. Аналитически было выведено, что оптимальным значением коэффициента д является 0.5. Анализ результатов работы алгоритмов с данной QoS-метрикой (табл. 5.5) показывает, что первоначальное отклонение максимального маршрута от оптимального маршрута, составляло 64%, а после применения балансировки данное отклонение в среднем может уменьшиться на 9% (TE-модуль) и 39% (АБПД).

Композитная метрика - это QoS-метрика, которая учитывает множество различных QoS-параметров. Композитная метрика обычно устанавливается в сети вручную администратором сети или программистом, и, обычно используется для отладки некорректной работы алгоритмов балансировки потоков данных. Анализ результатов работы алгоритмов с данной QoS-метрикой (табл. 5.6) показывает, что первоначальное отклонение максимального маршрута от оптимального маршрута, составляло 65%, а после применения балансировки данное отклонение в среднем может уменьшиться на 7% (TE-модуль) и 48% (АБПД).

На основе проведенных исследований можно сделать следующие выводы: предложенный алгоритм балансировки потоков данных позволяет балансировать нагрузку не только между смежными интерфейсами, как классический TE-модуль, но и между проложенными маршрутами за счет контроля за параметрами а,0,у. С добавлением двух новых коэффициентов (/? и у) появляется дополнительная возможность контроля работы алгоритма: большая часть загруженных каналов и, следовательно, маршрутов в ПКС будут сбалансированы (разгружены), тогда как в случае классического подхода, возможно, будет только уменьшена метрика максимально-загруженного канала в маршруте, а отклонение от длины оптимального маршрута изменится незначительно.

Таким образом, разработанный метод и алгоритмов балансировки потоков данных позволяет значительно повысить на быстродействие и надежность передачи данных и обеспечить требуемое качество сервиса в ПКС.