Method and apparatus for distributing requests among a plurality of resources

• US 8,103,767 B2
• Filed: 01/16/2009
• Issued: 01/24/2012
• Est. Priority Date: 03/13/1998
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Karger, David, Lehman, Eric, Leighton, F. Thomson, Levine, Matthew, Lewin, Daniel, Panagrahy, Rina
• Primary Examiner(s): WINDER, PATRICE L
• Application Number:
  US12/355,433
• Publication Number:
  US 20090248874A1
• Time in Patent Office: 1,103 Days
• Field of Search: None
• 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 circular mapping space using a hash function. Each of the plurality of resources is mapped to a respective location or locations in the circular mapping space. The request is allocated to one of the resources based on the given request location and the resource location in the circular mapping space.

Claims

1. A computer readable medium having computer program instructions that, when executed by a computer system, cause the computer system to distribute information requests among a collection of server resources by performing a method comprising the steps of:

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

hashing an identifier associated with a server resource to at least one resource location in the circular mapping space;

associating the request to the server resource based on a given relationship between the request location and the resource location in the circular mapping space; and

allocating the request to the server resource.

2. The computer readable medium of claim 1, wherein the server resource comprises a cache server.

3. The computer readable medium of claim 1, wherein the collection of server resources is a set of cache servers.

4. The computer readable medium of claim 3, wherein the computer program instructions further cause the computer system to add a cache server to the set of cache servers, the addition of the cache server modifying at least one resource location in the circular mapping space.

5. The computer readable medium of claim 1, wherein at least one of hashing the request and hashing the identifier comprises randomly choosing a mapping function from a family of hash functions.

6. The computer readable medium of claim 1, wherein hashing the request comprises employing at least one of i) geographic information about the request or ii) information about the location of the request in a network topology.

7. The computer readable medium of claim 1, wherein hashing the identifier comprises employing at least one of i) geographic information about the server resource or ii) information about the location of the server resource in a network topology.

8. The computer readable medium of claim 1, wherein the request is associated with the server resource whose resource location is the least distance from the request location.

9. The computer readable medium of claim 1, wherein the request is associated with the server resource whose resource location is the first encountered when the circular mapping space is traversed in one of a clockwise or a counter-clockwise direction from the request location.

10. The computer readable medium of claim 1, wherein the request is associated with the server resource whose resource location is a specified number of points from the request location.

11. The computer readable medium of claim 1, wherein the identifier associated with the server resource is hashed to a plurality of resource locations in the circular mapping space.