Distributed routing

• US 6,370,584 B1
• Filed: 09/01/1998
• Issued: 04/09/2002
• Est. Priority Date: 01/13/1998
• Status: Expired due to Term

• Current Assignee: Trustees of Boston University
• Original Assignee: Trustees of Boston University
• Inventors: Crovella, Mark E., Bestavros, Azer
• Primary Examiner(s): Rinehart, Mark H.
• Assistant Examiner(s): KANG, PAUL H
• Application Number:
  US09/144,668
• Time in Patent Office: 1,316 Days
• Field of Search: 709/218, 709/201, 709/226, 709/206, 709/203, 709/238, 709/240, 709/241, 709/243, 709/104, 709/105, 709/217, 709/223, 711/202, 714/15, 707/3
• US Class Current: 709/238
• CPC Class Codes: G06F 2209/505 Clust
• CPC Class Codes: H04L 45/24 Multipath
• 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/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 9/40 Network security protocols

Abstract

In a computer network with a plurality of client computers and a group of host computers, each host computer in the group is capable of both servicing requests from the client computers and rerouting requests to other host computers in the group. Distribution of servicing and routing functions in accordance with predetermined criteria promotes fault tolerance, transparency and load sharing within the group. The predetermined criteria can be either stateless or utilize states. In the case of an Internet Web server, distribution of Layer 4 routing obviates the need for a connection router to achieve load balancing. Distribution of Layer 3 routing reduces reliance on routing devices in general.

Claims

1. Apparatus for responding to data units that are transmitted from source computers via a computer network, comprising:

a router device for receiving said data units on behalf of a plurality of computer devices organized within a group, wherein said router device operates to distribute said data units among said plurality of computer devices, wherein each of said plurality of computer devices monitors connection establishment and termination between said source computers and each of said plurality of computer devices, and wherein each one of said plurality of computer devices is operable to receive those of said data units which are addressed to it, and wherein each one of said plurality of computer devices within said group is further operable to perform a distributed routing function to;

process a first subset of said data units addressed to it by transmitting a response to at least one of said source computers in the event that predetermined criteria are satisfied; and

reroute a second subset of said data units addressed to it to other ones of said computer devices organized within said group, without processing said second subset of said data units, to obtain a predetermined distribution of the number of data units processed by each said computer device in the event that the predetermined criteria are not satisfied, wherein said rerouting is responsive, at least in part, to said monitoring of said connection establishment and termination between said source computers and each of said plurality of computer devices.

2. The apparatus of claim 1 further including a router device that is coupled between said source computers and said group, and which is operative to disperse said data units among the computer devices in said group.

3. The apparatus of claim 1 further including a stateless rerouting function that is employed to designate one of the computer devices in said group as a destination for a rerouted data unit.

4. The apparatus of claim 3 wherein said stateless rerouting function includes a hash function which provides a destination designator from address information that is associated with the data units.

5. The apparatus of claim 4 wherein said address information includes at least one Internet Protocol address and at least one Transmission Control Protocol port address.

6. The apparatus of claim 1 further including a rerouting function that utilizes states and is employed to designate one of the computer devices in said group as a destination for a rerouted data unit.

7. The apparatus of claim 6 wherein said rerouting function provides an output based at least in part on information selected from the group consisting of load on each computer device in the group, availability of data, requested service type, requested file, requested file type, requested file size, level of Quality of Service to be extended to the particular client, and the necessity that successive requests be rerouted to the same computer device for correct session semantics.

8. The apparatus of claim 1 wherein, when a data unit that designates a first address as destination is rerouted from a first computer device that is assigned said first address in said group to a second computer device that is assigned a second address in said group, the data unit is modified to designate the second address as destination before the data unit is rerouted to the second computer if only one address is published in the network for the group.

9. The apparatus of claim 8 wherein the second computer device processes the data unit by transmitting at least one data unit to the client device in response, and the response data unit designates the first address as source.

10. The apparatus of claim 1 wherein the data unit includes a Media Access Control address, and the rerouting function rewrites the Media Access Control address.

11. The apparatus of claim 1 wherein the rerouting function tunnels the data unit to at least one other computer device in the group.

