Методы и алгоритмы автоматического масштабирования облачных систем с нестационарной нагрузкой тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат наук Жмылёв Сергей Александрович

• Жмылёв Сергей Александрович
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Жмылёв Сергей Александрович

Реферат

Synopsis

Введение

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

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

1.1.1 Подходы к организации облачных вычислений

1.1.2 Сервисы удаленных рабочих мест

1.1.3 Способы управления облачными системами

1.1.4 Алгоритмы автоматического масштабирования

1.1.5 Особенности потоков в облачных системах

1.1.6 Технико-экономическое обоснование работы

1.2 Проблема нестационарности в облачных системах

1.2.1 Соотношение нестационарности и случайности

1.2.2 Сложность исследования нестационарных процессов

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

1.2.4 Постановка задачи и направления исследований

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

1.3.1 Исследование патентов

1.3.2 Исследование непатентных источников

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

1.3.4 Заключение о патентном поиске

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

Глава 2. Анализ влияния нагрузочных процессов на характеристики функционирования облачных систем

2.1 Полимодальные процессы

2.1.1 Причины возникновения полимодальности в облачных системах

2.1.2 Проблема моделирования полимодальных процессов

2.1.3 Исследование влияния полимодальности на характеристики систем

2.2 Самоподобные процессы

2.2.1 Моделирование самоподобных процессов

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

2.3 Нестационарные процессы

2.3.1 Имитационная модель системы с нестационарным потоком запросов

2.3.2 Анализ влияния нестационарности на характеристики облачных систем

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

Глава 3. Разработка методов исследования нестационарной нагрузки

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

3.1.1 Автокорреляционный метод

3.1.2 Итерационный метод

3.2 Моделирование нестационарных процессов

3.2.1 Метод построения аналитической модели нестационарной нагрузки

3.2.2 Метод оценки времени до начала потерь в перегруженных системах с очередями

3.2.3 Метод композиции нестационарных потоков поступающих в облачную систему запросов

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

Глава 4. Методика автоматического масштабирования облачных

систем с нестационарной нагрузкой

4.1 Разработка алгоритма автоматического масштабирования

4.1.1 Анализ вычислительной сложности и области применения разработанных методов

4.1.2 Имитационная модель облачной системы

4.1.3 Минимизация энергетических затрат в облачной системе

4.1.4 Алгоритм автоматического масштабирования

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

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

4.2.2 Технические требования к тестовому окружению

4.2.3 Описание программы и методики испытаний

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

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

Заключение

Список аббревиатур

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

Приложение 1. Исходный текст программы, реализующей композицию плотностей распределений

Приложение 2. Акт о внедрении результатов в ООО «Тюн-ит»

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

Приложение 4. Нормативно-методическая документация

Приложение 5. Публикации по теме диссертации

РЕФЕРАТ

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

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

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

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

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

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

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

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

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

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

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

Степень разработанности проблемы.

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

описывающих решения, максимально полно соответствующие задаче исследования. Поиск патентной информации проводился в патентных базах данных Федеральной службы по интеллектуальной собственности, патентам и товарным знакам Российской Федерации (Роспатент, www1.fips.ru), Бюро по патентам и товарным знакам США (УБРТО, www.uspto.gov) и Европейского патентного бюро (ЕРО, www.epo.org). В дополнение выполнен обзор непатентных источников: научных публикаций, статей и литературы по теме диссертационной работы. Среди рассмотренных материалов не найдено ни одной публикации, описывающей подход, полностью соответствующий представленным в диссертационной работе идеям. Решения, наиболее близкие к представленным в работе, основываются на прогнозировании будущих состояний системы с помощью нейронных сетей и других численных методов машинного обучения. В рассмотренных публикациях описываются алгоритмы, не использующие аналитические методы моделирования для управления облачной системой, прогнозирования ее будущих состояний или анализа протекающих в ней нестационарных процессов. Таким образом, рассматриваемая проблема имеет низкую степень научной разработанности.

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

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

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

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

задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Соответствие диссертации паспорту научной специальности. Диссертационная работа соответствует паспорту научной специальности 05.13.15 «Вычислительные машины, комплексы и компьютерные сети», а проведенное исследование - формуле специальности. Исследование соответствует следующим пунктам паспорта специальности.

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

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

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

Апробация работы. Основные положения работы прошли апробацию на следующих научных конференциях: XX международная конференция «Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь» (2017 г.); XXII международная научная

