Abstract
We study the problem of scheduling VMs (Virtual Machines) in a distributed server platform, motivated by cloud computing applications. The VMs arrive dynamically over time to the system, and require a certain amount of resources (e.g. memory, CPU, etc) for the duration of their service. To avoid costly preemptions, we consider non-preemptive scheduling: Each VM has to be assigned to a server which has enough residual capacity to accommodate it, and once a VM is assigned to a server, its service cannot be disrupted (preempted). Prior approaches to this problem either have high complexity, require synchronization among the servers, or yield queue sizes/delays which are excessively large. We propose a non-preemptive scheduling algorithm that resolves these issues. In general, given an approximation algorithm to Knapsack with approximation ratio r, our scheduling algorithm can provide rβ fraction of the throughput region for β < r. In the special case of a greedy approximation algorithm to Knapsack, we further show that this condition can be relaxed to β<1. The parameters β and r can be tuned to provide a trade-off between achievable throughput, delay, and computational complexity of the scheduling algorithm. Finally extensive simulation results using both synthetic and real traffic traces are presented to verify the performance of our algorithm.
- AWS Pipeline 2017. AWS Data Pipeline. (2017). https://aws.amazon.com/datapipeline/.Google Scholar
- Theophilus Benson, Aditya Akella, and David A Maltz. 2010. Network traffic characteristics of data centers in the wild. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement. ACM, 267--280. Google ScholarDigital Library
- Thomas Bonald and Davide Cuda. 2012. Rate-Optimal scheduling schemes for asynchronous Input-Queued packet switches. ACM SIGMETRICS Performance Evaluation Review 40, 3 (2012), 95--97. Google ScholarDigital Library
- Christopher Clark, Keir Fraser, Steven Hand, Jacob Gorm Hansen, Eric Jul, Christian Limpach, Ian Pratt, and Andrew Warfield. 2005. Live migration of virtual machines. In Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation-Volume 2. USENIX Association, 273--286. Google ScholarDigital Library
- Waltenegus Dargie. 2014. Estimation of the cost of VM migration. Proceedings - International Conference on Computer Communications and Networks, ICCCN (2014).Google ScholarCross Ref
- EC2 2017. Elastic Compute Cloud (EC2) Cloud Server and Hosting - AWS. (2017). https://aws.amazon.com/ec2/Google Scholar
- Deniz Ersoz, Mazin S. Yousif, and Chita R. Das. 2007. Characterizing network traffic in a cluster-based, multi-tier data center. Proceedings - International Conference on Distributed Computing Systems 1 (2007). Google ScholarDigital Library
- Expedia. 2017. http://www.expedia.com. (2017).Google Scholar
- Anja Feldmann and Ward Whitt. 1998. Fitting mixtures of exponentials to long-tail distributions to analyze network performance models. Performance Evaluation 31, 3--4 (1998), 245--279. Google ScholarDigital Library
- M R Garey and D S Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). Computers and Intractability (1979), 340. Google ScholarDigital Library
- Javad Ghaderi. 2016. Randomized algorithms for scheduling VMs in the cloud. In IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications. IEEE, 1--9.Google ScholarCross Ref
- Javad Ghaderi, Sanjay Shakkottai, and R Srikant. 2016. Scheduling Storms and Streams in the Cloud. ACM Transactions on Modeling and Performance Evaluation of Computing Systems 1, 4 (2016), 1--28. Google ScholarDigital Library
- Javad Ghaderi, Yuan Zhong, and R Srikant. 2014. Asymptotic optimality of BestFit for stochastic bin packing. ACM SIGMETRICS Performance Evaluation Review 42, 2 (2014), 64--66. Google ScholarDigital Library
- James Glanz. 2012. Power, pollution and the internet. The New York Times 22 (2012).Google Scholar
- Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. 2014. Multi-resource packing for cluster schedulers. In ACM SIGCOMM Computer Communication Review, Vol. 44. ACM, 455--466. Google ScholarDigital Library
- Joe Wenjie Jiang, Tian Lan, Sangtae Ha, Minghua Chen, and Mung Chiang. 2012. Joint VM placement and routing for data center traffic engineering. In Proceedings of IEEE INFOCOM. 2876--2880.Google ScholarCross Ref
- Wolfgang John, Kostas Pentikousis, George Agapiou, Eduardo Jacob, Mario Kind, Antonio Manzalini, Fulvio Risso, Dimitri Staessens, Rebecca Steinert, and Catalin Meirosu. 2013. Research directions in network service chaining. In Future Networks and Services (SDN4FNS), 2013 IEEE SDN for. IEEE, 1--7.Google Scholar
- Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Introduction to NP-Completeness of knapsack problems. Springer.Google Scholar
- Edward Yu-Hsien Lin. 1998. A Bibliographical Survey on Some Well-Known Non-Standard Knapsack Problems. Infor 36, 4 (1998), 274--317.Google Scholar
- Minghong Lin, Adam Wierman, Lachlan L H Andrew, and Eno Thereska. 2013. Dynamic right-sizing for powerproportional data centers. IEEE/ACM Transactions on Networking 21, 5 (2013), 1378--1391. Google ScholarDigital Library
- Siva Theja Maguluri and R Srikant. 2013. Scheduling jobs with unknown duration in clouds. In Proceedings 2013 IEEE INFOCOM. 1887--1895.Google ScholarCross Ref
- Siva Theja Maguluri and R Srikant. 2014. Scheduling jobs with unknown duration in clouds. IEEE/ACM Transactions on Networking 22, 6 (2014), 1938--1951. Google ScholarDigital Library
- Siva Theja Maguluri, R. Srikant, and Lei Ying. 2012. Stochastic models of load balancing and scheduling in cloud computing clusters. Proceedings - IEEE INFOCOM (2012), 702--710.Google ScholarCross Ref
- Marco Ajmone Marsan, Andrea Bianco, Paolo Giaccone, Emilio Leonardi, and Fabio Neri. 2002. Packet-mode scheduling in input-queued cell-based switches. IEEE/ACM Transactions on Networking (TON) 10, 5 (2002), 666--678. Google ScholarDigital Library
- Xiaoqiao Meng, Vasileios Pappas, and Li Zhang. 2010. Improving the scalability of data center networks with trafficaware virtual machine placement. In 2010 Proceedings of IEEE INFOCOM. 1--9. Google ScholarDigital Library
- Sean P Meyn and Richard L Tweedie. 1993. Stability of markovian processes II: continuous time processes and sampled chains. Advances in Applied Probability (1993), 487--517.Google Scholar
- Paul Nash. 2015. Introducing Preemptible VMs. https://cloudplatform.googleblog.com/2015/05/Introducing- Preemptible-VMs-a-new-class-of-compute-available-at-70-off-standard-pricing.html. (2015).Google Scholar
- Bernt K. Oksendal. 2003. Stochastic Differential Equations: An Introduction with Applications (Sixth ed.). Springer.Google Scholar
- Charles Reiss, Alexey Tumanov, Gregory R. Ganger, Randy H. Katz, and Michael a. Kozuch. 2012. Heterogeneity and dynamicity of clouds at scale : Google Trace Analysis. Proceedings of the Third ACM Symposium on Cloud Computing - SoCC '12 (2012), 1--13. Google ScholarDigital Library
- Charles Reiss, Alexey Tumanov, Gregory R Ganger, Randy H Katz, and Michael A Kozuch. 2012. Heterogeneity and dynamicity of clouds at scale: Google trace analysis. In Proceedings of the Third ACM Symposium on Cloud Computing. ACM, 7. Google ScholarDigital Library
- Devavrat Shah and Jinwoo Shin. 2012. Randomized scheduling algorithm for queueing networks. The Annals of Applied Probability 22, 1 (2012), 128--171.Google ScholarCross Ref
- Mark Stillwell, Frédéric Vivien, and Henri Casanova. 2012. Virtual machine resource allocation for service hosting on heterogeneous distributed platforms. In Parallel & Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International. IEEE, 786--797. Google ScholarDigital Library
- Alexander Stolyar and Yuan Zhong. 2013. Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints. arXiv preprint arXiv:1306.4991 (2013).Google Scholar
- Alexander L Stolyar. 2013. An infinite server system with general packing constraints. Operations Research 61, 5 (2013), 1200--1217.Google ScholarCross Ref
- Alexander L Stolyar and Yuan Zhong. 2013. A large-scale service system with packing constraints: Minimizing the number of occupied servers. In Proceedings of the ACM SIGMETRICS/international conference on and modeling of computer systems. ACM, 41--52. Google ScholarDigital Library
- Leandros Tassiulas and Anthony Ephremides. 1992. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. Automatic Control, IEEE Transactions on 37, 12 (1992), 1936--1948.Google ScholarCross Ref
- Vijay V Vazirani. 2013. Approximation algorithms. Springer Science & Business Media. Google ScholarDigital Library
- Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, and John Wilkes. 2015. Large-scale cluster management at Google with Borg. Proceedings of the Tenth European Conference on Computer Systems - EuroSys '15 (2015), 1--17. Google ScholarDigital Library
- John Wilkes. 2011. Google Cluster Data. https://github.com/google/cluster-data. (2011).Google Scholar
- Jing Xu and Jose AB Fortes. 2010. Multi-objective virtual machine placement in virtualized data center environments. In 2010 IEEE/ACM Int'l Conference on Green Computing and Communications (GreenCom), & Int'l Conference on Cyber, Physical and Social Computing (CPSCom). 179--188. Google ScholarDigital Library
- Yağiz Onat Yazir, Chris Matthews, Roozbeh Farahbod, Stephen Neville, Adel Guitouni, Sudhakar Ganti, and Yvonne Coady. 2010. Dynamic resource allocation in computing clouds using distributed multiple criteria decision analysis. In IEEE Conference on Cloud Computing (CLOUD). 91--98. Google ScholarDigital Library
- Shunyuan Ye, Yanming Shen, and Shivendra Panwar. 2010. An O(1) scheduling algorithm for variable-size packet switching systems. In Annual Allerton Conference on Communication, Control, and Computing. 1683 1690.Google ScholarCross Ref
Index Terms
- On Non-Preemptive VM Scheduling in the Cloud
Recommendations
On Non-Preemptive VM Scheduling in the Cloud
SIGMETRICS '18We study the problem of scheduling VMs (Virtual Machines) in a distributed server platform, motivated by cloud computing applications. The VMs arrive dynamically over time to the system, and require a certain amount of resources (e.g. memory, CPU, etc) ...
On Non-Preemptive VM Scheduling in the Cloud
SIGMETRICS '18: Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer SystemsWe study the problem of scheduling VMs (Virtual Machines) in a distributed server platform, motivated by cloud computing applications. The VMs arrive dynamically over time to the system, and require a certain amount of resources (e.g. memory, CPU, etc) ...
Modified Rate-Monotonic Algorithm for Scheduling Periodic Jobs with Deferred Deadlines
The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-...
Comments