1 Россиискии университет дружбы народов, г. Москва, Россия 2 Институт проблем информатики ФИЦ ИУ РАН, г. Москва, Россия

Abstract

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

-

In the paper, cloud computing system with dynamic scaling is analyzed in terms of multiserver queuing system with hysteretic control of active server numbers based on queue length thresholds, and noninstantaneous server activation. To decrease computing complexity of the algorithms for evaluation of response time characteristics, we provide the analysis under simplifying assumption that only three servers may run activation procedures simultaneously. Recurrent algorithm for Laplace-Stieltjes transform of the response time and the sojourn time is developed. The algorithm is used to analyze response time characteristics of a cloud computing system.

Cloud computing; response time; hysteretic control; dynamic scaling; Laplace-Stieltjes transform. правило, масштабируемыми, что позволяет системе справляться с высокои нагрузкои и иметь возможность снизить энергопотребление в периоды снижения нагрузки.

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

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

Одним из способов реализации третьего подхода является динамическая активация виртуальных машин [ 5,10 ]. Иными словами, регулируется количество ресурсов (серверов, машин) в зависимости от текущеи нагрузки [ 6-8 ]. При анализе таких систем применяются модели с пороговым управлением обслуживанием, в том числе, с гистерезисным управлением количеством включенных приборов [ 2,4 ]. При этом основнои проблемои при моделировании облачных систем с помощью методов теории телетрафика является высокая вычислительная сложность получаемых в результате алгоритмов [ 1 ]. В [ 4 ] исследована система с гистерезисным управлением обслуживанием для анализа предоставления услуги видео по требованию, стационарные характеристики системы получены с помощью матричных методов, которые не применимы для анализа современных облачных платформ из-за высокои вычислительнои сложности. В [ 10 ] система с гистерезисным управлением обслуживанием применена для анализа облачных систем с конечным числом приборов, а для случая трех приборов получен эффективныи вычислительныи алгоритм расчета стационарных характеристик функционирования облачнои системы, имеющии линеиную сложность. Однако слабои сторонои предложеннои модели является чрезвычаино большая мощность пространства состоянии, которая имеет квадратичную зависимость от количества серверов. Поэтому в даннои статье мы рассмотрим упрощенную модель с уменьшенным пространством состоянии благодаря наложению ограничения на максимальное количество одновременно возможных активации, и проведем анализ ее характеристик с помощью известных своиств преобразования Лапласа-Стилтьеса, алгоритм получения которого и будет предложен в даннои работе. Статья является развитием работы [ 10 ], а также продолжением работы [ 3 ], в которои был разработан эффективныи алгоритм вычисления стационарных вероятностеи и показателеи качества функционирования системы. Математическая модель

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

В пустои системе активным, т.е. готовым при поступлении заявки мгновенно начать ее обслуживание, является один прибор. При поступлении заявок в систему активация приборов происходит не мгновенно, при этом количество активных приборов определяется числом заявок в очереди, в которои установлены парные пороги, заданные значениями векторов Η  (H1 , H 2 ,..., H K1 ) H1  H 2  ...  H K1 , и L  (L1 , L2 ,..., LK1 ) , L1  L2  ...  LK1 , где Li1  H i , i  1, K  2 и Li  Hi , i  1, K  1 . Заявки обслуживаются в порядке поступления, т.е. очередь имеет дисциплину FCFS (First Come First Served). При поступлении на прибор заявка сохраняет место в очереди. Кроме того, накладывается ограничение на число одновременных активации, которых не 1,1,0 1,1,1  

   1,1,2 ... 1,1,L1 1 ...

    

1,1,H1  должно быть больше трех. Таким образом, когда в системе уже запущено два процесса активации, то при возникновении необходимости в запуске третьего дополнительного прибора его активация происходит мгновенно.

Правила работы системы следующие: 1. Если в системе уже есть H i заявок, то при поступлении новои заявки активируется (подключается) один (i 1) -и дополнительныи прибор, но не мгновенно, а через случаиное время, имеющее экспоненциальное распределение с параметром  ;

