Method and Apparatus for Efficiently Managing Network Distance between Physical Computers in a Computing Cloud

• US 20120124194A1
• Filed: 11/14/2010
• Published: 05/17/2012
• Est. Priority Date: 11/14/2010
• Status: Abandoned Application

• Current Assignee: Caroline Jacqueline Shouraboura
• Original Assignee: Caroline Jacqueline Shouraboura
• Inventors: Shouraboura, Caroline Jacqueline
• Application Number:
  US12/945,875
• Publication Number:
  US 20120124194A1
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length

Abstract

The invention provides faster and more efficient placement recommendations for virtual machines within a computing cloud. By mapping cloud resources as points on a two-dimensional surface and using well known geometric algorithms based on Voronoi Diagrams and Delaunay Triangulation, the present invention takes advantage of the geometric proximity information inherent in those models to complete processing that normally requires Order N-squared computations in less than Order log(n) computations. The invention maintains weights on the edges of the Delaunay Triangulation representing dynamic changes in network performance. These weights modify the basic distance calculations to achieve optimal placement. This proximity information also enables consideration of durability constraints which require distance separation of virtual machines to assure uncorrelated failure.

Claims

1. ) A server apparatus for receiving geographic location data for a plurality of devices connected to a computer network including physical computers and network routing devices, identifiable by at least one Internet Protocol address, said sever apparatus comprising assigning means for storing the locations in in-memory tables as vertices connected by edges representing the geographic distance between the vertices.

2. ) The server apparatus of claim 1 further comprising table means including receiving latency data for single network links between said physical computers and network devices, including aggregated latency data for a plurality of network links, and assigning means for storing said latency data associated with said graph edges where the network links are approximated by the graph edges.

3. ) The server apparatus of claim 1 further comprising table means including receiving occupancy information relating to the virtual machines operating at said vertices and assignment means for storing said occupancy information with said vertices.

4. ) The server apparatus of claim 3 comprising means including identification of a plurality of vertices having favorable network latency with respect to a given target vertex using latency estimation means comprised of successive selection of optimal edges, beginning with an arbitrary candidate vertex and traversing the optimal edge to the next candidate vertex, where the optimal edge is selected by determining the angle between each edge of the candidate vertex and a vector to said given vertex, choosing the edge with the smallest angle as optimal.

5. ) The server apparatus of claim 4 wherein said latency estimation means includes a further constraint of minimum distance allowed between said candidate vertex and said target vertex.