Анализ моделей массового обслуживания для оценки времени отклика в системе облачных вычислений тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Горбунова, Анастасия Владимировна

• Горбунова, Анастасия Владимировна
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Горбунова, Анастасия Владимировна

Оглавление

Стр.

Введение

Глава 1. Построение моделей массового обслуживания для

систем облачных вычислений

1.1 Показатели эффективности системы облачных вычислений

1.2 Обзор систем параллельного обслуживания заявок

1.3 Постановка задачи исследования

Глава 2. Анализ системы характеристик системы массового

обслуживания с параллельной обработкой запросов

2.1 Особенности модели системы облачных вычислений с расщеплением запросов

2.2 Время отклика в системе облачных вычислений

2.3 Время синхронизации в системе облачных вычислений

2.4 Результаты расчётов вероятностно-временных характеристик

Глава 3. Анализ времени отклика системы облачных вычислений с гистерезисным управлением

подключением виртуальных машин

3.1 Рекуррентный алгоритм вычисления преобразования Лапласа-Стилтьеса времени отклика системы

3.2 Рекуррентный алгоритм вычисления преобразования Лапласа-Стилтьеса времени отклика системы с ограничением на одновременное число активаций

3.3 Вероятностно-временные характеристики времени отклика. Численные результаты применения рекуррентного алгоритма

Заключение

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

Список рисунков

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

Введение

Актуальность темы исследования. Облачные вычисления (cloud computing) представляют собой технологию, позволяющую удалённому пользователю в режиме реального времени по требованию получать доступ к вычислительным ресурсам: программным приложениям, серверам, устройствам хранения данных, сервисам и др., через Интернет в рамках согласованного качества обслуживания для выбранной ценовой категории. В задачи поставщика таких услуг входит не только обеспечение требуемого уровня оказываемых услуг [1], но и, как следствие, избежание перегрузки ресурсов при обработке пользовательских требований и снижение энергозатрат.

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

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

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

Несмотря на то, что современные облачные системы проектируются, как правило, масштабируемыми, всё равно остается проблема недостаточного использования ресурсов системы, что тоже является одной из причин потерь энергии. Одним из способов повышения энергетической эффективности и энергетического сбережения в системах облачных вычислений является динамическая активация виртуальных машин [5-7]. Иными словами, регулируется количество выделяемых ресурсов для обработки запросов пользователей в зависимости от текущей нагрузки [8-12]. Одной из проблем анализа подобных систем является вычислительная сложность предложенных решений для анализа вероятностно-временных характеристик, таких как время отклика, вызванная, в частности, увеличением ёмкости системы и количества обслуживающих приборов, что вполне естественно для современных систем облачных вычислений при росте числа пользователей и серверов для их обслуживания. Поэтому применение матрично-геометрических методов для получения стационарных характеристик системы, моделирующей облачный центр, становится затруднительным [13-15]. В работах [6; 7; 16] был предложен вычислительный алгоритм расчёта стационарных вероятностей числа запросов для модели облачной системы, имеющий линейную сложность, с помощью которого становится возможным определить величину среднего времени отклика. Но, как уже говорилось выше, для анализа современных облачных платформ требуются эффективные вычислительные алгоритмы, позволяющие при этом получить оценку не только для среднего значения времени отклика, но и для его моментов более высоких порядков.

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

высокой готовности и производительности системы, в [4] была предложена система массового обслуживания с параллельной обработкой данных (fork-join queueing system). К одному из первых упоминаний этой системы можно отнести работу [17]. В этой статье анализировалась система с двумя параллельно функционирующими блоками D/M/1, моделирующими ситуацию одновременного прибытия в аэропорт пассажиров и их вещей, последующего разделения этих двух условных блоков и их соединения через некоторое время в зоне выдачи багажа. В более поздних работах рассматривались уже параллельные блоки М/М/1 [18-24]. Точное выражение для среднего времени отклика было получено в работе [18] только для случая двух параллельно функционирующих систем М/М/1, в других же публикациях были получены различными методами аппроксимации среднего времени отклика [21-32]. Сложность в исследовании этой системы объясняется существующей зависимостью между очередями подзапросов из-за общих моментов поступления. В источниках [25-30] рассматривались отличные от экспоненциального распределения времён пребывания подзапросов в подсистемах, а для анализа времени отклика были предложены методы теории порядковых статистик [33-35], благодаря которым были получены приближения для величины среднего времени отклика. Несмотря на широкий спектр задач, которые решаются с помощью систем массового обслуживания с параллельной обработкой запросов, и их популярность среди зарубежных авторов, в нашей стране данная система исследовалась значительно меньше [36-42]. Среди отечественных учёных, внёсших вклад в анализ подобных систем можно назвать С.П. Моисееву. В работах [37-42] была исследована система параллельного обслуживания сдвоенных заявок с неограниченным числом приборов, в результате были получены точные выражения для двумерного распределения вероятностей числа подзапросов в системе (приборов в каждой подсистеме), характеристик числа занятых приборов в соответствующих подсистемах и коэффициента корреляции между ними.