2. Если в системе находится Li заявок и при этом одна заявка обслужилась, то (i 1) -и прибор мгновенно отключается, либо, если он не был активен, останавливается процедура его активации. (I)

      (II) 2,1,L1 ... 2,1,L2 1 ... 2,1,H1 1 ... 2,1,H2

          (I) 2,2,L1 ... 2,2,L2 1 ... 2,2,H11 ... 2,2,H2 2 2 2 2 2 2  

      3,1,L2 ... 3,1,H1 ... 3,1,L3 1 ... 3,1,H2 1 ... 3,1,H3 2 2  2   2    2   2 3 (II) 3,2,L2 ... 3,2,H1 ... 3,2,L3 12...23,2,H2 1 ... 3,2,H3  2 2  2 2  2 2 

        (I) 3,3,L2 ... 3,3,H1 ... 3,3,L3 1 ... 3,3,H2 1 ... 3,3,H3 3 3 3 3 3 3 3 3  (III)    level 1,1 level 2,1 level 2,2 level 3,1 level 3,2 ... 4 2

        3 4,2,L3 ... 4,2,H2 ... 4,2,L4 1 ... 4,2,H3 1 ... 4,2,H4

22 2 22 2 2 2 2 2 2 2 2 (II) 4,3,L3 ... 4,3,H2 ... 4,3,L4 1 ... 4,3,H3 1 ... 4,3,H4

 3 3  3 3  3 3  3 3  (I) 4,4,L43...44,4,H24 ... 44,4,L4 14 ... 44,4,H3 41..4.4,4,H4 (III)  

 3

   5,3,L4 ... 5,3,H3 ...

4 23 3 23 5 (II) 5,4,L4 ... 5,4,H3 ...

 4 4  4 (IV) 5,5,L4 ... 5,5,H3 ...

5 5 5

(III)      5,3,L5 1 ... 5,3,H4 1 ... 5,3,R 3 2 3 3 2 3 3 2    5,4,L5 1 ... 5,4,H4 1 ... 5,4,R 4  4 4  4 4       55,5,L5 15 ... 55,5,H4 51 ..5.5,5,R Рис.1. Диаграмма интенсивностей переходов для системы с K=5 приборами Функционирование системы описывается Марковским процессом X (t) с множеством состоянии  0  n  H1, k  1, i  1    S  k,i, n Lk1  n  H k , k  2, i  k 1, k 

,  Lk1  n  H k , k  3, K 1, i  k  2, k    Lk1  n  R, k  K, i  k  2, k  где k – необходимое количество приборов; i – количество активированных приборов; n – количество заявок в очереди. Для выбранного расположения пороговых значении относительно друг друга диаграмма интенсивностеи переходов для системы с K  5 приборами представлена на рисунке 1. Метод вычисления преобразования Лапласа-Стилтьеса для времени отклика системы Для того чтобы составить объективное мнение о поведении времени отклика системы, недостаточно знать только среднее значение этои случаинои величины. Для всеи полноты картины, а также для решения актуальных практических задач наряду с математическим ожиданием желательно иметь представление о значениях дисперсии и моментов высших порядков. В этои связи определение функции распределения времени отклика – в нашем случае в терминах преобразования Лапласа-Стилтьеса (ПЛС) – приобретает особую важность. Vkm,i,n (s)  1, m  i. (1) В остальных случаях будут справедливы рекуррентные соотношения, полученные, исходя из следующих соображении: время ожидания m -и в очереди заявки, если система находится в состоянии (k,i, n) , складывается из суммы двух времен, а именно времени, проведенного в ожидании перехода в одно из следующих возможных состоянии и времени пребывания заявки в очереди в ожидании обслуживания, оставшегося уже после совершения этого шага, проделав которыи, естественно, что заявка может сменить свое местоположение в очереди. Теперь, вроасзплиолчьнзыохвасвосштиосяьнифиосримстуелмоыи: полнои вероятности, запишем следующие соотношения для Vkm,k ,n (s)    kk  s Vkm,k,1n1 (s)    k  s Vkm,k,n1 (s),

1  k  K , Lk 1  n  H k ; k  Vk m,k,Lk1 (s)    k  s Vkm1,1k1,Lk11(s)    k  s Vkm,k,Lk11(s), 2  k  K ; Vkm,k ,Hk (s)    kk  s Vkm,k,1Hk 1(s)    k  s Vkm1,k,Hk 1 (s), 1  k  K 1;

K

VKm,K ,R (s)  K  s VKm,K1,R1 (s); Vkm,k 2,n (s)    (k (k2)2) 2  s Vkm,k12,n1 (s)    (k  2)  2  s Vkm,k2,n1 (s)  

2   (k  2)  2  s Vkm,k1,n (s), 2  k  K , Lk1  n  H k ; Vkm,k1,n (s)    (k(k1)1)  s Vkm,k11,n1 (s)    (k 1) )  s Vkm,k1,n1(s)  

   (k 1)   s Vkm,k,n (s), 2  k  K , Lk1  n  H k ; Vkm,k2,Lk1 (s)    (k (k2)2) 2  s Vkm1,1k2,Lk11 (s)    (k  2)  2  s Vkm,k 2,Lk11 (s)  

