Модели, методы и средства исследования нестационарных нагрузочных процессов в эластичных вычислительных системах тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Мартынчук Илья Геннадьевич

• Мартынчук Илья Геннадьевич
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Мартынчук Илья Геннадьевич

Реферат

Synopsis

Введение

Глава 1. Принципы организации эластичных систем

1.1 Понятие эластичной системы

1.2 Способы реализации эластичных систем

1.2.1 Центры обработки данных

1.2.2 Облачные платформы

1.2.3 Системы контейнерной оркестрации

1.3 Управление вычислительными ресурсами эластичных систем

1.3.1 Защита системы от перегрузок

1.3.2 Снижение стоимости владения

1.3.3 Анализ характера нагрузочного процесса

1.3.4 Оценка необходимого количества ресурсов

1.3.5 Планирование распределения вычислительных ресурсов

1.4 Нестационарные процессы в эластичных системах

1.4.1 Случайность и нестационарность в эластичных системах

1.4.2 Способы моделирования нестационарных процессов

1.5 Постановка задачи

1.6 Аналитический обзор источников по теме исследования

1.6.1 Научные публикации и монографии

1.6.2 Прочие источники

1.6.3 Патентный поиск по теме исследования

1.6.4 Отличия проводимого исследования

1.6.5 Выводы по результатам аналитического обзора

1.7 Выводы по главе

Глава 2. Аналитическое моделирование эластичных систем

2.1 Описание моделей эластичных систем

2.2 Метод оценки задержек в моделях эластичных систем

2.2.1 Описание метода

2.2.2 Имитационная модель для оценки точности метода

2.2.3 Результаты имитационных экспериментов

2.3 Классификация нестационарных процессов

2.4 Метод аналитического описания нестационарного распределения

2.5 Композиция нестационарных распределений

2.6 Выводы по главе

Глава 3. Численные модели и методы прогнозирования нестационарных нагрузочных процессов

3.1 Метод линейной аппроксимации временных параметров в эластичных системах

3.2 Прогнозирование нестационарных нагрузочных процессов в окружениях эластичных систем

3.2.1 Сезонная регрессионная модель случайных процессов

3.2.2 Модель мультисезонной сезонно-трендовой декомпозиции временного ряда

3.3 Алгоритм быстрого поиска периода

3.4 Сравнение моделей MSTL и SARIMA

3.4.1 Постановка эксперимента

3.4.2 Результаты экспериментов

3.5 Выводы по главе

Глава 4. Методика планирования и управления вычислительными ресурсами эластичных систем

4.1 Разработка алгоритма планирования и управления вычислительными ресурсами

4.1.1 Капитальные затраты

4.1.2 Операционные расходы

4.1.3 Оценка эффективности применения разрабатываемого алгоритма

4.1.4 Алгоритм планирования и управления вычислительными ресурсами

4.2 Тестирование разработанного алгоритма

4.2.1 Описание тестового аппаратно-программного комплекса

4.2.2 Результаты те стирования

4.3 Выводы по главе

Заключение

Список сокращений и условных обозначений

Библиографический список

Список иллюстративного материала

Приложение 1. Исходный текст программы сравнения моделей

MSTLиSARIMA

Приложение 2. Акт о внедрении результатов исследования в образовательный процесс

Приложение 3. Тесты публикаций по теме исследования

РЕФЕРАТ

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

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

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

В настоящее время широко применяется два способа масштабирова-

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

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

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

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

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

1. Разработать модели и методы исследования эластичных систем и протекающих в них нагрузочных процессов.

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

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

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

Предметом исследования являются методы и алгоритмы планирования и управления вычислительными ресурсами эластичных систем.

Теоретическую основу исследования составляют научные труды отечественных и зарубежных авторов в области облачных технологий, теории вероятностей и теории очередей.

Методологическую основу исследования составляют методы теории вероятностей, методы теории очередей, методы математической статистики и метод имитационного моделирования, методы теории временных рядов.

Информационная база исследования. Основными научными источниками диссертации являются книга В. Столлингса «Современные компьютерные сети», книга Т. И. Алиева «Основы моделирования дискрет-

ных систем» и книга М. Портного «Основы виртуализации».

Введение диссертации (часть автореферата) на тему «Модели, методы и средства исследования нестационарных нагрузочных процессов в эластичных вычислительных системах»

Научная новизна работы.

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

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

3. Впервые сформулирована методика планирования и управления вычислительными ресурсами эластичных систем на основе комбинированного подхода с применением аналитических, имитационных и численных методов.

Основные положения, выносимые на защиту.

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

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

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

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

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

Апробация результатов исследования. Основные положения работы прошли апробацию на следующих девятнадцати научных конференциях: XXII международная научная конференция «Волновая электроника и инфокоммуникационные системы (WECONF-2019)» (2019 г.); X, XI MICSECS - The Majorov International Conference on Software Engineering and Computer Systems (2018-2019 гг.); VIII и IX Научно-практическая конференция молодых ученых «Вычислительные системы и сети (Майоров-ские чтения)» (2017 г.); VI Научно-практическая конференция с международным участием «Наука настоящего и будущего» (2018 г.); XLVI и XLVII, XLVIII, XLIX, L, LI Научная и учебно-методическая конференция Университета ИТМО (2017-2022 гг.); VI, VII и VIII, IX, X, XI, XII Всероссийский конгресс молодых ученых (2017-2023 гг.).

Публикации. Основные результаты по теме диссертации изложены в 11 печатных изданиях. Одна статья издана в журналах, рекомендованных ВАК. Три статьи индексированы базой Scopus.

Внедрение результатов работы. Основные результаты диссертационной работы внедрены в учебный процесс факультета программной инженерии и компьютерной техники университета ИТМО (дисциплины «Телекоммуникационные системы», «Моделирование»), что подтверждается соответствующим актом о внедрении, а также использованы в следующих

научно-исследовательских работах (НИР).

1. НИР-ФУНД №617026 «Разработка методов интеллектуального управления киберфизическими системами с использованием квантовых технологий».

2. НИР-ФУНД №619296 «Разработка методов создания и внедрения киберфизических систем».

3. НИР-ПОИСК №620164 «Методы искусственного интеллекта для киберфизических систем».

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

1. Защита системы от перегрузок.

2. Снижение стоимости владения вычислительными ресурсами.

3. Определение характера нагрузочного процесса на целевую систему.

4. Определение необходимого количества вычислительных ресурсов.

5. Планирование распределения вычислительных ресурсов.

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

« г

О 5

ч

оо

^ 4

о

! з

Кол-во

узлов

Требуемое кол-во узлов

Перегруженные

узлы

Кол-во обрабатыва ющих узлов

Время

в

0 5

л з

^ 4 о

1 з

Кол-во

узлов

Требуемое кол-во узлов

Кол-во обрабатыва ющих узлов

Время

Рисунок 1 - Проактивное масштабирование

7

7

6

6

2

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

Определено, что для достижения поставленной в диссертационном

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

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

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

3. Возможность функционирования и построения моделей в условиях нестационарных и произвольных нагрузочных процессов на систему.

4. Возможность работы с эластичными системами различных классов, то есть с публичными и частными инсталляциями как облачных систем, так и систем контейнерной кластеризации.

5. Возможность моделирования структурной организации эластичной системы и изменение модели в соответствии с протекающими в системе процессами.

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

1. Нестационарность, характерная для протекающих в эластичных системах процессов, усложняет исследование и прогнозирование по-

ведения системы как на этапе ее проектирования, так и во время эксплуатации.

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

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

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

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

Предложена формула для расчета приближенного среднего времени ожидания в СМО класса в/в/К:

й - т + г и, ) - (КР)К+ г ь ) ~ 2(1 - р) ' ('а) ~ К!(1 - р) 2(1 - р) } К) '

где К - количество однотипных обслуживающих приборов, р - загрузка системы, Р0 - вероятность того, что в системе нет заявок, Ь - среднее время обслуживания заявок, уа - коэффициент вариации интервалов времени между поступлениями запросов, уъ - коэффициент вариации длительности обслуживания запросов, /(уа) - корректирующая функция, рассчиты-

ваемая следующим образом:

pf \ 3p(vlWb)

fМ = < ^ а bb_ 1 л