Одним из методов исследования систем с динамическим управлением подключением виртуальных машин является анализ с помощью моделей массового обслуживания с динамической активацией дополнительных приборов [43; 44]. Стоит отметить, что, как правило, выделяют два типа гистерезисного управления: гистерезисное управление входящим потоком (текущей нагрузкой) [45; 46] и гистерезисное управление обслуживанием [47-49], и для анализа этих моде-

лей используются методы теории вероятностей, теории массового обслуживания и теории телетрафика [50-54]. Среди авторов, внёсших серьёзный вклад в исследования можно назвать: М.А. Красносельского и А.В. Покровского [55], К.Е. Самуйлова [56-61], А.В. Печинкина [62-65], Ю.В. Гайдамака [56-61; 66], С.Я. Шоргина [60; 67], С.П. Моисееву [37-42], В.А. Нетеса [1-3], R.D. Nelson и A.N. Tantawi [18], F. Baccelli [68; 69], S. Balsamo и I. Mura [22-24], L. Flatto and S. Hahn [19], C. Kim и A.K. Agrawala [70], A. Thomasian [25; 30-32], J. Menon [25], I. Tsimashenka и W.J. Knottenbelt [4], E. Varki [20; 71], S. Varma и A.M. Makowski [21] и др. Работы [56; 57; 72] были посвящены математическому и имитационному моделированию систем с гистерезисным управлением интенсивностью входящего потока и непосредственному анализу этого механизма управления в сетях SIP-серверов (Session Initiation Protocol); в статьях [58;62-66; 73] в качестве анализируемых моделей рассматривались системы массового обслуживания с пуассоновским входящим потоком и экспоненциальным распределением для времён обслуживания запросов для аналогичных сетей. В работах [7; 16; 43; 74] модель с гистерезисным управлением обслуживанием использовалась уже для анализа систем облачных вычислений.

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

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

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

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

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

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

Краткое содержание диссертации. В главе 1 исследуются особенности построения моделей массового обслуживания для анализа системы облачных вычислений, формулируется задача исследования. В разделе 1.1 определяются показатели эффективности функционирования облачного центра, такие как время отклика и время синхронизации, а также рассматриваются особенности построения моделей облачного центра с гистерезисным управлением подключением дополнительных приборов. В разделе 1.2. приведен обзор существующих методов анализа системы облачных вычислений, моделируемой системой параллельного обслуживания заявок, для решения ресурсоемких задач. В разделе 1.3 формулируется задача исследования. Разделы 1.1 - 1.3 созданы на основе публикаций [75; 76] с участием автора.

В главе 2 приведен анализ характеристик производительности системы облачных вычислений, представленной в виде системы массового обслуживания с параллельной обработкой запросов, в контексте решения супер-задач. В разделе 2.1 рассмотрены особенности построения модели системы облачных вычислений с расщеплением запросов, представлена система уравнений равновесия, а также получено в явном виде маргинальное распределение числа подзапросов в системе облачных вычислений с расщеплением. В разделе 2.2 проанализировано время отклика системы облачных вычислений, представлены формулы для оценок математического ожидания и дисперсии этой случайной величины, полученные с помощью методов теории порядковых статистик. Раздел 2.3 посвящен анализу времени, проведённому подзапросами в буфере синхронизации, выведена аппроксимирующая формула для дисперсии времени синхронизации. В разделе 2.4 проведен численный анализ рассматриваемых характеристик, а также сравниваются аппроксимирующие формулы для среднего времени отклика, представленные в различных источниках. Разделы 2.1-2.4 диссертационной работы изложены на основе публикаций [77-80] при участии автора.

В главе 3 предложен в терминах преобразования Лапласа-Стилтьеса рекуррентный алгоритм расчета функции распределения времени ожидания начала обслуживания и времени отклика системы облачных вычислений с гисте-резисным управлением, что позволяет определить моменты высших порядков этих случайных величин. Ранее же можно было оценить только математическое ожидание исследуемых характеристик с помощью решения системы уравнений равновесия. В разделе 3.1 описан рекуррентный алгоритм для вычисления указанных выше величин в терминах преобразования Лапласа-Стилтьеса. В разделе 3.2 представлен рекуррентный алгоритм для вычисления времени ожидания начала обслуживания и времени отклика в терминах преобразования Лапласа-Стилтьеса для системы облачных вычислений с гистерезисным управлением и ограничением на одновременное число активаций. Раздел 3.3 посвящен численному анализу полученных результатов. Разделы 3.1-3.4 диссертации изложены на основе публикаций [81; 82] при участии автора.

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

