The present invention relates generally to communication networks, and, more particularly, to expediting reconvergence in a routing device.
In today""s information age, data communication networks are evolving as more and more information is transferred and accessed by electronic means. Specifically, transmission facilities are migrating toward higher speed technologies such as fiber-optic and broadband technologies, and networking devices such as routers and switches are evolving to more efficiently and quickly handle information. In order to realize the potential of these improved data communication networks, it is important for the communication protocols used in the data communication networks to also be efficient.
In order for the communication protocols to be efficient and still be flexible, many communication protocols are implemented in layers (often referred to as a xe2x80x9cprotocol stackxe2x80x9d). Each protocol layer provides a specific set of services to the protocol layer immediately above it in the protocol stack. Although there are different protocol layering schemes in use today, the different protocol layering schemes have certain common attributes. Specifically, protocols at the lowest layer in the protocol stack, typically referred to as the xe2x80x9clayer 1xe2x80x9d or xe2x80x9cphysical layerxe2x80x9d protocols, define the physical and electrical characteristics for transporting data across a connection. Protocols at the next layer in the protocol stack, typically referred to as the xe2x80x9clayer 2xe2x80x9d or xe2x80x9cdata link layerxe2x80x9d protocols, define the format of the data transported by the physical layer protocols. Protocols implemented at layer 3 (typically referred to as the xe2x80x9cnetwork layerxe2x80x9d) and above ultimately utilize the services provided by the data link layer protocols to transport information within the communication network.
In a common networking model, the communication network includes a number of interconnected routers that route information from a source to a destination. Each router maintains a connection to at least one other router, and typically to two or more other routers. For convenience, the connection between two routers is referred to hereinafter as a xe2x80x9clogical connection.xe2x80x9d
Generically, each logical connection consists of one or more communication channels (referred to hereinafter as xe2x80x9clogical channelsxe2x80x9d). A logical channel can be a physical communication channel or a virtual communication channel. Specifically, a logical channel can be a physical layer channel or subchannel (for example, a subchannel derived through time-division multiplexing, frequency-division multiplexing, code-division multiplexing, wavelength-division multiplexing, or other physical layer multiplexing scheme) or a virtual channel at another protocol layer (for example, a virtual channel derived through packet switching, frame relay switching, cell switching, or other multiplexing scheme, typically at the data link layer). For convenience, the protocol layer at which the logical channels are supported is referred to hereinafter as the xe2x80x9clogical channel protocol layer.xe2x80x9d Also for convenience, a logical connection is considered to be xe2x80x9cactivexe2x80x9d if at least one of its constituent logical channels is active.
In order to route information from a source to a destination across the network, each router maintains a routing table that effectively maps the destination to one of the logical connections supported by the router. The router selects a preferred logical connection for the destination based upon, among other things, routing information received from the other routers in the network. Specifically, the routers in the network exchange routing information using a routing protocol, such as the Routing Information Protocol (RIP) or the Open Shortest Path First (OSPF) protocol, that is implemented at a routing protocol layer above the logical channel protocol layer. The router uses the routing information it receives from the other routers to determine the preferred logical connection for the destination and to update its routing table accordingly.
Of course, the preferred logical connection for the destination may change over time due to congestion or outages in the network. Therefore, the router routinely exchanges routing information with the other routers in the network so that the router can update its routing table to adapt to network changes. Specifically, if the preferred logical connection becomes unusable (for example, due to a failure of all of its constituent logical channels) such that an alternate logical connection must be used, or the preferred logical connection otherwise becomes less desirable than the alternate logical connection (for example, due to congestion on the preferred logical connection), then the router updates its routing table to map the destination to the alternate logical connection. Likewise, if the preferred logical connection subsequently becomes usable or otherwise becomes more desirable than the alternate logical connection, then the router updates its routing table to map the destination back to the preferred logical connection. For convenience, the process of dynamically updating the routing table in response to network changes is referred to hereinafter as xe2x80x9creconvergence.xe2x80x9d
Therefore, when the preferred logical connection becomes unusable due to a failure of all of its constituent logical channels, the router reconfigures its routing table to bypass the failed logical connection. Although the logical channel protocol layer may detect the logical channel failures quickly, the router typically does not update its routing table until the communication failure is detected by the routing protocol operating at the routing protocol layer. In a large network having many routers, it can take a substantial amount of time for the routing protocol to detect the communication failure. For example, in one prior art embodiment in which the router uses the OSPF routing protocol, it can take up to three (3) minutes for the OSPF protocol to determine that the preferred logical connection failed. Thus, there can be a significant period of time following the communication failure when the router continues routing information over the failed logical connection rather than re-routing the information to the alternate logical connection. As a result, a significant amount of data can be lost (a problem that is only magnified by the high-speed transmission facilities used in the network), and user sessions, which typically have time out periods significantly shorter than three (3) minutes, can time out such that they must be re-established after communication is restored. In worst case scenarios, the significant delay in detecting the communication failure and updating the routing tables can lead to network outages.
Similarly, when communication over the preferred logical connection is restored, the router typically reconfigures its routing table to use the restored logical connection. Again, the logical channel protocol layer may detect the restored logical channels quickly, but the router typically does not update its routing table until the restored logical connection is detected by the routing protocol operating at the routing protocol layer. Thus, there can be a significant period of time following restoral of the preferred logical connection when the router continues routing information over the alternate logical connection rather than rerouting the information to the preferred logical connection. This can perpetuate additional network delays and congestion when the alternate logical connection provides a less optimal routing path than the preferred logical connection.
Thus, a need has remained for a mechanism by which the router can quickly reconverge when the status of a logical connection changes.
In accordance with one aspect of the invention, first protocol layer logic at a first protocol layer of a protocol stack monitors the status of the logical connection, and triggers routing table updates at a second protocol layer of the protocol stack based on the status of the logical connection.
In accordance with another aspect of the invention, the first protocol layer logic determines that the logical connection failed, and triggers the routing table update at the second protocol layer to bypass the failed logical connection.
In accordance with yet another aspect of the invention, the first protocol layer logic determines that the logical connection has been restored following a logical connection failure, and triggers the routing table update at the second protocol layer to use the restored logical connection.
In various embodiments of the invention, the logical connection comprises one or more physical layer communication channels, one or more physical layer communication subchannels (for example, time-division multiplexed subchannels, frequency-division multiplexed subchannels, code-division multiplexed subchannels, wavelength-division multiplexed subchannels, or other multiplexed subchannels), or one or more virtual channels at a data link layer or other protocol layer. The second protocol layer can be a network protocol layer, a routing protocol layer, or other protocol layer.
USPTO Backgrounds
USPTO Backgrounds