[ехр{ - (1 - р)v^) , va > 1 .

В среде имитационного моделирования AnyLogic Professional разработана модель многоканальной системы G/G/К, использующая логнор-мальное распределение в качестве задающего распределения для интенсивности запросов и времени обслуживания.

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

По результатам второй серии экспериментов с варьированием параметра ß в распределении времени обслуживания выявлено, что разница между теоретическими расчетами и имитационными экспериментами демонстрирует схожее поведение, как в случае с варьированием интервалов времени между поступлениями запросов. Показано, что при р > 0,8 отклонение рассчитанного с помощью предлагаемых в работе аналитическим зависимостей w имеет отклонение в пределах общепринятой погрешности имитационного моделирования равной 5%.

Предложена классификация нестационарных процессов с точки зрения характера задающего распределения и характера изменения показателей.

Получено аналитическое представление нестационарного распределения, характеризующего нестационарный нагрузочный процесс:

/(х,1) = / 1(х,Х(1)) ;

т = /2(1) ,

где /(х¿) - закон распределения вероятностей, / 1(ж, А(£)) - функция, задающая закон распределения вероятностей, Х(Ъ) - параметр распределения, /2(Ъ) - функция изменения параметра распределения.

Получены результирующие аналитические модели последовательной и параллельной композиции нестационарных распределений, имеющие следующий вид:

/

вит(х.;Ь) = а(Х$ (¿),х)®

< <8> Ь(Хд (г),х); Хн(1) = ф)+ (1(1) .

V

/

сотр(х,Ь) = (а(Х$ (Ь),х) + + Ь(Хд (1),х))/2;

<

Хн = с(Ъ) + (1(Ъ) ; а + Ь=1 .

где вит(х.;Ь) - последовательная композиция, сотр(х,Ь) - параллельная композиция, Хи - результирующая функция изменения параметра распределения.

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

1. Нагрузочные процессы в эластичных вычислительных системах имеют нестационарную природу, обусловленную естественной суточной активностью пользователей. Известные результаты теории

массового обслуживания не применимы для исследования и расчета характеристики таких систем.

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

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

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

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

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

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

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

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

• метод наименьших квадратов (МНК);

• метод достижения консенсуса на основе случайных выборок (Random Sample Consensus, RANSAC);

• метод главных компонент (Principal Component Analysis, PCA).

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

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

По завершению экспериментов выявлено, что с доверительной вероят-

ность 0,95, начиная с 50 точек в исходном наборе данных, разработанный метод демонстрирует линейное снижение времени выполнения аппроксимации по сравнению с МНК. При этом максимальное снижение 23% достигается на самом большом наборе данных. Определено, что с доверительной вероятностью 0,95 значение среднего отклонения 5ср для обоих методов в рамках экспериментов одинаково, что свидетельствует об одинаковой точности разработанного метода и метода наименьших квадратов.

Определено, что нестационарные нагрузочные процессы могу быть представлены в виде временных рядов (рис. 2). Показано, что нагрузочные процессы в эластичных системах являются мультисезонными, так как обладают не только дневной периодичностью, вызванной суточной активностью пользователей, но и недельной сезонностью, связанной с пятидневной рабочей неделей.

Обоснована необходимость проверки возможности использования модели мультисезонной сезонно-трендовой декомпозиции временного ряда на основе LOWESS (М8ТЬ) и сравнение ее производительности с широко используемой сезонной интегрированной моделью авторегрессонно-го скользящего среднего ^АММА) для решения задач исследования и прогнозирования мультисезонных нагрузочных процессов в эластичных вычислительных системах.

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

Для повышения степени автоматизации процессов управления ресурсами эластичных систем предложено находить величину сезонности в автоматическом режиме с помощью итерационного алгоритма быстрого поиска периода. По полученным в ходе многочисленных экспериментов показателям качества прогноза и производительности моделей (табл. 1, 2) выявлено, что высокая вычислительная сложность модели 8ЛЯ1МЛ позволяет обработать только недельный набор данных.

Таблица 1. Рассчитанные ЯМБЕ и Я2 для прогноза на день вперед на

основе недельных и месячных данных

SARIMA(0,1,0)(0,0,0)[288] MSTL(288, 2016)

Недельный набор данных Месячный набор данных Недельный набор данных Месячный набор данных

ЯМБЕ 474,94404 - 2524,79448 711,03479

Я2 0,97192 - 0,206541 0,93902

Таблица 2. Время расчета моделей и потребление памяти во время

проведения экспериментов

Недельный набор данных Месячный набор данных

Время выполнения, с Потребление памяти, ГБ Время выполнения, с Потребление памяти, ГБ

SARIMA 1080,92 ± 1,2 ОП: 48,447 swap: 6,4 ± 0,4

MSTL 6,48 ± 0,03 0,375 ± 0,025 15,23 ± 0,08 0,375 ± 0,025

Показано, что на недельном наборе данных модель 8ЛЯ1МЛ демонстрирует лучшее качество прогноза по сравнению с М8ТЬ, а при месячном наборе данных показатели качества для М8ТЬ приближаются к недельным показателям 8ЛЯ1МЛ.

Определена зависимость коэффициента детерминации от количества измерений во временном ряду (рис. 3).

й

1

0,9 0,8

$ 0,7

I 0,6

н

и 0 5

о °,5 Я

g 0,4

S 0,3

3

0,2

----Дневная и недельная

сезонности

■Недельная сезонность

0 5 10 15 20

Величина набора данных для построения модели, недели

Рисунок 3 - Результаты расчета показателя В2 при различных параметрах сезонности в модели М8ТЬ

Выявлено, что в случае недельной сезонности качество прогноза

М8ТЬ значительно выше на большинстве исходных наборов данных и приближается к модели 8ЛЯ1МЛ на недельном наборе данных.

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

1. Предложенный метод линейной аппроксимации временных параметров в эластичных системах, наряду с методом наименьших квадратов и в отличие от методов ЯЛК8ЛС и РСЛ, удовлетворяет требованиям, предъявляемым к методам, функционирующим в окружениях эластичных систем. Начиная с некоторой величины исходного набора данных, метод демонстрирует снижение времени выполнения аппроксимации по сравнению с МНК.

2. Естественная периодичность нагрузочных процессов, характерных для эластичных систем, требует отдельного применения методов поиска периода. Для снижения накладных расходов на операции поиска периода предложено использовать описанный в работе итерационный метод.

3. Модель М8ТЬ показала свое преимущество по сравнению с моделью 8ЛЯ1МЛ по времени выполнения и использованию памяти при исследовании и прогнозировании мультисезонных нагрузочных процессов, характерных для эластичных вычислительных систем.

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

Сформулирована оценка затрат на владение эластичной системой:

N

¡=1

где I - расчетный период, Бут - стоимость одного вычислительного узла

за расчетный период, Nvm - количество функционирующих вычислительных узлов в течение расчетного периода, Ssiav - штраф за нарушение SLA на единицу времени для арендатора; Ti - интервал времени нарушения SLA, N - количество временных интервалов нарушения SLA арендатором. На основе предложенной оценки сформулирован критерий эффективности применения алгоритма управления ресурсами:

^ = п • А + m • В, (1)

где п - вес затрат на вычислительные узлы, m - вес штрафных санкций, А - стоимость вычислительных узлов, В - величина штрафных санкций за нарушение SLA.

Разработана методика, направленная как на планирование ресурсов на этапе ввода эластичной системы в эксплуатацию, так и на управление вычислительными ресурсами системы на всех этапах ее жизненного цикла. Для тестирования предложенного алгоритма управления вычислительными ресурсами эластичных систем сформирован тестовый аппаратно-программный комплекс на основе операционной системы Windows 10, гипервизора Hyper-V, операционной системы Debian GNU/Linux и системы контейнерной оркестрации Kubernetes.

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

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

загрузки обеспечивает в среднем 12,5%±2,1% времени превышения порогового значения времени отклика системы, в то время как разработанный алгоритм обеспечивает снижение времени превышения до 1,5%о ± 0,3%% (рис. 4). Сделан вывод, что отсутствие прогнозирования основных изменений в нагрузке не позволяет стандартному подходу вовремя реагировать даже на типичные изменения в нагрузочном процессе, что приводит к повышению времени нахождения системы в перегруженном состоянии с повышением времени отклика на запросы.

Выявлено, что в случае использования сглаженного исходного набора данных метод на основе граничных значений загрузки обеспечивает в среднем 1,2% ± 0,3% времени превышения порогового значения времени отклика системы, в то время как разработанный алгоритм обеспечивает также снижение времени превышения до 0,1%о ± 0,05%.

Определено, что при использовании исходного набора данных стандартный метод за месячный расчетный период использовал на 7%±0,45%о меньше вычислительных узлов, а в случае сглаженного нагрузочного процесса предлагаемый алгоритм обеспечивает снижение среднего количества вычислительных узлов на 5%о ± 0,22%о.

яи 30

ен э 25

т

& н £ 20 и

Л т 5 15

о о

н ^ 10

Л м ел

л е т 5

и нн

л 0

Д

Типовой алгоритм

Д

А

Л! Д

1Т и

А

фД Д А

л ад

Разработанный алгоритм

Д

Д

Д1

ооооооооооооооооо ооооооооооооооооо

т

м т ^ ш ю ь м Время

Рисунок 4 - Превышения порогового значения времени отклика

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

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

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

2. Затраты на владение эластичной системой зависят от соотношения величины штрафов за нарушение качества обслуживания пользователей и стоимости аренды вычислительных узлов

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

печивает возможность исследования эффективности функционирования эластичной системы как на этапе ее проектирования, так и во время промышленной эксплуатации.

4. В результате применения разработанного алгоритма управления ресурсами эластичных систем на тестовом аппаратно-программном комплексе удалось добиться повышения эффективности функционирования эластичной системы в соответствии с предложенным в работе критерием.

Список литературы диссертационного исследования кандидат наук Мартынчук Илья Геннадьевич, 2023 год

Литература

1. Aliev T.I., Rebezova M.I., Russ A.A. Statistical methods for monitoring travel agencies in the settlement system // Automatic Control and Computer Sciences. 2015. V. 49. N 6. P. 321-327. https:// doi.org/10.3103/s0146411615060024

2. Lorido-Botran T., Miguel-Alonso J., Lozano J.A. A review of auto-scaling techniques for elastic applications in cloud environments // Journal of Grid Computing. 2014. V. 12. N 4. P. 559-592. https://doi. org/10.1007/s10723-014-9314-7

3. Nikravesh A.Y., Ajila S.A., Lung C.H. Towards an autonomic auto-scaling prediction system for cloud resource provisioning // Proc. of the IEEE/ACM 10th International Symposium on Software Engineering for Adaptive and Self-Managing Systems. 2015. P. 3545. https://doi.org/10.1109/seams.2015.22

4. Moore L.R., Bean K., Ellahi T. Transforming reactive auto-scaling into proactive auto-scaling // Proc. of the 3rd International Workshop on Cloud Data and Platforms (CloudDP '13). 2013. P. 7-12. https:// doi.org/10.1145/2460756.2460758

5. Aceto G., Botta A., de Donato W., Pescape A. Cloud monitoring: A survey // Computer Networks. 2013. V. 57. N 9. P. 2093-2115. https:// doi.org/10.1016/j.comnet.2013.04.001

6. Portnoy M. Virtualization Essentials. John Wiley & Sons, 2012. 286 p.

7. Bogatyrev V.A., Bogatyrev A.V. Functional reliability of a real-time redundant computational process in cluster architecture systems // Automatic Control and Computer Sciences. 2015. V. 49. N 1. P. 4656. https://doi.org/10.3103/S0146411615010022

8. Bogatyrev V.A., Parshutina S.A., Poptcova N.A., Bogatyrev A.V. Efficiency of redundant service with destruction of expired and irrelevant request copies in real-time clusters // Communications in Computer and Information Science. 2016. V. 678. P. 337-348. https:// doi.org/10.1007/978-3-319-51917-3_30

9. Богатырев В.А., Богатырев С.В. Резервированная передача данных через агрегированные каналы в сети реального времени // Известия вузов. Приборостроение. 2016. Т. 59. № 9. С. 735-740. https://doi.org/10.17586/0021-3454-2016-59-9-735-740

10. Remondino F. Detectors and descriptors for photogrammetric applications // International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. 2006. V. 36. N 3. P. 49-54.

11. Markovsky I., Van Huffel S. Overview of total least-squares methods // Signal Processing. 2007. V. 87. N 10. P. 2283-2302. https://doi. org/10.1016/j.sigpro.2007.04.004

12. Fischler M.A., Bolles R.C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography // Communications of the ACM. 1981. V. 24. N 6. P. 381395. https://doi.org/10.1145/358669.358692

13. Abdi H., Williams L.J. Principal component analysis // Wiley Interdisciplinary Reviews: Computational Statistics. 2010. V. 2. N 4. P. 433-459. https://doi.org/10.1002/wics.101

14. Othman M.M., El-Mousa A. Internet of Things & Cloud Computing Internet of Things as a service approach // Proc. of the 11th International Conference on Information and Communication Systems (ICICS). 2020. P. 318-323. https://doi.org/10.1109/ icics49469.2020.239503

References

1. Aliev T.I., Rebezova M.I., Russ A.A. Statistical methods for monitoring travel agencies in the settlement system. Automatic Control and Computer Sciences, 2015, vol. 49, no. 6, pp. 321-327. https://doi.org/10.3103/s0146411615060024

2. Lorido-Botran T., Miguel-Alonso J., Lozano J.A. A review of auto-scaling techniques for elastic applications in cloud environments. Journal of Grid Computing, 2014, vol. 12, no. 4, pp. 559-592. https:// doi.org/10.1007/s10723-014-9314-7

3. Nikravesh A.Y., Ajila S.A., Lung C.H. Towards an autonomic auto-scaling prediction system for cloud resource provisioning. Proc. of the IEEE/ACM 10th International Symposium on Software Engineering for Adaptive and Self-Managing Systems, 2015, pp. 35-45. https://doi.org/10.1109/seams.2015.22

4. Moore L.R., Bean K., Ellahi T. Transforming reactive auto-scaling into proactive auto-scaling. Proc. of the 3rd International Workshop on Cloud Data and Platforms (CloudDP '13), 2013, pp. 7-12. https:// doi.org/10.1145/2460756.2460758

5. Aceto G., Botta A., de Donato W., Pescapè A. Cloud monitoring: A survey. Computer Networks, 2013, vol. 57, no. 9, pp. 2093-2115. https://doi.org/10.1016/j.comnet.2013.04.001

6. Portnoy M. Virtualization Essentials. John Wiley & Sons, 2012, 286 p.

7. Bogatyrev V.A., Bogatyrev A.V. Functional reliability of a real-time redundant computational process in cluster architecture systems. Automatic Control and Computer Sciences, 2015, vol. 49, no. 1, pp. 46-56. https://doi.org/10.3103/S0146411615010022

8. Bogatyrev V.A., Parshutina S.A., Poptcova N.A., Bogatyrev A.V. Efficiency of redundant service with destruction of expired and irrelevant request copies in real-time clusters. Communications in Computer and Information Science, 2016, vol. 678, pp. 337-348. https://doi.org/10.1007/978-3-319-51917-3_30

9. Bogatyrev V.A., Bogatyrev S.V. Redundant data transmission using aggregated channels in real-time network. Journal of Instrument Engineering, 2016, vol. 59, no. 9, pp. 735-740. (in Russian). https:// doi.org/10.17586/0021-3454-2016-59-9-735-740

10. Remondino F. Detectors and descriptors for photogrammetric applications. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2006, vol. 36, no. 3, pp. 49-54.

11. Markovsky I., Van Huffel S. Overview of total least-squares methods. Signal Processing, 2007, vol. 87, no. 10, pp. 2283-2302. https://doi. org/10.1016/j.sigpro.2007.04.004

12. Fischler M.A., Bolles R.C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 1981, vol. 24, no. 6, pp. 381-395. https://doi.org/10.1145/358669.358692

13. Abdi H., Williams L.J. Principal component analysis. Wiley Interdisciplinary Reviews: Computational Statistics, 2010, vol. 2, no. 4, pp. 433-459. https://doi.org/10.1002/wics.101

14. Othman M.M., El-Mousa A. Internet of Things & Cloud Computing Internet of Things as a service approach. Proc. of the 11th International Conference on Information and Communication Systems (ICICS), 2020, pp. 318-323. https://doi.org/10.1109/icics49469.2020.239503

Авторы

Мартынчук Илья Геннадьевич — аспирант, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, sc 57208319866, https://orcid.org/0000-0003-2409-9677, [e-mail] Жмылёв Сергей Александрович — кандидат технических наук, инженер-консультант, ООО «ГК Ядро», Москва, 125373, Российская Федерация, sc 57208416951, https://orcid.org/0000-0001-8916-5474, [e-mail]

Authors

Ilya G. Martynchuk — PhD Student, ITMO University, Saint Petersburg, 197101, Russian Federation, sc 57208319866, https://orcid.org/0000-0003-2409-9677, [e-mail]

Sergei A. Zhmylev — PhD, Engineering consultant, GK YADRO LLC, Moscow, 125373, Russian Federation, sc 57208416951, https://orcid. org/0000-0001-8916-5474, [e-mail]

Статья поступила в редакцию 30.12.2022 Одобрена после рецензирования 25.04.2023 Принята к печати 25.05.2023

Received 30.12.2022

Approved after reviewing 25.04.2023

Accepted 25.05.2023

Работа доступна по лицензии Creative Commons «Attribution-NonCommercial»

Analytical methods of nonstationary processes

modeling*

Sergei zhmyW0000-0001"8916-5474], Ilya Martyu^0000"0003"2409"9677], Valeriy Kireevl0000"0003"1619"0681], and Taufik AhevE0000"0003"0278"688*]

