Failsafe management of periodic communications during system upgrade for a network device

The invention is directed to techniques for failsafe management of periodic communications between network devices. A first network device, for example, establishes with a second network device a first response interval by which the first device responds to a message received from the second device. Prior to commencing a software upgrade, the first device determines whether the event requires an interval of time during which the first device cannot respond to the message within the established first response interval. Based on the determination and prior to commencing the upgrade, the first device establishes with the second device a second response interval that equals or exceeds the first response interval. Upon completion of the event, the first device establishes with the second device a third response interval. The first network device therefore may automatically adjust response intervals to accommodate upgrades that may cause unnecessary thrashing.

TECHNICAL FIELD

The invention relates to computer networks and more particularly, to managing communications between network devices within computer networks.

BACKGROUND

A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.

Certain devices, referred to as routers, maintain routing information that describes available routes through the network. Each route defines a path between two locations on the network. Upon receiving an incoming packet, the router examines information within the packet and forwards the packet in accordance with the routing information.

In order to maintain an accurate representation of a network, routers maintain control-plane peering sessions through which they exchange routing or link state information that reflects the current topology of the network. In addition, these routers typically send periodic packets to each other via the session to communicate the state of the devices. These periodic packets are sometimes referred to as “keepalives” or “hellos.” For example, a first router may send a packet to a second router every five seconds to verify that the router is still operational. The first router may require or otherwise expect the second router to respond to the packet in a certain amount of time. When a response packet is not received in the allotted time frame, the first router expecting the message may conclude a network failure has occurred, such as failure of the second router or failure of the link connecting the two routers. Consequently, the first router may update its routing information to exclude that particular link, and may issue a number of routing protocol update messages to neighboring routers indicating the topology change.

However, a number of non-failure conditions may prevent the second router from responding to the first router within the required periodic response time. Failure to respond due to these and other conditions can result in significant network thrashing and other problems. As one example, the computing resources of the second router may be consumed due to heavy network traffic loads. In other words, with the increased amount of network traffic on the Internet, for example, many conventional routers have become so busy performing other functions, such as route resolution, that the response time to periodic packets is not sufficient. Furthermore, during certain procedures, such as software upgrades or patches, the router may not be able to respond to the periodic packets while it switches from a primary to a secondary or backup routing engine. If the time during which it cannot respond exceeds the allotted time the second router will wait for a response, the first router will signal to the second that it has failed even though the failure is most likely only temporary in these circumstances.

For example, a router may undergo a system software upgrade that causes a switch from a primary routing engine to a secondary routing engine requiring a significant period of time, e.g., five seconds. This time period for the switchover may exceed an allowable response time to a periodic packet received from a peer routing device. By the time the router has switched to the backup routing engine and therefore is able to respond to the periodic packet, the neighboring router may already mistakenly interpret that the router or link has failed. Consequently, the neighboring router may update its routing information to exclude the “failed” router. Furthermore, the neighboring router may send update messages to its neighboring routers indicating the failure, causing its neighboring routers to perform route resolution in similar fashion. Shortly thereafter, the “failed” router may have performed the switch and the backup routing engine (acting as the new primary routing engine) is able to send its neighboring router a response packet indicating that it is operational while a software upgrade of the primary routing engine is performed. As a result, the neighboring router again updates its routing information to include the router and sends another update message to its neighbors, causing the neighboring routers to once again perform route resolution. The unnecessary route resolution and update messages cause the network routers to thrash, creating significant network delays.

SUMMARY

In general, the invention is directed to techniques for failsafe management of periodic communications between network devices during an upgrade for system software on one of the devices. More specifically, when establishing a peering session, a first network device initially negotiates with a second network device a first response interval by which the first network device responds to messages received from the second network device. The negotiation of the first response interval occurs in accordance with a protocol, such as the bidirectional forwarding detection (BFD) protocol. In the event a software upgrade is initiated that will cause a switchover event from a primary to a backup controller within the first network device, the first network device proactively automatically and dynamically lengthens the response interval by negotiating a second response interval to accommodate the software upgrade and avoid network thrashing. Once the switchover has occurred successfully, the backup controller of the first network device may negotiates a third response interval (e.g., a short interval the same as the initial first response interval) to resume fast detection of broken links.

For example, a first network device negotiates with a second network device in accordance with a protocol a first response interval by which the first network device need respond to a message sent by the second network device also in accordance with the protocol, such as the BFD protocol. The first network device automatically detects initiation of a software upgrade within a primary controller included within the first network device. The first network device may automatically detect the initiation by monitoring commands issued by an administrator or an automated script. Prior to commencing the software upgrade, the first network device may dynamically compute a predicted upgrade time to determine whether the predicted upgrade time exceeds or equals the first response interval.

