Method and apparatus for selecting redundant routers using tracking

1. Field of the Invention

The present invention relates to the field of network management technologies. In particular, the present invention relates to the election of a master router in a redundant router protocol by tracking external events.

2. Background Information and Description of Related Art

The use of standby routers in an Internet Protocol (IP) network is known in the art. The Internet Engineering Task Force (IETF) has published a draft standard protocol for using standby routers, also referred to as redundant routers, entitled Virtual Router Redundancy Protocol , version 2-05, on Jan. 5, 2000 (VRRP).

In a typical network configuration, end-hosts that are connected to a layer-2 domain communicate with other subnets through the use of a default router. Often, the default router is statically configured as it minimizes configuration and processing overhead on the end-host and is widely supported by most Internet Protocol (IP) networks. As noted by the IETF, one of the drawback s of using a, statically configured default router is that it creates a single point of failure. Therefore, loss of the default router results in a catastrophic event, isolating all end-hosts that are unable to detect any alternate path that may be available. The use of standby routers (redundant routers) eliminates the single point of failure inherent in the static default routed environment. (VRRP, Section 1, Introduction).

Protocols for using standby routers involve the notion of a virtual router. A virtual router is an abstract object managed by a standby router protocol (SRP), and it functions as a default router for end-hosts on a network. The virtual router is defined by a Virtual Router Identifier (VRID) and a set of associated IP addresses. The virtual router may be implemented with two or more routers running the SRP. The SRP specifies an election process whereby the responsibility for forwarding packets sent to the IP address(es) associated with the virtual router is dynamically assigned to one of the SRP routers, called the master. The remaining SRP routers are referred to as backup or slave routers, and are available to assume forwarding responsibility for a virtual router should the current master fail.

Under the IETF's VRRP, the election process is based on the relative value of the priority field reported for each SRP router for a given VRID. The priority field may be an 8-bit unsigned integer field as set forth in the IETF's VRRP, Section 5.3.4. Higher values equal higher priority. The value of the priority field reported for the SRP router that owns the IP address(es) for a given VRID, i.e. the master SRP router, is always the highest priority value of 255. The value of the priority field reported for the backup SRP router(s) is a value from 1 to 254. The default priority field for a backup SRP router is 100. A value of zero in the priority field has a special meaning, and indicates that the SRP router has stopped participating in the SRP. This triggers the SRP backup router(s) to quickly elect one of among them transition to master status without waiting for the current master to timeout.

The determination of a priority for a particular SRP router may vary widely depending on the election process of the particular protocol in use and the policies set by network management. The efficiency of the transition from backup to master will depend in large part on how those priorities are determined. It would be desirable, therefore, to devise an SRP election process that takes into account a large number of operation scenarios such that the transition is as smooth and efficient as possible, and avoids erroneously electing a master SRP router that cannot communicate with the outside world.

According to one aspect of the invention, a method and system is provided for electing an SRP master router from one or more routers participating in the SRP protocol using tracking parameters. The master SRP router functions as the default router for the subnet associated with the virtual router. The remaining SRP routers function as backup SRP routers, also referred to as slave routers, standing by to become the master SRP router if the current master is not re-elected. The tracking parameters include a ping tracking parameter that represents the metric of the active routes that can accept packets from an SRP router, an environmental parameter that represents the metric of the state of the operational environment of the SRP router, and a diagnostic parameter that represents the metric of the state of the functionality of SRP router.

According to another aspect of the invention, the SRP routers trade packet data at certain time intervals containing the priority field values that reflect their current tracking parameters in the form of protocol data units (PDUs). The SRP election process uses the priority field values to arbitrate the election of the master SRP router for a given virtual router ID (VRID). If, as a result of the tracking parameters, the election process determines that the backup (slave) has a higher priority than the master, then the master SRP router relinquishes control of its master status, and the backup(slave) with the highest priority is elected to be the next master SRP router.