2   (k  2)  2  s Vkm,k1,Lk1 (s), 2  k  K ; Vkm,k1,Lk1 (s)    (k(k 1)1)  s Vkm1,1k1,Lk11 (s)    (k 1)    s Vkm,k1,Lk11 (s)  

   (k 1)    s Vkm,k,Lk1 (s), 2  k  K ; 

2   (k  2)  2  s Vkm,k1,Hk (s), 2  k  K 1; Vkm,k2,Hk (s)    (k (k2)2) 2  s Vkm,k12,Hk 1 (s)    (k  2)  2  s Vkm1,k 1,Hk 1 (s)  (2) (3) (4) (5) (6) (7) (8) (9) (10)

i (K  i)

VKm,i,R (s)  i  (K  i)  s VKm,i,1R1(s)  i  (K  i)  s VKm,i1,R (s), 1  i  K.

Далее на основе рекуррентных соотношении (1)–(12) составляется алгоритм уже для вычисления ПЛС Vkn,i,n (s), с помощью которого можно наити ПЛС V (s) времени ожидания и ПЛС W (s) времени пребывания заявки в системе:

V (s) 

 k,i,nVkn,i,n (s); (k,i,n)S W (s) 

V (s),    s (11) (12) (13) (14) где  k,i,n – стационарные вероятности для соответствующих состоянии (k, i, n) , алгоритм вычисления которых приведен в [ 3 ]. Последовательность применения рекуррентных формул для вычисления Vkn,i,n (s) в силу громоздкости ее описания приводить не будем, но заметим, что в качестве первых шагов итерации следует рассматривать ПЛС для времени ожидания обслуживания заявки, стоящеи первои в очереди, постепенно отдаляя ее от обслуживающих приборов.

Задача обращения ПЛС для времени ожидания начала обслуживания и времени отклика системы в случае большого объема накопителя и, соответственно, значении парных порогов активации и отключения дополнительных приборов, представляет собои значительную вычислительную трудность. Однако благодаря своиствам ПЛС, в частности, тому, что n -и момент случаинои величины  равен:

E n  (1)n (n) (0) , где  (n) (0) – это значение n -и производнои ПЛС случаинои величины  в нуле, возможно вычислить моменты высших порядков и составить полноценное представление о поведении исследуемых случаиных величин. Численный пример

Рассмотрим применение разработанного метода расчета временных характеристик модели системы облачных вычислении в терминах преобразования Лапласа-Стилтьеса для следующего набора данных: число приборов K  4 , максимальная длина очереди R  75 , векторы нижних и верхних порогов L  (10,20,30) , H  (25,35,45) , интенсивность обслуживания заявок   1 . Рис.2. Математическое ожидание времени отклика На рисунке 2 изображены графики зависимости среднего времени отклика от интенсивности входящего потока  для различных значении параметра  экспоненциального времени активации дополнительных приборов, на которых в целом наблюдается рост математического ожидания, что вполне естественно для увеличения значении интенсивности входящего потока. При   0.1 колебания среднего времени отклика незначительны, и с ростом  кривая сглаживается, поскольку большую часть времени заявки проводят в ожидании начала обслуживания. Для двух других значении  на графиках более четко выражены локальные минимумы, что объясняется выигрышем во времени при небольших значениях загрузки системы за счет быстрого и своевременного подключения дополнительных приборов.

Рис.3. Дисперсия времени отклика Как видно из рисунка 3, на графике дисперсии тоже присутствуют локальные минимумы, что также вызвано вышеописаннои причинои. При малом значении   0.1 система ведет себя более определенно, так как серверы в преобладающем большинстве случаев не успевают вовремя подключиться и заявкам приходится длительную часть времени пребывать в очереди. При больших значениях  наблюдаются скачки, в частности, локальныи максимум при   4 . Заключение

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

Исследование выполнено при частичной финансовой поддержке РФФИ в рамках научных проектов № 14-07-00090, 15-07-03051, 15-07-03608.

References

References

1. Basharin G.P. , Gaidamaka Yu .V., Samuilov K .E. Mathematical teletraffic theory and its application to the analysis of the next generations multiservice networks // Automatic control and computer sciences, Latvia , Riga: Institute of electronics and computer science of the Latvian university. - 2013. - № . 2. - P. 11 - 21 .