конференция «Волновая электроника и инфокоммуникационные системы (WECONF-2019)» (2019 г.); MICSECS 2018 - The Majorov International Conference on Software Engineering and Computer Systems (2018 г.); VI, VII, VIII и IV Научно-практическая конференция молодых ученых «Вычислительные системы и сети (Майоровские чтения)» (2014-2018 гг.); VI Научно-практическая конференция с международным участием «Наука настоящего и будущего» (2018 г.); XLIV, XLV, XLVI и XLVII Научная и учебно-методическая конференция Университета ИТМО (2015-2018 гг.); II, III, IV, V, VI, VII и VIII Всероссийский конгресс молодых ученых (2013-2019 гг.).

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

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

1. НИР № 610481 «Разработка методов и средств системотехнического проектирования информационных и управляющих вычислительных систем с распределенной архитектурой».

2. НИР № 617026 «Технологии киберфизических систем: управление, вычисления, безопасность».

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

Объем и структура работы. Работа состоит из введения, четырех

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

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

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

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

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

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

3. На физическом узле может быть размещено столько ВМ, сколько позволяют физические ограничения. Если ВМ требуется 1 ГГц ЦПУ, а ресурсы физического узла ограничены 5 ГГц, то на таком физическом узле может выполняться не более пяти ВМ.

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

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

на классификация облачных систем (рис. 1) в соответствии со степенью автоматизации процесса управления системными ресурсами.

г.

V

Облачные системы

С полностью ручным управлением ресурсами

С автоматизированным управлением ресурсами

С полуавтоматизированным управлением ресурсов

С автоматическим управлением ресурсами

Рисунок 1 - Классификация облачных систем

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

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

1. Алгоритмы автоматического масштабирования облачных систем направлены на обеспечение эффективности использования аппарат-

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

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

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

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

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

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

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

О,

f(x) = { рХе^

Хх

X < О

О <х < D

рХе^Хх + (1 - p)Xe-^x~D\ х ^ D

М = В(1-р) + ^

где О - величина межмодового интервала, ар - вероятность поступления запроса для формирования первой моды.

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

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

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

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

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

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

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

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

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

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

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

ложения.

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

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

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

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

/ОМ) = а(\/{г),х) ;

а=

где А/(£) - функция изменения параметра распределения, а а(А/(£),ж) -функция плотности распределения.

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

-Период Т-

XI _

Х21 _

Хк21+1 _

X =

Х1 : Х2

Х+1

Х+2

Хк+1

Хк+2

Х1 х+1 Хк+1

V. У

Х2 V.

Х+2 Хк1+2

у

1оуо А,1,У1

Рисунок 2 - Принцип группировки исходных данных

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

фициента неустойчивости системы К:

t(E) К =