Наиболее важные результаты исследования оформлены в виде утверждений. Для проведения численного анализа с помощью сред Scilab и GPSS (General Purpose Simulation System) были разработаны программные средства.

Научная новизна.

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

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

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

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

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

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

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

Результаты работы использованы в рамках исследований по грантам РФФИ № 15-07-03051 «Формализация моделей и развитие методов анализа вероят-

ностных характеристик инфокоммуникационных межмашинных беспроводных сетей пятого поколения» и № 15-07-03608 «Разработка методов решения задач управления доступом в широкополосных беспроводных инфокоммуникацион-ных сетях на основе нелинейного анализа и математической теории телетрафика», а также в учебном процессе при подготовке выпускных работ бакалавров и магистров, обучающихся по направлению «Фундаментальная информатика и информационные технологии».

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

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

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

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

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

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

Результаты диссертационного исследования докладывались на следующих научных конференциях: Вторая молодежная научная конференция «Задачи современной информатики» (Москва, 2015 г.); IX Международная отраслевая научно-техническая конференция «Технологии информационного общества» (Москва, 2015 г.); X Юбилейная Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование» (Москва, 2015 г.); XV Международная конференция имени А.Ф. Терпугова «Информационные технологии и математическое моделирование» (ИТММ-2016) (Томск, 2016 г.); Девятнадцатая международная научная конференция «Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь» (ЭССК-2016) (Москва, 2016 г.); I Международная научная конференция «Конвергентные когнитивно-информационные технологии» (Москва, 2016 г.).

Соответствие паспорту специальности. Диссертационное исследование выполнено в соответствии с паспортом специальности 05.13.17 «Теоретические основы информатики» и включает оригинальные результаты в области исследования информационных процессов и требований их пользователей к показателям эффективности, в области разработки моделей информационных процессов, разработки общих принципов организации телекоммуникационных систем и оценки их эффективности. Таким образом, диссертационное исследование соответствует следующим разделам паспорта специальности 05.13.17 «Теоретические основы информатики»: п. 2 (Исследование информационных структур, разработка и анализ моделей информационных процессов и структур), п. 16 (Общие принципы организации телекоммуникационных систем и оценки их эффективности).

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

Публикации. Основные результаты по теме диссертационного исследования изложены в 8 печатных изданиях [75-82], из которых 2 — изданы в журналах, рекомендованных ВАК РФ [75; 78].

Глава 1. Построение моделей массового обслуживания для систем

облачных вычислений

1.1 Показатели эффективности системы облачных вычислений

Облачные вычисления в настоящее время представляют собой высокопроизводительную вычислительную среду, доступ к которой удаленному пользователю предоставляется посредством интернет-сервисов. Интерес к системам облачных вычислений объясняется множеством преимуществ их использования (доступность, гибкость, масштабируемость, легкость в управлении, сравнительно низкую стоимость внедрения), а также потребностью коммерческих и научных организаций в мощной вычислительной инфраструктуре для выполнения сложных ресурсоемких расчетов при сравнительно небольших затратах [83].

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

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

представлять собой минимум из времён пребывания всех экземпляров задачи в системе [84].

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

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

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

Вообще говоря, методы повышения энергетической эффективности и энергосбережения можно условно разделить на три категории: «воздействие» на поведение пользователей, изменение рабочей нагрузки, перенастройка ресурсов [8-12; 85]. Если говорить о первом подходе, то положительный опыт внедрения мер стимулирования потребителей к энергосбережению имеется, в част-

ности, у энергетических компаний. Применение системы тарификации, предполагающей значительное снижение стоимости электроэнергии в периоды низкой активности, например, ночью, побуждает потребителей к использованию электричества хотя бы отчасти в ночное время, что в свою очередь, приводит к выравниванию рабочей нагрузки. Идея же второго — заключается в использовании дополнительного устройства между сервисом и пользователем, которое изменяет интенсивность входящего трафика посредством буферизации: увеличивает продолжительность «спящего» режима и удлиняет периоды высокой загрузки [85]. Однако у этих двух методов имеется существенный недостаток, который заключается в снижении качества оказываемых услуг, что является нарушением SLA.

Список литературы диссертационного исследования кандидат наук Горбунова, Анастасия Владимировна, 2017 год

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

1. Козин А.А., Нетес В.А. Кто разрабатывает международные стандарты для облачных вычислений // Вестник связи. — 2014. — № 11. — С. 35-39.

2. Сулейманов А.А., Нетес В.А. Анализ времени подключения к облачной услуге «виртуальный рабочий стол» // T-Comm — Телекоммуникации и транспорт. — 2016. — № 7. — С. 41-45.

