Method and apparatus for distributing requests among a plurality of resources

• US 6,553,420 B1
• Filed: 06/02/1998
• Issued: 04/22/2003
• Est. Priority Date: 03/13/1998
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Lewin, Daniel, Karger, David, Levine, Matthew, Lehman, Eric, Panigrahy, Rina, Leighton, F. Thomson
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Cardone, Jason D.
• Application Number:
  US09/088,825
• Time in Patent Office: 1,785 Days
• Field of Search: 709/226, 709/225, 709/105, 709/238, 709/241, 709/213, 709/215, 370/256, 370/238, 370/351
• 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 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. An apparatus for querying one of a plurality of servers, comprising:

an interface for receiving a query;

distance logic for determining the distance of each of the plurality of servers and identifying a subset of the plurality of servers to be an acceptable distance from the apparatus;

a router in communication with the interface for choosing a first node on a virtual network of nodes and for generating at least one route from the first node in the virtual network of nodes to another node in the virtual network of nodes in response to the query;

an allocator in communication with the router for allocating each of the nodes on the route in the virtual network to a respective one of the subset of the plurality of servers; and

an output in communication with the allocator for requesting data from the respective one of the plurality of servers mapped to the first node.

2. The apparatus of claim 1, wherein the query comprises a data request.

3. The apparatus of claim 2, wherein the query comprises a web page request and the plurality of servers each comprises a web server.

4. The apparatus of claim 3, wherein the web page request comprises a uniform resource locator (URL).

5. The apparatus of claim 2, wherein the data request comprises identification of the desired data and a sequence of nodes through which the request may be directed.

6. The apparatus of claim 2, wherein the router chooses the first node from a subset of a plurality of nodes in response to the data request.

7. The apparatus of claim 1 wherein the distance logic determines distance based on communications latency.

8. The apparatus of claim 7, wherein the communications latency comprises a time from which a previous query was made until the previous query was responded to.

9. The apparatus of claim 7, wherein the communications latency comprises an estimate based on prior communication durations.

10. The apparatus of claim 1 wherein the distance logic identifies a subset of the plurality of servers that are each a distance that is less than a predetermined distance value.

11. The apparatus of claim 10, wherein the predetermined distance value is the distance of one of the plurality of servers.

12. The apparatus of claim 1, wherein the number of nodes in the virtual network is equal to the number of the plurality of servers.

13. The apparatus of claim 12, wherein the number of nodes in the virtual network is equal to the number of servers in the subset of the plurality of servers.

14. The apparatus of claim 1, wherein the allocator uses a hash function to allocate the nodes on the route to a respective one of the subset of the plurality of servers.

15. The apparatus of claim 14, wherein the allocator uses consistent hashing to allocate the nodes on the route to a respective one of the subset of the plurality of servers.

16. The apparatus of claim 1 wherein the distance logic determines distance based on a number of network hops.

17. The apparatus of claim 1, wherein the distance is determined as a function of network topology.

18. The apparatus of claim 1, wherein the distance is determined as a function of at least one of capacity, bandwidth, throughput, load, and location.

19. The apparatus of claim 1 further comprising a transmitter for transmitting the query from a client to the one of the plurality of servers.

20. The apparatus of claim 1, wherein the router generates a virtual network of nodes structured as a tree structure.

21. The apparatus of claim 1, wherein the router generates a virtual network of nodes structured as a circle structure having a center node located inside the circle structure as a root node, and wherein the at least one virtual network route comprises the selected first node on the perimeter of the circle through the next nodes along the perimeter of the circle to the root node.

22. The apparatus of claim 1, wherein the router randomly chooses the first node.

23. The apparatus of claim 1, wherein the router chooses the first node from a subset of a plurality of nodes in response to the identity of a client.

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

(a) receiving a query;

(b) determining a distance for each of the plurality of servers;

(c) identifying a subset of the plurality of servers with an acceptable distance;