12. The apparatus of claim 1, wherein said router device comprises one of said computer devices organized within said group.

13. A method for processing data units that are transmitted from computer devices to a group of computers via a computer network, comprising:

receiving said data units at a router device on behalf of said group of computers, wherein said router device operates to distribute said data units among said group of computers;

monitoring, by a plurality of computers within said group of computers, connection establishment and termination between said computer devices and said group of computers;

receiving, responsive to said distribution by said router device, respective ones of said data units at ones of said computers in said group, such that each of said data units is received by a respective one of said computers in said group;

performing a distributed routing function in at least a plurality of said computers in said group, wherein said routing function includes

determining, by respective ones of said plurality of computers within said group, whether to process ones of said data units received at said respective ones of said plurality of computers within said group based on predetermined criteria,

processing said data units by respective ones of said plurality of computers within said group receiving respective ones of said data units if said predetermined criteria are satisfied by transmitting at least one responsive data unit to the computer device that transmitted the data unit toward the group, and

rerouting said data units by said respective ones of said plurality of computers within said group receiving said respective ones of said data units to other ones of said computers in said group, without processing said second subset of said data units, to obtain a predetermined distribution of the number of data units processed by each said computer in said group, if said predetermined criteria is not satisfied, wherein said rerouting is responsive, at least in part, to said monitoring of said connection establishment and termination between said computer devices and said group of computers.

14. The method of claim 13 further including the step of employing a hash value to designate one of the computers in the group to process the data unit.

15. The method of claim 14 further including the step of using address information from the data unit including at least one Internet Protocol address and at least one Transmission Control Protocol port address as inputs to calculate the hash value.

16. The method of claim 13 further including the step of designating one of the computers in the group to process the data unit based upon state information associated with the other computers in the group.

17. The method of claim 16 further including the step of designating the computer to process the data unit based at least in part on information selected from the group consisting of load on each computer in the group, availability of data for the response, requested service type, requested file, requested file type, requested file size, level of Quality of Service to be extended to the particular client, and the necessity that successive data units be rerouted to the same computer for correct session semantics.

18. The method of claim 13 further including the step of, when a data unit that designates a first address as destination is rerouted from a first computer device that is assigned said first address in said group to a second computer device that is assigned a second address in said group, modifying the data unit to designate the second address as destination before routing the data unit to the second computer if only one address is published in the network for the group.

19. The method of claim 18 further including the step of processing the data unit from the second computer by transmitting a responsive data unit that designates the first address as source to the computer that transmitted the data unit.

20. The method of claim 13 wherein the data unit includes a Media Access Control address, and further including the step of rewriting the Media Access Control address.

21. The method of claim 13 including the further step of tunneling the data unit to at least one other computer device in the group.

22. Apparatus for hosting an Internet Server Site by servicing requests that are transmitted from client computers via the Internet, comprising:

a router device operable to receive said requests on behalf of a cluster of host computers, wherein said router device operates to distribute said data units among ones of said cluster of host computers, wherein a plurality of host computers within said cluster of host computers is operative to perform a distributed routing function to;

monitor connection establishment and termination between said computer devices and said group of computers;

receive said requests at respective ones of said plurality of host computers within said cluster of host computers to which respective ones of said requests are directed by said router device;

service, at said respective ones of said plurality of host computers within said cluster of host computers at which respective ones of said requests are received, at least some of said requests upon satisfaction of a condition, and

for at least some requests, reroute at least some of the data units associated with said requests from said respective ones of said plurality of host computers within said cluster of host computers at which respective ones of said requests are received, without processing said data units that are rerouted, to at least one other host computer in said cluster to obtain a predetermined distribution of the number of requests serviced by each said host computer upon failure of the condition, wherein said rerouting is responsive, at least in part, to said monitoring of said connection establishment and termination between said client computers and ones of said cluster of host computers.

23. The apparatus of claim 22 wherein each host computer in said cluster is capable of servicing each of said requests.

24. The apparatus of claim 22 further including a stateless rerouting function for designating one of the host computers in the cluster as a destination for a rerouted request based solely on information that is included in the request.

25. The apparatus of claim 24 wherein said stateless rerouting function includes a hash function which provides a destination designator from address information that is associated with the request.

