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.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     Priority is claimed to U.S. Provisional Patent Application Ser. No. 60/071,012, entitled METHODS FOR DISTRIBUTED PACKET REWRITING, filed Jan. 13, 1998. 
    
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     Research and development of the subject matter of this application was at least partially supported by United States government grants NSF CCR-9706685 and CCR-9501882. The United States government may have rights in this invention. 
    
    
     BACKGROUND OF THE INVENTION 
     The present invention is related to computer networks, and particularly to routing of data units in computer networks. 
     The flow of traffic in computer networks such as the World Wide Web is limited by the performance of host computers. Each host computer interacts with multiple client computers. For example, a host computer that hosts an Internet Web Site responds to requests from multiple client computers by transmitting the data that comprises the pages of the web site to the client computers. However, the number of client computers that can be contemporaneously serviced by the host computer is limited. Hence, access to the web site is limited by the performance of the host computer. 
     It is known to employ a distributed system to increase the load handling capability of a web site. The distributed system includes a “cluster” of host computers, each of which is capable of servicing requests from clients and may be assigned a distinct Internet Protocol (“IP”) address. To access a web site that is associated with a cluster of hosts on the World Wide Web, a string of text known as a “domain name” that identifies the web site is initially entered at the client computer. The domain name is employed to obtain an IP address that is associated with one of the host computers in the cluster. The IP address may be obtained from a mapping that is stored by the client computer or an intermediate network device which maintains mappings of domain names to IP addresses based on information that is obtained from a “root host computer.” The root host computer encourages distribution of the load within the cluster by advertising the different IP addresses of the hosts in the cluster to intermediate network devices in a round-robin manner. The intermediate network devices cache the mappings that are advertised by the root host to facilitate timely response. However, caching of IP addresses by clients and intermediate network devices can cause an imbalance of the load within the cluster. For example, if a gateway device caches the IP address of a particular host in the cluster, every client that obtains an IP address for the web site from that gateway device transmits requests to a single host within the cluster. This can create a serious imbalance in the case of a gateway device that handles all traffic for a particular country or region. 
     It is known to employ a connection router to balance the load in the cluster. The connection router is a device that is coupled between the clients and the cluster. The root host computer advertises the IP address of the connection router so that all clients employ the IP address of the connection router when transmitting requests to the cluster. The connection router monitors the activity of each host in the cluster and selectively distributes the requests to the hosts in a manner which tends to balance the load. However, connection routers inhibit efficiency and scaling because at least one connection router is required even if only a small number of hosts are needed, and no more than a predetermined number of hosts can be supported by a single connection router. Further, the entire cluster becomes crippled when the connection router fails. 
     BRIEF SUMMARY OF THE INVENTION 
     In accordance with the present invention, routing functions for a group of computers are distributed among the computers in the group. In the case of a cluster of host devices that host a Web Site, each host device is capable of both servicing requests from client devices and rerouting requests to other host devices in the cluster to promote load sharing. Layer  4  routing functions can be distributed to obviate the need for a connection router to achieve load balancing. Layer  3  routing functions can be distributed to reduce reliance on routers in general. 
     Distributing routing functions among each host device in the cluster facilitates scaling. Increasing the number of host devices in the cluster results in a proportional improvement in performance because each new host device adds both servicing and routing capability. Further, the size of the cluster is not constrained to a fixed upper limit. 
     Distributing routing functions among each host device in the cluster makes the cluster less susceptible to catastrophic failure. In particular, the failure of a host device results in a proportional degradation in the capacity of service that can be provided by the cluster. Further, operation of the cluster as a whole is not completely dependent upon any single device. 
     Distributing routing functions facilitates transparency. Client devices are not exposed to design internals, and cannot distinguish and target individual devices in the cluster. Efficiency is also facilitated because the capacity of the cluster to service and route requests is approximately equal to the total capacity of the constituent host devices, regardless of the number of hosts in the cluster. 
    
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING 
     The foregoing features of this invention, as well as the invention itself, may be more fully understood from the following Detailed Description of the Invention, and Drawing, of which: 
     FIG. 1 is a diagram of a distributed web site that employs distributed routing within a Local Area Network; 
     FIG. 2 is a diagram of a distributed web site that employs distributed routing across networks; and 
     FIG. 3 is a diagram of a network in which a random router is employed in conjunction with distributed routing. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     U.S. Provisional Patent Application Ser. No. 60/071,012, entitled METHODS FOR DISTRIBUTED PACKET REWRITING, filed Jan. 13, 1998 is incorporated herein by reference. 
     Referring to FIG. 1, a plurality of host devices  10 ,  12 ,  14 ,  16 ,  18  are organized into a group  20  such as a cluster. In the illustrated embodiment, the host devices are each members of a Local Area Network (“LAN”)  22 . A plurality of client devices  24 ,  26 ,  28  are coupled with the group  20  via a network  30  such as the Internet. 
     Each host device  10 ,  12 ,  14 ,  16 ,  18  in the group  20  is capable of servicing requests from the client devices  24 ,  26 ,  28 . Requests are directed from an individual client to an individual host. For example, request  32  is directed from client  26  to host  16 . The requests may include data units such as packets, frames and cells that prompt transmission of web site pages in the case of a group  20  that hosts an Internet Web Site. Each request is serviced by transmitting a response from at least one of the host devices to the client device that transmitted the request. For example, response  34  is transmitted from host  12  to client  16 . 
     Each host device  10 ,  12 ,  14 ,  16 ,  18  in the group is capable of rerouting requests to other host devices in the group to promote load sharing within the group. For example, request  32  is rerouted from host  16  to host  12 . Upon receiving a request from one of the client devices, the host device will either service the request or reroute the request to another host device in the group in accordance with predetermined criteria. 
     The predetermined criteria for determining whether to service or reroute a request may include a stateless rerouting function. In the illustrated embodiment, the stateless rerouting function computes a hash value based on source and destination Internet Protocol (“IP”) addresses and Transmission Control Protocol (“TCP”) port addresses that are associated with the request. In particular, the IP address and port number associated with the client device are used as inputs into a hash function to determine which host will service the request. The IP address/port of the client forms a unique key for each request so successive port numbers from the same client device tend to map to different hosts, thereby dispersing requests among the hosts and promoting balance of the load within the group  20 . 
     The predetermined criteria for determining whether to service or reroute a request may include a rerouting function that utilizes states. To implement the rerouting function, each host  10 ,  12 ,  14 ,  16 ,  18  tracks TCP connection establishment and termination between clients  24 ,  26 ,  28  and the group  20  by maintaining a state table that indicates which connections are being rerouted. The state table is employed to reroute requests based on conditions such as current load on each host, availability of data for the response, requested service type (e.g., FTP, HTTP), requested file, file type, file size, a level of Quality of Service (“QoS”) to be extended to the particular client, and the necessity that successive requests be rerouted to the same host for correct session semantics. A user daemon can be employed to adjust the rerouting criteria as conditions change. After recording an indication of which host is selected in the state table, the address information associated with the request is updated using a Media Access Control (“MAC”) rewriting technique. 
     To update the address information associated with the rerouted request  32  when there is only one published IP address for the group  20 , the IP address of the original destination device  16  (IP 1 ) associated with the request  32  is replaced with the IP address of the new destination device  12  (IP 2 ) before the request  32  is rerouted. When the new destination device  12  services the client  26  with response  34 , the IP new source address (IP 2 ) is replaced with the original IP source address (IP 1 ) in the data units that are transmitted in the response  34  to avoid causing confusion at the client device  26 . Further, IP and TCP checksums which depend on the destination IP addresses in the data units are adjusted to agree with IP 1 . 
     To update the address information associated with rerouted requests when the group employs more than one published IP address, both the original address (IP 1 ) and the new address (IP 2 ) are included in the data units which are transmitted between the original destination device  16  and the new destination device  12 . In the illustrated embodiment, the MAC address of the data unit is rewritten prior to transmission and the original IP addresses and checksums are not modified. However, this technique is unsuitable if both host devices are not located on the same LAN. 
     Referring to FIG. 2, the host devices may be members of a diverse group  36  such as a Virtual Local Area Network (“VLAN”), the members of which are not all on a single LAN. Each host device  38 ,  40 ,  42 ,  44 ,  46 ,  48 ,  50 ,  52  is capable of servicing requests from the client devices  54 ,  56 ,  58  and rerouting requests to other host devices in the group  36  in order to promote load sharing within the group. Upon receiving a request from one of the client devices, the host device will either service the request or reroute the request to another host device in the group in accordance with predetermined criteria. The host device to which the request is rerouted is not necessarily located on the same LAN as the host device that originally received the request. The predetermined criteria may include a stateless rerouting function as described above and a rerouting function that utilizes states. The rerouting function that utilizes states could be employed to reroute requests based on conditions such as current load on each host, distance between the client and host, availability of data for the response, a level of Quality of Service (“QoS”) to be extended to the particular client, and the necessity that successive requests be rerouted to the same host for correct session semantics. 
     IP-level rerouting is employed to update the address information associated with rerouted data units when greater than one IP address is published for the group and the hosts are located on different LANs. In the illustrated embodiment, an original data unit  60  is tunneled from host device  48  (IP 1 ) to host device  42  (IP 2 ) using IPIP encapsulation. The outer IPIP header is discarded and the inner header is interpreted when the packet arrives at device  42 . 
     In general, the host device designated by address IP 2  eventually receives and processes a data unit bearing the original destination address IP 1  whether MAC rewriting or IPIP encapsulation is employed. Therefore, each host is configured to respond to all of the possible original destination addresses (such as IP 1 ) in the group. 
     Referring to FIG. 3, distributed Layer  3  routing can be employed for transmissions between various types of computer devices in a network. In the illustrated embodiment, a group  62  of computer devices  64 ,  66 ,  68 ,  70  is coupled to a network  72  via a router device  74 . Data units are transmitted toward at least one of the computer devices in the group  62  by another computer device  76  via the network  72 . The data units may indicate group membership of the destination computer device by specifying, for example, the LAN with which the destination computer is associated. The router device  74  is operative to receive data units from the network  72  that are destined for the group  62 . The router device  74  distributes the received data units among the computer devices in the group  62  without regard to which individual computer device or devices are designated as being a destination for the data unit. In the illustrated embodiment, the router randomly transmits each received data unit to one of the computers in the group. The computer that receives the data unit from the router is operative to determine which computers are designated as destinations for the data unit, and forwards the data unit to each of the designated computers. Hence, Layer  3  routing some or all of the functions that were formerly provided by a router device are distributed among the computers in the group. 
     Having described the embodiments consistent with the present invention, other embodiments and variations consistent with the present invention will be apparent to those skilled in the art. Therefore, the invention should not be viewed as limited to the disclosed embodiments but rather should be viewed as limited only by the spirit and scope of the appended claims.