3. Нетес В.А. Виртуализация, облачные услуги и надежность // Вестник связи. — 2016. — № 8. — С. 7-9.

4. Tsimashenka I., Knottenbelt W.J. Reduction of Subtask Dispersion in Fork-Join Systems // Computer Performance Engineering. — Springer Berlin Heidelberg, 2013. — Pp. 325-336.

5. Goswami V., Patra S.S., Mund G.B. Performance Analysis of Cloud with Queue-Dependent Virtual Machines // Proc. of 1st Int'l Conf. on Recent Advances in Information Technology / IEEE. — 2012. — Pp. 357-362.

6. Threshold-based Queuing System for Performance Analysis of Cloud Computing System with Dynamic Scaling / S.Y. Shorgin, A.V. Pechinkin, K.E. Samouylov et al. // Proceedings of the 12th International Conference of Numerical Analysis and Applied Mathematics ICNAAM-2014. — Vol. 1648. — 2015. — Pp. 1-3.

7. Анализ показателей эффективности функционирования системы облачных вычислений с динамическим масштабированием / А.В. Печинкин, Ю.В. Гайдамака, Э.С. Сопин, М.О Таланова // Сборник избранных трудов IX Международной ежегодной научно-практической конференции «Современные информационные технологии и ИТ-образование». — 2014. — С. 395-406.

8. Kaxiras S., Martonosi M. Computer Architecture Techniques for Power-Efficiency // Synthesis Lectures on Computer Architecture. — 2008. — Vol. 3, no. 1. — Pp. 1-207.

9. Dynamic right-sizing for power-proportional data centers / M. Lin, A. Wier-man, L.L.H. Andrew, E. Thereska // IEEE/ACM Transactions on Networking (TON). — 2013. — Vol. 21, no. 5. — Pp. 1378-1391.

10. Meisner D., Gold B.T., Wenisch T.F. Powernap: eliminating server idle power // ACM Sigplan Notices. — 2009. — Vol. 44, no. 3. — P. 205-216.

11. Critical power slope: Understanding the runtime effects of frequency scaling / A. Miyoshi, C. Lefurgy, E.V. Hensbergen et al. // Proceedings of the 16th Annual ACM International Conference on Supercomputing. — 2002. — Pp. 3544.

12. Formal control techniques for power performance management / Q. Wu, P. Juang, M. Martonosi et al. // IEEE Micro. — 2005. — Vol. 25, no. 5. — Pp. 52-62.

13. Basharin G.P., Gaidamaka Yu.V., Samouylov K.E. Mathematical theory of teletraffic and its application to the analysis of multiservice communication of next generation networks // Automatic control and computer sciences. — 2013. — Vol. 47, no. 2. — Pp. 62-69.

14. Мокрое Е.В., Самуйлов К.Е. Модель системы облачных вычислений в виде системы массового обслуживания с несколькими очередями и с групповым поступлением заявок // T-Comm - Телекоммуникации и Транспорт. — 2013. — Т. 11, № 7. — С. 139-141.

15. Мокрое Е.В., Чукарин А.В. Анализ показателей эффективности системы облачных вычислений с миграцией серверов // T-Comm - Телекоммуникации и Транспорт. — 2014. — Т. 8, № 8. — С. 64-67.

16. Гайдамака Ю.В., Сопин Э.С., Таланова М.О. Анализ показателей качества функционирования систем облачных вычислений с гистерезисным управлением // T-Comm - Телекоммуникации и Транспорт. — 2015. — Т. 9, № 9. — С. 54-60.

17. Mandelbaum M, Itzhak A.-B. Introduction to queueing with splitting and matching // Israel Journal of Technology. — 1968. — Vol. 6, no. 5. — Pp. 376382.

18. Nelson R., Tantawi A.N. Approximate analysis of fork/join synchronization in parallel queues // IEEE Transactions on Computers. — 1988. — Vol. 37. — Pp. 739-743.

19. Flatto L., Hahn S. Two parallel queues created by arrivals with two demands I // SIAM Journal on Applied Mathematics. — 1984. — Vol. 44, no. 5. — Pp. 1041-1053.

20. Varki E, Merchant A., Chen H. The M/M/1 fork-join queue with variable subtasks [Электронный ресурс] // URL: http://www.cs.unh.edu/^varki/publication/2002-nov-open.pdf (дата обращения 01.09.2016).

21. Varma S., Makowski A.M. Interpolation approximations for symmetric fork-join queues // Performance Evaluation. — 1994. — Vol. 20. — Pp. 245-265.

22. Balsamo S., Mura I. Approximate Response Time Distribution in Fork and Join Systems // SIGMETRICS Performance Evaluation Review. — 1995. — Vol. 23, no. 1. — Pp. 305-306.

