Method and apparatus for distributing requests among a plurality of resources

• US 20060242299A1
• Filed: 11/07/2005
• Published: 10/26/2006
• Est. Priority Date: 03/13/1998
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Leighton, F. Thomas, Lewin, Daniel, Karger, David, Levine, Matthew, Panagrahy, Rina, Lehman, Eric
• Granted Patent: US 7,500,002 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The invention relates to a method and apparatus for distributing a request to one of a plurality of resources. A request is mapped to a location in mathematical mapping space. Each of the plurality of resources is mapped to a respective location or locations in the mathematical mapping space. The request is allocated to one of the resources based on a mathematical relationship between the request location and the resource location in the mathematical mapping space. An apparatus for distributing a request to one of a plurality of resources includes the plurality of resources and an input receiving a resource request. A mapper in communication with the input maps the request to a request location in a mathematical mapping space and maps each of the plurality of resources to at least one resource locations in the mathematical mapping space. A distributor distributes the request to one of the plurality of resources in response to a mathematical relationship between the locations of the request and resources in the mathematical mapping space. The invention also relates to a method and apparatus for requesting data from one of a plurality of servers. An virtual network of nodes is generated in response to a data request. A first node on the virtual network of nodes is chosen randomly, and a path generated from the first node to the root on the virtual network. At least one node on the path is mapped to a respective one of the plurality of servers and data is requested from a server. The node may be mapped to the server using the method and apparatus for distributing a request to one of a plurality of resources of the present invention.

Claims

1-7. -7. (canceled)

8. A method for requesting data from one of a plurality of servers, comprising the steps of:

generating a virtual network of servers in response to a data request;

selecting a first server to receive the data request on said virtual network of servers and generating a path of servers from the first server to a root server on the virtual network of servers, wherein the root server is the last server on the path;

mapping at least one server on the path to a respective one of the plurality of servers with an acceptable distance; and

requesting data from the one of the plurality of servers.

9-59. -59. (canceled)