ITMO University, Kronverkskiy pr., 49, lit. A, St. Petersburg, 197101, Russia korgOcs.ifmo.ru, mt4.ilj aOgmail.com, kkOcs.ifmo.ru, alievOcs.ifmo.ru

Abstract. Due to complex structure and a huge scale, cloud systems design and development requires a preliminary workload estimation. A typical solution for this design step is a workload upper-boundary estimation based on a sum of maximal intensities per cloud application. This solution is not well suitable for nonstationary functioning cloud computing systems, due to such an estimation would result in lots of hardware resources mostly unused during the worktime. Any workload can be represented as a combination of a probability density function and certain parameters for modeling purposes. For any stationary processes, a shape of the probability density function and the parameters would have constant values. On the contrary, nonstationary processes are characterized by changes of the values in time. The objective of the work is to develop an analytical method for the nonstationary processes modeling and representation. Completing the objective, the authors proposed a linear-equation nonstationary processes representation form. Which allowed to carry out the estimation using standard mathematical transformations and operations. The proposed numerical method makes it possible to approximate periodic non-stationary distributions whose change in time is sinusoidal. The method is tested with different types of synthetic signals and in all cases demonstrates a high degree of compliance of the results with the original data.

Keywords: Nonstationarity • Mathematical modeling • Simulation • Cloud computing • Computational resources scaling.

1 Introduction

Currently, computing is widespread in cloud systems that solve a wide range of tasks with small user requests processing time [1]. Examples of such systems include various Internet services for converting image formats and media files, services for performing mathematical calculations and services for collaborative work with office documents. Due to the fact that cloud systems, as a rule, have a web interface, there is no need in specialized software to work with them,

* Supported by ITMO University.

therefore the number of their users is constantly increasing as well as the total workload. Therefore, these systems require continuous operation and high performance to ensure the high quality of the services provided.

A cloud system is a set of computing systems, as a rule, located in one data center, serviced by one staff and under the jurisdiction of one managing organization [2]. The management organization provides the services of renting a part of the cloud system computing power using virtualization technologies automatically or in a manual manner. For instance, there could be a special software for company administrators whis is capable of provisioning new computing resources for any software. Thus, the tenant receives a certain number of virtual nodes with the same configuration on which the cloud application can be launched. The cloud application has a single entry point for user requests and it is horizontally scalable, so the structure of the cloud application is hidden from users [3]. Cloud applications in contradiction to desktop apllications are characterized with a high level of horizontal scalability. Therefore, if a tenant has insufficient computing capacity at some point in time, he can rent additional virtual nodes and launch additional instances of it's cloud application, increasing the overall performance of his cloud application.

2 Problem formulation

Due to complex structure and a huge scale, cloud systems design and development requires a preliminary workload estimation. A typical solution for this design step is a workload upper-boundary estimation based on a sum of maximal intensities per cloud application [4]. This solution is not well suitable for nonstationary functioning cloud computing systems, due to such an estimation would result in lots of hardware resources mostly unused during the worktime. Consider a cloud system with many cloud applications. An average workload of the applications in queries per second could be either constant or experience changes over the measurement time.

Any workload can be represented as a combination of a probability density function and certain parameters for modeling purposes [5]. For any stationary processes, a shape of the probability density function and the parameters would have constant values. On the contrary, nonstationary processes are characterized by changes of the values in time. Thus nonstationarity in any systems could be delimited in three classes: with constant probability distribution, with constant parameters (mean, variation, etc.), and total non-constant [6]. Each of those nonstationarity classes is typical for specific environmental conditions. Mostly, nonstationarity may occur due to natural workload behavior. There are number of nonstationarity reasons that could be converged in three classes: periodic, aperiodic (e.g. damped oscillations) and chaotic - without any visible structure or reproducibility. Figure 1 represents a workload of the biggest Internet data exchange point of the Russian Federation - MSK-IX. It's shown that a network traffic tends to be a periodic nonstationary process, due to number of Internet users at a specific point: much more active users during an evening.

Analytical methods of nonstationary processes modeling

3S00

зооо

l/l

+J 2S00

la

О

и it 2ооо

ПЗ

+J

■a ai 1S00

l/l

ПЗ

0) 1000

2

S00

о о

о

о

00

Fig. 1. MSK-IX weekly traffic

Absolutely the same workload class - periodic nonstationary process - was discovered in a course of numerous cloud systems studies. In spite this fact, typical approach of cloud systems design and real-time management consists of an estimation on maximum intensity values [7]. Such an approach leads to nonoptimal workload distribution due to big amount of unused hardware resources. Therefore, the objective of the work is to develop an analytical method for the nonstationary processes modeling and representation.

3

о

3 Period estimation

For the non-stationary processes investigation during measurements on a real system, it is necessary to take not only the numerical characteristics of the distribution into account, which affect the absolute values of the measurands, but also the periodic component describing distribution characteristics changing with time. There is a need to automatically estimate the period length based on a sample of measured values in order to present the observed process in an analytical form. Below we propose a method for such processes period length estimating to ensure their analytical description and research.

Existing methods for such problems solving are usually associated with the sound signals analysis or have a different, narrow field of application, which makes it difficult to use them in network computing systems [8]. In addition, currently used methods are not suitable for the investigation of non-stationary processes occurring in cloud computing systems, since the function describing changes in such processes does not always have a sinusoidal form. Methods such as, for example, the fast Fourier transform (FFT) are not suitable for the period estimation of signals with a missing fundamental [9]. In particular, the fast

Fourier transform has a fairly good algorithmic complexity, but it requires a large number of floating point operations, including the results post-processing, which eliminates the algorithmic complexity advantage over the method described below. Also, despite the fact that the fast Fourier transform works well on signals having a natural nature, its applicability is not always relevant for the "artificial" signals observed in computer science [10]. In particular, the number of terms required for the FFT calculating in gap functions processing rushes to infinity, which makes the calculation impossible [11]. Therefore, it became necessary to develop a method for the period T length estimating, satisfying the following requirements.

1. The method should evaluate the period on an incomplete set of input data. Since the load created by users changes over time [12], to manage the cloud system, it is necessary to estimate the length of the requests arrival process period in "real time".

2. The method must have a polynomial or constant algorithmic complexity. It is clear that during long-term high frequency measurements, a sufficiently large number of measured values will be obtained, which will lead to a large processing time using existing algorithms with the exponential complexity [13].

3. The main memory usage should linearly dependent on the amount of input data, since it is assumed to use the developed method to manage the cloud system with a limited memory capacity [14].

4. The method should be resistant to measurement errors and obtain reliable results (in real environment as well) characterized by a non-ideal input signal form [15].

5. Calculation results should not depend on the quality of a periodic input data, due to real systems discreteness and therefore function holes presence.

Let there be some periodic value Y, depending on time Y = y(t). Obviously, there exists a moment of time ti for which the interval (0; ti) is an integer number of the y(t) function periods. However, in practice, measurements of the Y values can be made with a variable time step, often skipping i-th samples. This makes it impossible to iteratively pass through all points in time at an equal step to analyze the y(t) function behavior, so it becomes necessary to obtain the missing values of Y, that is, to move from the Y values to the Y' values pending at regular time intervals.

A linear interpolation could be used for y'(t) missing values estimation. Having computational complexity of O(1), it provides more precise period estimation [16].

Since the period T includes an integer number of intervals At (provided that T > At and Tmod At = 0), at time ti the y'(ti) = y'(ti — T) equality is true. Thus, two arbitrary adjacent equal intervals in which the y'(t) function will have the same behavior can be found to search for a period in the sample.