The first network device may dynamically compute the predicted upgrade based on a number of factors. As one example, the first network device may dynamically analyze the size of the software upgrade and set the predicted upgrade time based on this size. As another example, in instances where the first network device comprises a primary and a secondary controller, e.g., respective active and backup routing engines, the first network device may estimate the time necessary for switchover to the secondary controller. The estimated switchover time may be preconfigured by an administrator or may be set based on measurements taken from previous switchovers.

Prior to commencing the software upgrade, the first network device determines whether the predicted upgrade time exceeds the first response interval, and if so, negotiates with the second network device in accordance with the protocol a second response interval such that the second response interval equals or exceeds the predicted upgrade time. After initiating the software upgrade and possibly upon completion of the switchover, the first network device negotiating with the second network device in accordance with the protocol a third response interval such that the third response interval is shorter than the second response interval. Through automatic detection of the initiation of a software upgrade and dynamic computation of prediction interval, the first network device automatically and dynamically lengthens the response interval to accommodate the software upgrade. Automatic detection frees the administrator from having to perform this function. Dynamic computation possibly allows for a tailored response to software upgrades which avoids excessive response intervals where no monitoring of the link is conducted. Thus, the techniques may more effectively monitor links during software upgrades.

In one embodiment, a method comprising negotiating with a first network device in accordance with a protocol a first response interval by which a second network device need respond to a message sent by the first network device also in accordance with the protocol and automatically detecting initiation of a software upgrade within a primary controller of the second network device. The method further comprising, prior to commencing the software upgrade, dynamically computing a predicted upgrade time with the second network device to determine whether the predicted upgrade time exceeds or equals the first response interval, and based on the determination and prior to commencing the software upgrade, negotiating with the first network device in accordance with the protocol a second response interval such that the second response interval equals or exceeds the predicted upgrade time. The method further comprising, after initiating the software upgrade, negotiating with the first network device in accordance with the protocol a third response interval such that the third response interval is shorter than the second response interval.

In another embodiment, a network device comprising a control unit that negotiates with another network device in accordance with a protocol a first response interval by which the network device need respond to a message sent by the other network device also in accordance with the protocol and a management module that (i) automatically detects initiation of a software upgrade within the network device, and (ii) prior to commencing the software upgrade, dynamically computes a predicted upgrade time to determine whether the predicted upgrade time exceeds or equals the first response interval. The control unit, based on the determination and prior to commencing the software upgrade, further negotiates with the other network device in accordance with the protocol a second response interval such that the second response interval equals or exceeds the predicted upgrade time, and after initiating the software upgrade, negotiates with the first network device in accordance with the protocol a third response interval such that the third response interval is shorter than the second response interval.

In another embodiment, the invention is directed to a computer-readable medium containing instructions. The instructions cause a programmable processor to negotiate with a first network device in accordance with a bidirectional forwarding detection (BFD) protocol a first response interval by which a second network device need respond to a message sent by the first network device also in accordance with the protocol, automatically detect initiation of a software upgrade within a controller of the second network device, and prior to commencing the software upgrade, dynamically compute a predicted upgrade time with the second network device to determine whether the predicted upgrade time exceeds or equals the first response interval. The instruction further cause the programmable processor to, based on the determination and prior to commencing the software upgrade, negotiate with the first network device in accordance with the protocol a second response interval such that the second response interval equals or exceeds the predicted upgrade time, and after initiating the software upgrade, negotiate with the first network device in accordance with the protocol a third response interval such that the third response interval is shorter than the second response interval.

In another embodiment, a network device comprises a control unit that negotiates with another network device in accordance with a protocol a first response interval by which the network device need respond to a message sent by the other network device also in accordance with the protocol, and a management module that (i) automatically detects initiation of an event processing function within the network device, wherein the event processing function comprises an event that disrupts the transfer of the message such that the second network device does not receive the message within the first response interval, and (ii) prior to commencing the software upgrade, dynamically computes a predicted upgrade time to determine whether the predicted upgrade time exceeds or equals the first response interval. The control unit of the network device further negotiates, based on the determination and prior to commencing the software upgrade, with the other network device in accordance with the protocol a second response interval such that the second response interval equals or exceeds the predicted upgrade time, and after initiating the software upgrade, negotiates with the first network device in accordance with the protocol a third response interval such that the third response interval is shorter than the second response interval.

