Paper Info
Title
Brief Announcement: Towards Fault-Tolerant Bin Packing for Online Cloud Resource Allocation.
Abstract
We consider an online fault-tolerant bin packing problem that models the reliable resource allocation in cloud-based systems. In this problem, any feasible packing algorithm must satisfy an exclusion constraint and a space constraint. The exclusion constraint is generalized from the fault-tolerance requirement and the space constraint comes from the capacity planning. The target of bin packing is to minimize the number of bins used. We first derive a lower bound on the number of bins needed by any feasible packing algorithm. Then we study two heuristic algorithms mirroring and shifting. The mirroring algorithm has a low utilization of the bin capacity. Compared with the mirroring algorithm, the shifting algorithm requires fewer numbers of bins. However, in online packing, the process of opening bins by the shifting algorithm is not smooth. It turns out that even for packing a few items, the shifting algorithm needs to quickly open a large number of bins. We therefore propose a new heuristic algorithm named mixing which can gradually open new bins for incoming items. We prove that the mixing algorithm is feasible and show that it balances the number of bins used and the process of opening bins.
Year
DOI
Venue
2017
10.1145/3087556.3087596
SPAA
Keywords
Field
DocType
Fault-tolerance, Bin packing, Online algorithm
Online algorithm,Heuristic,Mathematical optimization,Bin,Heuristic (computer science),Computer science,Upper and lower bounds,Capacity planning,Resource allocation,Bin packing problem
Conference
Citations 
PageRank 
References 
0
0.34
9
Authors
2
Name
Order
Citations
PageRank
Chuanyou Li194.31
Xueyan Tang2155992.36