23. Balsamo S., Mura I. On queue length moments in fork and join queuing networks with general service times // Computer Performance Evaluation Modelling Techniques and Tools. LNCS. — 1997. — Vol. 1245. — Pp. 218-231.

24. Balsamo S., Donatiello L., Van Dijk N.M. Bound performance models of heterogeneous parallel processing systems // IEEE Transactions on Parallel and Distributed Systems. — 1998. — Vol. 9, no. 10. — P. 1041-1056.

25. Thomasian A., Menon J. RAID5 performance with distributed sparing // IEEE Transactions on Parallel and Distributed Systems. — 1997. — Vol. 8, no. 6. — Pp. 640-657.

26. Johnson N.L., Kotz S., Balakrishnan N. Continuous Univariate Distributions. — Wiley Series in Probability and Statistics, 1995. — Vol. 1. — P. 752.

27. Arnold B.C. Distribution-free bounds on the mean of the maximum of a dependent sample // SIAM Journal on Applied Mathematics. — 1985. — Vol. 38, no. 1. — Pp. 163-167.

28. Harrison P., S. Zertal. Queueing Models with Maxima of Service Times // Computer Performance Evaluation. Modelling Techniques and Tools. — Springer Berlin Heidelberg, 2003. — Pp. 152-168.

29. Lebrecht A.S., Knottenbelt W.J. Response time approximations in fork-join queues //In Proceedings of the 23rd Annual UK Performance Engineering Workshop (UKPEW'07). — 2007.

30. Thomasian A., Tantawi A.N. Approximate solutions for M/G/l fork/join synchronization // Proceedings of the 26th conference on Winter simulation (WSC'94) / Society for Computer Simulation International. — 1994. — Pp. 361-368.

31. Thomasian A. Analysis of fork/join and related queueing systems // ACM Computing Surveys (CSUR). — 2014. — Vol. 47, no. 2. — Pp. 17:1-17:71.

32. Thomasian A., Avizienis A. Dynamic scheduling of tasks requiring multiple processors // Proceedings of the 11th IEEE Computer Society International Conference (COMPCON'75 Fall). — 1975. — Pp. 77-80.

33. David H.A. Order Statistics. — Wiley, New York, 1981.

34. David H.A., Nagaraja H.N. Order Statistics. — John Wiley & Sons, 2003. — P. 458.

35. Gumbel E.J. Statistics of Extremes. — New York: Columbia University Press, 1958. — P. 375.

36. Вышенский С.В., Григорьев П.В., Дубенская Ю.Ю. Идеальный синхронизатор маркированных пар в сети разветвление-объединение // Обозрение прикладной и промышленной математики. — 2008. — Т. 15, № 3. — С. 385-399.

37. Моисеева С.П., Ивановская И. А. Исследование математической модели параллельного обслуживания заявок смешанного типа // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. — 2010. — Т. 317, № 5. — С. 32-34.

38. Моисеева С.П., Синякова И.А. Метод моментов для исследования математической модели параллельного обслуживания сдвоенных заявок потока марковского восстановления // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. — 2012. — Т. 321, № 5. — С. 24-29.

39. Moiseeva S., Sinyakova I. Investigation of output flows in the system with parallel service of multiple requests // Problems of Cybernetics and Informatics (PCI'2012) : IV International Conference. Baku, Azerbaijan. — 2012. — 12-14 September. — Pp. 180-181.

40. Моисеева С.П., Ивановская И.А. Математическая модель параллельного обслуживания заявок в распределенных вычислительных системах // Теория вероятностей, математическая статистика и их приложения: сборник научных статей. — Т. 3. — 2010. — С. 122-126.

41. Моисеева С.П., Синякова И.А. Математическая модель страховой компании в виде системы массового обслуживания М|М|то // Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей: международная научная конференция. — Т. 3. — 2013. — С. 154-159.

42. Моисеева С.П., Синякова И.А. Исследование модели параллельного обслуживания сдвоенных заявок в нестационарном режиме // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. — 2010. — Т. 12, № 3. — С. 21-28.

43. Распределение времени выхода из множества состояний перегрузки в системе М\М|1| < L,H > \ < H,R > с гистерезисным управлением нагрузкой / Ю.В. Гайдамака, А.В. Печинкин, Р.В. Разумчик и др. // Информатика и её применения. — 2013. — Т. 7, № 4. — С. 20-33.

44. Golubchik L., Lui J. Bounding of Performance Measures for Threshold-Based Queuing Systems: Theory and Application to Dynamic Resource Management in Video-on-Demand Servers // IEEE Transactions on Computers. — 2002. — Vol. 51, no. 4. — Pp. 353-372.