DETAILED DESCRIPTION

FIG. 1is a block diagram illustrating an example computer network2comprising network devices4A-4C coupled by links6. Network devices4A-4C (“network devices4”) communicate data within computer network2, and may include routers, hubs, switches and any other type of network device capable of communicating in accordance with a network protocol.

Network devices4communicate in accordance with one or more control-plane protocols to maintain accurate representation of the topology of network2. For example, as routers, network devices4maintain peering sessions with each other and exchange routing information for routes or links within network2in accordance with a routing protocol. Example protocols include the Border Gateway Protocol (BGP) distance vector routing protocol and the Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS) link state routing protocols.

In addition to exchanging session messages to convey network topology information, network devices4periodically send status inquiries (e.g., send “periodic packets” or “periodic data”) to one another in order to monitor the state of the other devices. That is, by sending periodic inquiries and expecting timely responses, network devices4detect any failures in communicating data between each other, either as a result of failure of one or more of network devices4or the communication links6between them. Upon detecting such a failure, the detecting network device4updates its internal representations of the topology of network2and outputs session messages to the other network devices4to inform them of the changes.

Typically, the length of time between which network devices4transmit the periodic data or messages to one another correlates directly to the speed at which network devices4detect any failure in communications between one another and thus update their respective representation of the topology of network2to respond to the failure. For this reason, network devices4may be configured to expect a response to a periodic inquiry in a relatively short length of time, e.g., a few seconds or less.

One exemplary protocol, referred to as the bidirectional forwarding detection (BFD) protocol, is commonly used between routing devices in order for each router to closely monitor the state (e.g., health) of the other routing device. For examples, routers that exchange routing information via the OSPF or ISIS routing protocols may establish BFD session for sending and responding to status inquiries in the form of Hello packets or Echo packets, either asynchronously or when needed (e.g., as in the BFD Demand Mode). In either case, the BFD protocol provides a very short interval of time between which network devices4must respond to periodic messages, and thus may facilitate the quicker detection of failures by network devices4.

Although described herein in reference to the BFD protocol, the techniques may apply to any protocol allowing for periodic messages for inquiring as to the status of a peering device. Further, the techniques may be applicable to network devices4that use these periodic communications for media access control (MAC) layer protocols, such as the frame relay LMI, point-to-point (PPP) protocol. Moreover, the techniques further include instances where network devices4employ the BFD protocol in conjunction with any of the above protocols, as well as, protocols not contemplated herein. In these instances, network devices4may employ the BFD protocol for detecting failures and the other protocol for other routing functions, such as route resolution.

In the example ofFIG. 1, network devices4exchange periodic messages in accordance with the BFD protocol. The BFD protocol enables each of network devices4to negotiate a response interval for each BFD session. In other words, network device4A may negotiate a first BFD session with network device4B, and network devices4A,4B may agree to a 0.5 second response interval. Meanwhile, network device4A may negotiate a second BFD session with network device4C, and network devices4A,4C may agree to a 0.8 second response interval. The response interval indicates the length of time by which a first network device of an associated BFD session, e.g., network device4A, has to respond to a message sent by the second network device of the associated BFD session, e.g., network device4B, before the second network device4B determines a failure has occurred.

A response interval may also be negotiated relative to a particular network device. That is, the response interval may vary for each network device4of the BFD session. For example, the response interval for network device4A to respond to a periodic message sent by network device4B may be 0.5 seconds, while the response interval for network device4B to respond to a periodic message sent by network device4A may be 1.0 seconds. This notion of relative response intervals explains the “bidirectional” or “B” of the “BFD” protocol, as the periodic messages can be controlled in each direction.

Once the first response interval is negotiated, for example, between network devices4A,4B, network devices4A,4B respond in accordance with the BFD protocol to periodic messages sent by network device4B,4A within their respective response intervals. For exemplary purposes, the first response interval is assumed to be 0.5 seconds. While responding to these periodic messages, an administrator8(“admin8” inFIG. 1) may load a software upgrade10onto one of network devices4A,4B, e.g., network device4A inFIG. 1.

Admin8may next initiate the installation of software upgrade10to a primary controller (not shown inFIG. 1) of network device4A. Software upgrade10may comprise a software “patch,” which generally updates one or more components of an application (e.g., a dynamically link library (DLL) in the context of the Microsoft Windows™ operating system), or a software install, which completely replaces the application for an upgraded application. In conventional network devices, initiating a software upgrade similar to software upgrade10may lead to thrashing within network2, as network device4A would fail to respond to the periodic messages sent by network device4B due to the application of software upgrade10.