= Е( 1 - У1) - у\ (Л2 - //)( 1 - yi) ЗО/1У1Л2 _ ЯА1 '

X < 1 ,

где Е - емкость буферной памяти, yi,h - нагрузка на систему и средняя длина очереди до начала переходного процесса, соответственно, /х -интенсивность обработки запросов и А2 - интенсивность поступающих запросов в конце переходного процесса.

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

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

seq(x,t) = a(Xf(t), х) <g) b(Xg(t), х X h{t) = c{t) + d{t) и параллельная синхронная композиция

parseq(x,t) = w\a(Xf(t): x) + W2b(Xg(t): x c(t) + d(t) ; 1

A h(t)

2

E wi i= 1

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

исходных распределений а(А/(£),ж), 6(АР(£),ж) и весовых коэффициентах

т-ч V-/ V-/

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

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

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

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

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

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

VJ ТЛ VJ

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

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

Четвертая глава посвящена разработке методики автоматического масштабирования облачных систем с помощью разработанных методов. Выполнен анализ и определена вычислительная сложность для каждого из разработанных в работе методов, а также определены области их применения. Показано, что использование автокорреляционного метода оценки длины периода целесообразно только при недостаточном объеме архивных данных (рис. 3).

Для исследования предложенных методов в среде имитационного моделирования AnyLogic Professional разработана имитационная модель облачной системы с автоматическим масштабированием виртуальных машин для двух облачных приложений (рис. 4). Многочисленные имитационные эксперименты позволили выявить причины массовых потерь в облачных системах с нестационарной нагрузкой.

Автокорреляционный

10 100 1000 10000 100000 1000000 Длина анализируемого ряда, шт

Рисунок 3 - Зависимость времени получения результата от объема исходных данных для предложенных методов оценки длины периода

Мгновенная для Максимально

Рисунок 4 - Длины очередей облачных приложений с постоянной

структурой

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

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

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

т

к^ 1

Е

к=1

К

к

(*-1)! К\

К+Е к=Е

У_\к К

Ро

где - число ВМ, а - мгновенная нагрузка, может быть вычислено с учетом вероятности простоя системы:

Ро

К-1 ^ уК^Е+^уЕ+г^ -1

¿Ь Л! + К1К*(К^у)

К-1 к

—

(Е + 1)К К\

к

уфК;

у = К.

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

Список литературы диссертационного исследования кандидат наук Жмылёв Сергей Александрович, 2019 год

Литература

1. 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. doi: 10.1007/978-3-319-51917-3_30

2. Patel R.P. Cloud computing and virtualization technology in radiology // Clinical Radiology. 2012. V. 67. N 11. P. 1095-1100. doi: 10.1016/j.crad.2012.03.010

3. Moreno-Vozmediano R., Montero R.S, Llorente I.M. Iaas cloud architecture: from virtualized datacenters to federated cloud infrastructures // Computer. 2012. V. 45. N 12. P. 65-72. doi: 10.1109/mc.2012.76

4. Chang B.R., Tsai H.F., Chen C.M. Empirical analysis of server consolidation and desktop virtualization in cloud computing // Mathematical Problems in Engineering. 2013. V. 2013. 11 p. doi: 10.1155/2013/947234

5. Мартынчук И.Г., Жмылёв С.А. Архитектура и организация сервисов автомасштабирования в облачных системах // Альманах научных работ молодых ученых Университета ИТМО. 2017. Т. 5. С. 200-203.

6. Жмылёв С.А., Мартынчук И.Г., Киреев В.Ю., Алиев Т.И. Оценка длины периода нестационарных процессов в облачных системах // Известия вузов. Приборостроение. 2018. Т. 61. № 8. С. 645-651. doi: 10.17586/0021-3454-2018-61-8-645-651

References

1. 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. doi: 10.1007/978-3-319-51917-3_30

2. Patel R.P. Cloud computing and virtualization technology in radiology. Clinical Radiology, 2012, vol. 67, no. 11, pp. 10951100. doi: 10.1016/j.crad.2012.03.010

3. Moreno-Vozmediano R., Montero R.S, Llorente I.M. Iaas cloud architecture: From virtualized datacenters to federated cloud infrastructures. Computer, 2012, vol. 45, no. 12, pp. 65-72. doi: 10.1109/mc.2012.76

4. Chang B.R., Tsai H.F., Chen C.M. Empirical analysis of server consolidation and desktop virtualization in cloud computing. Mathematical Problems in Engineering, 2013, vol. 2013, 11 p. doi: 10.1155/2013/947234

5. Martynchuk I.G., Zhmylev S.A. Architecture and organization of autoscaling services in cloud systems. Al'manakh Nauchnykh Rabot Molodykh Uchenykh Universiteta ITMO. St. Petersburg, ITMO University Publ., 2017, vol. 5, pp. 200-203. (in Russian)

6. Zhmylev S.A., Martynchuk I.G., Kireev V.Yu., Aliev T.I. Estimation of periods of nonstationaty processes in cloud systems. Journal of Instrument Engineering, 2018, vol. 61, no. 8, pp. 645-651 (in Russian). doi: 10.17586/0021-3454-2018-61-8645-651

7. Cattani C., Kudreyko A. Application of periodized harmonic wavelets towards solution of eigenvalue problems for integral equations // Mathematical Problems in Engineering. 2010. 8 p. doi: 10.1155/2010/570136

8. Chen W.W., Liu S., Wang Q.J. Fast Fourier transform based numerical methods for elasto-plastic contacts of nominally flat surfaces // Journal of Applied Mechanics. 2008. V. 75. N 1. doi: 10.1115/1.2755158

9. Левина А.Б., Таранов С.В. Исследование влияния сложности функции кодирования на распределение вероятности маскировки ошибки // Научно-технический вестник информационных технологий, механики и оптики. 2016. Т. 16. № 2. С. 331-337. doi: 10.17586/2226-1494-2016-16-2-331-337

10. Bogatyrev V.A. Fault tolerance of clusters configurations with direct connection of storage devices // Automatic Control and Computer Sciences. 2011. V. 45. N 6. P. 330-337. doi: 10.3103/S0146411611060046

11. Bogatyrev V.A., Bogatyrev S.V., Golubev I.Yu. Optimization and the process of task distribution between computer system clusters // Automatic Control and Computer Sciences. 2012. V. 46. N 3. P. 103-111. doi: 10.3103/S0146411612030029

12. Письмак А.Е., Харитонова А.Е., Цопа Е.А., Клименков С.В. Оценка семантической близости предложений на естественном языке методами математической статистики // Научно-технический вестник информационных технологий, механики и оптики. 2016. Т. 16. № 2. С. 324-330. doi: 10.17586/2226-1494-2016-16-2-324-330

13. Shahzad A., Lee Y.S., Lee M. et al. Real-time cloud-based health tracking and monitoring system in designed boundary for cardiology patients // Journal of Sensors. 2018. V. 2018. 15 p. doi: 10.1155/2018/3202787

14. Суммарный трафик участников, передаваемый через MSK-IX [Электронный ресурс]. Режим доступа: https://www.msk-ix. ru/traffic/ (дата обращения: 09.04.2019).

15. Беззатеев С.В., Елина Т.Н., Мыльников В.А. Моделирование процессов подбора параметров облачных систем для обеспечения их устойчивости с учетом надежности и безопасности // Научно-технический вестник информационных технологий, механики и оптики. 2018. Т. 18. № 4. С. 654-662. doi: 10.17586/2226-1494-2018-18-4-654-662

7. Cattani C., Kudreyko A. Application of periodized harmonic wavelets towards solution of eigenvalue problems for integral equations. Mathematical Problems in Engineering, 2010, 8 p. doi: 10.1155/2010/570136

8. Chen W.W., Liu S., Wang Q.J. Fast Fourier transform based numerical methods for elasto-plastic contacts of nominally flat surfaces. Journal of Applied Mechanics, 2008, vol. 75, no. 1. doi: 10.1115/1.2755158

9. Levina A.B., Taranov S.V. Investigation of influence of encoding function complexity on distribution of error masking probability. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2016, vol. 16, no. 2, pp. 331-337 (in Russian). doi: 10.17586/2226-1494-2016-16-2-331-337

10. Bogatyrev V.A. Fault tolerance of clusters configurations with direct connection of storage devices. Automatic Control and Computer Sciences, 2011, vol. 45, no. 6, pp. 330-337. doi: 10.3103/S0146411611060046

11. Bogatyrev V.A., Bogatyrev S.V., Golubev I.Yu. Optimization and the process of task distribution between computer system clusters. Automatic Control and Computer Sciences, 2012, vol. 46, no. 3, pp. 103-111. doi: 10.3103/S0146411612030029

12. Pismak A.E., Kharitonova A.E., Tsopa E.A., Klimenkov S.V. Evaluation of semantic similarity for sentences in natural language by mathematical statistics methods. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2016, vol. 16, no. 2, pp. 324-330. doi: 10.17586/22261494-2016-16-2-324-330

13. Shahzad A., Lee Y.S., Lee M. et al. Real-time cloud-based health tracking and monitoring system in designed boundary for cardiology patients. Journal of Sensors, 2018, vol. 2018, 15 p. doi: 10.1155/2018/3202787

14. MSK-IX Traffic. Available at: https://www.msk-ix.ru/traffic/ (accessed: 09.04.2019).

15. Bezzateev S.V., Elina T.N., Myl'nikov V.A. Modeling of selection processes of cloud systems parameters providing their stability in accordance with reliability and safety. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2018, vol. 18, no. 4, pp. 654-662 (in Russian). doi: 10.17586/2226-1494-2018-18-4-654-662

Авторы

Жмылёв Сергей Александрович — ассистент, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, ORCID ГО: 0000-0001-8916-5474, [e-mail]

Authors

Sergey A. Zhmylev — Assistant, ITMO University, Saint Petersburg, 197101, Russian Federation, ORCID ID: 0000-0001-8916-5474, [e-mail]

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

УДК 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]. В частности, быстрое преобразование Фурье характеризуется низкой алгоритмической сложностью, но при этом требует большого количества операций

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

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

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

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

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

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

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

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

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

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

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

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

г = СОУ^О ...Ц^Ц/2 ...и) а[о /2 ]а[/2 —и ]

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

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