45. Takagi H. Analysis of a finite-capacity M/G/l queue with a resume level // Performance Evaluation. — 1985. — Vol. 5, no. 3. — P. 197-203.

46. Benaboud H, Mikou N. Analysis by queuing model of multi-thresholdmechanism in ATM switches // Proc. 5th IEEE Conference (International) on High Speed Networks and Multimedia Communications (HSNMC 2002). — 2002. — P. 147-151.

47. Golubchik L., Lui J. Bounding of performance measures for a threshold-based queueing system with hysteresis // ACM SIGMETRICS Performance Evaluation Review. — 1997. — Vol. 25, no. 1. — P. 147-157.

48. Жерновый К.Ю., Жерновый Ю.В. Система M0/G/1 c гистерезисным переключением интенсивности обслуживания // Информационные процессы. — 2012. — Т. 12, № 3. — С. 176-190.

49. Sindal R., Tokekar S. Modeling and analysis of voice/data call admission control scheme in CDMA cellular network for variation in soft handoff threshold parameters // Proc. 16th IEEE Conference (International) on Networks (ICON 2008). — 2008. — Pp. 1-6.

50. Башарин Г.П. Введение в теорию вероятностей: Учеб. пособие для студентов II-III курсов специальностей «Математика», «Прикладная математика». — Москва: РУДН, 1990. — С. 228.

51. Башарин Г.П. Лекции по математической теории телетрафика. — Москва: РУДН, 2009. — С. 342.

52. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. — Москва: Изд-во РУДН, 1995. — С. 529.

53. Queueing theory / P.P. Bocharov, C. D'Apice, A.V. Pechinkin, S. Salerno. — Brill Academic Publishers, 2004. — P. 457.

54. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. — Москва: Высшая школа, 2000. — С. 480.

55. Красносельский М.А., Покровский А.В. Системы с гистерезисом. — Наука, 1983. — С. 272.

56. Абаев П.О., Гайдамака Ю.В., Самуйлов К.Е. Гистерезисное управление сигнальной нагрузкой в сети SIP-серверов // Вестник РУДН. Серия Математика. Информатика. Физика. — 2011. — № 4. — С. 55-73.

57. Abaev P., Gaidamaka Yu, K. Samouylov. Queuing model for loss-based overload control in a SIP server using a hysteretic technique // Internet of things, smart spaces, and next generation networking. — Springer Berlin Heidelberg, 2012. — Vol. 7469 of Lecture notes in computer science. — P. 371-378.

58. Abaev P., Gaidamaka Yu., K. Samouylov. Modeling of hysteretic signalling load control in next generation networks // Internet of things, smart spaces, and next generation networking. — Springer Berlin Heidelberg, 2012. — Vol. 7469 of Lecture notes in computer science. — P. 440-452.

59. Гайдамака Ю.В., Самуйлов К.Е., Сопин Э.С. Модель одной системы массового обслуживания типа M/G/1 с гистерезисным управлением входящим потоком // T-Comm — Телекоммуникации и транспорт. — 2012. — № 7.

— С. 60-62.

60. Shorgin S., Samouylov K., Gaidamaka Yu. Polling system with threshold control formodeling of SIP server under overload // Advances in Systems Science.

— 2014. — P. 97-107.

61. Hysteretic control technique for overload problem solution in network of SIP servers / P. Abaev, Yu. Gaidamaka, K. Samouylov et al. // Computing and Informatics. — 2014. — Vol. 33, no. 1. — Pp. 218-236.

62. Abaev P., Pechinkin A., Razumchik R. On analytical model for optimal SIP server hop-by-hop overload control // Proc. 4th Congress (International) on Ultra Modern Telecommunications and Control Systems (ICUMT-2012) / IEEE.

— 2012. — P. 299-304.

63. Abaev P., Pechinkin A., Razumchik R. Analysis of queueing system with constant service time for SIP server hop-by-hop overload control // Modern Probabilistic Methods for Analysis of Telecommunication Networks. — Springer Berlin Heidelberg, 2013. — Pp. 1-10.

64. Abaev P., Pechinkin A., Razumchik R. On mean return time in queueing system with constant service time and bi-level hysteric policy // Modern Probabilistic Methods for Analysis of Telecommunication Networks. — Springer Berlin Heidelberg, 2013. — Pp. 11-19.

65. Pechinkin A.V., Razumchik R.V. Approach for analysis of finite M2/M2/l/R with hysteric policy for SIP server hop-by-hop overload control // ECMS. — 2013. — P. 573-579.

66. Гайдамака Ю.В. Модель с пороговым управлением нагрузкой для анализа серверов протокола SIP в режиме перегрузок // Автоматика и вычислительная техника. — 2013. — № 4. — С. 65-75.

