System, device, and method for expediting reconvergence in a communication network

[0002] The present invention relates generally to communication systems, and more particularly to expediting reconvergence in a communication system.

[0003] In today's information age, communication networks are often used for interconnecting computers and computer peripherals. A communication network typically includes a number of nodes that interoperate to route protocol messages. The various nodes in the communication network utilize various routing protocols in order to determine the routes that are used to route the protocol messages.

[0004] One type of routing protocol, known as a “link state” routing protocol, determines routes based upon the status of communication links between the various nodes. A link state routing protocol, such as OSPF and IS-IS, requires each node to have complete topology information. Each node maintains a topology database that indicates all nodes in the communication network and lists the communication links that are associated with each node.

[0005] The various nodes in the communication network exchange link status information using link state advertisement (LSA) protocol messages. Specifically, each node periodically tests the communication links to each of its neighbors and sends a LSA protocol message including the link status information to all of the other nodes. Each node computes the routes based upon the link status information received from the other nodes.

[0006] When a node receives a LSA protocol message, the node updates its topology database based upon the link status information received in the LSA protocol message, and runs a special algorithm to determine the routes based upon the updated topology information. One well-known algorithm for determining routes is the Dijkstra shortest path algorithm. The Dijkstra shortest path algorithm computes the shortest paths to all destinations from a single source.

[0007] When a communication link fails, the various nodes in the communication network interoperate to route protocol messages around the failed communication link. This is often referred to as “reconvergence.” Each node that supports the failed communication link (referred to hereinafter as a “supporting” node) sends an LSA protocol message to the other nodes in the communication network identifying the failed communication link. Each supporting node may detect the communication link failure at a different time, and therefore each supporting node may send the LSA protocol message at a different time. Each node updates its topology database to reflect the failed communication link, based upon the link status information from the LSA protocol messages, and uses the Dijkstra shortest path algorithm in order to compute new routes.

[0008] In one prior art embodiment, a node computes new routes each time it receives an LSA protocol message. Specifically, upon receiving an LSA protocol message, a node updates its topology database based upon the link status information in the LSA protocol message, and computes new routes based upon the updated topology database.

[0009] In the case of a communication link failure, each supporting node sends an LSA protocol message identifying the failed communication link. When a node receives such an LSA protocol message from a supporting node, the node updates its topology database, specifically by removing the failed communication link from the list of communication links associated with the supporting node, and then computes new routes based upon the updated topology database. Because each node may receive multiple LSA protocol messages relating to the same communication link failure, each node may update its topology database and compute new routes multiple times for the same communication link failure. Reconvergence is not complete until all LSA protocol messages are processed, since each LSA protocol message identifies the communication link failure from the perspective of one particular supporting node. Furthermore, the Dijkstra shortest path algorithm is computationally intensive and can take a relatively long time to complete, especially in communication networks having many nodes, so it is desirable to reduce the number of times new routes are computed, preferably once per communication link failure.

[0010] In another prior art embodiment, each node computes new routes based upon link status information received over a period of time. Specifically, upon receiving a first LSA protocol message, a node updates its topology database based upon the link status information in the LSA protocol message, and starts a timer. If the node receives additional LSA protocol messages while the timer is running, the node updates its topology database based upon the link status information in the additional LSA protocol messages. This allows the node to receive multiple LSA protocol messages relating to the same communication link failure before computing new routes. When the timer expires, the node computes new routes based upon all link status information received during the timeout period. This reduces the number of times the routes are computed, but delays reconvergence.

[0011] In the case of a communication link failure, each supporting node sends an LSA protocol message identifying the failed communication link. When a node receives a first such LSA protocol message from a supporting node, the node updates its topology database, specifically by removing the failed communication link from the list of communication links associated with the supporting node, and starts the timer. During the timeout period, the node receives additional LSA protocol messages from the other supporting nodes. For all such additional LSA protocol messages, the node updates its topology database, specifically by removing the failed communication link from the lists of communication links associated with the other supporting nodes. When the timer expires, the node computes new routes based upon the updated topology database, which includes all link status information received during the timeout period. The node only computes new routes once, although, as before, reconvergence is not complete until all LSA protocol messages are processed.

[0012] In order for the communication network to operate efficiently, it is important for reconvergence to occur as quickly as possible following a communication link failure. Unfortunately, in both prior art embodiments described above, reconvergence does not occur until each node processes LSA protocol messages from all supporting nodes. This may take a substantial amount of time, during which the nodes may continue routing protocol messages to the failed communication link.

[0013] Thus, a technique for expediting reconvergence following a communication link failure is needed.

[0014] In accordance with one aspect of the invention, a first indication of a communication link failure prompts a node to compute new routes. Upon receiving the first indication of the communication link failure, the node determines the nodes that are associated with the failed communication link. The node disassociates the failed communication link from all such nodes, and computes new routes. Subsequent indications of the same communication link failure are ignored.