However, network device4A in accordance with the principles of the invention performs failsafe management of periodic communications to automatically and dynamically lengthen the response interval to accommodate the application of software upgrade10, and thereby prevent thrashing within network2. To perform failsafe management, network device4A automatically detects the initiation of software upgrade10. Network device4A may automatically detect the initiation by monitoring commands input by admin8or, if initiated by an automated script instead of admin8, by monitoring commands specified by the automated script.

Prior to commencing the software upgrade within the primary controller, network device4A next dynamically computes a predicted upgrade time to determine whether the predicted upgrade time exceeds or equals the first response interval. Network device4A may compute this predicted upgrade time in a number of ways. In one embodiment, network device4A may compute the predicted upgrade time based on the size (in bytes) of software upgrade10. In another embodiment, network device4A may include not only a primary controller but a secondary controller, and network device4A may initiate software upgrade10within the secondary controller prior to initiating software upgrade10within the primary controller. Based on the time necessary to apply software upgrade10to the secondary controller, network device4A may compute the predicted upgrade time for applying software upgrade10to the primary controller.

In yet another embodiment, network device4A may also include both the primary and secondary controllers, however, in this embodiment, network device4A may compute the predicted upgrade time based on an estimate of the amount of time required to switch control of network device4A from the primary controller to the secondary controller. Network device4A may use this estimated switchover time because the secondary controller may, upon assuming control of network device4A, respond to the messages, thereby resuming routing functionality more quickly, as network device4A does not have to wait until the application of software upgrade10to the primary controller is complete. The estimated switchover time may be configured by admin8or an automated script or be based on measurements taken from previous switchovers. In still another embodiment, network device4A may compute the predicted upgrade time based on a preconfigured value, such as a value entered by admin8. For exemplary purposes, it is assumed that network device4A computes a predicted upgrade time of 2.9 seconds.

Based on the predicted upgrade time and prior to commencing software upgrade10, network device4A negotiates with network device4B in accordance with the BFD protocol a second response interval such that the second response interval equals or exceeds the predicted upgrade time, e.g., 3.0 seconds. This second response interval may be negotiated such that the BFD session maintained between network devices4A,4B need not be torn down. In other words, network device4A may transmit a message via the already present BFD session to negotiate the second response interval. Alternatively, network device4A may tear down the existing BFD session and initiate a new BFD session during which network device4A negotiates the second response interval. Generally, network device4A employs the former alternative as it avoids tearing down the existing BFD session. Moreover, when tearing down the BFD session, link6between network devices4A,4B may not be monitored, and thus network devices4A,4B may fail to detect an error during this down time. Thus, network devices4A,4B typically avoid tearing down BFD sessions to maintain constant monitoring of links6.

After initiating software upgrade10, network device4A negotiates, in one of the above described ways, with network device4B in accordance with the BFD protocol a third response interval such that the third response interval is shorter than the second response interval, e.g., 0.9 seconds. In some embodiments, network device4A renegotiates the first response interval. In this manner, network device4A may prevent network device4B from declaring a failure to network device4C and subsequently, within 2.9 seconds, declaring to network device4C that network device4A is again operational, thereby avoiding thrashing within network2.

FIGS. 2A-2Bare block diagrams each illustrating example routers14A,14B that implement the failsafe management techniques described herein.FIG. 2Ais a block diagram illustrating an example router14A comprising two routing engines24A,24B that cooperate in order to provide failsafe management of periodic messages during a system software upgrade in accordance with the principles of the invention.FIG. 2Bis a block diagram illustrating an example router14B comprising a single routing engine25that singly provides failsafe management of periodic messages during a system software upgrade in accordance with the principles of the invention.

As shown inFIG. 2A, Router14A comprises a control unit16and one or more interface cards18(“IFCs18”) that receive and transmit the periodic messages, as well as, other data and/or messages via respective network links20,22. Control unit16further includes routing engines24A,24B (“routing engines24”) that provide an operating environment for communication protocols28. Routing engines24therefore may include one or more processors that execute software instructions stored to a computer-readable medium, such as a disk drive, optical drive, Flash memory or any other type of volatile or non-volatile memory, that cause a programmable processor, such as control unit16, to perform the failsafe management of periodic communications as described herein. Alternatively, routing engines24may comprise dedicated hardware, such as an integrated circuit, for performing the techniques described herein.