67. Design and software architecture of SIP server for overload control simulation / P. Abaev, Yu. Gaidamaka, K. Samouylov, S. Shorgin // ECMS. — 2013. — Pp. 580-586.

68. Baccelli F. Two parallel queues created by arrivals with two demands: The M/G/2 symmetrical case // INRIA Rapport de Recherche. — 1985. — Vol. 426.

69. Baccelli F., Makowski A. Queueing models for systems with synchronization delays // Proceedings of the IEEE. — 1989. — Vol. 77, no. 1. — P. 138-161.

70. Kim C., Agrawala A.K. Analysis of the fork-join queue // IEEE Transactions on Computers. — 1989. — Vol. 38, no. 2. — Pp. 250-255.

71. Varki E. Response time analysis of parallel computer and storage systems // IEEE Transactions on Parallel and Distributed Systems. — 2001. — Vol. 12, no. 11. — Pp. 1146-1161.

72. Simulation of overload control in SIP server networks / P.O. Abaev, Yu.V. Gaidamaka, A.V. Pechinkin et al. // ECMS. — 2012. — P. 533-539.

73. Абаев П.О., Разумчик Р.В. Моделирование работы SIP-сервера с помощью системы массового обслуживания с гистерезисом и прогулками в дискретном времени // T-Comm — Телекоммуникации и транспорт. — 2012. — № 7. — С. 5-8.

74. Gaidamaka Yu, Sopin E, Talanova M . A simplified model for performance analysis of cloud computing systems with dynamic scaling // Proc. of the 18th International Scientific Conference «Distributed Computer and Communication Networks: Control, Computation, Communications» DCCN-2015. — Москва: ИПУ РАН, 2015. — P. 75-86.

75. Самуйлов К. Е ., Зарядов И.С., Горбунова А. В. Анализ времени отклика системы облачных вычислений // T-Comm: Телекоммуникации и транспорт. — 2015. — Т. 9, № 11. — С. 57-61.

76. Самуйлов К.Е., Зарядов И.С., Горбунова А.В. Анализ времени отклика системы облачных вычислений //IX Международная отраслевая научно-техническая конференция «Технологии информационного общества». Тезисы научно-технических секций. — 2015. — С. 29-30.

77. Горбунова А.В. Оценка времени отклика обработки запросов в системе облачных вычислений // Труды Второй молодежной научной конференции «Задачи современной информатики». — 2015. — С. 79-85.

78. Аппроксимация времени отклика системы облачных вычислений / А.В. Горбунова, И.С. Зарядов, С.И. Матюшенко и др. // Информатика и её применения. — 2015. — Т. 9, Вып. 3. — С. 32-38.

79. Оценка вероятностных характеристик системы облачных вычислений с расщеплением запросов / А.В. Горбунова, И.С. Зарядов, С.И. Матюшенко, Э.С. Сопин // Информационные технологии и математическое моделирование (ИТММ-2016): Материалы XV Международной конференции имени А.Ф. Терпугова. — 2016. — Ч. 1. — С. 167-172.

80. The Estimation of Probability Characteristics of Cloud Computing Systems with Splitting of Requests / A.V. Gorbunova, I.S. Zaryadov, S.I. Matushenko, E.S. Sopin // Proceedings of the Nineteenth International Scientific Conference Russia: Distributed computer and communication networks: control, computation, communications (DCCN-2016). — Vol. 3: Youth School-Seminar. — 2016. — P. 467-472.

81. Алгоритм вычисления преобразования Лапласа-Стилтьеса для времени отклика системы облачных вычислений с гистерезисным управлением /

К.Е. Самуйлов, Ю.В. Гайдамака, Э.С. Сопин, А.В. Горбунова // Современные информационные технологии и ИТ-образование. — 2015. — Т. 2, № 11. — С. 172-177.

82. Горбунова А.В., Самуйлов К.Е., Сопин Э.С. Преобразование Лапласа-Стилтьеса для времени отклика системы облачных вычислений с гисте-резисным управлением и ограничением на одновременное число активаций // Современные информационные технологии и ИТ-образование. — 2016. — Т. 12, № 1. — С. 21-27.

83. Khazae H., Misic J., Misic V.B. A fine-grained performance model of cloud computing centers // IEEE Transactions on Parallel and Distributed Systems.

— 2012. — Vol. 24, no. 11. — Pp. 2138-2147.

84. Joshi G., Soljanin E., Wornell G. Efficient redundancy techniques for latency reduction in cloud systems // arXiv preprint arXiv:1508.03599. — 2015.

85. Reducing network energy consumption via sleeping and rate-adaptation / S. Nedevschi, L. Popa, G. Iannaccone et al. // NSDI. — Vol. 8. — 2008.

— P. 323-336.