N N 2

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

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

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

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

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

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

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

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

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

Результаты. В ходе экспериментов с синусоидальным, треугольным, пилообразным, линейным и прямоугольным сигналами, амплитуда которых формировалась как идеальными функциями, так и функциями с наложенным случайным шумом, достигающим 50 % амплитуды исходного сигнала, выявлено, что при анализе выборок, состоящих от 2Т до 2 000 последовательных измерений функции у' (г) с периодом Т > 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 );

Валерий Юрьевич Киреев

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

Сергей Александрович Жмылёв

Тауфик Измайлович Алиев

Сведения об авторах Университет ИТМО; кафедра вычислительной техники; ассистент; E-mail: [e-mail]

магистрант; Университет ИТМО; кафедра вычислительной техники; E-mail: [e-mail]

студент; Университет ИТМО; кафедра вычислительной техники; E-mail: [e-mail]

д-р техн. наук, профессор; Университет ИТМО; кафедра вычислительной техники; заведующий кафедрой; E-mail: [e-mail]

Поступила в редакцию 17.02.18 г.

Ссылка для цитирования: Жмылёв С. А., Мартынчук И. Г., Киреев В. Ю., Алиев Т. И. Оценка длины периода нестационарных процессов в облачных системах // Изв. вузов. Приборостроение. 2018. Т. 61, № 8. С. 645—651.

