Finding Optimal Allocation of Constrained Cloud Capacity Using Hyperbolic Voronoi Diagrams on the Sphere

Shanthi Shanmugam, Caroline Shouraboura

Forest Ridge School, Seattle, USA.
University of California, Berkeley, Berkeley, USA.

DOI: 10.4236/iim.2012.425035                

Abstract

We consider a network of computer data centers on the earth surface delivering computing as a service to a big number of users. The problem is to assign users to data centers to minimize the total communication distance between compu-ting resources and their users in the face of capacity constrained datacenters. In this paper, we extend the classical pla-nar Voronoi Diagram to a hyperbolic Voronoi Diagram on the sphere. We show that a solution to the distance minimi-zation problem under capacity constraints is given by a hyperbolic spherical Voronoi Diagram of data centers. We also present numerical algorithms, computer implementation and results of simulations illustrating our solution. We note applicability of our solution to other important assignment problems, including the assignment of population to regional trauma centers, location of airbases, the distribution of the telecommunication centers for mobile telephones in global telephone companies, and others.

Keywords

Cloud Computing; Voronoi Diagram; Voronoi Diagram on the Sphere

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. Gilbert and N. Lynch, “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services,” ACM SIGACT News, Vol. 33, No. 2, 2002, pp. 51-59. doi:10.1145/564585.564601
[2]	http://docs.amazonwebservices.com/AWSEC2/latest/ UserGuide/using-regions-availability-zones.html.
[3]	F. Aurenhammer, “Voronoi Diagrams—A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, Vol. 23, No. 3, 1991, pp. 345-405. doi:10.1145/116873.116880
[4]	P. Bleher and C. Shouraboura, “Placement of Applications in Computing Clouds Using Voronoi Diagrams,” Journal of Internet Services and Applications, Vol. 2, No. 3, 2011, pp. 229-241. doi:10.1007/s13174-011-0037-8
[5]	M. Gavrilova, ed., “Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence (Studies in Computational Intelligence 158),” Springer, New York, 2008.
[6]	W. A. Johnson and R. F. Mehl, “Reaction Kinetics in Processes of Nucleation and Growth,” Transactions of the American Institute of Mining, Metallurgical and Petroleum Engineers, Vol. 135, 1939, 416-458.
[7]	J. M?ller, “Lectures on Random Voronoi Tessellations. Lecture Notes in Statistics,” Springer-Verlag, New York, 1994. doi:10.1007/978-1-4612-2652-9
[8]	A. Okabe, B. Boots, K. Sugihara and S. N. Chiu, “Spatial Tessellations—Concepts and Applications of Voronoi Diagrams,” 2nd edition, John Wiley, Hoboken, 2000.
[9]	K. Q. Brown, “Geometric Transforms for Fast Geometric Algorithms,” Ph.D. Dissertation, Carnegie Mellon University, Pittsburgh, 1979.
[10]	K. Q. Brown, “Voronoi Diagrams from Convex Hulls,” Information Processing Letters, Vol. 9, No. 5, 1979, pp. 223-228. doi:10.1016/0020-0190(79)90074-7
[11]	H.-S. Na, C.-N. Lee and O. Cheong, “Voronoi Diagrams on the Sphere. Computational Geometry: Theory and Applications,” 2002, pp. 183-194. doi:10.1016/S0925-7721(02)00077-9