Competitiveness of Dynamic Bin Packing for Online Cloud Server Allocation
- 9 December 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 25 (3) , 1324-1331
Abstract
Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by “pay-as-you-go” billing. The above job dispatching problem can be modeled as a variant of the dynamic bin packing (DBP) problem known as MinUsageTime DBP. In this paper, we study the competitiveness bounds of MinUsageTime DBP. We establish an improved lower bound on the competitive ratio of Any Fit family of packing algorithms, and a new upper bound of μ + 3 on the competitive ratio of the commonly used First Fit packing algorithm, where μ is the max/min job duration ratio. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of μ, and shows that First Fit packing is near optimal for MinUsageTime DBP.Keywords
Funding Information
- National Research Foundation, Prime Minister’s office, Singapore, under its IDM Futures Funding Initiative
- Singapore Ministry of Education Academic Research Fund Tier 2 (MOE2013-T2-2-067)
- NSF of China (61602266)
This publication has 21 references indexed in Scilit:
- MASTER2015
- Dynamic Bin Packing for On-Demand Cloud Resource AllocationIEEE Transactions on Parallel and Distributed Systems, 2015
- Efficient Online Strategies for Renting Servers in the Cloud2015
- Real-time scheduling to minimize machine busy timesJournal of Scheduling, 2014
- On dynamic bin packing for resource allocation in the cloud2014
- GamingAnywhereACM Transactions on Multimedia Computing, Communications, and Applications, 2014
- Scheduling Jobs With Unknown Duration in CloudsIEEE/ACM Transactions on Networking, 2013
- The Case for Energy-Proportional ComputingComputer, 2007
- Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic HelpsSIAM Journal on Computing, 1998
- Chapter 9 Sequencing and scheduling: Algorithms and complexity1993