In the proposed method, an iterative passage through the normalized sample of a given value is used, starting from the moment of to, that is, the moment of its first measurement. At every second moment of time ti the interval t = ti —10

is divided into two equal segments t0 ... ti/2 and ti/2 ... ti respectively. If the y'(t) behaves identically on the obtained segments, then the segment ti/2 is the desired y'(t) function period.

Considered many ways to assess the functions characters similarity. In the proposed method, as a measure of the y'(t) function behavior similarity degree on time intervals t0 ... ti/2 and ti/2 ... ti Pearson correlation coefficient r is used, which is calculated according to the formula (1).

cov(to . . . ti/2 ,ti/2 ...ti)

r = ~f-T-r -i" (1)

a[t0 . . . ti/2] * a[ti/2 . . . ti]

Here, the correlation moment cov(t0 ... ti/2, ti/2 ... ti) is defined as cov(X, Y) = M[(X — M[X]) * (Y — M[Y])], where M is the mean value defined for the series of values analyzing task as the arithmetic average. The standard deviation a is defined as a = ^M[X2] — M[X]2.

Due to the limitation on the method computational complexity, for calculating M and a values, required for the r coefficient determination, it is proposed to also store £N=0 y'(tj) and N=0 y' (tj )2 sums for each value of the y' (ti) function. This makes it possible to reduce the mean value determination time of the sample to the time of calculating the difference between two values and the quotient, and the operation computational complexity is O(1), while the r coefficient calculating computational complexity decreases to O(N).

Thus, for each second sample of the y'(t) function, the similarity degree of the two functions describing both halves of a known values series is calculated, respectively. If the correlation r exceeds a certain threshold value R, the t' = ti/2 value is assumed to be a multiple of the function period T. In this case, the t' value s placed in the table of the y'(t) function expected periods. This table is a correspondence of a supposed period T/ and the number of times n, which this period was recorded among the y' (t) function values y' (t) with a high degree of similarity. Therefore, it is necessary not only to estimate the y'(t) function halfsegments similarity degree of the half-segments of the function when processing the next incoming samples of the y'(t) function, but also to evaluate the added samples similarity of the function with all multiple expected periods.

To increase the accuracy of the obtained results, the n value can be considered not the number of periods occurrences in the set of the function known values, but the calculated correlation coefficients sum. In this case, for r ^ R the n value will increase by the An = R ^ An ^ 1 value. Such an approach does not decrease the proposed method algorithmic complexity, however, it will require slightly more floating-point calculations, which may be undesirable, for example, in embedded systems.

In the course of numerous experiments it was found that for ideal functions (sinusoidal, meander, sawtooth and triangular) the suitable value of R is 0,999. On data received from Russia's largest traffic exchange point [17], high estimation accuracy is achieved at R = 0, 9. In the general case, it is proposed to estimate R using preparatory simulation experiments or use R = 0,8.

4 Composition

To solve the problem of designing cloud systems [18] with non-stationary processes it is important to identify the properties of the nonstationary distributions composition. Let two non-stationary processes are given by non-stationary distributions (2) and (4).