26. The apparatus of claim 25 wherein said address information includes at least one Internet Protocol address and at least one Transmission Control Protocol port address.

27. The apparatus of claim 22 further including a rerouting function that utilizes states and is employed to designate one of the host computers in said cluster as a destination for a rerouted request.

28. The apparatus of claim 27 wherein said rerouting function provides an output based at least in part on information selected from the group consisting of load on each host computer, availability of data, requested service type, requested file, requested file type, requested file size, level of Quality of Service to be extended to the particular client, and the necessity that successive requests be rerouted to the same host computer for correct session semantics.

29. The apparatus of claim 22 wherein, when a request that designates a first Internet Protocol address as destination is rerouted from a first host computer that is assigned said first Internet Protocol address in said cluster to a second host computer that is assigned a second Internet Protocol address in said cluster, the request is modified to designate the second Internet Protocol address as destination before the request is rerouted to the second host computer if only one address is published in the network for the server site.

30. The apparatus of claim 29 wherein the second host computer services the request by transmitting a response to the client device, and the response designates the first Internet Protocol address as source.

31. The apparatus of claim 22 wherein the request includes a Media Access Control address, an Internet Protocol address and at least one checksum, and the rerouting function rewrites the Media Access Control address and does not rewrite the Internet Protocol address and the at least one checksum.

32. The apparatus of claim 22 wherein the rerouting function tunnels the request to at least one other host computer device in the cluster.

41. The method of claim 32 including the further step of tunneling the request to at least one other host computer in the cluster.

33. A method for performing a distributed routing function while servicing requests that are transmitted from client devices to a cluster of host computers via the Internet, wherein said distributed routing function comprises:

receiving said requests at a router device on behalf of said cluster of host computers, wherein said router device operates to distribute said requests among said cluster of host computers;

monitoring, by a plurality of host computers within said cluster of host computers, connection establishment and termination between said client devices and said cluster of host computers;

receiving each of said requests at respective ones of said plurality of host computers within said cluster, such that each of said requests is received at a respective one of said plurality of host computers within said cluster to which said request is specifically directed by said router device;

determining, at said respective ones of said plurality of host computers within said cluster receiving respective ones of said requests, whether to service each of said requests based on predetermined criteria;

servicing respective ones of said requests at said respective ones of said plurality of host computers within said cluster receiving said respective ones of said requests if said predetermined criteria are satisfied; and

rerouting respective ones of said requests by said respective ones of said plurality of host computers within said cluster receiving said respective ones of said requests, without processing said requests that are rerouted, to other ones of said plurality of host computers within said cluster, to obtain a predetermined distribution of the number of data units processed by each of said plurality of host computers in said cluster, if said predetermined criteria are not satisfied, wherein said rerouting is responsive, at least in part, to said monitoring of said connection establishment and termination between said client devices and said cluster of host computers.

34. The method of claim 33 further including the step of employing a hash value to designate one of the host computers in the cluster to service the request.

35. The method of claim 34 further including the step of using address information from the request including at least one Internet Protocol address and at least one Transmission Control Protocol port address as inputs to calculate the hash value.

36. The method of claim 33 further including the step of designating one of the host computers in the cluster to service the request based upon state information associated with the other computers in the cluster.

37. The method of claim 36 further including the step of designating the host computer to service the request based at least in part on information selected from the cluster consisting of load on each host, availability of data for the response, requested service type, requested file, requested file type, requested file size, level of Quality of Service to be extended to the particular client, and the necessity that successive requests be rerouted to the same host computer for correct session semantics.

38. The method of claim 33 further including the step of, when a request that designates a first address as destination is rerouted from a first host computer that is assigned said first address in said group to a second host computer that is assigned a second address in said group, modifying the request to designate the second address as destination before rerouting the request to the second host computer if only one address is published in the network for the cluster.

39. The method of claim 38 further including the step of servicing the request from the second host computer by transmitting a response that designates the first address as source to the client device.

40. The method of claim 33 wherein the request includes a Media Access Control address, an Internet Protocol address and at least one checksum, and further including the step of rewriting the Media Access Control address without modifying the Internet Protocol address and the at least one checksum.