Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1999-03-08
2002-05-28
Maung, Zarni (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S245000, C709S200000, C370S401000
Reexamination Certificate
active
06397260
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
Not Applicable
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
The present invention is related to the field of data communications networks, and in particular to routers in data communications networks that are responsible for forwarding data messages along routing paths from source to destination network nodes.
As the use of computer networks has expanded, there has been an increased need for dependability in network operation. One way in which increased dependability has been achieved is through redundancy. Thus for example it is known to provide one or more backup routers whose function is to take the place of a primary router if it should fail. While such redundancy is desirable from the viewpoint of network dependability, it can also lead to reduced efficiency if not intelligently exploited. Where previously one or more primary routers were employed, a larger number of routers are used in order to provide the desired backup capability. As a general matter, it is not desirable for an expensive network device such as a router to be idle for extended periods, because network operating costs are increased. Thus it is a goal of network operators to find efficient ways of introducing redundancy, so as to increase network dependability without unduly harming operating efficiency.
One way in which greater efficiency has been achieved is to implement load sharing, a technique which forces routing traffic to be distributed among a number of routers. Load sharing between routers has been known. For example, in the routing protocol OSPF routing choices depend in part on the loading at candidate next hop routers. However, OSPF is a complicated protocol that is not suitable for use by hosts or end-stations.
One way in which load sharing has been achieved in the Internet is through the configuring of so-called “default routers”. A default router is a router to which a source node may send messages intended for a destination that is not directly reachable by the source. For example, the intended destination may be a node on a different subnetwork from the subnetwork on which the source node resides. The source node sends the message to the router at the default router address, and the router in turn forwards the packet toward the destination node using known techniques. Load sharing is achieved by attaching two or more routers to the network, and configuring different source nodes on a network with different default router addresses. In such a case each router handles only the portion of the overall forwarding workload that is generated by the source nodes configured with that router's address as the default router address.
The load-sharing scheme described above is static in nature, and requires the active participation of a network manager to configure the different default router addresses. The process is time consuming and error-prone. Also, the configuration may become invalid if a router becomes unavailable, for example due to hardware malfunction. Thus the network manager must monitor the validity of the load-sharing distribution in the face of changes in router availability, and must re-configure the default routers as necessary to maintain desired operational behavior.
Recently, a protocol referred to as Virtual Router Redundancy Protocol (VRRP) has been established in order to improve the availability of network routers and reduce the demand for active network management during operation. According to VRRP, routers operate either as Master or Backup for one or more abstractly-defined Virtual Routers. The Master router handles routing traffic in the usual manner. The Backup routers monitor the operation of the Master, and when the Master fails a Backup assumes the role of Master. A given physical router normally operates as Master of an associated Virtual Router, and operates as Backup for one or more other physical routers.
While redundancy schemes like VRRP address the issue of router availability, and thus can reduce the need for active network manager participation when a router fails, they do not address the problem of load sharing. Even when using VRRP, a network manager must manually configure the network nodes in a manner that is calculated to achieve a desired sharing of the forwarding load.
It would be desirable to achieve load sharing in a network without the need to manually configure default routers for the network nodes, to provide for more efficient operation and management of data communications networks.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, a method for sharing a message forwarding load is disclosed that does not require the manual configuration of different default routers to achieve the desired distribution of forwarding traffic. The method enables source network nodes to automatically configure themselves to direct forwarding traffic to different routers, improving the ease with which networks are managed.
In the disclosed method, two or more routers on a network are configured as a load-sharing set of routers. The address space of source nodes on the network is partitioned into multiple non-overlapping subspaces, and different routers in the load-sharing set are associated with different subspaces. Each router is configured with an identifier uniquely identifying the router in the load-sharing set. During operation, source nodes on the network broadcast address request messages, each message identifying a predetermined forwarding route and containing the source address of the broadcasting node. In response to each address request message, each router determines whether the source address in the message is within the address subspace associated with the router, and if so returns the router's identifier to the source node. Each source node maintains an association between the forwarding route and the identifier returned in response to its address request message.
When a data message is to be transmitted from a source node to a destination node on another network via a router, the source node transmits the message on the network along with the identifier returned in response to the address request message broadcast by the source node. Each router responds only to those messages that contain the router's identifier. The router responds by determining a suitable next hop node for the message and forwarding the message to the next hop node. In this manner the forwarding traffic being generated by the source nodes on the network is automatically distributed among the routers in the load-sharing set, once the source address space has been partitioned.
In one embodiment the load-sharing technique is used on the Internet. The forwarding route is identified by an Internet Protocol (IP) address, and the source nodes and routers employ the Address Resolution Protocol (ARP) to exchange address request and response messages. The source addresses examined by the routers are layer-
2
addresses such as Ethernet Media Access Control (MAC) addresses, and the identifiers returned by the routers are used to form layer-
2
addresses for the routers. The technique uses standard Internet protocols to achieve load sharing in an automatic fashion.
Other aspects, features, and advantages of the present invention are disclosed in the detailed description which follows.
REFERENCES:
patent: 4760572 (1988-07-01), Tomikawa
patent: 5473599 (1995-12-01), Li et al.
patent: 5917820 (1999-06-01), Rekhter
patent: 5949788 (1999-09-01), Friedman et al.
patent: 6006090 (1999-12-01), Coleman et al.
patent: 6101616 (2000-08-01), Joubert et al.
patent: 6189042 (2001-02-01), Keller-Tuberg
patent: 6195705 (2001-02-01), Leung
patent: 6249820 (2001-06-01), Dobbins et al.
Knight et al., “Request for Comments: 2338” The Internet Society Apr., 1998.
Jeffree T., “IEEE Standards for Local and Metropolitan Area Network” Contribution to the Apr. 1996 Link Aggregation Interim Meeting, Apr. 1998.
Hiscock James Scott
Townsend William Daniel
Wils Joris Johannes Maria
3Com Corporation
Lin Wen-Tai
Maung Zarni
Weingarten Schurgin, Gagnebin & Lebovici LLP
LandOfFree
Automatic load sharing for network routers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic load sharing for network routers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic load sharing for network routers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905308