(d) generating a virtual network of nodes;

(e) choosing a first node on the virtual network;

(f) generating at least one route of nodes in the virtual network from the first node to another node in response to the query; and

(g) allocating nodes on the route in the virtual network to a respective one of the subset of the plurality of servers.

25. The method of claim 24, wherein the receiving step (a) comprises receiving a data request.

26. The method of claim 25, wherein the data request comprises a web page request, and wherein each of the plurality of servers comprises a web server.

27. The method of claim 26, wherein the web page request comprises a uniform resource locator (URL).

28. The method of claim 25, wherein the data request comprises identification of the desired data and a sequence of nodes through which the request should be directed.

29. The method of claim 24, wherein the determining step (b) further comprises determining the distance based at least in part on communications latency.

30. The method of claim 29, wherein the communications latency associated with one of the plurality of servers comprises a time period including a time from when a previous query was made by a client until the previous query was responded to by the one of the plurality of servers.

31. The method of claim 29, wherein the communications latency is derived from time determinations made during prior communication.

32. The method of claim 24, wherein the identifying step (c) comprises identifying a subset of the plurality of servers that are each a distance that is less than a predetermined distance value.

33. The method of claim 32, wherein the predetermined value is the distance of one of the plurality of servers.

34. The method of claim 32, wherein the identifying step (c) further comprises:

i. identifying a subset of the plurality of servers that are each a distance less than a predetermined distance value;

ii. determining whether the identified subset would result in an acceptable ratio of servers to clients; and

iii. repeating steps (i) and (ii) with an increased predetermined distance value if the ratio is not acceptable.

35. The method of claim 32, wherein the identifying step (c) further comprises:

i. identifying a subset of the plurality of servers that are each a distance less than a predetermined distance value;

ii. determining whether the identified subset would result in an acceptable ratio of servers to clients; and

iii. identifying a subset that includes all of the plurality of servers if the ratio is not acceptable.

36. The method of claim 24, wherein the distance is determined as a function of network topology.

37. The method of claim 36, wherein the distance is determined as a function of at least one of capacity, bandwidth, throughput, load, and location.

38. The method of claim 24, wherein the generating step (d) comprises generating a virtual network of nodes having a number of nodes equal to the number of the plurality of servers.

39. The method of claim 38, wherein the generating step (d) comprises generating a virtual network of nodes having a number of nodes equal to the number of servers in the subset of the plurality of servers.

40. The method of claim 24, wherein the receiving step (a) further comprises receiving the query from a user.

41. The method of claim 24, wherein the receiving step (a) further comprises receiving the query from a computer.

42. The method of claim 24, wherein the determining step (b) further comprises determining the distance at least in part as a function of a number of network hops.

43. The method of claim 24 further comprising the step of transmitting the query from a client to the one of the plurality of servers allocated to the first node on the virtual network of nodes.

44. The method of claim 24, wherein the generating step (d) comprises generating a virtual network of nodes structured as a tree structure.

45. The method of claim 24, wherein the generating step (d) comprises generating a virtual network of nodes structured as a circle structure having a center node located inside the circle structure as a root node, and wherein a virtual network route comprises a first node on the perimeter of the circle through next nodes along the perimeter of the circle to the root node.

46. The method of claim 24, wherein the choosing step (e) comprises randomly choosing a first node on the virtual network.

47. The method of claim 24, wherein the choosing step (e) comprises selecting a first node from a subset of a plurality of nodes determined by the identity of a client.

48. The method of claim 24, wherein the choosing step (e) comprises selecting a first node from a subset of a plurality of nodes based on the query.

49. The method of claim 24, wherein the allocating step (g) comprises randomly allocating nodes in the virtual network to the plurality of servers.

50. The method of claim 24, wherein the allocating step (g) comprises allocating nodes using consistent hashing to consistently allocate nodes on the route to a respective one of the subset of the plurality of servers.