Method and apparatus for distributing requests among a plurality of resources

• US 20020156892A1
• Filed: 06/03/2002
• Published: 10/24/2002
• Est. Priority Date: 03/13/1998
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Leighton, Thomas F., Lewin, Daniel, Karger, David, Levine, Matthew, Panagrahy, Rina, Lehman, Eric
• Granted Patent: US 6,963,915 B2
• Time in Patent Office: Days
• US Class Current: 709/225
• 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. A method for distributing a request to one of a plurality of resources, comprising the steps of:

mapping said request to a request location in a mathematical mapping space;

mapping each of said plurality of resources to a respective at least one resource location in the mathematical mapping space;

allocating said request to one of said plurality of resources based on a mathematical relationship between the request location in the mathematical mapping space and each of the resource locations in the mathematical mapping space.

2. The method of claim 1 wherein the mathematical mapping space is a circle.

3. The method of claim 1 wherein the request is a data request and the resource is a server.

4. The method of claim 1 wherein the step of mapping each of said plurality of resources to a respective at least one resource location in the mathematical mapping space comprises hashing each of said plurality of resources to the respective resource location in the mathematical mapping space.

5. The method of claim 1 wherein the step of mapping said request to a location in a mathematical mapping space comprises hashing the request to the request location in mathematical mapping space.

6. An apparatus for distributing a request to one of a plurality of resources, comprising:

the plurality of resources;

an input receiving a resource request;

a mapper in communication with said input, said mapper mapping said request to a request location in a mathematical mapping space and mapping each of said plurality of resources to at least one resource locations in said mathematical mapping space; and

a distributor distributing said request to one of said plurality of resources in response to a mathematical relationship between the request location in the mathematical mapping space and the at least one resource location of each of the plurality of resources in the mathematical mapping space.

7. A computer-readable medium whose contents cause a computer system to distribute a request to one of a plurality of resources, the computer system executing the contents of the computer-readable medium by performing a program comprising the steps of:

mapping said request to a request location in a mathematical mapping space;

mapping each of said plurality of resources to a respective at least one location in the mathematical mapping space;

allocating said request to one of said plurality of resources based on a mathematical relationship between the request location in the mathematical mapping space and the resource location of each of the plurality of resources in the mathematical mapping space.

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

generating an virtual network of nodes in response to a data request;

randomly choosing a first node on said virtual network of nodes and generating a path from the first node to the root node on the virtual network of nodes;

mapping at least one node on the path to a respective one of the plurality of servers; and

requesting data from the one of the plurality of servers.

9. The method of claim 8 wherein the step of requesting data from the one of the plurality of servers is accomplished with a data request comprising identification of the desired data and a sequence of nodes through which the request should be directed.

10. The method of claim 9 wherein the data request also comprises a sequence of servers that should act as the nodes.

11. The method of claim 8 wherein the step of requesting the data from the server mapped to the chosen node comprises the step of transmitting a request from a client to the server.

12. The method of claim 8 wherein the step of mapping at least one node on the path to a respective one of the plurality of servers comprises calculating a hash function.

13. The method of claim 8 wherein the step of mapping at least one node on the path to a respective one of the plurality of servers comprises:

mapping a node to a node location in a mathematical mapping space;

mapping each of said plurality of servers to a respective at least one server location in the mathematical mapping space;

allocating said node to one of said plurality of servers based on a mathematical relationship between the node location in the mathematical mapping space and each of the server locations in the mathematical mapping space.

16. The method of claim 15 wherein the step of mapping a server to the next node comprises calculating a hash function.

17. The method of claim 15 wherein the first data request is substantially similar to the second data request.

18. The method of claim 15 wherein the second data request includes a sequence of nodes.

19. The method of claim 15 farther comprising:

receiving the data from the server mapped to the next node in response to the second data request;

determining the total number of times the data in the first data request has been requested; and

caching the data requested by the first data request if the count of the number of times the data in the first data request was requested exceeds a threshold.

20. The method of claim 19 further comprising the step of responding to the first request by transmitting the data.

14. An apparatus for requesting data from one of a plurality of servers, comprising:

an input receiving a data request;

a path generator in communication with the input randomly choosing a node on an virtual network and generating at least one path of nodes in response to the data request;

a mapper in communication with the path generator mapping nodes on the at least one path of nodes to one of the plurality of servers; and

an output in communication with the mapper and requesting data from the one of the plurality of servers mapped to the nodes on the at least one path of nodes.

15. A method for responding to data requests made by a client, comprising:

receiving a first data request comprising a sequence of nodes corresponding to a sequence of servers;

determining whether the data specified in the data request is not available on a selected server; and

if the data is not available, further comprising;

determining a next node from the sequence of nodes;

mapping a server to the next node; and

requesting the data by transmitting a second data request to the server mapped to the next node.

21. An apparatus for responding to data requests made by a client, comprising:

an input receiving a first data request comprising a sequence of nodes corresponding to a sequence of servers;

decision logic determining whether the data specified in the data request is available on a selected server, and if the data is not available determining a next node from the sequence of nodes;

a mapper mapping a server to the next node; and

an output requesting the data by transmitting a second data request to the server mapped to the next node.