×

Optimal energy-efficient policies for data centers through sensitivity-based optimization. (English) Zbl 1435.68056

Summary: In this paper, we propose a novel dynamic decision method by applying the sensitivity-based optimization theory to find the optimal energy-efficient policy of a data center with two groups of heterogeneous servers. Servers in Group 1 always work at high energy consumption, while servers in Group 2 may either work at high energy consumption or sleep at low energy consumption. An energy-efficient control policy determines the switch between work and sleep states of servers in Group 2 in a dynamic way. Since servers in Group 1 are always working with high priority to jobs, a transfer rule is proposed to migrate the jobs in Group 2 to idle servers in Group 1. To find the optimal energy-efficient policy, we set up a policy-based Poisson equation, and provide explicit expressions for its unique solution of performance potentials by means of the RG-factorization. Based on this, we characterize monotonicity and optimality of the long-run average profit with respect to the policies under different service prices. We prove that the bang-bang control is always optimal for this optimization problem, i.e., we should either keep all servers sleep or turn on the servers such that the number of working servers equals that of waiting jobs in Group 2. As an easy adoption of policy forms, we further study the threshold-type policy and obtain a necessary condition of the optimal threshold policy. We hope the methodology and results derived in this paper can shed light to the study of more general energy-efficient data centers.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B22 Queues and service in operations research
90C40 Markov and semi-Markov decision processes
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barroso, La; Hölzle, U., The case for energy-proportional computing, Computer, 40, 12, 33-37 (2007)
[2] Benini, L.; Bogliolo, A.; De Micheli, G., A survey of design techniques for system-level dynamic power management, IEEE Trans Very Large Scale Integr VLSI Syst, 8, 3, 299-316 (2000)
[3] Becker R, Zilberstein S, Lesser V (2004) Decentralized Markov decision processes with event-driven interactions. In: Proceedings of the 3rd international joint conference on autonomous agents and multiagent systems, vol 1, 302-309
[4] Bell, Ce, Optimal operation of an M/M/2 queue with removable servers, Oper Res, 28, 5, 1189-1204 (1980) · Zbl 0444.60092
[5] Bodenstein, C.; Schryen, G.; Neumann, D., Energy-aware workload management models for operation cost reduction in data centers, Eur J Oper Res, 222, 1, 157-167 (2012)
[6] Cao, Xr, Stochastic learning and optimization—A sensitivity-based approach (2007), New York: Springer, New York · Zbl 1130.93057
[7] Chen, X.; Wardi, Y.; Yalamanchili, S., Instruction-throughput regulation in computer processors with data-center applications, Discrete Event Dynamic Systems: Theory and Applications, 28, 1, 127-158 (2018) · Zbl 1384.93077
[8] De Napoli C, Forestiero A, Lagana D, Lupi G, Mastroianni C, Spataro L (2016) Business scenarios for geographically distributed data centers. RT-ICAR-CS-16-03
[9] Engel Y, Etzion O (2011) Towards proactive event-driven computing. In: Proceedings of the 5th ACM international conference on distributed event-based system, pp 125-136
[10] Gandhi A (2013) Dynamic server provisioning for data center power management. Ph.D. Thesis, School of Computer Science Carnegie Mellon University, Pittsburgh, USA
[11] Gandhi, A.; Doroudi, S.; Harchol-Balter, M.; Scheller-Wolf, A., Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Queueing Systems, 77, 2, 177-209 (2014) · Zbl 1307.60130
[12] Gandhi, Anshul; Gupta, Varun; Harchol-Balter, Mor; Kozuch, Michael A., Optimality analysis of energy-performance trade-off for server farm management, Performance Evaluation, 67, 11, 1155-1171 (2010)
[13] Gandhi, A.; Harchol-Balter, M., M/G/k with staggered setup, Oper Res Lett, 41, 4, 317-320 (2013) · Zbl 1286.90029
[14] Gandhi, Anshul; Harchol-Balter, Mor; Adan, Ivo, Server farms with setup costs, Performance Evaluation, 67, 11, 1123-1138 (2010)
[15] Gandhi A, Harchol-Balter M, Kozuch MA (2012) Are sleep states effective in data centers? In: 2012 international green computing conference (IGCC), pp 1-10
[16] Gebrehiwot, Me; Aalto, S.; Lassila, P., Optimal energy-aware control policies for FIFO servers, Perform Eval, 103, 41-59 (2016)
[17] Gebrehiwot, Me; Aalto, S.; Lassila, P., Energy-performance trade-off for processor sharing queues with setup delay, Oper Res Lett, 44, 1, 101-106 (2016) · Zbl 1408.90067
[18] Gebrehiwot, Me; Aalto, S.; Lassila, P., Energy-aware SRPT server with batch arrivals: Analysis and optimization, Perform Eval, 115, 92-107 (2017)
[19] Hassin, R.; Shaki, Yy; Yovel, U., Optimal service-capacity allocation in a loss system, Nav Res Logist, 62, 2, 81-97 (2015) · Zbl 1310.90025
[20] Hipp, Sk; Holzbaur, Ud, Decision processes with monotone hysteretic policies, Oper Res, 36, 4, 585-588 (1988) · Zbl 0652.90047
[21] Huang, L.; Neely, Mj, Utility optimal scheduling in energy-harvesting networks, IEEE/ACM Trans Netw, 21, 4, 1117-1130 (2013)
[22] Hong, Ks; Lee, C., Integrated pricing and capacity decision for a telecommunication service provider, Multimed Tools Appl, 64, 2, 389-406 (2013)
[23] Hunter, Jj, Generalized inverses and their application to applied probability problems, Linear Algebra Appl, 45, 157-198 (1982) · Zbl 0493.15003
[24] Kamitsos I, Andrew L, Kim H, Chiang M (2010) Optimal sleep patterns for serving delay-tolerant jobs. In: Poceedings of the 1st international conference on energy-efficient computing and networking, pp 31-40
[25] Kamitsos I, Andrew L, Kim H, Ha S (2012) Better energy-delay tradeoff via server resource pooling. In: The 2012 international conference on computing, networking and communications, pp 611-616
[26] Kamitsos, I.; Ha, S.; Andrew, L.; Bawa, J.; Butnariu, D.; Kim, H.; Chiang, M., Optimal sleeping: models and experiments for energy-delay tradeoff, International Journal of Systems Science: Operations & Logistics, 4, 4, 356-371 (2017)
[27] Kliazovich, D.; Bouvry, P.; Khan, Su, GreenCloud: a packet-level simulator of energy-aware cloud computing data centers, J Supercomput, 62, 3, 1263-1283 (2012)
[28] Koole, G., Structural results for the control of queueing systems using event-based dynamic programming, Queueing Systems, 30, 3-4, 323-339 (1998) · Zbl 0917.90136
[29] Kuehn, Pj; Mashaly, Me, Automatic energy efficiency management of data center resources by load-dependent server activation and sleep modes, Ad Hoc Netw, 25, Part B, 497-504 (2015)
[30] Li QL (2010) Constructive computation in stochastic models with applications: The RG-factorizations. Springer · Zbl 1208.60073
[31] Li, Ql; Cao, J., Two types of RG-factorizations of quasi-birth-and-death processes and their applications to stochastic integral functionals, Stoch Model, 20, 3, 299-340 (2004) · Zbl 1061.60089
[32] Li QL, Ma JY, Xie MZ, Xia L (2017) Group-server queues. In: International conference on queueing theory and network applications, pp 49-72 · Zbl 1391.90191
[33] Lu, Fv; Serfozo, Rf, M/M/1 queueing decision processes with monotone hysteretic optimal policies, Oper Res, 32, 5, 1116-1132 (1984) · Zbl 0547.60096
[34] Ma J Y, Li Q L, Xia L (2019) Optimal asynchronous dynamic policies in energy-efficient data centers. arXiv:1901.03371, pp 1-63
[35] Maccio, Vj; Down, Dg, On optimal policies for energy-aware servers, Perform Eval, 90, 36-52 (2015)
[36] Maccio, Vj; Down, Dg, Structural properties and exact analysis of energy-aware multiserver queueing systems with setup times, Perform Eval, 121, 48-66 (2018)
[37] Maccio VJ, Down DG (2018) Asymptotic performance of energy-aware multiserver queueing systems with setup times. In: 2018 annual american control conference, pp 6266-6272
[38] Mazzucco M, Dyachuk D, Deters R (2010) Maximizing cloud providers revenues via energy aware allocation policies. In: IEEE international conference on cloud computing, pp 131-138
[39] Mitrani, I., Service center trade-offs between customer impatience and power consumption, Perform Eval, 68, 11, 1222-1231 (2011)
[40] Mitrani, I., Managing performance and power consumption in a server farm, Ann Oper Res, 202, 1, 121-134 (2013) · Zbl 1260.90069
[41] Natural Resources Defense Council (2016) Environmental issues [Online]. Available: https://www.nrdc.org/resources/americas-data-centers-consuming-and-wasting-growing-amounts-energy
[42] Phung-Duc T (2015) Multiserver queues with finite capacity and setup time. In: International conference on analytical and stochastic modeling techniques and applications, Springer, pp 173-187 · Zbl 1392.68132
[43] Phung-Duc, T., Exact solutions for M/M/c/setup queues, Telecommun Syst, 64, 2, 309-324 (2017)
[44] Phung-Duc T, Ren Y, Chen JC, Yu ZW (2016) Design and analysis of deadline and budget constrained autoscaling (DBCA) algorithm for 5G mobile networks. In: 2016 IEEE international conference on cloud computing technology and science (CloudCom), pp 94-101
[45] Puterman ML (2014) Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons · Zbl 0829.90134
[46] Qiu Q, Pedram M (1999) Dynamic power management based on continuous-time Markov decision processes. In: Proceedings of the 36th annual ACM/IEEE design automation conference, pp 555- 561
[47] Qiu, Q.; Qu, Q.; Pedram, M., Stochastic modeling of a power-managed system-construction and optimization, IEEE Trans Comput Aided Des Integr Circuits Syst, 20, 10, 1200-1217 (2001)
[48] Ren Y, Phung-Duc T, Chen JC, Yu ZW (2016) Dynamic auto scaling algorithm (DASA) for 5G mobile networks. In: 2016 IEEE global communications conference (GLOBECOM), pp 1-6
[49] Ren Y, Phung-Duc T, Liu YK, Chen JC, Lin YH (2018) ASA: Adaptive VNF scaling algorithm for 5G mobile networks. In: 2018 IEEE 7th international conference on cloud networking (CloudNet), pp 1-4
[50] Schwartz C, Pries R, Tran-Gia P (2012) A queuing analysis of an energy-saving mechanism in data centers. In: The international conference on information network (ICOIN), pp 70-75
[51] Shehabi A, Smith S, Sartor D et al (2016) United States data center energy usage report. Lawrence Berkely Lab
[52] Šimunić, T.; Benini, L.; Glynn, P.; De Micheli, G., Event-driven power management, IEEE Trans Comput Aided Des Integr Circuits Syst, 20, 7, 840-857 (2001)
[53] Tan, Y.; Lu, Y.; Xia, Ch, Provisioning for large scale loss network systems with applications in cloud computing, ACM Sigmetrics Performance Evaluation Review, 40, 3, 83-85 (2012)
[54] Van Der Laan, D., Assigning multiple job types to parallel specialized servers, Discrete Event Dyn Syst, 28, 4, 471-507 (2018) · Zbl 1407.90176
[55] Xia, L., Service rate control of closed Jackson networks from game theoretic perspective, Eur J Oper Res, 237, 2, 546-554 (2014) · Zbl 1304.90071
[56] Xia, L., Event-based optimization of admission control in open queueing networks, Discrete Event Dynamic Systems: Theory and Applications, 24, 2, 133-151 (2014) · Zbl 1296.93115
[57] Xia, L.; Cao, Xr, Performance optimization of queueing systems with perturbation realization, Eur J Oper Res, 218, 2, 293-304 (2012) · Zbl 1244.90070
[58] Xia, L.; Chen, S., Dynamic pricing control for open queueing networks, IEEE Trans Autom Control, 63, 10, 3290-3300 (2018) · Zbl 1423.90063
[59] Xia, L.; He, Qm; Alfa, As, Optimal control of state-dependent service rates in a MAP/M/1 queue, IEEE Trans Autom Control, 62, 10, 4965-4979 (2017) · Zbl 1390.90266
[60] Xia, L.; Jia, Qs, Parameterized Markov decision process and its application to service rate control, Automatica, 54, 29-35 (2015) · Zbl 1318.93062
[61] Xia, L.; Jia, Qs; Cao, Xr, A tutorial on event-based optimization——A new optimization framework, Discrete Event Dynamic Systems: Theory and Applications, 24, 2, 103-132 (2014) · Zbl 1296.93116
[62] Xia, L.; Miller, D.; Zhou, Z.; Bambos, N., Service rate control of tandem queues with power constraints, IEEE Trans Autom Control, 62, 10, 5111-5123 (2017) · Zbl 1390.90267
[63] Xia, L.; Shihada, B., Max-min optimality of service rate control in closed queueing networks, IEEE Trans Autom Control, 58, 4, 1051-1056 (2013) · Zbl 1369.90054
[64] Xia, L.; Shihada, B., A Jackson network model and threshold policy for joint optimization of energy and delay in multi-hop wireless networks, Eur J Oper Res, 242, 3, 778-787 (2015) · Zbl 1341.90025
[65] Yadin, M.; Naor, P., Queueing systems with a removable service station, J Oper Res Soc, 14, 4, 393-405 (1963)
[66] Yang, J.; Zhang, S.; Wu, X.; Ran, Y.; Xi, H., Online learning-based server provisioning for electricity cost reduction in data center, IEEE Trans Control Syst Technol, 25, 3, 1044-1051 (2017)
[67] Yao, Y.; Huang, L.; Sharma, Ab; Golubchik, L.; Neely, Mj, Power cost reduction in distributed data centers: A two-time-scale approach for delay tolerant workloads, IEEE Trans Parallel Distrib Syst, 25, 1, 200-211 (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.