Введение 4
Обзор литературы 6
Постановка задачи 8
Глава 1. Анализ временных рядов 9
1.1. Основные определения 9
1.2. Прогнозирование временных рядов на сетях 11
Глава 2. Описание алгоритмов 14
2.1. Алгоритмы прогнозирования 14
2.1.1 Авторегрессионная модель 15
2.1.2 Векторная авторегрессионная модель 17
2.1.3 Методы градиентного бустинга 18
2.2. Алгоритмы сглаживания 25
2.3. Алгоритм валидации 30
Глава 3. Анализ данных 33
3.1. Abilene 33
3.2. Totem 39
3.3. PeMSD7 44
3.4. Вывод 49
Глава 4. Вычислительные эксперименты 50
4.1. Подготовка среды 50
4.2. Тестирование и выбор основных методов 51
4.3. Результаты валидации 53
4.3.1 Одномерные модели 53
4.3.2 Многомерные модели 55
4.4. Анализ результатов 57
Заключение 59
Список литературы 61
Приложение А. Обзор литературы 64
Приложение Б. Результаты валидации одномерных моделей для трафика по узлам 68
Приложение В. Результаты валидации многомерных моделей для трафика по узлам 74
Приложение Г. Визуализация результатов прогнозирования .... 80
С появлением и быстрым развитием компьютерных технологий и Интернета к сети подключается все большее количество устройств, что приводит к увеличению ее масштабов и сложности, а запросы пользователей к качеству связи только повышаются. Разумно распределяя сетевые ресурсы, можно оптимизировать маршрутизацию, тем самым уменьшить задержку связи, предотвратить перегрузку сети и обеспечить качество услуг. Однако для диагностики сети, обнаружения аномалий и эффективного использования имеющихся ресурсов необходимо точное прогнозирование ключевых показателей сети, таких как трафик, задержки, вызовы и т. д. Таким образом, прогнозирование сетевого трафика является основой для улучшения качества обслуживания пользователей.
С телекоммуникационной точки зрения сетевой трафик представляет собой матрицу, описывающую объем потока данных между всеми парами узлов сети в данный момент времени. Задачу прогнозирования сетевого трафика можно сформулировать как предсказание данной матрицы в определенный момент времени в будущем на основе исторических данных. Для решения поставленной задачи используют методы, которые можно разделить на две группы: линейные и нелинейные. Линейные методы, такие как авторегрессионные модели [19, 23], моделируют характеристики временной последовательности трафика на основе математической статистики. К нелинейным относятся модели прогнозирования, основанные на вейвлет-анализе [7, 2], байесовских сетях [21], нейронных сетях [20, 5, 6] и так далее. Поскольку одна линейная или нелинейная модель не может точно описать динамику сетевого трафика, то для решения подобных задач в последнее время все чаще стали использовать комбинированные методы [12], основанные на нейронных сетях, способных моделировать пространственные и временные признаки. Однако и у данных методов есть свои недостатки. Например, в некоторых случаях сначала извлекаются пространственные характеристики с использованием графовой нейронной сети (GNN[24, 11]), а затем захватываются временные признаки. Методы на основе GNNсоздают статическую матрицу смежности для моделирования топологии сети, где каждый узел передает сообщения только своим непосредственным соседям. При этом не учитывается тот факт, что пространственные зависимости сети динамичны, то есть важность различных узлов меняется со временем, что делает структуру графа более сложной. Такие методы могут сильно ограничивать возможности моделирования сложного сетевого трафика.
Для решения задачи прогнозирования сетевого трафика мы предлагаем использовать ряд линейных и нелинейных методов, дополнив их возможностью обрабатывать пространственную информацию. Также в работе проведен анализ временных и пространственных зависимостей данных, определенных на графах и сетях, и рассмотрены различные способы фильтрации для уменьшения влияния шума на модели.
Областью исследования данной работы являются методы машинного обучения. Предмет исследования - данные с сетевой структурой. В данной работе предстоит решить такие проблемы как: выбор подходящих методов прогнозирования; поиск открытых баз данных; разработка алгоритмов прогнозирования; тестирование и анализ полученных результатов.
В работе приведен обзор литературы по изучаемой теме и сформулированы цель и задачи исследования. В первой главе представлены некоторые теоретические сведения по теории временных рядов и их прогнозированию. Вторая глава посвящена описанию алгоритмов, которые будут исследованы. В третьей главе проведен корреляционный анализ рассматриваемых наборов данных. В четвертой главе представлены результаты вычислительных экспериментов. В заключении подведены итоги проведенной работы.
Целью данного исследования была разработка эффективных алгоритмов для прогнозирования сетевого трафика. Созданная библиотека содержит методы как для сглаживания временных рядов, так и для их предсказания и валидации построенных моделей (одномерных или многомерных). Были получены следующие результаты: на примере набора данных PeMSD7в одномерном случае лучшие показатели, а именно МАРЕ = 0.098, МАЕ = 4.5, были достигнуты авторегрессионной моделью с логарифмическим преобразованием данных, а среди многомерных алгоритмов - LightGBMс логарифмированием (МАРЕ = 0.044, МАЕ = 2.065). Реализованные многомерные методы прогнозирования превосходят одномерные аналоги, а также они способны конкурировать с современными нейросетевыми подходами и при некоторых условиях даже превосходить их. Например, точность предсказания модели LightGBMс использованием логарифмирования на наборе данных PeMSD7 сравнима с моделью, основанной на графовых нейронных сетях, из работы [24].
Точность моделей прогнозирования напрямую зависит от данных, их зашумленности, а также от размера обучающей выборки. Результаты работы алгоритмов улучшались с использованием различных способов фильтрации, особенно их комбинаций.
В ходе работы были выполнены следующие задачи:
1. изучены возможные решения данной проблемы;
2. найдены и проанализированы открытые наборы данных, имеющие сетевую структуру;
3. реализованы все необходимые алгоритмы прогнозирования, сглаживания и валидации;
4. проведено обучение, тестирование и валидация моделей;
5. проанализированы полученные результаты, выполнено сравнение реализованных моделей и сделаны соответствующие выводы.
Подводя итог, можно отметить, что задача прогнозирования трафика сетевой системы является довольно сложной и требует не только разработки алгоритмов предсказания, но и тщательного анализа данных, поиска пространственных зависимостей элементов сети, адаптации моделей к смене динамики, устойчивости к выбросам.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