2. Гайдамака Ю.В. , Печинкин А .В., Разумчик Р .В., Самуйлов А .К., Самуйлов К .Е., Соколов И .А., Сопин Э .С., Шоргин С .Я. Распределение времени выхода из множества состояний перегрузки в системе M | M | 1 | <L,H> | <H,R> с гистерезисным управлением нагрузкой // Информатика и ее применения. - 2013 . - Т . 7, Вып . 4. - С . 20 - 33 .

3. 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

4. Golubchik L. , Lui J.C.S. Bounding of Performance Measures for Threshold-Based Queuing Systems: Theory and Application to Dynamic Resource Management in Video-on- Demand Servers // IEEE Trans. Computers . - 2002 . - Vol. 51 , № . 4. - P. 353 - 372 .

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, Dhanbad, India. - 2012 . - P. 357 - 362 .

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

7. Lin M. , Wierman A. , Andrew L.L.H. , Thereska E . Dynamic right-sizing for power-proportional data centers // INFOCOM , Proceedings IEEE . - 2011 . - P. 1098 - 1106 .

8. Meisner D. , Gold B.T. , Wenisch T.F. Powernap : eliminating server idle power // CM SIGPLAN Notices . - 2009 . - Vol. 44 . - P. 205 - 216 .

9. Nedevschi S. , Popa L. , Iannaccone G. , Ratnasamy S. , Wetherall D. Reducing network energy consumption via sleeping and rate-adaptation // Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation , NSDI' 08 , Berkeley, CA, USA. USENIX Association. - 2008 . - P. 323 - 336 .

10. Shorgin S.Y. , Pechinkin A.V. , Samouylov K.E. , Gaidamaka Y.V. , Gudkova I.A. , Sopin E.S. Threshold-based Queuing System for Performance Analysis of Cloud Computing System with Dynamic Scaling // Proc. of the 12th International Conference of Numerical Analysis and Applied Mathematics ICNAAM-2014 , Rhodes, Greece, 2014 , USA, AIP Publishing - 2015 . - Vol. 1648 . - P. 1 - 3 .

1. Basharin G.P. , Gaidamaka Yu .V., Samuilov K .E. Mathematical teletraffic theory and its application to the analysis of the next generations multiservice networks // Automatic control and computer sciences, Latvia , Riga: Institute of electronics and computer science of the Latvian university. - 2013. - № . 2. - P. 11 - 21 .

2. Gaydamaka Yu .V., Pechinkin A.V. , Razumchik R.V. , Samuylov A.K. , Samuylov K.E. , Sokolov I.A. , Sopin E.S. , Shorgin S. Ya . Raspredelenie vremeni vykhoda iz mnozhestva sostoyaniy peregruzki v sisteme M | M | 1 | <L,H> | <H, R> s gisterezisnym upravleniem nagruzkoy // Informatika i ee primeneniya . - 2013 . - T. 7 , Vyp . 4. - S. 20 - 33 .

3. 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

4. Golubchik L. , Lui J.C.S. Bounding of Performance Measures for Threshold-Based Queuing Systems: Theory and Application to Dynamic Resource Management in Video-on- Demand Servers // IEEE Trans. Computers . - 2002 . - Vol. 51 , № . 4. - P. 353 - 372 .

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, Dhanbad, India. - 2012 . - P. 357 - 362 .

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

7. Lin M. , Wierman A. , Andrew L.L.H. , Thereska E . Dynamic right-sizing for power-proportional data centers // INFOCOM , Proceedings IEEE . - 2011 . - P. 1098 - 1106 .

8. Meisner D. , Gold B.T. , Wenisch T.F. Powernap : eliminating server idle power // CM SIGPLAN Notices . - 2009 . - Vol. 44 . - P. 205 - 216 .

9. Nedevschi S. , Popa L. , Iannaccone G. , Ratnasamy S. , Wetherall D. Reducing network energy consumption via sleeping and rate-adaptation // Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation , NSDI' 08 , Berkeley, CA, USA. USENIX Association. - 2008 . - P. 323 - 336 .

10. Shorgin S.Y. , Pechinkin A.V. , Samouylov K.E. , Gaidamaka Y.V. , Gudkova I.A. , Sopin E.S. Threshold-based Queuing System for Performance Analysis of Cloud Computing System with Dynamic Scaling // Proc. of the 12th International Conference of Numerical Analysis and Applied Mathematics ICNAAM-2014 , Rhodes, Greece, 2014 , USA, AIP Publishing - 2015 . - Vol. 1648 . - P. 1 - 3 .