ESTIMATION OF PERIODS OF NONSTATIONATY PROCESSES IN CLOUD SYSTEMS

S. A. Zhmylev, I. G. Martynchuk, V. Yu. Kireev, T. I. Aliev

ITMO University, 197101, St. Petersburg, Russia E-mail: [e-mail]

The problem of automated evaluation of load process period in cloud systems is considered. A common approach to load simulation for such systems implies the stationary nature of incoming requests flow, which results in inadequate matching of the models to the objects under investigation. To automatically construct an adequate analytical model, it is necessary to estimate the length of the loading process period from measured data. A numerical method of automated period estimation for any periodic functions is proposed. The method allows real-time processing of measured values, restoring missing data by interpolation of known neighboring values. Pearson correlation coefficient is chosen as a criterion to calculate functions similarity. It's proposed to store arrays of sums of mean values and standard deviation values in the main memory to improve the method's performance. Computational complexity of the method is reduced to polynomial, which means that the method could be implemented even in the embedded systems. Period estimation accuracy is demonstrated by presented results of numerous experiments with ideal, randomly noised, and real signals.

Keywords: periodical function, cloud system, numerical method, queue system, mathematical modelling

REFERENCES

1. Bogatyrev V.A., Bogatyrev A.V. Automatic Control and Computer Sciences, 2015, no. 1(49), pp. 46-56.

2. Bogatyrev V.A., Parshutina S.A., Poptcova N.A., Bogatyrev A.V. Communications in Computer and Information Science, 2016, no. 678, pp. 337-348.

3. Bekker M.Ya., Gatchin Yu.A., Karmanovskiy N.S., Terent'yev A.O., Fedorov D.Yu. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2011, no. 1(71), pp. 97-102. (in Russ.)

4. Zikratov I.A., Odegov S.V. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2012, no. 4(80), pp. 121-126. (in Russ.)

5. Bogatyrev V.A., Bogatyrev S.V. Journal of Instrument Engineering, 2017, no. 2(60), pp. 171-177. (in Russ.)

6. https://www.msk-ix.ru/traffic/. (in Russ.)

7. Sridhar P., Sheikh-Bahaei S., Xia S., Jamshidi M. Proc. IEEE Int. Conf. on Systems, Man and Cybernetics, Washington, 2003, vol. 2, pp. 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. Automatic Control and Computer Sciences, 2015, no. 6(49), pp. 321-327.

10. Churayev S.O., Adamova A.D., Paltashev T.T. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2011, no. 1(71), pp. 72-76. (in Russ.)

11. Korotkov A.V., Mukhin A.I. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2012, no. 1(77), pp. 33-36. (in Russ.)

Sergey A. Zhmylev Ilya G. Martynchuk Valery Yu. Kireev Taufik I. Aliev

For citation: Zhmylev S. A., Martynchuk I. G., Kireev V. Yu., Aliev T. I. Estimation of periods of nonsta-tionaty processes in cloud systems. Journal of Instrument Engineering. 2018. Vol. 61, N 8. P. 645—651 (in Russian).

DOI: 10.17586/0021-3454-2018-61-8-645-651

Data on authors

ITMO University, Department of Computation Technologies; Assistant; E-mail: [e-mail]