In some embodiments, one of routing engines24operates as an active routing engine or more generally a primary controller, while the other one of routing engines24operates as a backup routing engine or more generally a secondary controller. The active one of routing engines24may be responsible for forwarding the data arriving via links20to other network devices within or coupled to the network via links22. The backup one of routing engines24may be responsible for resuming the forwarding activity of the active one of routing engines24should the active one require maintenance, malfunction, or stop forwarding packets for either a short or long period of time. For ease of illustration, it is assumed below that the active one of routing engines24is routing engine24A and the backup one of routing engines24is routing engine24B.

Generally, routing engines24are responsible for maintain and updating respective routing information26. Routing engines24B may also synchronize its routing information26to that routing information26of routing engine24A so that in the event of a failure in routing engine24A, routing engine24B may quickly resume performance of routing engine24A's routing responsibilities. Thus, both of routing engines24may maintain substantially similar routing information26. A detailed description of exemplary techniques for synchronizing state information between dual control planes of a router is provided in co-pending application Ser. No. 10/678,280, filed Oct. 3, 2003, entitled “Synchronizing State Information Between Control Units,” by named inventors R. Balakrishna et al., the entire contents of which are hereby incorporated by reference as if fully set forth herein.

Each of routing engines24may further include protocols28, and again each of protocols28may be substantially similar to each other so that routing engine24B may quickly resume performance of routing engines24A's routing responsibilities. In the context of protocols28, routing engine24B typically maintains similar tables or other data structures as that maintained by routing engine24A for storing protocol state information relevant to routing engine24A's routing responsibilities. Thus, routing engines24may maintain substantially similar protocols28to one another as well as associated protocol information.

As shown inFIG. 2A, each of protocols28include an OSPF protocol28A (“OSPF28A”), an ISIS protocol28B (“ISIS28B”), a border gateway protocol28C (“BGP28C”), and a BFD protocol (“BFD28D”). As discussed above, routing engines24may employ BFD28D in conjunction with one or more other protocols, such as one or more of OSPF28A, ISIS28B, and BGP28C. Although shown as comprising multiple protocols28A-28C, only one of protocols28A-28C need be employed for routing engines24to properly manage routing information26. Thus, the invention should not be limited strictly to the exemplary embodiment shown inFIG. 2A.

As further shown inFIG. 2A, router14A also includes a command line interface30(“CLI30”) and a management module32. CLI30serves as a daemon process that listens for commands from one or more users or automated software agents. Although described herein with respect to CLI30, the techniques may allow for users to enter commands via any other type of interface, such as a user interface or a graphical user interface. Management module32may comprise a software module executing within control unit16, a hardware module included within control unit16or a combination thereof. Management module32further includes a software upgrade34, which represents a software patch or module that management module32may apply to upgrade the functionality of routing engines24. While shown inFIG. 2Aas presenting an interface for uploading software upgrade34to management module32, CLI30may give way to direct communication between a user and management module32.

Initially, a user, such as an administrator36(“admin36”), may interact with CLI30to initiate uploading system software upgrade34to management module32for installation on router14A. Admin36may perform this upload by issuing a command to CLI30, whereupon CLI30receives software upgrade34and transmits software upgrade34to management module32. Admin36may further enter a command to cause management module32to apply software upgrade34to routing engines24. Upon receiving this command, management module32may first apply software upgrade34to routing engine24B, as application of a software upgrade, such as software upgrade34, typically requires a temporary halt of all routing activity on the one of routing engines24targeted for the upgrade. Because of this temporary halt, router14A upgrades backup routing engine24B, switches routing responsibility from active routing engine24A to upgraded routing engine24B, and upgrades the now, backup routing engine24A.

Prior to this upgrade process, routing engine24A negotiates with another router in accordance with BFD30D a first response interval, e.g., 0.5 seconds. Because of this short response interval, routing engine24A may quickly identify a failure in communications with the other router, and therefore quickly update its topology of the network, such as network2ofFIG. 1, as reflected in its routing information26. However, this short first response interval may not provide adequate time to both respond to a message from the other routing engine and switch routing responsibility from routing engine24A to routing engine24B. That is, the interval required to perform the switching event may comprise a longer interval of time than the first response interval. Thus, management module32automatically detects initiation of an upgrade via, for example, a command entered by one of admin36, an automated script, or any other conceivable manner by which commands to initiate upgrade34may be entered. Next, management module32dynamically computes a predicted time to complete the upgrade so as to determine whether the interval of time to apply software upgrade34to primary routing engine24A will exceed the first response interval.