According to another aspect of the invention, the priority field values reflecting the tracking parameters may be pre-determined by the network administrator. The priority field values reflecting the environmental and diagnostic tracking parameters may be set to an automatic fail-over level when necessary (i.e. a forced takeover by the standby router). Similarly, the priority field values reflecting the ping tracking parameters may be set to force the router to standby status when ping tracking of certain critical addresses fails.

In accordance with other aspects of the present invention, apparatus are provided for carrying out the above and other methods.

The present invention will be described by way of exemplary embodiments, but not limitations, illustrated in the accompanying drawings in which like references denote similar elements, and in which:

FIG. 1 illustrates a block diagram of a typical prior art network configuration using the virtual redundant router protocol (VRRP); and

FIG. 2 illustrates a block diagram of a network configuration using a standby router protocol in accordance with one embodiment of the present invention;

FIG. 3 illustrates a flow diagram of the election of a master SRP router for a virtual router in accordance with one embodiment the present invention; and

FIG. 4 illustrates a flow diagram of the SRP tracking of an SRP router in preparation for the election of the master SRP router as shown in FIG. 3 , and in accordance with one embodiment the present invention.

In the following description various aspects of the present invention, a method for selecting redundant routers using tracking, will be described. Specific details will be set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced with only some or all of the described aspects of the present invention, and with or without some or all of the specific details. In some instances, well known architectures, steps, and techniques have not been shown to avoid unnecessarily obscuring the present invention. For example, specific details are not provided as to whether the method and system is implemented in a router, server or gateway, as a software routine, hardware circuit, firmware, or a combination thereof.

Various operations will be described as multiple discrete steps performed in turn in a manner that is most helpful in understanding the present invention. However, the order of description should not be construed as to imply that these operations are necessarily performed in the order they are presented, or even order dependent. Lastly, repeated usage of the phrase “in one embodiment” does not necessarily refer to the same embodiment, although it may.

Referring now to FIG. 1 , wherein a block diagram illustrating a typical prior art network configuration using the IETF virtual redundant router protocol (VRRP) is shown. As illustrated, routers R 1 110 and R 2 120 are defined as VRRP routers connected to a local area network (LAN) 115 supporting virtual routers VRID 1 and VRID 2 . VRID 1 is defined as the virtual router associated with IP subnet 10.2.3.1, and VRD 2 is defined as the virtual router associated with IP subnet 10.2.4.1. Hosts H 1 130 and H 2 135 have configured a static default route throu R 1 's IP address 10.2.3.1, and hosts H 3 140 and H 4 145 have configured a static default route through R 2 's IP address 10.2.4.1. R 1 110 is the initial master for VRID 1 and R 2 120 is the backup (slave) router. Likewise, R 2 is the initial master for VRID 2 and R 1 is the backup (slave) router. Thus, if R 1 110 fails such as when the R 1 ISP 150 connection to the Internet 155 goes down, then R 2 120 is elected the new master VRRP router for VRID 1 , and publishes the new subnet route 10.2.4.1 for hosts H 1 130 and H 2 135 . Likewise, if R 2 120 fails, then R 1 110 is elected the new master VRRP router for VRID 2 , and publishes the new subnet route 10.2.3.1 for hosts H 3 140 and H 4 145 . The election of the new master VRRP router is performed in accordance with the election process defined for the IETF VRRP protocol.

Referring now to FIG. 2 , wherein a block diagram illustrating a network configuration 200 using a standby router protocol (SRP) in accordance with one embodiment of the present invention. As illustrated, routers R 3 210 and R 4 120 are defined as SRP routers connected to a local area network (LAN) 115 supporting virtual routers VRID 1 and VRID 2 . As before, VRID 1 is defined as the virtual router associated with IP subnet 10.2.3, and VRD 2 is defined as the virtual router associated with IP subnet 10.2.4. Each IP subnet may be configured as a virtual LAN (VLAN). Hosts H 1 130 and H 2 135 have configured a static default route through R 3 's IP address 10.2.3.1, and hosts H 3 140 and H 4 145 have configured a static default route through R 4 's IP address 10.2.4.1. R 2 210 is the initial master for VRID 1 and R 4 220 is the backup (slave) router. Likewise, R 4 220 is the initial master for VRID 2 and R 3 210 is the backup (slave) router.

