DATA CENTER SERVER PROVISION: DISTRIBUTEDASYNCHRONOUS CONTROL FOR COUPLEDRENEWAL SYSTEMS
ABSTRACT
This paper considers a cost minimization problemfor data centers with N servers and randomly arriving servicerequests. A central router decides which server to use for eachnew request. Each server has three types of states (active, idle,and setup) with different costs and time durations. The serversoperate asynchronously over their own states and can chooseone of multiple sleep modes when idle. We develop an onlinedistributed control algorithm so that each server makes itsown decisions. The request queues are bounded and the overalltime average cost is near optimal with probability 1. First thealgorithm does not need probability information for the arrivalrate or job sizes. Finally, an improved algorithm that uses a singlequeue is developed via a “virtualization” technique, which isshown to provide the same (near optimal) costs. Simulation experimentson a real data center traffic trace demonstrate the efficiencyof our algorithm compared with other existing algorithms.
EXISTING SYSTEM:
Related WorksIn this paper, we use renewal-reward theory (together with Lyapunov optimization to developa simple implementable algorithm for this problem. Our workis not alone in approaching the problem this way. Work in uses Lyapunov theory for a system with one renewal server,while work in considers a multi-server system but in adeterministic context. The work in develops a two stagealgorithm for stochastic multi-server systems, but the firststage must be solved offline. This paper is distinct in that weovercome the open challenges of previous work and developa near optimal fully online algorithm for a stochastic systemwith multiple servers.Several alternative approaches to multi-server systems usequeueing theory. Specifically, the work in treats themulti-server system as an M/M/k/setup queue, whereas thework in considers modeling a single server system as amulti-class M/G/1 queue. These approaches require Poissontraffic and do not treat the asynchronous control problem withmultiple sleep options considered in the current paper
PROPOSED SYSTEM:
On the theoretical side, the current paper is the first toconsider the stochastic control problem with heterogeneousservers and multiple idle and setup states at each server. Thisgives rise to a nonstandard asynchronous problem with coupledMarkov decision systems. A novel aspect of the solutionis the construction of a process with super-martingale propertiesby piecing together the asynchronous processes at eachserver. This is interesting because neither the individual serverprocesses nor their asynchronous sum are super-martingales.The technique yields a simple distributed algorithm that canlikely be applied more broadly for other coupled stochasticMDPs.On the practical side, we run our algorithm on a real datacenter traffic trace with server setup time on the order ofseconds. Simulation experiments show that our algorithm iseffective compared to several existing algorithms.
CONCLUSIONS
This paper proposes an efficient distributed asynchronouscontrol algorithm reducing the cost in a data center, wherethe front-end load balancer makes slot-wise routing requeststo the shortest queue and each server makes a frame-basedservice decision by only looking at its own request queue.Theoretically, this algorithm is shown to achieve the nearoptimal cost while stabilizing the request queues. Simulationexperiments on a real data center traffic trace demonstrate thatour algorithm outperforms several other algorithms in reducingthe power consumption as well as achieving lower delays.
REFERENCES
[1] D. P. Bertsekas, Dynamic Programming and Optimal Control, vols. 1–2.Belmont, MA, USA: Athena Scientific, 1995.
[2] M. L. Puterman, Markov Decision Processes: Discrete StochasticDynamic Programming. Hoboken, NJ, USA: Wiley, 2005.
[3] S. Ross, Introduction to Probability Models, 8th ed. San Diego, CA,USA: Academic, 2002.
[4] R. Gallager, Discrete Stochastic Processes. Boston, MA, USA: Kluwer,1996.
[5] L. Georgiadis, M. J. Neely, and L. Tassiulas, “Resource allocation andcross-layer control in wireless networks,” Found. Trends Netw.,vol.1,no. 1, pp. 1–144, 2006.
[6]M.J.Neely,Stochastic Network Optimization with Application toCommunication and Queueing Systems. San Rafael, CA, USA:Morgan & Claypool, 2010.
[7] M. J. Neely, “Dynamic optimization and learning for renewal systems,”IEEE Trans. Autom. Control, vol. 58, no. 1, pp. 32–46, Jan. 2013.
[8] M. J. Neely, “Asynchronous scheduling for energy optimality in systemswith multiple servers,” in Proc. 46th Annu. Conf. Inf. Sci. Syst. (CISS),Mar. 2012, pp. 1–6.
[9] M. J. Neely, “Online fractional programming for Markov decision systems,”in Proc. Allerton Conf. Commun., Control, Comput., Sep. 2011,pp. 353–360.
[10] A. Gandhi, S. Doroudi, M. Harchol-Balter, and A. Scheller-Wolf, “Exactanalysis of the M/M/k/setup class of Markov chains via recursiverenewal reward,” in Proc. ACM Sigmetrics, 2013, pp. 153–166.