×

Resource allocation algorithms for virtualized service hosting platforms. (English) Zbl 1233.68087

Summary: Commodity clusters are used routinely for deploying service hosting platforms. Due to hardware and operation costs, clusters need to be shared among multiple services. Crucial for enabling such shared hosting platforms is virtual machine (VM) technology, which allows consolidation of hardware resources. A key challenge, however, is to make appropriate decisions when allocating hardware resources to service instances. In this work we propose a formulation of the resource allocation problem in shared hosting platforms for static workloads with servers that provide multiple types of resources. Our formulation supports a mix of best-effort and QoS scenarios, and, via a precisely defined objective function, promotes performance, fairness, and cluster utilization. Further, this formulation makes it possible to compute a bound on the optimal resource allocation. We propose several classes of resource allocation algorithms, which we evaluate in simulation. We are able to identify an algorithm that achieves average performance close to the optimal across many experimental scenarios. Furthermore, this algorithm runs in only a few seconds for large platforms and thus is usable in practice.

MSC:

68M14 Distributed systems

Software:

CPLEX; GALib; Eucalyptus
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ali, S.; Kim, J. -K.; Siegel, H. J.; Maciejewski, A. A.: Static heuristics for robust resource allocation of continuously executing applications, Journal of parallel and distributed computing 68, 1070-1080 (2008) · Zbl 1243.68271
[2] M. Aron, P. Druschel, W. Zwaenepoel, Cluster reserves: a mechanism for resource management in cluster-based network servers, in: Proc. of the ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems, June 2000.
[3] N. Bansal, A. Caprara, M. Sviridenko, Improved approximation algorithms for multidimensional bin packing problems, in: Foundations of Computer Science, 2006, pp. 697–708.
[4] P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, A. Warfield, Xen and the art of virtualization, in: Proc. of the ACM Symp. on Operating Systems Principles, October 2003, pp. 164–177.
[5] M.A. Bender, S. Chakrabarti, S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, in: Proc. of the Symp. on Discrete Algorithms, 1998, pp. 270–279. · Zbl 0929.68012
[6] M. Bichler, T. Setzer, B. Speitkamp, Capacity planning for virtualized servers, in: Proc. of the 16th Annual Workshop on Information Technologies & Systems, WITS, 2006.
[7] Caprara, A.; Toth, P.: Lower bounds and algorithms for the 2-dimensional vector packing problem, Discrete applied mathematics 111, No. 3, 231-262 (2001) · Zbl 0996.68245 · doi:10.1016/S0166-218X(00)00267-5
[8] D. Carrera, M. Steinder, I. Whalley, J. Torres, E. Ayguadé, Utility-based placement of dynamic web applications with fairness goals, in: IEEE Network Operations and Management Symposium, 2008, pp. 9–16.
[9] Chase, J.; Anderson, D.; Thakar, P.; Vahdat, A.; Doyle, R.: Managing energy and server resources in hosting centers, SIGOPS operating systems review 35, No. 5, 103-116 (2001)
[10] Chekuri, C.; Khanna, S.: On multi-dimensional packing problems, SIAM journal on computing 33, No. 4, 837-851 (2004) · Zbl 1101.68606 · doi:10.1137/S0097539799356265
[11] Chen, Y.; Iyer, S.; Liu, X.; Milojicic, D.; Sahai, A.: Translating service level objectives to lower level policies for multi-tier services, Cluster computing 11, No. 3, 299-311 (2008)
[12] L. Cherkasova, R. Gardner, Measuring CPU overhead for I/O processing in the Xen virtual machine monitor, in: Proc. of the Usenix Annual Technical Conference, 2005.
[13] C. Clark, K. Fraser, S. Hand, J.G. Hansen, E. Jul, C. Limpach, I. Pratt, A. Warfield, Live migration of virtual machines, in: Proc. of the Symp. on Networked Systems Design and Implementation, 2005, pp. 273–286.
[14] ILOG CPLEX: high-performance software for mathematical programming and optimization. http://www.ilog.com/products/cplex/.
[15] Csirik, J.; Frenk, J. B. G.; Labbe, M.; Zhang, S.: On multidimensional vector bin packing, Acta cybernetica 9, No. 4, 361-369 (1990) · Zbl 0724.68048
[16] R.P. Doyle, J.S. Chase, O.M. Asad, W. Jin, A.M. Vahdat, Model-based resource provisioning in a web service utility, in: Proc. of the USENIX Symposium on Internet Technologies and Systems, 2003.
[17] De La Vega, W. Fernandez; Lueker, G. S.: Bin packing can be solved within \(1+\varepsilon \) in linear time, Combinatorica 1, No. 4, 349-355 (1981) · Zbl 0485.68057 · doi:10.1007/BF02579456
[18] GAlib: a C++ library of genetic algorithm components, 2010. http://lancet.mit.edu/ga/.
[19] Garey, M. R.; Johnson, D. S.: Computers and intractability, A guide to the theory of NP-completeness, (1979) · Zbl 0411.68039
[20] D. Gmach, Managing shared resource pools for enterprise applications, Ph.D. Thesis, Technische Universität München, Fakultät für Informatik, 2009.
[21] D. Gmach, J. Rolia, L. Cherkasova, G. Belrose, T. Turicchi, A. Kemper, An integrated approach to resource pool management: policies, efficiency and quality metrics, in: Proc. of the IEEE Intnl. Conf. on Dependable Systems and Networks, June 2008, pp. 326–335.
[22] D. Gmach, J. Rolia, L. Cherkasova, A. Kemper, Workload analysis and demand prediction of enterprise data center applications, in: Proc. of the 10th IEEE Intnl. Symp. on Workload Characterization, September 2007, pp. 171–180.
[23] Gmach, D.; Rolia, J.; Cherkasova, L.; Kemper, A.: Resource pool management: reactive versus proactive or let’s be friend, Computer networks 53, 2905-2922 (2009)
[24] L. Grit, D. Irwin, V. Marupadi, P. Shivam, A. Yumerefendi, J. Chase, J. Albrecht, Harnessing virtual machine resource control for job management, in: Proc. of the 1st Workshop on System-level Virtualization for High Performance Computing, November 2007.
[25] J. Gueyoung, K. Joshi, M. Hiltunen, Performance aware regeneration in virtualized multitier applications, in: Proc. of Proactive Failure Avoidance Recovery and Maintenance, PFARM, June 2009.
[26] Gupta, D.; Cherkasova, L.; Vahdat, A.: Comparison of the three CPU schedulers in xen, ACM SIGMETRICS performance evaluation review (PER) 35, No. 2, 42-51 (2007)
[27] D. Gupta, R. Gardner, L. Cherkasova, XenMon: QoS monitoring and performance profiling tool, Technical Report HPL-2005-187, Hewlett-Packard Labs, 2005.
[28] D. Irwin, J. Chase, L. Grit, A. Yumerefendi, D. Becker, K. Yocum, Sharing networked resources with brokered leases, in: Proc. of the USENIX Technical Conference, June 2006.
[29] S.T. Jones, A.C. Arpaci-Dusseau, R.H. Arpaci-Dusseau, Antfarm: tracking processes in a virtual machine environment, in: Proc. of the USENIX Annual Technical Conf., June 2006.
[30] S.T. Jones, A.C. Arpaci-Dusseau, R.H. Arpaci-Dusseau, Geiger: monitoring the buffer cache in a virtual machine environment, in: Proc. of Architectural Support for Programming Languages and Operating Systems, October 2006.
[31] A. Karve, T. Kimbrel, G. Pacifici, M. Spreitzer, M. Steinder, M. Sviridenko, A. Tantawi, Dynamic placement for clustered web applications, in: Proceedings of the 15th International Conference on the World Wide Web, 2006, pp. 595–604.
[32] Kou, L. T.; Markowsky, G.: Multidimensional bin packing algorithms, IBM journal of research and development 21, No. 5, 443-448 (1977) · Zbl 0361.68060 · doi:10.1147/rd.215.0443
[33] Kusic, D.; Kephart, J.; Hanson, J.; Kandasamy, N.; Jiang, G.: Power and performance management of virtualized computing environments via lookahead control, Cluster computing 12, No. 1, 1-15 (2009)
[34] Legrand, A.; Su, A.; Vivien, F.: Minimizing the stretch when scheduling flows of divisible requests, Journal of scheduling 11, No. 5, 381-404 (2008) · Zbl 1168.90455 · doi:10.1007/s10951-008-0078-4
[35] W. Leinberger, G. Karypis, V. Kumar, Multi-capacity bin packing algorithms with applications to job scheduling under multiple constraints, in: Proc. of the Intl. Conf. on Parallel Processing, 1999, pp. 404–412.
[36] Marchal, L.; Yang, Y.; Casanova, H.; Robert, Y.: Steady-state scheduling of multiple divisible load applications on wide-area distributed computing platforms, International journal of high performance computing applications 20, No. 3, 365-381 (2006)
[37] Maruyama, K.; Chang, S. K.; Tang, D. T.: A general packing algorithm for multidimensional resource requirements, International journal of computer and information sciences 6, No. 2, 131-149 (1977)
[38] M. McNett, D. Gupta, A. Vahdat, G.M. Voelker, Usher: an extensible framework for managing clusters of virtual machines, in: Proc. of the 21st Large Installation System Administration Conference, November 2007, pp. 167–181.
[39] N. Mi, G. Casale, L. Cherkasova, E. Smirni, Burstiness in multi-tier applications: symptoms, causes, and new models, in: Proc. of the 9th ACM/IFIP/USENIX International Conference on Middleware, 2008, pp. 265–286.
[40] Microsoft virtual PC. http://www.microsoft.com/windows/products/winfamily/virtualpc/default.mspx.
[41] K. Nesbit, J. Laudon, J. Smith, Virtual private caches, in: Proc. of the Symp. on Computer Architecture, 2007.
[42] D. Nurmi, R. Wolski, C. Grzegorczyk, G. Obertelli, S. Soman, L. Youseff, D. Zagorodnov, The Eucalyptus open-source cloud-computing system, in: Proc. of Cloud Computing and its Applications, October 2008.
[43] D. Ongaro, A.L. Cox, S. Rixner, Scheduling I/O in virtual machine monitors, in: Proc. of the ACM SIGPLAN/SIGOPS Intl. Conf. on Virtual Execution Environment, VEE, March 2008.
[44] Pacifici, G.; Spreitzer, M.; Tantawi, A. N.; Youssef, A.: Performance management for cluster-based web services, Journal on selected areas in communications 23, No. 12, 2333-2343 (2005)
[45] P. Padala, K.G. Shin, X. Zhu, M. Uysal, Z. Wang, S. Singhal, A. Merchant, K. Salem, Adaptive control of virtualized resources in utility computing environments, in: Proc. of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems, 2007, pp. 289–302.
[46] L. Ramakrishnan, L. Grit, A. Iamnitchi, D. Irwin, A. Yumerefendi, J. Chase, Toward a doctrine of containment: grid hosting with adaptive resource control, in: Proc. of the International Conference for High Performance Computing Networking, Storage, and Analysis, 2006.
[47] J. Rolia, A. Andrzejak, M.F. Arlitt, Automating enterprise application placement in resource utilities, in: Proc. of the 4th IFIP/IEEE International Workshop on Distributed Systems: Operations and Management, DSOM, 2003.
[48] J. Rolia, L. Cherkasova, M. Arlitt, A. Andrzejak, A capacity management service for resource pools, in: Proc. of the 5th International Workshop on Software and Performance, 2005, pp. 229–237.
[49] N. Roy, J.S. Kinnebrew, N. Shankaran, G. Biswas, D.C. Schmidt, Toward effective multi-capacity resource allocation in distributed real-time and embedded systems, in: Proceedings of the 11th Symposium on Object Oriented Real-Time and Distributed Computing, 2008.
[50] P. Ruth, R. Junghwan, D. Xu, R. Kennell, S. Goasguen, Autonomic live adaptation of virtual computational environments in a multi-domain infrastructure, in: Proc. of the IEEE Intl. Conf. on Autonomic Computing, June 2006, pp. 5–14.
[51] D. Schanzenbach, H. Casanova, Accuracy and responsiveness of CPU sharing using Xen’s cap values, Technical Report ICS2008-05-01, Computer and Information Sciences Dept., University of Hawai’i at Mānoa. Available at: http://www.ics.hawaii.edu/research/tech-reports/ICS2008-05-01.pdf/view (May 2008).
[52] K. Shen, H. Tang, T. Yang, L. Chu, Integrated resource management for cluster-based internet services, in: Proc. of the 5th Symposium on Operating Systems Design and Implementation, December 2002.
[53] P. Shivam, S. Babu, J. Chase, Active and accelerated learning of cost models for optimizing scientific applications, in: Proc. of the International Conference on Very Large Data Bases, VLDB, 2006.
[54] Y. Song, H. Wang, Y. Li, B. Feng, Y. Sun, Multi-tiered on-demand resource scheduling for VM-based data center, in: Proc. of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, 2009, pp. 148–155.
[55] C. Stewart, K. Shen, Performance modeling and system management for multi-component online services, in: Proc. of the 2nd Symposium on Networked Systems Design & Implementation, 2005, pp. 71–84.
[56] M. Stillwell, D. Schanzenbach, F. Vivien, H. Casanova, Resource allocation using virtual clusters, Technical Report ICS2008-09-01, Information and Computer Sciences Dept., University of Hawai’i at Mānoa, September 2008. · Zbl 1233.68087
[57] M. Stillwell, D. Schanzenbach, F. Vivien, H. Casanova, Resource allocation using virtual clusters, in: Proc. of the 9th IEEE Symposium on Cluster Computing and the Grid, CCGrid’09, May 2009. · Zbl 1233.68087
[58] M. Stillwell, F. Vivien, H. Casanova, Dynamic fractional resource scheduling for HPC workloads, in: Proc. of the 24th IEEE International Parallel & Distributed Processing Symposium, IPDPS, April 2010.
[59] Urgaonkar, B.; Shenoy, P.; Chandra, A.; Goyal, P.; Wood, T.: Agile dynamic provisioning of multi-tier Internet applications, ACM transactions on autonomous and adaptive systems 3, No. 1, 1-39 (2008)
[60] Urgaonkar, B.; Shenoy, P.; Roscoe, T.: Resource overbooking and application profiling in shared hosting platforms, SIGOPS operating systems review 36, No. SI, 239-254 (2002)
[61] US Environmental Protection Agency, Report to Congress on Server and Data Center Energy Efficiency. http://repositories.cdlib.org/lbnl/LBNL-363E/ (August 2007).
[62] Virtualcenter, 2008, http://www.vmware.com/products/vi/vc.
[63] VMware. http://www.vmware.com/.
[64] R. Wang, N. Kandasamy, A distributed control framework for performance management of virtualized computing environments: some preliminary results, in: Proc. of the 1st Workshop on Automated Control for Datacenters and Clouds, 2009, pp. 7–12.
[65] A. Warfield, S. Hand, T. Harris, I. Pratt, Isolation of shared network resources in XenoServers, Technical Report PDN-02-2006, PlanetLab Project, November 2002.
[66] P. Willmann, J. Shafer, D. Carr, A. Menon, S. Rixner, A.L. Cox, W. Zwaenepoel, Concurrent direct network access for virtual machine monitors, in: Proc. of the Intl. Symp. on High-Performance Computer Architecture, February 2007.
[67] T. Wood, L. Cherkasova, K. Ozonat, P. Shenoy, Profiling and modeling resource usage of virtualized applications, in: Proceedings of the 9th International ACM/IFIP/USENIX Middleware Conference, 2008.
[68] Proc. of the 1st USENIX Workshop on I/O Virtualization, WIOV, December 2008.
[69] Citric XenServer enterprise, 2008. http://www.xensource.com/products/Pages/XenEnterprise.aspx.
[70] X. Zhu, D. Young, B.J. Watson, Z. Wang, J. Rolia, S. Singhal, B. McKee, C. Hyser, D. Gmach, R. Gardner, T. Christian, L. Cherkasova, 1000 Islands: integrated capacity and workload management for the next generation data center, in: Proceedings of the International Conference on Autonomic Computing, ICAC’08, June 2008, pp. 172–181.
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.