86. Duda A., Czachorski T. Performance evaluation of fork and join synchronization primitives // Acta Informatica. — 1987. — Vol. 24, no. 5. — P. 525-533.

87. Green L. A queueing system in which customers require a random number of servers // Operations Research. — 1980. — Vol. 28, no. 6. — Pp. 1335-1346.

88. Omahen K.J., Schrage L. A queueing analysis of a multiprocessor system with shared memory // Proc. of the Symposium on Computer Communication Networks and Teletraffic. — 1972. — Pp. 77-88.

89. Javidi T. Cooperative and Non-cooperative Resource Sharing in Networks: A Delay Perspective // IEEE Transactions on Automatic Control. — 2008. — Vol. 53, no. 9. — Pp. 2134-2142.

90. Kumar A., Shorey R. Performance Analysis and Scheduling of Stochastic Fork-Join Jobs in a Multicomputer System // IEEE Transactions on Parallel and Distributed Systems. — 1993. — Vol. 10, no. 4. — Pp. 1147-1164.

91. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications / G. Bolch, S. Greiner, H. de Meer, K.S. Trivedi. — John Wiley & Sons, 2006. — P. 896.

92. Boyce W.E., DiPrima R.C. Elementary Differential Equations and Boundary Value Problems. — John Wiley & Sons, 2012. — P. 809.

93. Barlow R.E., F. Proschan. Statistical Theory of Reliability and Life Testing: Probability Models. — John Wiley & Sons, 1981. — P. 290.

94. Perros H.G. On the M/Ck/1 queue // Performance Evaluation. — 1983. — Vol. 3, no. 2. — Pp. 83-93.

95. Neuts M.F. Matrix-geometric solutions in stochastic models: an algorithmic approach. — Courier Corporation, 1981. — P. 332.

96. Rao B.M., Posner M.J.M. Algorithmic and approximation analyses of the split and match queue // Stochastic Models. — 1985. — Vol. 1, no. 3. — Pp. 433-456.

97. Takahashi M, Osawa H, Fujisawa T. On a synchronization queue with two finite buffers // Queueing Systems. — 2000. — Vol. 36. — Pp. 107-123.

98. Takahashi M, Takahashi Y. Synchronization queue with two MAP inputs and finite buffers // Proc. of the Third International Conference on Matrix Analytical Methods in Stochastic Models. — 2000. — Pp. 375-390.

99. Generalized parallel-server fork-join queues with dynamic task scheduling / M.S. Squillante, Y. Zhang, A. Sivasubramaniam, N. Gautam // Annals of Operations Research. — 2008. — Vol. 160, no. 1. — Pp. 227-255.

100. Allen A.O. Probability, Statistics, and Queueing Theory: With Computer Science Applications. — Gulf Professional Publishing, 1990. — 740 c.

101. Kleinrock L. Queueing systems, volume I: theory. — Wiley Interscience, 1975. — P. 448.

102. Trivedi K.S. Probability and Statistics with Reliability, Queueing, and Computer Science Applications (2nd ed.). — John Wiley & Sons, 2002. — P. 830.

103. Gravey A. A simple construction of an upper bound for the mean of the maximum of N identically distributed random variables // Journal of Applied Probability. — 1985. — Vol. 22. — P. 844-851.

104. Petzold M. A note on the first moment of extreme order statistics from the normal distribution // rapport nr.: Seminar Papers. — 2000.

Список рисунков

1.1 Система массового обслуживания типа fork-join.......... 16

1.2 Система массового обслуживания типа split-merge......... 17

1.3 Система массового обслуживания типа fission-fusion........ 17

2.1 Схема облачного центра........................ 41

2.2 Схема системы массового обслуживания для облачного центра . . 43

2.3 Среднее время отклика: 1 — формула (2.55), 2 — формула (2.56), 3 — (2.57), 4 — (2.58), 5 — верхняя граница для максимума порядковых статистик (2.59), 6 — имитационная модель...... 57

2.4 Среднеквадратическое отклонение времени отклика: 1 — аналитическая модель; 2 — имитационная модель......... 57

2.5 Среднее время синхронизации: 1 — имитационная модель, 2 — аналитическая модель; среднеквадратическое отклонение времени синхронизации: 3 — имитационная модель, 4 — аналитическая модель ......................... 58

3.1 Диаграмма интенсивностей переходов................................60

3.2 Состояние диаграммы интенсивностей переходов ....................63

3.3 Диаграмма интенсивностей переходов для упрощённой модели . . 72

3.4 Математическое ожидание времени отклика: 1 — а = 0.1; 2 —

а = 1; 3 — а = 10............................ 82

3.5 Дисперсия времени отклика: 1 — а = 0.1; 2 — а = 1; 3 — а = 10 . 83