Placement of applications in computing clouds using Voronoi diagrams
Tóm tắt
The vision of millions of users launching tens of millions of applications running on millions of globally scattered servers presents a new challenge for Cloud Providers: how to assign so many virtual applications to physical servers, while meeting latency needs, improving network utilization, and satisfying availability constraints. Today’s application placement puts too much burden on the cloud user, lacks scalability and inhibits the global reach of Public Clouds. The size, breadth, and dynamic nature of Public Clouds present a special challenge to the task of placement. Cloud Providers able to provide rapid decisions and frequent optimizations for placement will have significant competitive advantage. Not only will they provide the best customer experience, their costs will be lower as they make more efficient use of their network resources. However, given the calculations required, data structures and the algorithms used to process location-based decisions must be as globally scalable as the Public Clouds themselves. In our study, we define a novel data structure, the Virtual Cloud Model, for modeling global cloud resources. We adapt a well-known geometric device, Voronoi Diagrams, and combine it with near-real-time network latency information. We then solve the application placement problem and suggest an API for Cloud Providers to support both “low-latency” and “high-availability” applications. The algorithms are scalable, parallelizable and distributable.
Tài liệu tham khảo
Agarwal S, Dunagan J, Jain N, Saroiu S, Wolman A, Bhogan H Volley: Automated data placement for geo-distributed cloud services. In: Proceedings of 7th USENIX symposium on networked systems design and implementation (NSDI)
Aurenhammer F (1991) Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Comput Surv 23(3):345–405
Bae SW, Chwa K-Y (2004) Voronoi diagrams with a transportation network on the Euclidean plane. In: Algorithms and computation: 15th international symposium, ISAAC, Hong Kong, 2004, pp 101–124
Beaumont O et al (2006) VoroNet: a scalable object network based on Voronoi tessellations. Laboratoire de l’Informatique du Parallélisme, Lyon, France, RR2006-11
Brakke KA (1985) Statistics of random plane Voronoi tessellations. Techn Report, Department of Math Sciences, Susquehanna University, Selinsgrove
Calka P (2003) An explicit expression of the distribution of the number of sides of the typical Poisson? Voronoi Cell Adv Appl Probab 35:863–870
Clark C et al. (2005) Live migration of virtual machines. In: USENIX NSDI
Demers A, Gealy M, Greene D, Hauser C, Irish W, Larson J (1989) Epidemic algorithms for replicated database maintenance. Association of Computing Machinery, New York
Devillers O, Pion S, Teillaud M (2001) Walking in a triangulation. In: 17th annual ACM symposium on computational geometry (SCG), pp 106–114
Fortune S (1992) Voronoi diagrams and Delaunay triangulations. In: Hwang F, Du D-Z (eds) Computing in Euclidean geometry. World Scientific, Singapore, pp 193–233
Hinde AL, Miles RE (1980) Monte Carlo estimates of the distributions of the random polygons of the Voronoi tessellation with respect to a Poisson process. J Stat Comput Simul 10:205–223
Hu S-Y, Liao G-M (2004) Scalable peer-to-peer networked virtual environment. In: Proc ACM SIGCOMM workshop on NetGames, pp 129–133
Icking C et al. (2003) Java applets for the dynamic visualization of Voronoi diagrams. In: Lecture notes in computer science, pp 191–205
Jin H, Liu H, Liao X, Hu L, Li P (2009) Live migration of virtual machine based on full-system trace and replay. In: HPDC ’09 proceedings of the 18th ACM international symposium on high performance distributed computing. ACM, New York
Khanban A, Edalat A, Lieutier A et al. (2002) Computability of partial Delaunay triangulation and Voronoi diagram. In: Computability and complexity in analysis, CCA 2002, July 2002
Kozuch M, Gass R, Ryan M (2009) Tashi: Location-aware cluster management. In: International conference on autonomic computing. ACM, New York, pp 43–48
Kramer L, Barbulescu L, Smith S Understanding performance tradeoffs in algorithms for solving oversubscribed scheduling. The Robotics Institute, Carnegie Mellon University
Le K, Zhang J, Meng J, Bianchini R, Nguyen T, Jaluria Y (2010) Reducing electricity cost through virtual machine placement in high performance computing clouds. Technical Report DCS-TR-680, Dept of Computer Science, Rutgers University, November 2010
Lee D, Lam SS (2008) Efficient and accurate protocols for distributed Delaunay triangulation under churn. In: Network protocols, ICNP 2008, pp 124–136
Meijering JL (1953) Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philips Res Rep 8:270–290
Meyerhenke H (2005) Constructing higher-order Voronoi diagrams in parallel. In: EWCG, pp 123–126
Møller J (1994) Lectures on random Voronoi tessellations. Springer, New York
Na H-S, Lee C-N, Cheong O (2002) Voronoi diagrams on the sphere. In: Computational geometry: theory and applications, September 2002, pp 183–194
Okabe A, Boots B, Sugihara K (1992) Spatial tessellations: concepts and applications of Voronoi diagrams. Wiley, Chichester
Oppenheimer D, Chun B, Patterson D, Snoeren A, Vahdat A (2006) Service placement in a shared wide-area platform. In: ATEC ’06 proceedings of the annual conference on USENIX ’06 annual technical conference. USENIX Association, Berkeley
Ostrobsky-Berman Y (2005) Computing transportation Voronoi diagram in optimal time. In: EWCG, pp 159–162
Ostrovsky-Berman Y (2003) Transportation Voronoi diagrams. Leibniz Center for Research in Computer Science, Jerusalem
Sapuntzakis C, Chandra R, Pfaff B, Chow J, Lam S, Rosenblum M (2002) Optimizing the migration of virtual computers. In: Proceedings of the 5th symposium on operating systems design and implementation (OSDI’02), December 8–11, 2002, Boston, MA, USA
Sedgewick R (1990) Algorithms in C. Addison-Wesley, Reading
Setzer T, Stage A (2009) Network-aware migration control and scheduling of differentiated virtual machine workloads. In: CLOUD ’09 proceedings of the 2009 ICSE workshop on software engineering challenges of cloud computing. IEEE Computer Society, Washington
Shamos M, Hoey D (1975) Closest-point problems. In: Proc 16th annu IEEE sympos found comput sci, pp 151–162
Sriram I, Khajeh-Hosseini A (2010) Research agenda in cloud technologies. In: 1st ACM symposium on cloud computing, SOCC. ACM, New York
Tanemura M (2003) Statistical distributions of Poisson Voronoi cells in two and three dimensions. Forma 18(4):221–247
VoroGlide (2010) Interactive Voronoi diagrams. Cooperative systems [Online]. http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/