{swn(x,t) = a(\f(t),x){g)

®b(\g(t),x) (3)

A h{t) = c{t) + d{t) ( comp(x,t) = (a(Xf(t),x) + (4) \ + b(Xg(t),x))/2 (5)

(Xh = c{t) + d{t)

To calculate the sum of these processes (3), it is assumed that the probability density function can be represented as a convolution of the original probabilty density functions [19], and to calculate their composition (5), the probability density function can be calculated as the half-sum.

To estimate an average and maximum queries intensity one can just sum the relevant values: A(t) = c(t) + d(t) and Xmax(t) = cmax{t) + dmax(t). All of those hypothesis have been successfully tested with a following model in AnyLogic Professional 7.0.1 simulation environment:

f{x,t) = ci(\f(t),x) X f(t) = c(t)

g(x,t) = b(\g(t),x) X g(t) = d(t)

-.-a - -a

-.-a - -a

Fig. 2. AnyLogic model

The model (Figure 2) has the following parameters: A^ (t) - input streams intensity; b - application processing time; A\(r) and A2(t) - input stream probability density functions; B(t) - application processing time probability distribution function; characteristic oa the model: p - load average.

As a result of modeling the following property was identified: if the sum of average values of intensity does not exceed intensity of service [20], then, regardless of the sum of maximum values of intensities, the system will not pass to constantly overloaded state [21]. Thus, with sufficient storage capacities in such systems, mass losses do not occur. The revealed property allows to draw conclusions about the expediency of redistribution of non-stationary load in cloud systems to solve the problem of automatic scaling of the cloud [22]. However,

the question of choosing suitable storage capacities remains open, so that the system functions correctly, without mass loss of applications [23].

Taking into account the confidence intervals with a confidence probability of 95% and the generally accepted error of simulation modeling of 5% [24], it can be concluded that at constant average intensities of incoming flows the total intensity is their sum.

5 Approximation

Let there be a series of non-stationary distributed data X = (x0, xi,..., xN), the distribution intensity of which A varies according to some time depinding periodic law: A(t), meanwhile the probability distribution function does not change.

Let A(t) be a periodic function, having the form of a sinusoid with a period T. Then the following function can be found (6), where A - the sin amplitude, 00 - the initial phase, C - the shift on the y-axis, which will most closely match the original A(t).

A' (t) = A * sin(u(t) + 00) + C (6)

At the same time, the Pearson correlation coefficient r can be chosen as a measure of compliance [24].

That is, the task of the X set approximation is reduced to the selection of such values A, 00, u and C, for which A(t) and A (t) have the highest correlation coefficient r value.

At the first stage of the method, it is proposed to obtain a set of averaged values Ai (i e (0..mT),m e N) with a length of one or several A(t) function periods by averaging the measured X values at i + kT points, where

k = (0,1,2,..., mr — 1).

Since /0 (A * sin(t) + C)dt = 2knC, C is the A(t) function's average [25].

TN A

Thus, C can be obtained as C = ^1, given number of A values N is multiple of the period [26].

The sine amplitude A can be calculated using the mean square of Ai values:

A =\J2*Ej=° a2. Or, given the value of C, A = \J2*E"o^izg^.

Having A and C values, the initial phase 00 could be estimated as follows, resulting in A (t) estimation. Consider 00 at point t = 0: A(0) = A0 = A * sin(00) + C. There are only two potential values of 00: 00(1) = arcsin( a°AC ) and 00(2) = n — arcsin( ). To choose the correct one, Pearson correlation coefficient [27] could be used again, and the function with proper 00 value would have higher coefficient value.

The proposed numerical method makes it possible to approximate periodic non-stationary distributions whose change in time is sinusoidal [28] and represent it in a form of (6). The method is tested with different types of synthetic signals and in all cases demonstrates a high degree of compliance of the results with the original data. The results of experiments with confidence intervals are presented in the table below.

Table 1. Experiment results

Signal type Correlation coefficient with exponential distribution Correlation coefficient with Erlang distribution, k=5

Sine Triangle Saw Meander (duty cycle 2) Meander (duty cycle 7/10) 0.890 ± 0.002 0.671 ± 0.006 0.712 ± 0.002 0.68 ± 0.02 0.58 ± 0.03 0.973 ± 0.002 0.915 ± 0.001 0.765 ± 0.001 0.75 ± 0.02 0.71 ± 0.04

We can conclude that for the case of low coefficient of variation [28] (v = , the Erlang distribution with k = 5), the method as a result sets the function A (t), strongly correlating with the initial A(t) for the sine and triangular wave and, in general, acceptable results in all other cases.

This fact confirms the possibility of using the method in practice for systems having a similar workload.

6 Putting results into practice

The results obtained in the work can be applied in algorithms for automatic scaling of cloud computing systems. For example, let the cloud system have two

nodes that run instances of the cloud application, shown on Figure 3.

* *

User 1 User 2

Fig. 3. Cloud system components and deployment

A workload from two users (User 1 and User 2) is distributed between the nodes, which is shown by solid and intermittent lines, respectively. Suppose each user creates a sinusoidal antiphase workload on the compute nodes. If we sum up the maximum values of the users workload intensities, we can make the erroneous conclusion that at least two nodes are needed to work simultaneously to ensure the required performance. At the same time, if we take into account the information about the nonstationarity of the load created by users and take advantage of the results obtained in the work, there will be no overload state with just one computing node. In this situation, the load balancer can send all user requests to one node, and the second node can be turned off to increase the energy efficiency of the cloud system.

Such an approach can significantly decrease energy consumption of large datacenters, in which cloud systems could use thousands and thousands of physical servers. Which is resulting in a huge economic cost reduce for the datacenter owners, who can farther reduce rent costs for end-users and increase their commerce income.

7 Conclusion

In this paper we proposed an analytical method for the nonstationary processes modeling and representation. This method includes the following: numerical parameterized method that allows to estimate a period length of non-stationary processes; a linear-equation nonstationary processes representation form, which allowed to carry out the estimation using standard mathematical transformations and operations; a numerical approximation method of periodic nonstation-ary distributions whose change in time is sinusoidal. This method helps to solve the problem of designing cloud systems with non-stationary processes.

References

1. Bogatyrev, Vladimir A., and A. V. Bogatyrev. "Functional reliability of a realtime redundant computational process in cluster architecture systems." Automatic Control and Computer Sciences 49.1 (2015): 46-56.

2. Park, K., Willinger, W. (2000). Self-similar network traffic and performance evaluation. John Wiley and Sons, Inc..

3. Bogatyrev, Vladimir A. "Fault tolerance of clusters configurations with direct connection of storage devices." Automatic Control and Computer Sciences 45.6 (2011): 330-337.

4. Aliev, T. I., M. I. Rebezova, and A. A. Russ. "Statistical methods for monitoring travel agencies in the settlement system." Automatic Control and Computer Sciences 49.6 (2015): 321-327.

5. Chhibber, Anju, and Sunil Batra. "Security analysis of cloud computing." International Journal of Advanced Research in Engineering and Applied Sciences 2.3 (2013): 2278-6252.

6. Mahon, Edward. Transitioning the Enterprise to the Cloud: A Business Approach. Cloudworks Publishing Company, 2015.

7. Kavis, Michael J. Architecting the cloud: design decisions for cloud computing service models (SaaS, PaaS, and IaaS). John Wiley and Sons, 2014.

8. Rafaels, Ray J. Cloud Computing: From Beginning to End. CreateSpace Independent Publishing Platform, 2015.

9. Buzzetto-More, Nicole A., ed. Advanced principles of effective e-learning. Informing Science, 2007.

10. Matthew Portnoy. Virtualization Essentials, 2nd Edition. New York: Wiley / Sybex, 2016

11. Jiang, Qiqi, Jianjun Qin, and Lele Kang. "A literature review for open source software studies." International Conference on HCI in Business. Springer, Cham, 2015.

12. Bogatyrev, Vladimir A., S. V. Bogatyrev, and I. Yu Golubev. "Optimization and the process of task distribution between computer system clusters." Automatic Control and Computer Sciences 46.3 (2012): 103-111.

13. V.A. Bogatyrev M.S. Vinokurova. "Control and Safety of Operation of Duplicated Computer Systems" Communications in Computer and Information Science, vol. 700, pp. 331-342 2017.

14. Grossman, Robert L. "The case for cloud computing." IT professional 11.2 (2009): 23-27.

15. Lee, Gillam. "Cloud Computing: Principles, Systems and Applications/Nick Antonopoulos, Lee Gillam." L.: Springer (2010).

16. Park, Kihong, and Walter Willinger. Self-similar network traffic and performance evaluation. John Wiley and Sons, Inc., 2000.

17. Marston, Sean, et al. "Cloud computing—The business perspective." Decision support systems 51.1 (2011): 176-189.

18. Mao, Ming, and Marty Humphrey. "A performance study on the vm startup time in the cloud." 2012 IEEE Fifth International Conference on Cloud Computing. IEEE, 2012.

19. Boniface, Michael, et al. "Platform-as-a-service architecture for real-time quality of service management in clouds." Internet and Web Applications and Services (ICIW), 2010 Fifth International Conference on. IEEE, 2010.

20. Cover, Thomas M., and Joy A. Thomas. "Elements of information theory 2nd edition." Willey-Interscience: NJ (2006).

21. He, Sijin, et al. "Elastic application container: A lightweight approach for cloud resource provisioning." Advanced information networking and applications (aina), 2012 ieee 26th international conference on. IEEE, 2012.

22. Rashvand, Habib F., ed. Using cross-layer techniques for communication systems. IGI Global, 2012.

23. Gogouvitis, Spyridon, et al. "Workflow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 (2012): 193-209.

24. Gogouvitis, Spyridon, et al. "Workflow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 (2012): 193-209.

25. Gogouvitis, Spyridon, et al. "Workflow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 (2012): 193-209.

26. Gogouvitis, Spyridon, et al. "Workflow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 (2012): 193-209.

27. Gogouvitis, Spyridon, et al. "Workflow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 (2012): 193-209.

28. Bogatyrev, V. A. "Protocols for dynamic distribution of requests through a bus with variable logic ring for reception authority transfer." Automatic control and computer sciences 33.1 (1999): 57-63.

Mathematical Modeling in Cloud Systems

Autoscaling

S. A. Zhmylev, I. G. Martynchuk

Saint Petersburg National Research University of Information Technologies, Mechanics and Optics University ITMO

Saint Petersburg, Russia Email: [e-mail]; [e-mail]

Abstract—The problem of forecasting the workload in the autoscaling services of cloud systems is considered. Methods are proposed for mathematical modeling of the non-stationary process of receiving users requests, allowing as a result to form an analytical model of the workload. Using the models generated in real time, the required configuration of the cloud system is synthesized. The practical significance of the work lies in the possibility of using the developed methods as part of the automatic scaling modules of cloud systems, ensuring more efficient management of their infrastructure resources.

Keywords—cloud systems; mathematical modeling; autoscaling; architecture; periodic processes

I. Introduction

Due to a significant expansion of the audience of Internet services users, increasing requirements for quality of service, as well as the tendency to move from placing their own hardware resources in private data centers to cloud providers, it becomes urgent to forecast the load on a cloud application and manage cloud resources in real of time. A cloud system is a collection of virtualized hardware resources used to run cloud applications. In turn, the architecture of cloud applications, as opposed to classic ones, implies efficient horizontal scaling. This allows real-time adaptation of the cloud application infrastructure to changes in load processes. This process is called automatic scaling of the cloud application.

In a typical case, in the context of cloud systems, three stakeholders can be distinguished: the cloud system user, the owner of the cloud application, the owner of the cloud system [1]. Services provided by owners of cloud applications and systems can be divided into three main categories.

A. Infrastructure as a service

In this model, as a service, the user is provided with infrastructure resources, including servers, data storage systems, network equipment, and a place in the data processing center. A distinctive feature of cloud platforms in this case is that all the above listed resources are provided using virtualization technologies such as VMWare ESXi, QEMU / KVM, Xen, etc. Thus, the user is given the opportunity to build and manage their own virtual infrastructure on top of the physical infrastructure of the data center.

B. Platform as a service

This model as a service implies software or development environment, on the basis of which higher-level services and applications are located. Users are given the opportunity to run their own applications, placing them on the infrastructure resources of the provider, providing some platform. For successful deployment and management of user applications, the platform must contain a specific set of software. In a typical case, this set may include an operating system and an application server.

C. Software as a service

In this model, the end user is provided with a complete instance of an application as an on-demand service. Examples of such applications can be various project management and collaboration systems, online organizers, document management systems, etc. Users do not require any investment in server hardware or software licenses.

Due to the process of automatic scaling, the owner of a cloud application can reduce the cost of renting cloud resources while maintaining the quality of user requests. At the same time, by turning off and redistributing hardware capacities, the owner of a cloud system can reduce the cost of consumed energy resources [2].

II. Formulation of the problem

In open sources there is no documentation of the proper level, which does not allow analyzing and qualitatively implementing software modules for automatic resource management. First of all, the analysis of eight approaches to building architecture, used by experts in more than 95 percent of cases: ARIS, TOGAF, Zachman Framework, IDEF, SWEBOK, FEAF, 4 plus 1 view, RM-ODP [3]. Among the methods considered, the first three offer a broader view of the corporate architecture [4]. Since the ARIS framework is a closed corporate, its use is severely limited. The Zachman model was used at the end of the 20th century and currently does not take into account all aspects of corporate architecture. The TOGAF approach, which is continuously being developed at the present time [5], has absorbed the advantages of the two previous ones, so it was chosen for this work. Key elements of the architecture [6] and their relationships are presented in the levels view shown in Fig. 1. The achievement of the target state determines the used IT strategy, within which the system

978-1-7281-2288-5/19/$31.00 ©2019 IEEE

needs the possibility of automated resource management. This feature is provided by the automatic scaling module that is part of a cloud application that provides an application service, which runs the main business process and provides an external business service to users. The automatic scaling module uses cloud infrastructure based on leased servers from multiple data center servers.

Fig. 1 Layered viewpoint on the autoscaling architecture.

The analysis of the four most common open source systems: Apache CloudStack, OpenStack, OpenNebula and HPE Eucalyptus [7]. With the use of indirect features: the configuration interface and user parameters, in addition, the analysis of cloud systems with closed source code was performed: Amazon AWS and VMware vSphere [8]. In all the considered systems, the autoscaling algorithm uses instant loading of hardware resources as a condition for changing the number of running copies of a cloud application. When the specified upper instantaneous load threshold is reached, the next computational node starts up, as a result of which the load value decreases [9]. A similar process occurs when a given lower load limit is reached: the number of computational nodes decreases in accordance with the configuration of the automatic scaling module. The activity diagram of the algorithm in the UML notation is presented in Fig. 2.

Fig. 2. Activity diagram of naive autoscaling algorithm.

In practice, when modeling real systems, a number of different assumptions are used. The purpose of using such assumptions is to simplify the models of the systems under study, allowing to calculate the characteristics of their functioning while maintaining an acceptable degree of adequacy. The main one of such assumptions is the assumption that processes occurring in simulated systems are stationary. Therefore, such an assumption implies the use of stationary distributions, which, in turn, allows the use of well-known analytical methods of queuing theory.

However, the processes occurring in real systems do not have the property of stationarity. This is due to various factors affecting the nature of user requests: time of day, time of year, calendar events, personal preferences of users, etc. Consequently, the question arises of the adequacy of the simulation results obtained by using stationary distributions. In addition when designing cloud systems for hosting large applications, the problem of geographic distribution of users arises.

Flows created by users of large cloud applications can differ in a different set of parameters: periodicity, intensity, etc. The transition to stationary processes in modeling does not allow to consider the nonstationarity of the processes of user requests to such applications. Consequently, there is no possibility of performing operations with non-stationary distributions describing load processes on cloud systems. Operations such as adding and merging multiple user request flows defined by non-stationary distributions can allow one to more accurately predict the load when designing and managing cloud systems. This problem is often solved with the help of simulation. However, in many cases, this approach may be unacceptable due to the possible complexity of the modeling process and the results obtained become less general.

That is, the algorithms used do not take into account historical data, and also cannot perform scaling based on the predicted load. This allows us to conclude about the low efficiency of the algorithms used under real loads.

Since the well-known analytical methods of the theory of mass service do not allow building models of non-stationary processes [10], the method of constructing a model of a non-stationary process was proposed. The following classification of non-stationary processes is formulated. By the nature of nonstationarity: periodic, aperiodic (for example, decaying) and chaotic. According to the assignment distributions: with a variable distribution function; with a variable parameter of the distribution law, but an unchanged distribution function; with changing as a parameter of the distribution law, and the distribution function. To ensure the possibility of building adequate models of network activity of real users [11], it was decided to analyze the load on network equipment of large distributed traffic exchange systems. Large traffic exchange points that provide workload information were selected for analysis: M-9 (MSK-IX), OST Dataline, StoreData, LinxTelecom, TrustInfo, and DataSpace. These services represent the highest level of the network hierarchy on the Internet and are intended for high-speed data exchange

between geographically distributed regions. The workload being analyzed fully corresponds typical user behavior due to high level of end-user localization for all considered services. The most common traffic for cloud systems has similar characteristics. Such a rule applies even for large-scale distributed systems as their architects typically decomposes the workload on a user location basis, implementing the content delivery networks approach. Fig. 3 is a graph of network activity obtained from the largest transport network hub of Russia [12] "Joint-Stock Company" Center for Interaction of Computer Networks "MSK-IX", according to which it can be concluded that the processes occurring in real systems belong to the class of periodic non-stationary processes.

3500

5 500 0

ooooooooooooooo

uSiiii-tNrcioddioiiiib'HiNtvjcooS .-i O fN .—I O tH O O tH O tH O o

^¿as&sk&soiailjajilia! "oooooaaoooaooo

Fig. 3. Network activity of the largest Russian Internet exchange point.

The following analytical form is proposed to describe the non-stationary distribution (1), which determines the real workload process.

f (x, t) = a(X f (t), x)

Xf (t) = c(t) (1)

In accordance with formula (1), any non-stationary distribution can be represented by a set of distribution function f (x, t) and time dependence of the distribution law parameter X f (t). To move from a real system to a model, first of all, it is necessary to obtain a sample of measurements of a given load

parameter. Then one should make a transition to the intensity

of incoming requests. For example, if the time interval between incoming user requests is used as the measured value [13], then the instantaneous intensity can be defined as the reciprocal. For the non-stationary processes investigation during measurements on a real system, it is necessary to take not only the numerical characteristics of the distribution into account, which affect the absolute values of the measurands, but also the periodic component describing distribution characteristics changing with time. There is a need to automatically estimate the period length based on a sample of measured values in order to present the observed process in an analytical form. Below we propose a method for such processes period length estimating to ensure their analytical description and research.

III. Period estimation method

Let there be a periodic non-stationary quantity Y, which is time dependent Y = y(t) with period P, the length of which is to be determined. By tabulating this value over time, one can get a finite series of N values of the value

{Y^} = y(0),y(1),...,y(N-1). Since the task requires low

computational complexity and fast convergence [14], simple arithmetic operations were chosen as the basic operations, and the method is a sequence of algorithms described below, as a result of which the value of the period P can be obtained.

A. Ranking possible period values

If we choose a certain value P' and perform piecewise averaging of the series {Yi}, choosing values with step P', that is, form a set

{Y '},T = {((P'ZNmP'y«) / N): m e [ON}, then it turns out that when P' = kP , where k e N , the values of the series {Yi} will correspond to the average values of the function y(t) over its period. At the same time, for P' ^ kP , where k e N , the values of {Yi} line up.

Using this property of non-stationary processes, one can estimate the period by the difference between the maximum and minimum values of the averaged function: if the expected period is not a multiple of the real one, then the result of averaging will tend to a straight line, therefore, the difference between the maximum and minimum values will be insignificant. For this estimate, it is necessary for all values of the estimated period P' to calculate the difference

HP, = max({YPj)-min({YP}). At the same time, the

possible period P'e (c1..c2), where c1 and c2 are the lower and upper bounds of the estimate, respectively.

B. The choice ofpoints to assess the nature of the function

At the same time, since the values of the assumed periods can take significant values, to calculate max({Y 'P '}) and

min({Y 'P '}) , it is required to take into account the value of

each point in the available sample. This approach requires numerous operations with the main memory and is characterized by low productivity [15, 16]. Therefore, it is proposed for ranking to take into account only ten to three points of the averaged function. Denote the number of points used for the evaluation as m. The boundary values for m are determined experimentally. When m < 3 , the probability of a successful evaluation tends to 0.5. When m = 10, the primary estimate allows ranking the considered series so that the value of kP is guaranteed to fall into the first 10% of the result. The procedure for selecting a specific value of m is presented below.

An important issue solved in the study was the choice of the interval between the points. As a result of numerous experiments, it was found that to minimize the risk of evaluation, in which the intervals between the considered

points are multiples of the period, the intervals should have different values, the greatest efficiency demonstrated with intervals corresponding to primes (supplemented by the value 1), scaled to the value of the estimated period. For example, if the expected period P' = 27 and decided to analyze the function by m = 4 points, it requires three intervals, which corresponds to the intervals between the first four primes: (1,2,3,5). At the same time, scaling them to the period it is

necessary to calculate the step as S = P'/ ^ i = 4.5, then

multiply S by the decremented interval values. The values of the averaged function used for further evaluation at P' = 27 : (0.4,9,18) are determined by rounding the result of the multiplication.

C. Selection of estimated period boundary values

Since the processes occurring in real systems are characterized by a high degree of randomness [17, 18], to level out random emissions of a function, it is necessary to maximize the number of intervals of piecewise averaging (minimize the value of c2 ). At the same time, in view of the specifics of actually functioning systems [19], it is necessary to ensure conditions under which a one-day period is successfully estimated for a weekly series of measurements. Therefore, the value of c2 is advisable to choose as the length of the original series N / 6 , which guarantees the inclusion of N /7 (corresponding to one day per week) in the set of possible values of P ' . This fact also allows us to conclude that the estimated period should be at least six times fit into the series of measured data, which is further used to calculate

c1.

The choice of the lower boundary of c1 depends on the method used to select intervals for piecewise averaging. When using intervals based on prime numbers, the value of c1 can

be defined as с1 = 6^^ Y(i), где Y(i) is a function, returning the i-th prime number. If during the determination of the lower bound it turns out that c1 > N, it is necessary to decrease m and repeat the estimate of the lower bound. To reduce the value of m makes sense for all values of m > 2 .

D. Initial evaluation of estimated periods

After selecting the points to assess the nature of the function and the boundary values for the estimated period, one can create a key-value table D based on the source series {Yi }"0, where the estimated period P' is used as the key, and the HP' as the value. The next step is to generate a set {B} of values that are not function periods. Initially it is assumed that

{B} = 0.

To complete the initial assessment is required in the cycle to perform the following steps.

1. Exclude from D all entries for the keys contained in

{B}.

2. If D contains no records, exit the loop. If by this time the estimate of the period did not produce a result, then complete all calculations, resulting that the period could not be determined.

3. Sort D records by the value in descending order. In case of identical values for different keys - sort by key values in ascending order.

4. Select the first entry D1 from D and perform the detailed standard deviation check described below, which leads to the conclusion whether the value D1 can be a period of the original function or a multiple of it. If the check fails, the value of D1, as well as all its multiples, must be placed in {B} and move to the next iteration of the loop. Otherwise, exit the loop assuming that D1 is a multiple of the period of the original function.

At the output of the first cycle, it is necessary to form the set of values {F} , multiples of D1, not contained in {B} and rank this set in ascending order. Then, by the ranked set in the loop, perform detailed checks on the standard deviation and total values, described below. If for all values of {F} the tests gave a negative result, then the value D1 is necessary and all multiples of it should be placed in {B} and return to step one of the first cycle. At the same time, if the results of both checks for some verifiable value PF from the series {F} are positive, then the value PF corresponds to the desired period of the function.

E. Detailed standard deviation check

The check is based on the fact that for the estimated period P', as well as the values of P '-1 and P'+1, the sum of the standard deviations of periodically repeating points is calculated: sq(P), sq(r-1) and sq(P,+t), respectively.

Considered set {Yi} is divided into subsets in accordance with the checked period value. For example, let the considered set {Yi} = y1, y2, y3, y4, y5, y6, y7, y8,y9 . Then, for the estimated period P' = 3 , the value of sq(P5 will be calculated as the sum of the standard deviations of the following sets: {y1,y4,y7},{y2,y5,y8} and {y3,y6,y9}. Based on the nonstationarity property, which amplifies periodic data, the check is considered successful if sq(P) < sq{P,-i) and

sq{P5 < sq(P,+i), since for P' = kP periodically repeating function values will have less variation relative to each other.

F. Detailed check on total values

By analogy with the previous one, this check is based on the calculation of three values sum(P 5, sum(P'-1) and sum(P'+1),

and each value is calculated as follows. Periodically repeated values of the original set are selected and averaged. For example, let the considered set

{Yi} = y1, y2, y3, y4, y5, y6, y7, y8,y9 . Then, to check the

estimated period P' = 3, the sum sum(r) will require averaging the following sets: s1 = {y1, y4, y7}, s2 = {y2, y5,y8} and s3 = {y3, y6, y9}. The result of such

averaging is the average values of the function on the period: s1, s2 and s3 . Then the arithmetic average s of these values is determined and the resulting sum sum(is calculated as

mr) = S(i=12 3) | st - s |. The check is considered successful

if sum(pP') > sum(pf'_rj and sum(pF,) > sum(pr+rj .

To test the accuracy of the method, a program has been developed that runs algorithms with different sets of parameters. Testing was conducted on a system with a CPU AMD FX 8120 with a clock frequency of 3.1 GHz in a single-threaded mode. The original signal was generated with an amplitude of 1. Varied: the waveform (sine wave, cosine wave, negative phase sinusoid, sawtooth, square wave, square wave with a duty cycle of 2.33, triangular and linear), period value (from 1 to 140), multiplier for amplitude (from 1 to 7) and the amplitude of the superimposed random noise (from 0 to 0.7).

In the course of numerous experiments for a linear stationary signal, it was not possible to successfully evaluate the period in any of the cases. This is due to the fact that the linear signal has no periodicity. In all experiments, the evaluation result corresponded to the upper boundary of the expected period, which allows to conclude that the method is not very effective for analyzing non-periodic signals. The percentage of errors for the other waveforms has the same value, which indicates that, on average, the method gives the same results for different waveforms, and this is due to errors that occur when estimating periods beyond the scope of the method. This led to the conclusion that the method is suitable for operation under conditions of a rapidly changing periodic non-stationary load.

IV. Models of nonstationary processes

Using a known period value, one can perform piecewise averaging of the intensity function by obtaining a set of

averaged points X'. Each such point is the arithmetic mean of a sample of multiples of the period of the intensity function values. At the same time, the distribution function f (x, t) can be obtained by approximating this sample by known methods [20]. Then a sample of averages X' can be approximated by known functions: sinusoid, polynomial or linear. For each approximation result, it is necessary to calculate its correlation coefficient with the original sample X' and select the approximation result with the highest coefficient value as the time dependence of the distribution parameter Xf (t). As a

result, we obtain a model of a nonstationary process in an analytical form (1).

Consider the schematic diagram of the relationship of user load with the infrastructure components of cloud systems, presented in Fig. 4

It can be seen that in a real cloud system more than one instance of a cloud application often functions; therefore, the total stream of user requests can be decomposed into separate flows for each instance of a cloud application. If we sum up the maximum values of the intensities, then we can make the erroneous conclusion that at least two nodes need to work simultaneously to ensure the necessary performance [21]. At the same time, if we take into account the information on non-stationarity, build analytical models of the load created by users and calculate the maximum intensity of the total flow, overload may not occur when only one node is operating.

suppose there are two nonstationary distributions, presented in analytical form (2) and (3), respectively.

f (x, t) = a(X f (t), x) X f (t) = c(t)

(2)

g (x, t) = b(X g (t), x)

X g (t) = d (t)

(3)

Fig. 4. Component diagram of the cloud system.

It was found that to determine the sum of such distributions, one can calculate their convolution (4), and for calculating the composition - half-sum (5).

[ S ( x, t ) = a(X} (t ), x) ® b(X g (t), x) [Xs (t ) = c(t) + d (t )

|C( x, t) =

a(k j (t ), x) + b(k g (t ), x)

(t ) = c(t ) + d (t )

(4)

(5)

In both cases, the function of changing the distribution parameter can be found as the sum of the corresponding functions of changing the parameters of the original distributions. These results were confirmed in the course of numerous simulation experiments in the simulation environment AnyLogic Professional 7.0.2. The results of simulation experiments are presented in Table 1. In the model with one servicing device, two non-stationary distributions were used, the intensity of which ranged from 0.03 s-1 to 0.06 s-1, respectively. The intensity of the service was 0.1 s-1.

TABLE I.

Table 1. Simulation results.

Intensity function Phase intensity ratio of incoming waves Maximum load Average utilization

Sinusoidal Common-mode intensity 1.198 0.853 ± 0.004

The phase shift of the intensity of the second wave by n 0.901 0.857 ± 0.012

The phase shift of the intensity of the second wave by n/2 1.108 0.858 ± 0.01

Sawtooth Common-mode intensity 1.199 0.832 ± 0.08

The phase shift of the intensity of the second wave by /0,03 + 0,06 V 2 0.998 0.828 ± 0.07

When summing the mean values of the intensities, it is possible to make an erroneous conclusion [22] that the system will not become overloaded at an intensity of 0.09, that is, a single servicing device is enough to prevent mass losses in the system. At the same time, in systems with an accumulator of limited capacity and an in-phase varying load, mass losses in such systems will arise. If to estimate the required number of servicing devices, use the sum of maximum intensities, then in conditions of antiphase workload, in the worst case, exactly 50% of the equipment will stand idle.

V. Putting results into practice

Taking into account all the above approaches, the architecture of the automatic scaling module for the openNebula cloud platform has been designed. The main architectural artifact created is the class diagram shown in Fig. 5. Module components are selected in accordance with the single responsibility principle [23], widely used in the design of modular applications [24]. The central module of the system is designed to control the remaining components, and also implements the functionality of automatic scaling in accordance with the naive algorithm shown in Fig. 2. This module stores the daily history and uses the accumulated data to more accurately estimate the number of computational nodes required. The analytical modeling component stores an array of load process models for each cloud application. This component implements the functionality of the construction and composition of models of load processes, as well as the functionality of estimating the required amount of computing resources. The proposed methods computational steps implementation is highlighted in a computational module that implements the approximation, interpolation, search for limit values and other functionality for working with time series. The comprehensive functionality of the search and correction of the time series period is rendered into a separate component. As an interface for interacting with the cloud system, a component has been developed that implements a set of functions that allow manage and control machine state on demand.

2

Fig. 5. Class diagram of the autoscaling software solution

All proposed methods and components are implemented in real system using the high-level programming language Perl version 5.18. A development version of the application is distributed on open rights and available on GitHub [25]. The application is a cross-platform utility integrated with openNebula cloud system platform. The integration interface consists of numerous executions of openNebula administration utility as well as virsh command, which is essential for OpenNebula installation. We have developed some Ansible scripts to simplify infrastructure deployment and perhaps even integration of the solution in production-ready environments. There are six Ansible roles available in the repository, including ones being used as a test application. As a test environment, we have used IBM Blade Center H chassis stocked with eleven Hs21 blades. our test cloud applications had haproxy as a single point of entry for user requests. We have developed system images for automatic network-based installation of Debian GNU/Linux and automatic configuration using Ansible. There are two bash scripts in the repository which are used for haproxy dynamic reconfiguration. These scripts allowed us to dynamically scale our cloud applications. The applications itself are just simple cpu-intensive code, which corresponds by its utilization to real applications. We have used Apache Jmeter to perform load tests of the cloud system, measure its performance and analyze its functional behavior. Three test plans with different workload types have been designed and stored in the repository. A Perl code with functions for analytical modeling is separated into software libraries, which makes it reusable in a wide range of open source projects. All necessary code is supplied with user documentation in Perl plain old documentation format. There is a unit test script, which was used to perform numerous tests on period analysis code as well as the scrips could be used to automate any testing scenarios. Finally, there is an approximation algorithm activity diagram, which was created during the work.

VI. Results

As a result of the work, a classification of non-stationary processes was proposed, their analytical representation was proposed as a combination of the distribution density function and the change function of the distribution law parameter, and expressions were formulated for calculating the sum and composition of non-stationary distributions. A method is proposed for quickly estimating the period of a non-stationary process using a successive approximation of the result of calculations to the desired quantity. The obtained results were checked and confirmed using numerous simulation experiments in the AnyLogic Professional 7.0.2 simulation environment. The practical significance of the results lies in the fact that, unlike the existing methods of cloud resources automatic control, the proposed methods allow building analytical models of non-stationary workload processes and more adequately predict the load on a cloud application and perform dynamic real-time rebalance of the user requests flows with a guaranteed non-overloaded cloud system state. An automatic scaling module for openNebula cloud system was designed and developed during the work. The module implements the proposed approaches.

Acknowledgment

We thank Dmitry Afanasiev for assistance with system administration works and help with cloud system testing environment. We would also like to show our gratitude to Valeriy Kireev for his comments on an earlier version of our software, especially on a cloud system integration part.

References

[1] Cover, Thomas M., and Joy A. Thomas. "Elements of information theory 2nd edition." Willey-Interscience: NJ, 2006.

[2] V. A. Bogatyrev, S. V. Bogatyrev, and I. Yu Golubev. "Optimization and the process of task distribution between computer system clusters." Automatic Control and Computer sciences 46.3: pp. 103-111, 2012.

[3] Sean Marston, Zhi Li, Subhajyoti Bandyopadhyaya, Juheng Zhanga, and Anand Ghalsasib. "Cloud computing - The business perspective." Decision support systems 51.1: pp. 176-189, 2011.

[4] Buzzetto-More, Nicole A., ed. Advanced principles of effective e-learning. Informing Science, 2007.

[5] Lee, Gillam. "Cloud Computing: Principles, Systems and Applications/Nick Antonopoulos, Lee Gillam." L.: Springer, 2010.

[6] V.A. Bogatyrev M.s. Vinokurova. "Control and safety of operation of Duplicated Computer systems" Communications in Computer and Information science, vol. 700, pp. 331-342, 2017.

[7] Jiang, Qiqi, Jianjun Qin, and Lele Kang. "A literature review for open source software studies." International Conference on HCI in Business. springer, Cham, 2015.

[8] Gogouvitis, Spyridon, et al. "Workflow management for soft real-time interactive applications in virtualized environments." Future Generation Computer systems 28.1: pp. 193-209, 2012.

[9] Mahon, Edward. Transitioning the Enterprise to the Cloud: A Business Approach, Cloudworks Publishing Company, 2015.

[10] T. I. Aliev, M. I. Rebezova and A. A. Russ "Statistical methods for monitoring travel agencies in the settlement system." Automatic Control and Computer Sciences 49.6: pp. 321-327, 2015.

[11] Rafaels, Ray J. Cloud Computing: From Beginning to End. Create Space Independent Publishing Platform, 2015.

[12] V. A. Bogatyrev, "Fault tolerance of clusters configurations with direct connection of storage devices." Automatic Control and Computer Sciences 45.6: pp. 330-337, 2011.

[13] Kavis, Michael J. Architecting the cloud: design decisions for cloud computing service models (SaaS, PaaS, and IaaS). John Wiley and Sons, 2014.

[14] Park, Kihong, and Walter Willinger. Self-similar network traffic and performance evaluation. John Wiley and Sons, Inc., 2000.

[15] Rashvand, Habib F., ed. Using cross-layer techniques for communication systems. IGI Global, 2012.

[16] Grossman, Robert L. "The case for cloud computing." IT professional 11.2: pp. 2327, 2009.

[17] V. A. Bogatyrev, "Protocols for dynamic distribution of requests through a bus with variable logic ring for reception authority transfer." Automatic control and computer sciences 33.1: pp. 57-63, 1999.

[18] He, Sijin, et al. "Elastic application container: A lightweight approach for cloud resource provisioning." Advanced information networking and applications (aina), 2012 ieee 26th international conference on. IEEE, 2012.

[19] Boniface, Michael, et al. "Platform-as-a-service architecture for real-time quality of service management in clouds." Internet and Web Applications and Services (ICIW), 2010 Fifth International Conference on. IEEE, 2010.

[20] Mao Ming, and Marty Humphrey. "A performance study on the vm startup time in the cloud." 2012 IEEE Fifth International Conference on Cloud Computing. IEEE, 2012.

[21] V. A. Bogatyrev and A. V. Bogatyrev. "Functional reliability of a realtime redundant computational process in cluster architecture systems." Automatic Control and Computer Sciences 49.1: pp. 46-56, 2015.

[22] Chhibber, Anju, and Sunil Batra. "Security analysis of cloud computing." International Journal of Advanced Research in Engineering and Applied Sciences 2.3: pp. 2278-6252, 2013.

[23] Matthew Portnoy. Virtualization Essentials, 2nd Edition. New York: Wiley /Sybex, 2016.

[24] Robert C Martin. Clean architecture: a craftsman's guide to software structure and design. Prentice Hall Press, 2017.

[25] Sergey Zhmylove. Caler. GitHub repository, https://github.com/zhmylove/caler, 2/19.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ

УДК 004.056.53 DOI: 10.17586/0021-3454-2018-61-8-645-651

ОЦЕНКА ДЛИНЫ ПЕРИОДА НЕСТАЦИОНАРНЫХ ПРОЦЕССОВ

В ОБЛАЧНЫХ СИСТЕМАХ

С. А. Жмылёв, И. Г. Мартынчук, В. Ю. Киреев, Т. И. Алиев

Университет ИТМО, 197101, Санкт-Петербург, Россия E-mail: [e-mail]

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

Ключевые слова: периодическая функция, облачная система, численный метод, система с очередями, математическое моделирование

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

Облачная система представляет собой множество вычислительных систем, расположенных обычно в одном центре обработки данных (ЦОД), обслуживаемых одним и тем же коллективом и находящихся в юрисдикции одной управляющей организации [3, 4]. Управляющая организация предоставляет услуги аренды части вычислительной мощности облачной системы с помощью технологии виртуализации. Таким образом, арендатор получает некоторое количество виртуальных узлов одинаковой конфигурации, с помощью которых выполняется облачное приложение. Облачное приложение имеет единую точку входа для пользовательских

запросов и обладает свойством горизонтальной масштабируемости [5], благодаря чему структура облачного приложения скрыта от пользователей. Если в какой-то момент времени вычислительной мощности недостаточно, арендатор может приобрести дополнительные виртуальные узлы, увеличив общую производительность своего облачного приложения.

Периодические нестационарные процессы. Рассмотрим типовую облачную систему, в которой в общем случае можно выделить владельца ЦОД, арендатора облачной системы и пользователя облачной системы. При проектировании облачной системы владельцу ЦОД необходимо оценить максимальную нагрузку на приобретаемое аппаратное обеспечение с помощью ее описания в терминах теории массового обслуживания. Нагрузка, в зависимости от временных характеристик, может быть как стационарной, так и нестационарной. При этом характер нагрузки обусловливается изменением 1) параметров закона распределения, 2) функции распределения с сохранением параметров (в частности, математического ожидания), 3) как функции распределения, так и параметров закона распределения.

Среди нестационарных процессов выделяют следующие классы: периодические, апериодические (например, затухающие) и хаотические.

Поскольку реальные нагрузочные процессы не обладают свойством стационарности, широко используемые аналитические методы теории массового обслуживания не подходят для их описания и исследования. Поэтому возникает необходимость разработки методики исследования нестационарных процессов. Определяющие нагрузку на облачные вычислительные системы процессы относятся к классу периодических нестационарных процессов, что подтверждается, например, графиком сетевой активности крупнейшего в России узла обмена интернет-трафиком MSK-IX [6] (см. рисунок, здесь v — скорость передачи данных).

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

Существующие методы решения таких задач, как правило, связаны с анализом звуковых сигналов [7—9] или имеют иную, узкую область применения, что затрудняет их использование в сетевых вычислительных системах. Кроме того, эти методы не подходят для исследования протекающих в облачных вычислительных системах нестационарных процессов, поскольку функция, описывающая их изменения, не всегда имеет синусоидальный вид. Такие методы, как, например, метод быстрого преобразования Фурье (БПФ) не годятся для оценки периода сигналов с отсутствующей основной гармоникой [10, 11]. В частности, быстрое преобразование Фурье характеризуется низкой алгоритмической сложностью, но при этом требует большого количества операций

Оценка длины периода нестационарных процессов в облачных системах 647

с плавающей точкой, в том числе при постобработке результатов. Также несмотря на высокую производительность быстрого преобразования Фурье для сигналов, имеющих естественную природу, его применимость не всегда актуальна для „искусственных" сигналов, например в вычислительной технике. В частности, количество слагаемых, которое требуется вычислить для БПФ при обработке функций с разрывами, стремится к бесконечности, что делает вычисление невозможным. В этой связи представленный в настоящей статье метод для оценки длины периода Т нестационарного процесса должен удовлетворять следующим требованиям.

1. Оценка периода должна производиться при неполном наборе входных данных. Поскольку создаваемая пользователями нагрузка изменяется со временем, для управления облачной системой необходимо в „реальном времени" оценивать длину периода процесса поступления заявок в систему.

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

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

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

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

Описание метода. Пусть имеется некоторая периодическая величина У, зависящая от времени — У = у(V). Очевидно, существует такой момент времени , для которого интервал

(О ) представляет собой целое число периодов функции у(V). Однако на практике измерения значений У могут производиться с переменным временным шагом, зачастую с пропуском г-х отсчетов. Это делает невозможным итеративный проход по всем моментам времени через равный шаг для анализа поведения функции у(V), поэтому возникает необходимость получения недостающих значений У, т.е. перехода от значений У к значениям У', отложенным через равные временные интервалы.

Для решения задачи получения недостающих значений функции у'(V) высокая эффективность достигается при линейной интерполяции. Ее вычислительная сложность составляет 0(1), при этом оценка периода по интерполированным значениям имеет более высокую точность. Поскольку период Т содержит целое число интервалов V (при условии, что Т > V и Т кратно V), в момент времени Ц справедливо равенство у' (VI) = у '(¿г- - Т). Таким образом, для

оценки периода в выборке можно найти два любых соседних равных по величине интервала, на которых функция у '(V) будет вести себя одинаково.

В предложенном методе используется итеративный проход по нормированной выборке заданной величины, начиная с момента to, т.е. момента первого измерения. В каждый второй момент времени Ц происходит разбиение интервала V = Ц - ^ на два равных отрезка: Ц --Л^ и /2 ..Л^. Если на полученных отрезках функция у '(V) ведет себя одинаково, то отрезок 1^2 является искомым периодом функции у '(V).

При разработке метода было рассмотрено множество способов оценивания схожести характеров функций. В качестве меры схожести поведения функции у'(¿) на отрезках времени ¿0 ■■■¿1 /2 и /2 ..л1 принят коэффициент корреляции Пирсона г , который рассчитывается по формуле

г = ^¿0 — Ц^Ь/2 ■■i)

а[ —и/2 ]а[/2 —и ]

Здесь корреляционный момент cov(to — /2, ¿г-/2 — ) определяется как осу(Х ; У) = М [(X - М [ X ])(У - М [У ])], где М — математическое ожидание (для задачи анализа ряда значений — среднее арифметическое), среднеквадратическое отклонение определяется как а = ^М X2 -М [X]2 .

Вследствие ограничения на вычислительную сложность разработанного метода для расчета величин М и а предлагается для каждого значения функции у'^) хранить в памяти

N N 2

вспомогательные суммы ^y'(tj) и ^У ^ ) , где N — количество рассмотренных времен-

7=0 j=o

ных отсчетов. Это позволяет сократить время определения математического ожидания выборки до времени вычисления разности двух величин и вычисления частного. При этом вычислительная сложность расчета М составит 0(1), а вычислительная сложность расчета коэффициента г уменьшится до 0(N).

Таким образом, для каждого второго отсчета функции у' ^) вычисляется степень схожести двух функций, характеризующих интервалы ¿0 ..Л1 /2 и /2..Л1 соответственно. Если коэффициент г превысил некоторое пороговое значение Я , величина t' = ¿г/2 предполагается кратной периоду функции. В этом случае величина ¿ указывается в таблице предполагаемых периодов функции у' ^). Эта таблица характеризует соответствие некоторого предполагаемого периода Т' и количества раз п, которое данный период был зафиксирован среди значений функции у' (¿) с высокой степенью схожести. Соответственно при обработке следующих поступающих отсчетов функции у' ^) необходимо оценить не только степень схожести указанных интервалов функции у' ^), но и схожесть добавленных отсчетов функции со всеми кратными предполагаемыми периодами.

Для увеличения точности результатов величину п можно считать не числом вхождений периодов во множество известных значений функции, а суммой рассчитанных коэффициентов корреляции. В этом случае при г > Я значение п будет увеличиваться на величину Ап : Я < Ап < 1. Такой подход не повышает алгоритмическую сложность предлагаемого метода, однако требует несколько большего количества вычислений с плавающей точкой, что может быть нежелательно, например, во встраиваемых системах.

Пример. Пусть в момент времени ¿12 для некоторой функции у ) известна следующая таблица предполагаемых периодов: [2 ^ 3;4 ^ 2;5 ^ 1]. В первую очередь необходимо выбрать из таблицы все кратные предполагаемые периоды. В данном случае из таблицы будут выбраны значения 2 и 4 . Затем для этих значений необходимо оценить корреляцию г соответствующих отрезков функции у'(¿). Для значения 2 — на отрезках 8 < t < 10 и 10 < t < 12, а для значения 4 — на отрезках 4 < t < 8 и 8 < t < 12. Если г > Я, то таблица предполагаемых периодов примет вид [2 ^ 4;4 ^ 3;5 ^ 1]. В противном случае из таблицы предполагаемых периодов исключается значение, при котором величина г не превышает пороговое значение Я.

Оценка длины периода нестационарных процессов в облачных системах 649

Наконец, необходимо оценить корреляцию г отрезков 0 < V < 6 и 6 < V < 12. Если г > Я, то в таблицу предполагаемых периодов добавляется запись [6 ^ 1].

Вопрос выбора значения Я , при котором получаемая оценка длины периода Т функции максимально соответствует реальной, требует особого внимания. Поскольку данная величина определяет нижнюю границу для функции автокорреляции, то чем меньше значение Я, тем больше вычислений потребуется произвести на каждом шаге алгоритма. Если Я < 0, то автокорреляция негативно влияет на получаемый результат: в лучшем случае (Я ^-1 и сумма полупериодов функции равна нулю) определяется длина полупериода, в остальных случаях период определить не представляется возможным. Следовательно, целесообразно всегда выбирать Я > 0 . С другой стороны, выбор слишком большого значения Я приводит к неточности выявления похожих выборок. Поскольку реальные процессы случайны по своей природе, корреляция периодов этих процессов никогда не достигает значения г = 1, хотя и стремится к нему.

В ходе экспериментов выявлено, что для идеальных функций (синусоидальной, меандра, пилообразной и треугольной) подходит значение Я = 0,999 . Согласно данным, полученным с узла MSK-IX [6], высокая точность оценки достигается при Я = 0,9. В общем случае предлагается оценивать Я с помощью подготовительных имитационных экспериментов либо использовать Я = 0,8.

В любой момент времени , если необходимо оценить длину периода функции у'(V), можно из таблицы предполагаемых периодов выбрать подмножество вариантов Т{, имеющих максимальное значение п. Затем оценить период функции у'(V) как медиану выбранного подмножества. Например, если таблица предполагаемых периодов имеет вид [4 ^ 2;5 ^ 2; 6 ^ 2;8 ^ 1;10 ^ 1], то nmax = 2, выбранное подмножество — [4; 5;6], а период Т = 5 .

Результаты. В ходе экспериментов с синусоидальным, треугольным, пилообразным, линейным и прямоугольным сигналами, амплитуда которых формировалась как идеальными функциями, так и функциями с наложенным случайным шумом, достигающим 50 % амплитуды исходного сигнала, выявлено, что при анализе выборок, состоящих от 2Т до 2 000 последовательных измерений функции у' (V) с периодом Т > 6, длина периода оценивалась верно в 99,9 ± 0,1 % случаев с доверительной вероятностью 0,95 . Анализ выборок с периодом 2 < Т < 6 продемонстрировал неэффективность метода при работе с функциями, имеющими такой период. Однако в результате оценки длины периода всегда и безошибочно определялись значения, кратные периоду: кТ, к е 2...16 . Такая неточность в оценке периода обусловлена тем, что взаимокорреляция длинных выборок значений зашумленной функции больше, чем взаимокорреляция коротких серий. Принимая во внимание область, для которой разработан метод оценивания длины периода в нагрузке на облачные системы, данной неточностью можно пренебречь, поскольку сигналы с малым значением периода можно считать стационарными, имеющими больший разброс. При анализе данных о сетевой активности в течение недели и месяца, полученных с узла MSK-IX [6], погрешность определения длины периода составила 0,1 ± 0,05 % от абсолютного значения с доверительной вероятностью 0,95.

Заключение. Предложенный численный параметризованный метод позволяет оценивать длину периода нестационарных процессов и полностью соответствует заявленным требованиям:

— позволяет работать с неполным набором данных за счет интерполяции выходных данных;

— позволяет пополнять таблицу предполагаемых периодов во время поступления данных;

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

к 0(N), а в худшем случае, когда таблица предполагаемых периодов содержит каждое второе

— занимает объем памяти, линейно зависящий от входных данных: в худшем случае в памяти хранится каждое значение функции, запись в таблице предполагаемых периодов и две записи в таблицах вспомогательных сумм;

— учитывает возможные погрешности измерений и случайные отклонения значений функции от среднего за счет варьирования порогового значения R .

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

1. Bogatyrev V. A., Bogatyrev A. V. Functional reliability of a realtime redundant computational process in cluster architecture systems // Automatic Control and Computer Sciences. 2015. Vol. 49, N 1. P. 46—56.

2. Bogatyrev V. A., Parshutina S. A., Poptcova N. A., Bogatyrev A. V. Efficiency of redundant service with destruction of expired and irrelevant request copies in real-time clusters // Communications in Computer and Information Science. 2016. Vol. 678. P. 337—348.

3. Беккер М. Я., Гатчин Ю. А., Кармановский Н. С., Терентьев А. О., Федоров Д. Ю. Информационная безопасность при облачных вычислениях: проблемы и перспективы // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2011. № 1 (71). С. 97—102.

4. Зикратов И. А., Одегов С. В. Оценка информационной безопасности в облачных вычислениях на основе байесовского подхода // Научно-технический вестник информационных технологий, механики и оптики. 2012. № 4 (80). С. 121—126.

5. Богатырев В. А., Богатырев С. В. Надежность мультикластерных систем с перераспределением потоков запросов // Изв. вузов. Приборостроение. 2017. Т. 60, № 2. С. 171—177.

6. АО „Центр взаимодействия компьютерных сетей МСК-IX". Суммарный трафик участников, передаваемый через MSK-IX [Электронный ресурс]: <https://www.msk-ix.ru/traffic>, 13.02.2018.

7. Sridhar P., Sheikh-Bahaei S., Xia S., Jamshidi M. Multi agent simulation using discrete event and soft-computing methodologies // Proc. IEEE Intern. Conf. on Systems, Man and Cybernetics. 2003. Vol. 2. P. 1711—1716.

8. Oppenheim A. V., Shchafer R. W. Digital Signal Processing. Pearson, 1999. 856 p.

9. Aliev T. I., Rebezova M. I., Russ A. A. Statistical methods for monitoring travel agencies in the settlement system // Automatic Control and Computer Sciences. 2015. Vol. 49, N 6. P. 321—327.

10. Чураев С. О., Адамова А. Д., Палташев Т. Т. Реализация алгоритма шумоподавления в речевом тракте систем мобильной связи на базе СБИС // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2011. № 1 (71). С. 72—76.

11. Коротков А. В., Мухин А. И. Усовершенствованный алгоритм анализа сигналов малозаметных радиолокационных станций на основе оконного преобразования Фурье // Научно-технический вестник информационных технологий, механики и оптики. 2012. № 1 (77). С. 33—36.

2

значение функции y'(t), сложность стремится к O(N );