[0015] More particularly, upon receiving a LSA protocol message from a supporting node indicating a communication link failure, the node updates its topology database by removing the failed communication link from the list of communication links associated with the supporting node. The node then uses its topology database to determine other nodes that are associated with the failed communication link, and updates its topology database by removing the failed communication link from the lists of communication links associated with the other nodes. The node then computes new routes based upon the updated topology database.

[0016] The node ignores any subsequent LSA protocol messages relating to the same communication link failure. A caching mechanism is preferably used to determine whether a particular LSA protocol message is related to a previous communication link failure.

[0017] One advantage of the present invention is that the node only computes new routes once for each communication link failure.

[0018] Another advantage of the present invention is that reconvergence is achieved upon processing the first LSA protocol message indicating the communication link failure.

[0019] The foregoing and other objects and advantages of the invention will be appreciated more fully from the following further description thereof with reference to the accompanying drawings wherein:

[0020] FIG. 1 shows an exemplary communication network having three interconnected nodes in accordance with an embodiment of the invention;

[0021] FIG. 2 is a logic flow diagram showing exemplary logic for processing a link state advertisement protocol message in accordance with an embodiment of the invention; and

[0022] FIG. 3 is a block diagram showing relevant logic blocks of an exemplary node in accordance with an embodiment of the invention.

[0023] An embodiment of the present invention expedites reconvergence following a communication link failure. Specifically, when a node receives a first LSA protocol message from a supporting node indicating a communication link failure, the node updates its topology database, specifically by removing the failed communication link from the list of communication links associated with the supporting node. Then, instead of waiting for additional LSA protocol messages from other supporting nodes, the node uses its topology database to determine other supporting nodes that are associated with the failed communication link, and removes the failed communication link from the lists of communication links associated with those other supporting nodes. As a result, the topology database is in the same state that it would be had the node waited for the additional LSA protocol messages from the other supporting nodes. Once the topology database is updated, the node computes new routes based upon the updated topology database. In this way, the node expedites reconvergence by computing new routes once per communication link failure upon receiving the first LSA protocol message.

[0024] The node ignores any subsequent LSA protocol messages that are related to the same communication link failure in order to prevent unnecessary and redundant iterations of the Dijkstra shortest path algorithm. In order to ignore any subsequent LSA protocol messages that are related to the same communication link failure, the node must determine whether a particular LSA protocol message is related to the same communication link failure. In an exemplary embodiment of the invention, the node uses a caching mechanism in order to identify LSA protocol messages that are related to the same communication failure. Specifically, the node stores the link status information from the first LSA protocol message in a cache as part of the processing of the first LSA protocol message. The link status information identifies the failed communication link. When the node receives a subsequent LSA protocol message, the node compares the link status information in the subsequent LSA protocol message to the link status information in the cache in order to determine whether the subsequent LSA protocol message is related to the same communication link failure as the first LSA protocol message. In particular, the node compares the link status information in the subsequent LSA protocol message to the link status information in the cache in order to determine whether the LSA protocol message indicates the same communication link failure. If the subsequent LSA protocol message is related to the same communication link failure as the firs t LSA protocol message, then the node discards the subsequent LSA protocol message without computing new routes. The cache can be used to store link status information relating to multiple communication link failures in order to prevent unnecessary and redundant iterations of the Dijkstra shortest path algorithm for any of such communication link failures. The link status information relating to a particular communication link failure is deleted from the cache after a predetermined period of time.

[0025] FIG. 1 shows an exemplary communication network 100 having three interconnected nodes, namely node A 102, node B 106, and node C 112. Node A 102 and node B 106 are interconnected over the communication link 104, and are the supporting nodes for the communication link 104. Node B 106 and node C 112 are interconnected over the communication link 110, and are the supporting nodes for the communication link 110. Node A 102 and node C 112 are interconnected over the communication link 108, and are the supporting nodes for the communication link 108.

[0026] Each node has complete topology information, which it maintains in a topology database. The topology database indicates all nodes in the communication network, and lists the communication links that are associated with each node. The topology database maintained by node A 102 indicates that node B 106 is associated with communication links 104 and 110, and indicates that node C 112 is associated with communication links 108 and 110. The topology database maintained by node B 106 indicates that node A 102 is associated with communication links 104 and 108, and indicates that node C 112 is associated with communication links 108 and 110. The topology database maintained by node C 112 indicates that node A 102 is associated with communication links 104 and 108, and indicates that node B 106 is associated with communication links 104 and 110.

[0027] Each node periodically tests its associated communication links, and provides the link status information to the other nodes by sending the link status information to the other nodes in LSA protocol messages. Node A 102 provides link status information for communication links 104 and 108 to node B 106 and node C 112. Node B 106 provides link status information for communication links 104 and 110 to node A 102 and node C 112. Node C 112 provides link status information for communication links 108 and 110 to node A 102 and node B 106.

[0028] When a communication link fails, each supporting node sends an LSA protocol message to the other nodes identifying the failed communication link. For example, assume the communication link 104 fails. When node A 102 detects the communication link failure, node A 102 sends an LSA protocol message to node B 106 and node C 112 indicating that the communication link 104 failed. Likewise, when node B 106 detects the communication link failure, node B 106 sends an LSA protocol message to node A 102 and node C 112 indicating that the communication link 104 failed. It is likely that node A 102 and node B 106 will detect the communication link failure at different times, and therefore node A 102 will send an LSA protocol message at a different time than node B 106.