Management module32may dynamically compute the predicted upgrade time in any number of ways. As one example, management module32may compute a predicted upgrade time based on a size in bytes of the current software upgrade34to be applied. Management module32may compute the predicted upgrade time by recording upgrade times for previous software upgrades of different sizes and then determining an algebraic relationship upgrade time and size of the upgrade, e.g., by linear interpolation.

As another example, management module32may monitor the time required to apply software upgrade34to routing engine24B, and assuming upgrade34was successfully applied, management module32may set the predicted upgrade time to this monitored interval of time. As yet another example, admin36or some other user may interact with management module32to pre-program a table defining approximate lengths of time for specific activities or possibly even a table comprising formulas for computing a length of time for specific activities. If formulas are used, one such formula may allow management module32to compute the predicted upgrade time based on the file size of software upgrade34. In still other embodiments, management module32may in a sense be “hardwired” to determine that application of software upgrade34exceeds the first response interval.

Regardless of the method used to compute the predicted upgrade time, management module32compares the predicted upgrade time to the first response interval. Management module32may, however, not have direct access to the first response interval because routing engine24A may not be required to inform management module32of this information. Management module32may therefore issue an instruction or message to routing engine24requesting the first response interval from routing engine24A. Upon receiving a response to this instruction or in instances where management module32is informed of this first response interval, management module32compares the predicted upgrade time to the first response interval.

If the predicted upgrade time does not exceed the first response interval, management module32may not cause routing engine24A to negotiate a second response interval, as management module32may apply software upgrade34with enough time left over to respond to any periodic messages that routing engine24A receives. However, if the predicted upgrade time exceeds or equals the first response interval, management module32may issue an instruction or message to routing engine24A that causes routing engine24A to negotiate a second response interval such that the second response interval exceeds or equals the predicted upgrade time. Within the instruction, for example, management module32may specify the predicted upgrade time and require that routing engine24A negotiate the second upgrade interface such that it equals or exceeds the specified predicted upgrade time. After negotiating the second response interval, routing engine24A may respond to the instruction or message issued by management module32stating that the second response interval has been negotiated. Management module32, upon receiving this response, may issue another instruction or message that causes routing engine24A to switch control to routing engine24B.

As mentioned above, routing engine24B generally replicates state information recorded on routing engine24A. In particular, routing engine24B may replicate state changes to protocols28. Thus, routing engine24B, upon receiving control from routing engine24A, may resume the routing responsibilities last active under routing engine24A's control and may access its BFD28D to determine the previous or first response interval. Alternatively, management module32may instruct routing engine24B to renegotiate the first response interval. In any event, routing engine24B, now the active one of routing engines24as the switching event is complete, renegotiates the first response interval with the other router according to BFD28D. If during the second interval, the other router sent a message, either of routing engines24A or24B may respond to that message prior to renegotiating the first response interval. That is, if control has not completely transferred to routing engine24B, for example, routing engine24A may respond to the message. If control has transferred successfully between routing engines24, routing engine24B may respond.

During switchover, routing engine24B may automatically determine that either a shorter or longer response interval is required and may not renegotiate the first response interval but some other third response interval. Routing engine24B may base this determination on the state of the link, the average congestion across the link, the amount of data flowing through IFCs18, or any other data that may affect the ability of routing engine24B to respond to the periodic messages within a given response interval.

As shown inFIG. 2B, routing engine14only executes a single routing engine25within control unit16. In all other aspects, router14B is substantially similar to router14A ofFIG. 2Ain that both include substantially similar control units16, IFCs18, routing information26, protocols28, CLIs30, management modules32, and software upgrades34.

In the embodiment shown inFIG. 2B, routing engine25may negotiate the first response interval, receive indication of an event, such as software upgrade34, negotiate the second response interval, perform the system upgrade, and, upon completion of the system upgrade, negotiate the third response interval without necessarily switching to a second routing engine. Instead of switching to a second routing engine, e.g., routing engine24B, management module32may, prior to commencing upgrade34, dynamically compute a predicted upgrade time with the second network device to determine whether the predicted upgrade time exceeds or equals the first response interval determine a time. The predicted upgrade time, in this instance, however may not equal the time to switch between routing engines24, but rather equals the time to successfully apply upgrade34to routing engine25plus the time required to respond to any messages that may have queued within router14B. Furthermore, as routing engine25typically generally halts routing functionality during application of upgrade34, routing engine25may respond to any messages prior to negotiating the second interval, as it will be unable to respond to these while undergoing the upgrade.