Graduate Student; ITMO University, Department of Computation Technologies; E-mail: [e-mail]

Student; ITMO University, Department of Computation Technologies; E-mail: [e-mail]

Dr. Sci., Professor; ITMO University, Department of Computation Technologies; Head of the Department; E-mail: [e-mail]

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

^¿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.

НАУЧНО-ТЕХНИЧЕСКИИ ВЕСТНИК ИНФОРМАЦИОННЫХ ТЕХНОЛОГИИ, МЕХАНИКИ И ОПТИКИ май-июнь 2018 Том 18 № 3 ISSN 2226-1494 http://ntv.ifmo.ru/

SCIENTIFIC AND TECHNICAL JOURNAL OF INFORMATION TECHNOLOGIES, MECHANICS AND OPTICS

May-June 2018

Vol. 18 No 3 ISSN 2226-1494

http://ntv.ifmo.ru/en

УДК 004.94

СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С ПОЛИМОДАЛЬНЫМИ

ПОТОКАМИ

С.А. Жмылёв", Т.И. Алиев"

a Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация Адрес для переписки: [e-mail] Информация о статье

Поступила в редакцию 19.02.18, принята к печати 26.03.18 doi: 10.17586/2226-1494-2018-18-3-473-478 Язык статьи - русский

Ссышка для цитирования: Жмылёв С.А., Алиев Т.И. Системы массового обслуживания с полимодальными потоками // Научно-технический вестник информационных технологий, механики и оптики. 2018. Т. 18. № 3. С. 473-478. doi: 10.17586/2226-1494-201818-3-473-478

Аннотация

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

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

QUEUE SYSTEMS WITH POLYMODAL QUERY FLOWS S.A. Zhmylev", T.I. Aliev"

a ITMO University, Saint Petersburg, 197101, Russian Federation Corresponding author: [e-mail] Article info

Received 19.02.18, accepted 26.03.18 doi: 10.17586/2226-1494-2018-18-3-473-478 Article in Russian

For citation: Zhmylev S.A., Aliev T.I. Queue systems with polymodal query flows. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2018, vol. 18, no. 3, pp. 473-478 (in Russian). doi: 10.17586/2226-1494-2018-18-3-473-478

Abstract

In queuing systems modeling it is traditionally assumed that the distribution of the inter-arrival time between requests entering the system is unimodal. At the same time, in practice, systems with a multimodal inter-arrival time distribution having two or more modes are encountered. The multimodal distribution is usually replaced by a unimodal one with appropriate numerical moments, which simplifies the modeling process, but introduces a methodical error in the obtained results. The subject of the study is the analysis of properties of multimodal flows and the estimation of such an error. Simulation modeling in the AnyLogic environment is used as a re-search method provided to discover the error dependence on the system load. It was revealed that in the high-load systems the error introduced by the replacement is not higher than 15%, but with a decrease in the system load, the error increases and can reach hundreds of percent. In the course of extensive experiments, it was found out that with an increase in the inter-arrival time the value of the variation coefficient between incoming queries in a polymodal flow tends to a constant value not greater than unity. The practical importance of the work

lies in simplification of design process for high-load computing systems with the use of simulation and analytical models by

replacing the polymodal flows with unimodal providing required accuracy of calculations.

Keywords

polymodal distribution, queue system, polymodal distribution approximation, statistical moment, multi-exponential distribution

Введение

При исследовании систем с очередями для построения модели потока обычно измеряются интервалы между происходящими событиями, затем вычисляются математическое ожидание и коэффициент вариации, и на основе этих характеристик выполняется аппроксимация потока заявок унимодальным распределением [1-3]. В то же время, если построить гистограмму реального распределения, то она может иметь полимодальный вид. Примерами реальных систем, для которых характерна такая гистограмма распределения, могут служить беспроводная вычислительная сеть с централизованным контролем доступа к среде передачи или вычислительная сеть с подтверждением приема сетевых пакетов [4-7]. И в том, и в другом случаях передаваемое сообщение разделяется на сетевые пакеты [8, 9]. Отправка каждого сетевого пакета требует также передачи служебного сетевого пакета меньшего размера [10-12]. В связи с этим в передающее оборудование пакеты поступают с распределением, имеющим две моды. Возникает вопрос правомочности аппроксимации реального распределения с помощью унимодальной функции. Материалов, посвященных данному вопросу, при обзоре предметной области не было найдено. Цель работы состоит в выявлении свойств систем с полимодальным распределением интервалов поступления заявок и оценке погрешности, возникающей при замене полимодального распределения унимодальным. Параметры используемого в модели распределения получены в результате анализа потоков данных в вычислительной сети с подтверждением приема сетевых пакетов.

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

