Resource Allocation in Cloud Computing Via Optimal Control to Queuing Systems

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

Ключевые слова

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

Литература

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.