While described herein with respect toFIG. 2B, the techniques described herein include the notion of a single routing engine25executing within control unit16. The invention therefore should not be limited strictly to router14A ofFIG. 2A. Moreover, even router14A may implement the techniques described in reference to router14B. That is, in some instances, such as when the second routing engine has failed and only single routing engine24A is operational, routine engine24A may perform the techniques as described in reference to routing engine25. Thus, the invention should further include this aspect and not be limited strictly to the separate and distinct descriptions of routers14A,14B, even though the remainder of the disclosure describes the techniques relative to a two routing engine implementation.

While described herein with respect to software upgrades, such as software upgrade10and software upgrades34, the failsafe management techniques may not be so strictly limited and may apply to any event processing function that may disrupt periodic communication, such as required by the BFD protocol, and thereby cause network thrashing. An example event processing function may include not only the software upgrade event described herein but also a loading event, whereby control unit16, for example, utilizes all of its available processing power performing complicated tasks, such as route resolution, and is unable to adequately respond to periodic messages. Management module32may determine an occurrence of this loading event by monitoring the available processing power of control unit16, and upon reaching a designated or dynamically determined level, indicate that routing engine25, for example, negotiate a second response interval to accommodate the lack of available processing power within control unit16. In this manner, the failsafe management techniques may apply to events unrelated to software upgrades so that routing engines may accommodate these other events and thereby avoid any such event that may lead to network thrashing.

FIG. 3is a diagram illustrating an exemplary control message38sent by router14A to a peer router to negotiate a particular response interval in accordance with the principles of the invention. In this example, control message38complies with the BFD protocol, such as BFD28D ofFIG. 2A, so that no changes need be implemented to the protocols executing on the receiving router. Control message38therefore may be referred to below as “BFD control message38.” BFD control message38may further be formulated as a packet and receive the moniker of “BFD control packet38.” Again, although described in reference to the BFD protocol and BFD control message38in particular, the techniques may apply equally to any protocol allowing for periodic messages and dynamic configuration of response intervals.

As shown inFIG. 3, BFD control message38comprises 6 rows of 32 bits (0-31across the top of BFD control message38inFIG. 3). BFD control message38further comprises fields40A-40K (“fields40”), where each of fields40may specify information relevant to specifying a response interval. Version field40A, for example, specifies the version number of the protocol, which may enable the receiving router to determine whether it supports BFD control message38. Diagnostic field40B specifies a coded reason for the last session state change to states of “Down” or “AdminDown.” State field40C specifies the current BFD session state as seen by the router transmitting BFD control message38. Typical, BFD session states comprises “AdminDown,” “Down,” “Init,” and “Up.” Modes field40D comprises a number of bits, where each bit specifies a particular BFD session mode. For example, one bit of modes field40D may specify whether the session requires authentication, e.g., whether the session is in “authentication mode.”

Detection timer multiplier field40E specifies a value that when multiplied by the value specified within desired minimum transfer interval40I provides the detection time for the router transmitting BFD control message38in “asynchronous mode.” Length field40F specifies the length of BFD control message38in bytes. My discriminator field40G specifies a unique, nonzero discriminator value generated by the router transmitting BFD control message38. My discriminator field40G may be used to demultiplex multiple BFD sessions between the same set of receiving and transmitting routers. Your discriminator field40H specifies the discriminator received from the corresponding router of the particular BFD session. Your discriminator field40H may specify a zero value, if the discriminator of received from the corresponding router is unknown by the transmitting router.

Desired minimum transfer interval field40I specifies the minimum interval, in microseconds, that the local system would like to use when transmitting BFD control message38and subsequent BFD control messages. Required minimum receive interval field40J specifies the minimum interval, in microseconds, between received BFD control messages that the router transmitting BFD control message38is capable of supporting. If the transmitting router sets required minimum receive interval field40J to zero, the transmitting router does not want the remote or receiving router to send any periodic BFD control messages. Required minimum echo receive interval field40K specifies the minimum interval, in microseconds, between received BFD echo messages that the transmitting router is capable of supporting. Specifying a zero to this field indicates that the transmitting router does not support the receipt of BFD echo packets.

A router, such as router14A ofFIG. 2A, may therefore generate and output BFD control message38under the direction of management module32to specify a particular response interval by which it will respond to a periodic BFD control message from a second router. In particular, management module32controls the dual routing engines24A,24B of router14A to produce BFD control messages that specify, in desired minimum transfer interval field40I, the above-described first response interval and each subsequent response interval, e.g., second and third response intervals so as to provide failsafe management of periodic communications when accommodating software upgrades.

