Expediting reconvergence in a routing device

Details Expediting reconvergence in a routing device Expediting reconvergence in a routing device

1998-11-23

2002-07-23

Nguyen, Chau (Department: 2663)

Multiplex communications

Diagnostic testing

Using oam cells

C370S248000, C370S395600

Reexamination Certificate

active

06424629

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to communication networks, and, more particularly, to expediting reconvergence in a routing device.
BACKGROUND OF THE INVENTION
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 “protocol stack”). 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 “layer
1
” or “physical layer” 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 “layer
2
” or “data link layer” protocols, define the format of the data transported by the physical layer protocols. Protocols implemented at layer
3
(typically referred to as the “network layer”) 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 “logical connection.”
Generically, each logical connection consists of one or more communication channels (referred to hereinafter as “logical channels”). 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 “logical channel protocol layer.” Also for convenience, a logical connection is considered to be “active” 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 “reconvergence.”
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.
SUMMARY OF THE INVENTION
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

Affiliated with

Also associated with

Rating

Expediting reconvergence in a routing device does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Expediting reconvergence in a routing device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Expediting reconvergence in a routing device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2857032