A Study on Various Dynamic Bin Packing Algorithms for Clouds

IJCSEC Front Page

Abstract:
This paper is based on the analysis of different bin-packing algorithms used for resource allocation in Clouds. Dynamic Bin-Packing (DBP) is an alternative form of classical bin- packing in which, items may arrive and depart at random time intervals. Dynamic Bin-Packing has been used to model the resource consolidation problems in Cloud computing. There are so many algorithms, being used to find an optimal solution for DBP problems in Cloud environment such as, Harmonic algorithm, Approximation algorithms, K-binary Algorithms etc.. An optimal solution to a Bin-Packing problem uses the fewest number of bins possible. The worst case and average case behavior of various bin-packing algorithms has been analyzed and the results are compared.

Keywords: Bin-Packing, Dynamic Bin-Packing, Algorithms

References:

  1. Yusen Li., Xueyan Tang., Wentong Cai On Dynamic Bin Packing for Resource Allocation in the Cloud.
  2. E.G. Coffman Jr., M.R. Garey, D.S. Johnson, Dynamic bin packing, SIAM J. Comput. 12 (2) (1983) 227–258.
  3. E. G. Coffman, J. Csirik, G. Galambos, S. Martello, and D. Vigo. Bin packing approximation algorithms: Survey and classification. Handbook of Combinatorial Optimization (second ed.), pages 455–531, 2013.
  4. Andreas Wolke , , Boldbaatar TsendAyush , Carl Pfeiffer , Martin Bichler Dynamic resource allocation strategies in cloud data centers Volume 52, August–September 2015, Pages 83–95
  5. E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-hard Problems, pages 46–93, 2007.
  6. Ye Hu, Johnny Wong, Gabriel Iszlai and Marin Litoiu Resource Provisioning for Cloud Computing 2nd International Conference on Autonomic Computing, Seattle, 2005.
  7. Swathi Venigella, Dr. Wolfgang Bein Cloud Storage and Online Bin Packing Department of Computer Science University of Nevada, Las Vegas.2012
  8. S.Suganya, P.RajiPriyadharshini, A.Mas anam Resource Provisioning in Cloud Computing Based on Virtual Machines International Journal of Advanced Research in Computer and Communication Engineering Vol. 3, Issue 3, March 2014