Although described in reference to setting a particular response interval, router14A may also specify an indefinite response interval by indicating within BFD control message38a change of state from “Up” or “Init” to “AdminDown.” Router14A may perform this state change by setting state field40C to “AdminDown” for example while further setting diagnostic field40B to explain the change of state. For example, diagnostic field40B may indicate that the state change occurred because a result of admin36's action, e.g., causing management module32to apply software upgrade34to active routing engine24A. The state change from “Up” to “AdminDown” causes periodic messaging to temporarily halt until the state change returns to either of “Init” or “Up.” In embodiments that implement this indefinite response interval, the router may not have to calculate a definite response interval, which may suit events that occur for unpredictable lengths of time. Thus, even when events are unpredictable, the techniques may dynamically adapt the response interval to accommodate the unpredictable nature of the events, and thereby further avoid network thrashing. For further information concerning the BFD protocol generally, BFD control message, and BFD control message fields, see the Internet Draft published by the Network Working Group of the Internet Engineering Task Force (IETF), titled “Bidirectional Forwarding Detection,” written by D. Katz and D. Ward, and dated March, 2007, the entire contents of which are hereby incorporated by reference as if fully set forth herein.

FIG. 4is a flowchart illustrating exemplary operation of a network device, such as router14A ofFIG. 2A, in performing failsafe management of periodic communications in accordance with the principles of the invention. Initially, routing engine24A negotiates a first response interval with a second network device by, for example, transmitting a BFD control message that specifies the first response interval in desired minimum transfer interval field40I, as shown inFIG. 3(42). As router14A receives subsequent periodic messages, routing engine24A responds to those messages within the first response interval in accordance with BFD28D (44).

At some point while responding to messages within the first response interval, routing engine24A may receive an indication of a software upgrade, e.g., software upgrade34(46). For example, management module32may receive user input from CLI30indicating that a system software upgrade has been initiated. If management module32, however, does not receive such an indication, routing engine24A continues to respond to any messages within the first response interval in accordance with normal operation (44).

If management module32does receive such an indication, it next dynamically computes a predicted upgrade time, as described above, (47) and automatically determines whether the predicted length of time to complete the software upgrade on routing engine24A, e.g., the predicted upgrade time, exceeds the first response interval, as described above (48). If the event interval does not exceed the first response interval, management module32does not issue any commands to routing engine24A and the routing engine continues to respond to the periodic messages within the first response interval (50,44).

However, if the predicted upgrade time exceeds the first response interval, management module32automatically outputs an instruction or message to routing engine24A indicating that a system software upgrade is about to be initiated for the routing engine. In the message, management module32specifies the predicted upgrade time for completion of the software upgrade on routing engine24A.

In response, routing engine24A performs two functions. First, routing engine24A negotiates a second response interval for the BFD session for each of its peering devices (e.g., with the second network device) by, for example, transmitting another BFD control message to the second network device (50,52). The second BFD control message may indicate a second response interval either by specifying the second response interval in desired minimum transfer interval field40I or by changing the state from “Up” to “AdminDown” within state field40C, as described above in reference to specifying an indefinite response interval. Second, upon successfully negotiating the second response interval, routing engine24A outputs an instruction or message to routing engine24B to initiate a switch of control so that routing engine24B takes over as the primary routing engine. Management module32may first issue an instruction or message to routing engine24A to initiate the switch, which then issues the above described instruction to coordinate the switch of control, or management module32may initiate application of software upgrade34to routing engine24A, which causes routing engine24A to perform the switch.

In some cases, routing engine24B may receive a periodic message before it can negotiate a shorter third response interval, e.g., during the switching event (54). If so, routing engine24B responds to the periodic message within the second response interval currently specified for the BFD session (56). Regardless of whether a message is received, routing engine24B may, upon resuming the routing responsibilities of routing engine24A, determine the event to be complete and negotiate a third response interval (60). Typically, routing engine24B renegotiates the first routing interval to shorten the period of time for failure detection back to the original amount; however, as described above, it may negotiate a third different interval if routing engine24B so determines. If the switch of control is not complete, routing engine24B may wait until it has completed (54,58). Once completed, routing engine24B may respond to messages within the third response interval (44).

Although described above with respect to a router14A and various routing engines24, the principles of the invention may be equally applicable to any network device, such as one of network devices4ofFIG. 1. In these embodiments, the techniques described herein may be embodied as instructions stored to a computer readable medium or as dedicated hardware. The instructions may cause a programmable processor to perform or the dedicated hardware may perform the failsafe management of periodic communication techniques described above. Thus, various embodiments of the invention have been described. These and other embodiments are within the scope of the following claims.