Method and apparatus for distributing requests among a plurality of resources

• US 6,963,915 B2
• Filed: 06/03/2002
• Issued: 11/08/2005
• 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
• Primary Examiner(s): Cardone, Jason D
• Application Number:
  US10/161,449
• Publication Number:
  US 20020156892A1
• Time in Patent Office: 1,254 Days
• Field of Search: 709/226, 709/225, 718/105
• 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 requesting data from one of a plurality of servers. A 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 requesting data from one of a plurality of servers, comprising the steps of:

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

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

mapping at least one node 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.

2. The method of claim 1, further comprising before the step of generating a virtual network of nodes in response to a data request, the step of receiving the data request.

3. The method of claim 2, further comprising before the step of generating a virtual network of nodes in response to a data request, the step of receiving the data request from a network node.

4. The method of claim 3, further comprising before the step of generating a virtual network of nodes in response to a data request, the step of receiving the data request from a network node, the network node comprising a web browser.

5. The method of claim 1 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.

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

7. The method of claim 5, wherein the data request comprises a uniform resource locator (URL) request and the one of the plurality of servers comprises a web server that can respond to the URL request.

8. The method of claim 1 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 the plurality of servers to a respective at least one server location in the mathematical mapping space; and

allocating the node to one of the 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.

9. The method of claim 8, wherein the mapping space comprises a line.

10. The method of claim 8, wherein the mapping space comprises a plane.

11. The method of claim 8, wherein the mapping space comprises a multi-dimensional mapping space.

12. The method of claim 8, wherein the at least one server location comprises at least two server locations.

13. The method of claim 8, wherein the step of mapping the node further comprises:

(i) deriving a value from the node; and

(ii) determining the output of a function using the value derived from the node as an input.

14. The method of claim 8, wherein the step of mapping each of the plurality of servers further comprises:

(i) deriving a value for each of the plurality of servers; and

(ii) determining the output of a function using each derived value as an input.

15. The method of claim 1 wherein the selected first node determines at least in part, the path of nodes from the first node to the root node.

16. The method of claim 15 wherein each node on the path determines at least in part, a path of nodes from that node to the root node.

17. The method of claim 1 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.

18. The method of claim 1 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.

19. The method of claim 1, further comprising before the step of generating a virtual network of nodes in response to a data request, the step of generating the data request.

20. The method of claim 1 wherein the step of requesting data from the one of the plurality of servers comprises the step of transmitting the data request to the one of the plurality of servers.

21. The method of claim 1 wherein the step of requesting data from the one of the plurality of servers comprises the step of transmitting information describing the data to the one of the plurality of servers.

22. The method of claim 1 further comprising, after the step of requesting data from the one of the plurality of servers, storing information describing the data and the one of the plurality of servers.

23. The method of claim 1 wherein the data request comprises specification of the path of nodes and the plurality of servers mapped to the nodes on the path of nodes.

24. The method of claim 1 wherein the generating step comprises generating a virtual network of nodes structured as a tree structure.

25. The method of claim 1 wherein the generating step comprises generating a virtual network of nodes structured as a circle structure having a center node located inside the circle structure as the root node, and wherein the virtual network path comprises the selected first node on the perimeter of the circle though the next nodes along the perimeter of the circle to the root node.

26. The method of claim 1 wherein the selecting step comprises randomly choosing the first node.

27. The method of claim 1 wherein the selecting step comprises selecting the first node from a subset of a plurality of nodes determined by the identity of a client.

28. The method of claim 1 wherein the selecting step comprises selecting the first node from a subset of a plurality of nodes determined by the data requested.

29. The method of claim 1 wherein the step of mapping at least one node on the path to a respective one of the plurality of servers uses a hash function.

30. The method of claim 1 wherein the step of mapping at least one node on the path to a respective one of the plurality of servers uses consistent hashing.

31. The method of claim 1 wherein a first data request uses a first virtual network and a second data request uses a second virtual network, where the first virtual network and the second virtual network are substantially different.

32. 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 selecting a node on a 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 with an acceptable distance; 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.

33. The apparatus of claim 32, wherein the input receives the data request from a network node.

34. The apparatus of claim 33, wherein the input receives the request from a network node, the network node comprising a web browser.

35. The apparatus of claim 32, further comprising a data request generator for generating the data request.

36. The apparatus of claim 32, further comprising a transmitter for transmitting the data request to the one the plurality of servers.

37. The apparatus of claim 32, further comprising a transmitter for transmitting information describing the data to the one of the plurality of servers.

38. The apparatus of claim 32, further comprising a data store for storing the data request and the information describing the one of the plurality of servers.

39. The apparatus of claim 32, wherein the data request is a uniform resource locator (URL) and the one of the plurality of servers is a web server that can respond to a URL request.

40. The apparatus of claim 32, wherein the mapper further comprises:

(i) a value generator for deriving a value from a node on the at least one path of nodes; and

(ii) a function calculator for determining the output of a function using the value derived from the node on the at least one path of nodes as an input.

41. The apparatus of claim 40, wherein the function comprises a hash function.

42. The apparatus of claim 32, wherein the mapper further comprises:

(i) a value generator for deriving a value for each of the plurality of servers; and

(ii) a function calculator for determining the output of a function using each derived value as an input.

43. The apparatus of claim 42, wherein the function comprises a hash function.