Each router R 3 210 and R 4 220 , is configured to run an SRP protocol in accordance with one embodiment of the invention. Although only two SRP routers are shown in the illustrated embodiment, additional SRP routers may be added to increase the level of redundancy. In one embodiment each router is a switch that is physically connected to the same layer-2 domain and the rest of the network 115 . Each switch is configured with the same subnet information of the VLANs they are sharing so that either switch is capable of functioning as the default router for a given VLAN. Initially, one switch will be elected as the master SRP router, and the other will be the backup (slave). For example, with reference to the illustrated embodiment, R 3 210 is the master SRP router for VRID 1 . As the master, R 3 functions as the default router for the subnet 10.2.3 associated with hosts H 1 and H 2 . It will handle all the data traffic for hosts H 1 and H 2 and export the subnet route for H 1 and H 2 to other routers. Likewise, R 4 220 is the master SRP router for VRID 2 . Thus, both VRID 1 and VRID 2 are each served by a master and a backup (slave).

In operation, R 3 210 and R 4 220 periodically trade SRP protocol data units (PDUs) 225 with each other at specified time intervals. The SRP protocol data units contain the priority values that reflect the SRP tracking parameters obtained for the routers R 3 and R 4 . The tracking parameters contain information about There are three types of SRP tracking parameters.

The first tracking parameter is a ping tracking parameter. The ping tracking parameter is obtained by pinging the IP addresses of interest as listed in the router's SRP Configuration table. The network administrator is responsible for configuring the IP addresses of interest, which are typically those addresses critical to the network, e.g. the SRP router's default gateway, if any, or a critical File Server that the hosts are likely to access frequently, etc. The value of the ping tracking parameter is the number of successful pings of IP addresses that respond that they are alive and capable of receiving traffic from the SRP router.

The second tracking parameter is the environmental tracking parameter. The environmental tracking parameter is obtained by inspecting the operational environment of the SRP router. The operational environment is quantified in measurements or statuses of environmental characteristics that are outside of the control of the SRP router, and includes but is not limited to the operating temperature of the SRP router as well as the status and temperature of its power supply and the fan.

The third tracking parameter is the diagnostics tracking parameter. The diagnostics tracking parameter is obtained by inspecting the diagnostic data provided by the SRP router about the router hardware and connectivity. The diagnostic data is quantified in measurements or statuses of router characteristics that are within the control of the SRP router, and includes but is not limited to the operability status of the router circuitry and channels as well as the packet-level connectivity to the physical layer backplane network.

If the SRP tracking parameters for either of the SRP routers R 3 210 and R 4 220 indicate that a new master must be elected, than an election process compares the relative priority values of the SRP routers R 3 210 and R 4 220 and elects the one with the highest priority value. For example, in one embodiment, if R 4 's priority values are decreased due to ping tracking parameter values which indicate that certain active routes on R 4 220 are not responding to the ping, then R 3 210 may have higher priority values than R 4 220 and may be elected to assume the master router function for virtual router VRID 2 serving subnet 10.2.4. An election process is performed, and upon election of R 3 210 to be the master router for virtual router VRID 2 , R 3 210 sends the new subnet route for hosts H 3 140 and H 4 145 to other routers on the network, and commences default routing. In this scenario, R 3 210 will be the master for both virtual routers VRID 1 and VRID 2 .

Referring now to FIGS. 3 a – 3 b , wherein a flow diagram of the election 300 of a master SRP router for a virtual router in accordance with one embodiment the present invention is illustrated. As shown, in block 305 , the SRP tracking is performed periodically at certain time intervals to obtain tracking parameters for the SRP routers participating in the SRP protocol for a given virtual router, e.g. VRID 1 .

