Resource Allocation in Cloud Computing Via Optimal Control to Queuing Systems

We consider resource allocation problem in the cloud computing. We use queuing model to model the process of entering into the cloud and to schedule and to serve incoming jobs. In this paper, the main problem is to allocate resources in the queuing systems as a general optimization problem for controlled Markov process with finite state space. For this purpose, we study a model of cloud computing where the arrival jobs follow a stochastic process. We reduce this problem to a routing problem. In the case of minimizing, cost is given as a mixture of an average queue length and number of lost jobs. We use dynamic programming approach. Finally, we obtain the explicit form of the optimal control by the Bellman equation.

Keywords

cloud computing; multiple queueing system; multiple job classes; stochastic control policy.

References

1. Foster I., Zhao Y., Raicu I., Lu S. Cloud Computing and Grid Computing 360-Degree Compared. Grid Computing Environments Workshop, 2008, vol. 32, pp. 1-10.
2. Armbrust M., Fox A., Griffith R., Joseph A., Katz R., Konwinski A., Lee G., Patterson D., Rabkin A., Stoica I. Above the Clouds: a Berkeley View of Cloud Computing. Technical Reports, 2009, p. UCB/EECS-2009-28.
3. Menasce D.A., Ngo P. Understanding Cloud Computing: Experimentation and Capacity Planning. Computer Measurement Group Conference, 2009, Dallas, 7-11 December, 11 p.
4. Vinothina V., Sridaran R., Padmavathi Ganapathi, Resource Allocation Strategies in Cloud Computing, International Journal of Advanced Computer Science and Applications, 2012, vol. 3, no. 6, pp. 18-22.
5. Vilaplana J., Solsona F., Teixidу I., Mateo J., Abella F., Rius J. A Queuing Theory Model for Cloud Computing. The Journal of Supercomputing, 2014, vol. 69, pp. 492-507.
6. Salehpour M., Shahbahrami A., Alleviating Dynamic Resource Allocation for Bag of Tasks Applications in Cloud Computing. International Journal of Grid and Distributed Computing, 2012, vol. 5, no. 3, pp. 95-110.
7. Stolyar A. Maxweight Scheduling in a Generalized Switch: State Space Collapse and Workload Minimization in Heavy Traffic. Applied Probability Journals, 2004, vol. 14, no. 1, pp. 1-53.
8. Eryilmaz A., Srikant R. Asymptotically Tight Steady-State Queue Length Bounds Implied by Drift Conditions. Queueing Systems, 2012, vol. 1, pp. 1-49.
9. Mitzenmacher M. The Power of Two Choices in Randomized Load Balancing. PhD thesis, University of California at Berkeley, Harvard University, 1996.
10. Bramson M., Lu Y., Prabhakar B. Randomized Load Balancingwith General Service Time Distributions. ACM SIGMETRICS Performance Evaluation Review, 2010, vol. 8, no. 1, pp. 275-286.
11. Hong Chen, Heng-Qing Ye. Asymptotic Optimality of Balanced Routing. Operation Research, 2010, vol. 60, no. 1, pp. 163-179. DOI: 10.1287/opre.1110.1011
12. Yu-Tong He, Down D.G. Limited Choice and Locality Considerations for Load Balancing. Performance Evaluation, 2008, vol. 65, pp. 670-687. DOI: 10.1016/j.peva.2008.03.001
13. Vvedenskaya N.D., Karpelevich F.I., Queueing System with Selection of the Shortest of Two Queues: an Asymptotic Approach. Problems of Information Transmission, 1996, vol. 32, pp. 15-27.
14. Guo L., Yan T., Zhao S., Jiang C. Dynamic Performance Optimization for Cloud Computing Using M/M/m Queueing System. Journal of Applied Mathematics, 2014, vol. 2014, article ID: 756592, 8 p. DOI: 10.1155/2014/756592
15. Eisa M., Esedimy E.I., Rashad M.Z. Enhancing Cloud Computing Scheduling Based on Queuing Models. International Journal of Computer Applications, 2014, vol. 85, no. 2, pp. 17-23.
16. Siva Theja Maguluri, Srikant R., Lei Ying. Heavy Traffic Optimal Resource Allocation Algorithms for Cloud Computing Clusters. Perfomance Evolution, 2014, vol. 81, pp. 20-39. DOI: 10.1016/j.peva.2014.08.002
17. Zuling Kang, Hongbing Wang. A Novel Approach to Allocate Cloud Resource with Different Performance Traits. Services Computing, 2013, article ID: 13878874, 6 p. DOI: 10.1109/ SCC.2013.109
18. Winston W. Optimality of the Shortest Line Discipline. Journal of Applied Probability, 1977, vol. 14, pp. 181-189.
19. Wan C., Davis M. Existence of Optimal Control for Stochastic Jump Processes. SIAM Journal on Control and Optimization, 1979, vol. 17, pp. 511-524.
20. Elliott R. A Partially Observed Control Problem for Markov Chains. Applied Mathematics and Optimization, 1992, vol. 25, pp. 151-169.
21. Elliott R., Aggoun L., Moore J. Hidden Markov Models. Estimation and Control. N.Y., Springer, 1995.
22. Boel R., Varaia P. Optimal Control of Jump Processes. SIAM Journal on Control and Optimization, 1977, vol. 15, pp. 92-119.
23. Miller B.M. Optimization of Queuing System via Stochastic Control. Automatica, 2009, vol. 45, pp. 1423-1430.
24. Solodyannikov Yu.V. Control and Observation for Dynamical Queueing Networks. Automation and Remote Control, 2014, vol. 75, pp. 422-446.
25. Kleinrock L. Queueing Systems. N.Y., Springer, 1976. \n26. Miller A.B. Using Methods of Stochastic Control to Prevent Overloads in Data Transmission Networks. Automation and Remote Control, 2010, vol. 71, pp. 1804-1815.