[0029] When node C 112 receives the first LSA protocol message indicating the failure of the communication link 104, for example, from node A 102, node C 112 updates its topology database by removing the communication link 104 from the list of communication links associated with node A 102. Node C 112 then uses the topology database to determine that node B 106 is also associated with the communication link 104 and updates its topology database by removing the communication link 104 from the list of communication links associated with node B 106. Node C 112 then computes new routes based upon the updated topology database. Node C 112 also stores the link status information from the first LSA protocol message indicating the failure of the communication link 104 in a cache.

[0030] When node C 112 receives a subsequent LSA protocol message relating to the failure of the communication link 104, from node B 106, node C 112 discards the LSA protocol message without computing new routes. Specifically, upon receiving the subsequent LSA protocol message from node B 106, node C 112 compares the link status information in the subsequent LSA protocol message to link status information in the cache, and determines that the subsequent LSA protocol message is related to the same communication link failure as the first LSA protocol message. Having already removed the communication link 104 from the list of communication links associated with node B 106 and computed new routes, node C 112 simply discards the subsequent LSA protocol message from node B 106.

[0031] FIG. 2 is a logic flow diagram showing exemplary logic 200 for processing a LSA protocol message in accordance with an embodiment of the invention. Beginning at step 202, and upon receiving an LSA protocol message from a supporting node indicating a communication link failure, in step 204, the logic checks the cache to determine whether the LSA protocol message is related to a previous communication link failure, in step 206. In particular, the logic compares the link status information in the received LSA protocol message to the link status information in the cache in order to determine whether the LSA protocol message indicates a previous communication link failure. If the LSA protocol message is related to a previous communication link failure (YES in step 208), then the logic discards the LSA protocol message without computing new routes, in step 220. If the LSA protocol message is not related to a previous communication link failure (NO in step 208), then the logic proceeds to update the topology database by removing the failed communication link from the list of communication links associated with the supporting node, in step 210. The logic then uses the topology database to determine any other nodes that are associated with the failed communication link, in step 212, and updates the topology database by removing the failed communication link from the lists of communication links associated with the other nodes, in step 214. The logic then computes new routes based upon the updated topology database, in step 216. The logic also stores link status information from the LSA protocol message in the cache, in step 218. The link status information identifies the failed communication link. The logic discards the LSA protocol message, in step 220. The logic 200 terminates in step 299.

[0032] FIG. 3 is a block diagram showing relevant logic blocks of an exemplary node 300 in accordance with an embodiment of the invention. Among other things, the node 300 includes routing protocol logic 302, a cache 304, and a topology database 306. The cache 304 is used for storing link status information relating to communication link failures. The topology database 306 is used for storing topology information for implementing a link state routing protocol. The routing protocol logic 302 implements the link state routing protocol, and includes the logic 200 for processing a LSA protocol message as shown and described with reference to FIG. 2 above.

[0033] In an exemplary embodiment of the present invention, predominantly all of the routing protocol logic is implemented as a set of computer program instructions that are stored in a computer readable medium and executed by an embedded microprocessor system within the node. Various embodiments of the invention may be implemented in any conventional computer programming language. For example, an embodiment may be implemented in a procedural programming language (e.g., “C”) or an object oriented programming language (e.g., “C++”). Alternative embodiments of the invention may be implemented using discrete components, integrated circuitry, programmable logic used in conjunction with a programmable logic device such as a Field Programmable Gate Array (FPGA) or microprocessor, or any other means including any combination thereof.

[0034] Alternative embodiments of the invention may be implemented as a computer program product for use with a computer system. Such implementation may include a series of computer instructions fixed either on a tangible medium, such as a computer readable media (e.g., a diskette, CD-ROM, ROM, or fixed disk), or fixed in a computer data signal embodied in a carrier wave that is transmittable to a computer system via a modem or other interface device, such as a communications adapter connected to a network over a medium. The medium may be either a tangible medium (e.g., optical or analog communications lines) or a medium implemented with wireless techniques (e.g., microwave, infrared or other transmission techniques). The series of computer instructions embodies all or part of the functionality previously described herein with respect to the system. Those skilled in the art should appreciate that such computer instructions can be written in a number of programming languages for use with many computer architectures or operating systems. Furthermore, such instructions may be stored in any memory device, such as semiconductor, magnetic, optical or other memory devices, and may be transmitted using any communications technology, such as optical, infrared, microwave, or other transmission technologies. It is expected that such a computer program product may be distributed as a removable medium with accompanying printed or electronic documentation (e.g., shrink wrapped software), preloaded with a computer system (e.g., on system ROM or fixed disk), or distributed from a server or electronic bulletin board over the network (e.g., the Internet or World Wide Web).

[0035] The present invention may be embodied in other specific forms without departing from the essence or essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive.