METHOD AND APPARATUS FOR DISTRIBUTING REQUESTS AMONG A PLURALITY OF RESOURCES

• US 20090248874A1
• Filed: 01/16/2009
• Published: 10/01/2009
• Est. Priority Date: 03/13/1998
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Lewin, Daniel, Leighton, F. Thomson, Karger, David, Levine, Matthew, Panagrahy, Rina, Lehman, Eric
• Granted Patent: US 8,103,767 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-20. -20. (canceled)

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.