Рассмотрим телекоммуникационную систему, работающую по протоколу передачи данных с подтверждением, состоящую из трех последовательно соединенных вычислительных узлов. Узлы функционируют под управлением операционной системы GNU/Linux версии Debian 8.4. Между узлами происходит обмен сообщениями размером 8,5 МБ. На основе результатов, полученных в процессе измерений характеристик потоков пакетов, построена гистограмма распределения времени (в миллисекундах) между поступлениями сетевых пакетов в промежуточный узел при установленных в ядре операционной системы настройках net.ipv4.tcp_wmem и net.ipv4.tcp_rmem в значение «1500, 1500, 1500» (рис. 1).

о «

3500 3000 2500 2000 1500 1000 500

0

ЧОб <N_ 00_ -^t (О <0 ^Н (N

Г"^ С* Г, <N_ U^ ЧОб ОО г, <N

ГЧ m" S оо" ©" -5t" оо" ©" <N" -5t" го Сл" >-ч

Время, мс

Рис. 1. Гистограмма распределения интервалов между сетевыми пакетами

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

Анализ полимодальных потоков

Полимодальную функцию можно получить путем композиции унимодальной функции f(x) и ее смещенного варианта [(х — О). В работе рассматриваются распределения, функции которых имеют две и три моды и являются мультиэкспонентами (ввиду удобства построения используются гипо- и гиперэкспоненты). Каждая мода полимодальной функции смещается относительно предыдущей на равные интервалы Б по оси абсцисс, т.е. = +0 = 10; ([ = 1,2,...); £>0 = 0. Например, распределение с интен-

сивностью Я, состоящее из композиции двух экспоненциальных функций, каждая из которых определяет значение случайной величины с вероятностью p, имеет плотность fx) и математическое ожидание M:

0, х < 0

f(X) =

М = D(1-p) +

X'

рХе~Хх, 0 <х < В ;

[рХе~:Кх + (1- р)Хе~Х(х~в) ,х > Б Характер полимодального распределения, полученного по этим формулам с разными значениями параметров р,0 и X, а именно: р± = р2> Рз, 03> 02> Х3 =Хг > Х2, имеет вид кривых 1, 2 и 3 (рис. 2).

1

3

D,

Время, с

Рис. 2. Примеры двухмодовых распределений

Для выявления свойств рассматриваемых полимодальных распределений построены имитационные модели потоков, составленные из функций, имеющих равные математические ожидания. Имитационные эксперименты выполнялись в среде AnyLogic 7.0.2 Professional в предположениях о детерминированном и экспоненциальном распределениях времени обслуживания. Модель представляет собой один или несколько приборов, обслуживающих поступающие заявки, и накопитель, в который помещается заявка, поступившая, когда все приборы заняты обслуживанием. Полимодальная функция задает распределение времени между поступлениями заявок в модель. При этом варьировались следующие параметры: величина смещения каждой моды D, создаваемая потоком нагрузка у, распределение времени обслуживания поступающих заявок f(T). В качестве исследуемых характеристик рассматривались среднее время пребывания заявок U в модели, загрузка прибора р, средняя длина очереди I и усредненная максимальная длина очереди 1тах, позволяющая оценить верхнюю границу емкости накопителя проектируемой системы. Для исключения влияния переходных процессов на измеряемые величины через системы пропускалось 500 тыс. заявок, что обеспечило отклонение характеристик систем не более 0,1%.

Аппроксимация полимодальных распределений

Аппроксимация вероятностных распределений по двум числовым моментам - математическому ожиданию М и второму начальному моменту - требует выбора аппроксимирующей функции на основе коэффициента вариации v. Для распределений с v >1 можно использовать гиперэкспоненциальное распределение, составленное из двух экспоненциальных распределений с математическими ожиданиями М^и М2 соответственно, одно из которых формирует значение случайной величины с вероятностью q, а второе - с вероятностью (1 — q). В этом случае формулы для нахождения параметров гиперэкспоненциального распределения [13, 14] имеют следующий вид:

2

Ч ^

v2 + 1'

1-4 „

Mi = M 1 + \ 2q (v2-1)\ ; М2=М 1 - Л

2(1-4)

(v2 - 1)

Для аппроксимации полимодальных распределений с коэффициентом вариации 0< V <1 использовались гипоэкспоненциальные распределения, представляемые суммой к1 экспоненциальных распределений с математическими ожиданиями Мх и к2 экспоненциальных распределений с математическими ожиданиями М2. При этом к = + к2. Формулы для нахождения параметров в этом случае имеют следующий вид [13, 14]:

V2

М

м± = Т

1+

к2

м

1 -

2 к

N

кг

Mw-i)

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

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

2

числовым моментам. Характер исходной функции плотности распределения, представляемой гистограммой, существенно отличается от характера аппроксимирующей функции, представляемой кривой (рис. 3).

Рис. 3. Аппроксимация полимодального распределения

Загрузка 0,3 0,7 0,95

/, шт 0,964±0,007 124% 2,655±0,08 14% 22,20±4,90 9%

0,429±0,005 2,33±0,044 20,22±3,85

/шах, шт 17,8±1,77 69% 36,8±3,45 10% 179,1±29,76 25%

10,5±0,88 33,5±1,49 142,8±20,65

и, с 14,684±0,26 37% 63,81±2,07 9% 553,75±122,2 9%

10,71±0,14 58,1585±1,12 504,5±96,15

Таблица. Сравнение характеристик систем с полимодальными и унимодальными потоками

В таблице показаны результаты сравнения систем с полимодальными и аппроксимирующими его унимодальными мультиэкспоненциальными потоками. Уровень доверия результатов составляет 95%. Интервалы между поступлением заявок в потоке имеют математическое ожидание 24,933±0,02, коэффициент вариации 1,00015±0,0004. Полимодальный поток составлен из двух гиперэкспоненциальных компонент с коэффициентом вариации, равным 5, расположенных на расстоянии 45,9.

Полученные значения характеристик для полимодального и унимодального потоков представлены в числителе и знаменателе соответственно. Для наглядности приведены отличия характеристик, выраженные в процентах. Видно, что при малых загрузках, характерных для многих реальных систем, расхождение измеренных величин достигает двух и более раз. Абсолютные значения характеристик меньше в системах с унимодальными потоками. Следовательно, могут возникать ошибки при проектировании реальных систем [15]. Для высоконагруженных систем значение расхождения имеет существенный разброс, однако в целом с увеличением загрузки системы погрешность замены полимодального распределения унимодальным уменьшается. Видно, что с увеличением загрузки существенно увеличивается доверительный интервал для измеренных значений (рис. 4). Это объясняется тем, что чем ближе система к перегруженному состоянию, тем значительнее отклоняются измеряемые значения от средних. Также погрешность такой замены увеличивается с увеличением числа обслуживающих приборов. Например, в системе с двумя приборами при загрузке 0,9 погрешность средней длины очереди достигает 70%. На данную величину оказывает существенное влияние и межмодовый интервал. Характеристики систем со сравнительно малым межмодовым интервалом стремятся к характеристикам систем с унимодальным распределением. Это объясняется тем, что у системы с полимодальным распределением заявки склонны к группировке, и при большом межмодовом интервале для получения конкретного математического ожидания потребуется формировать группы из большего числа заявок. Чем больше приборов в системе массового обслуживания, тем более явно наблюдается эффект группировки заявок, следовательно, тем больше расхождение средних значений исследуемых характеристик.

Среднее время пребывания заявки в системе монотонно возрастает с увеличением загрузки системы р и межмодового интервала Д. Коэффициент вариации двухмодового гиперэкспоненциального распределения зависит от Д: уменьшается, начиная со значения у0 >1, равного коэффициенту вариации первой составляющей (в случае, когда составляющие распределения имеют одинаковый коэффициент вариации), принимая некоторое минимальное значение при незначительном влиянии мод друг на друга, и при дальнейшем увеличении О принимает постоянное значение V <1. Для двухмодового гипоэкспонен-циального распределения коэффициент вариации также стремится к постоянному значению V <1 (рис. 5). Выявленное свойство позволяет сделать вывод, что при большом межмодовом интервале для моделирования можно использовать простейший поток, поскольку его коэффициент вариации больше. Однако, как показали многочисленные эксперименты, если поток имеет полимодальное распределение,

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

100

90

0х 80

л" 70

О о 60

и В 50

(D 40

& О 30

С 20

10

0

\

\

0,1