As illustrated in further detail in FIG. 3 b , at process block 310 , each SRP router pings its active routes to determine if they are alive, i.e. capable of receiving data packets. The number of live routes is quantified in a metric that reflects a priority field value. In one embodiment, the network manager may designate certain critical routes that must be alive in order for the SRP router to be a master. If those routes are not alive at block 315 , then the priority field value for this SRP router may be decreased at block 322 to a special value to prevent this SRP router from being elected master. If the routes are alive, then the priority field value for this SRP router may be increased at block 320 .

At block 325 the SRP tracking process continues by checking the SRP router's operating environment, such as the temperature of the router hardware and status of the power supply. If the operating environment is determined to be unacceptable at block 330 , then the priority field value may be decreased or even set to a special value at block 337 to prevent this SRP router from being elected master. If the operating environment is satisfactory, then the priority field value for this SRP router may be increased at block 335 .

At block 340 the SRP tracking process continues by checking the SRP router's diagnostics, such as the connectivity to the physical layer, or the reliability of the router's circuitry. If the diagnostics are determined to be unacceptable at block 345 , then the priority field value may be decreased or even set to a special value at block 352 to prevent this SRP router from being elected master. If the diagnostics are determined to be satisfactory, then the priority field value for this SRP router may be increased at block 350 . Finally, the SRP routers generate packets in the form of protocol data units (PDUs) that contain the priority field values set in the preceding blocks. At block 355 , the SRP router trades its PDUs with those of other SRP routers participating in the SRP protocol for a given virtual router ID.

In one embodiment, the special value of the priority field that prevents an SRP router from being elected to the master SRP router is 255, while in an alternative embodiment it is zero. Moreover, the designation of certain priority field values for certain tracking parameters may be set by the network administrator to conform to network policy. Thus, for example, certain SRP routers may be taken out of service when one or more of the tracking parameters meet pre-defined criteria set by the network administrator, such as the minimum number of live routes before allowing an SRP router to be elected the master router. It should be further noted that in one embodiment a network administrator may configure the order of obtaining the SRP tracking parameters differently for each SRP router, or the order may be pre-defined to occur in a different sequence than described above without departing from the spirit of the invention.

Returning now to FIG. 3 a , at block 360 , the election process is performed by comparing the relative values of the tracked priority fields for each of the SRP routers for a given VRID. If any of the slave SRP routers' tracked priority field values are greater than or equal to the current master SRP router's tracked priority field value, then an election 365 is triggered to determine which of the slave/backup routers participating in the virtual network has the highest priority. At block 370 , the newly elected master SRP router sends its subnet route to all of the other routers, and commences default routing for the subnet once the old master SRP router times out.

Accordingly, a novel method and system is described for a standby router protocol that provides an improved master election process using tracking. From the foregoing description, those skilled in the art will recognize that many other variations of the present invention are possible. In particular, while the present invention has been described as being implemented in a network comprising one or more routers R 3 210 and R 4 220 , some of the logic may be distributed in other components of a network or internetwork application.

For example, embodiments of the invention may be represented as a software product stored on a machine-accessible medium (also referred to as a machine or computer-readable medium, or a processor-readable medium). The machine-accessible medium may be any type of magnetic, optical, or electrical storage medium including a diskette, CD-ROM, memory device (volatile or non-volatile), or similar storage mechanism. The machine-accessible medium may contain various sets of instructions, code sequences, configuration information, or other data. As an example, the procedures described herein for an election process 300 and the performance of SRP tracking 305 in an SRP protocol can be stored on the machine-accessible medium. Those of ordinary skill in the art will appreciate that other instructions and operations necessary to implement the described invention may also be stored on the machine-accessible medium.

Thus, the present invention is not limited by the details described. Instead, the present invention can be practiced with modifications and alterations within the spirit and scope of the appended claims.