Method and apparatus for distributing requests among a plurality of resources

• US 7,127,513 B2
• Filed: 04/16/2003
• Issued: 10/24/2006
• Est. Priority Date: 03/13/1998
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Panigrahy, Rina, Lewin, Daniel, Leighton, F. Thomson, Karger, David, Levine, Matthew, Lehman, Eric
• Primary Examiner(s): WINDER, PATRICE L
• Application Number:
  US10/417,427
• Publication Number:
  US 20040083289A1
• Time in Patent Office: 1,287 Days
• Field of Search: 709/225, 709/226, 709/238, 709/241, 718/105, 370/238, 370/256, 710/241, 710/243, 719/317, 719/330
• 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/101 based on network conditions
• 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 distributing a request to one 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.

Claims

1. A method for querying one of a plurality of servers, comprising the steps of:

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

choosing a first node on the network of nodes;

generating a route from the first node to a last node;

identifying one of the plurality of servers to be the final server;

determining the distance of each of the plurality of servers;

identifying a subset of the plurality of servers to be a distance less than or equal to the final server;

mapping the first node on the route to one of the subset of the plurality of servers and mapping the last node to the final server; and

querying the one of the plurality of servers mapped to the first node on the route.

2. The method of claim 1 wherein the step of querying the one of the plurality of servers comprises transmitting a query and a sequence of nodes through which the query should be directed.

3. The method of claim 2 wherein the step of querying the one of the plurality of servers further comprises transmitting a route of servers mapped to the nodes on the route from the first node to the last node.

4. The method of claim 3 wherein the step of querying the one of the plurality of servers further comprises transmitting a request from a client to the server mapped to the first node on the route.

5. The method of claim 4 wherein the mapping step comprises calculating a hash function.

6. The method of claim 5 wherein the mapping step further comprises:

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

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

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

7. The method of claim 1 wherein the identifying step comprises identifying a subset of the plurality of servers to be a distance less than or equal to the final server only if the ratio of servers to the clients is smaller than a predetermined value.

8. The method of claim 1 wherein the determining step comprises determining distance based on communications latency.

9. The method of claim 1 wherein the determining step comprises determining distance based on the number of network hops.

10. A method for distributing an information request to a server resource, comprising the steps of:

hashing the request to a request location in a circular mathematical mapping space;

hashing the resource to a location in the circular mathematical mapping space;

matching the request to the resource based on a mathematical relationship between the request location and the resource location in the mathematical mapping space; and

allocating the request to the resource.