1. Field of the Invention
The invention relates to the field of communication. More specifically, the invention relates to communication networks.
2. Background of the Invention
A router hosts a routing protocol(s) that can include the Routing Information Protocol (RIP), the Interior Gateway Protocol (IGP), the Border Gateway Protocol (BGP), the Exterior Gateway Protocol (EGP), Open Short Path First (OSPF), Intermediate System to Intermediate System (IS—IS), etc. The router exchanges messages with neighboring routers in accordance with one or more of the hosted routing protocols. These messages are used to maintain a table of routing information (“routing table”). A routing table stores the state of the network topology and the best-known paths to destinations. A given routing table can include path information for hundreds of thousands of paths. Path information typically includes a destination network prefix, an Internet Protocol (IP) address for a next hop, an outgoing physical interface or port number, metrics of the path, etc.
FIG. 1 (PRIOR ART) is a diagram illustrating a prior art routing table. Routing tables are comprised of multiple columns. The routing table illustrated in FIG. 1 identifies destinations in the first column of the routing table 100. In the second column of the routing table 100, addresses for next hops corresponding to the destinations in the first column are identified. In the third column of the routing table 100, interfaces corresponding to the next hops in the second column are identified. A given row of the routing table 100 describes a path to the destination identified in the first column of the given row.
In the routing table 100 illustrated in FIG. 1, rows 1–3 of the routing table 100 identify destinations A, B, and C. The next hop in the paths to the destinations A–C is a network device X as indicated in the routing table 100. The interface for the next hop X is the interface 1 as indicated in the third column of rows 1–3 of the routing table 100. The last two rows of the routing table 100 identify a next hop for destinations M and N as Z. The last two rows identify an interface 3 as the interface corresponding to the next hop Z.
At startup, a given router, which hosts the routing table 100, downloads the routing table 100 into each of the router's line cards. The given router may download the entire routing table 100, or selected columns from the routing table 100, but every row of the routing table 100 is downloaded as a forwarding table for each line card. Typically, a router downloads the information in the first 3 columns of the routing table 100 for each of its line cards as the forwarding table. A router hosting the routing table 100 may download the first three columns of the routing table 100 as a forwarding table. FIG. 1B (PRIOR ART) illustrates a forwarding table 101 illustrated downloaded into each of the router's line cards.
Line cards host forwarding tables in order to remove from the central processing unit the intensive task of processing traffic. When a given one of a router's line cards receives traffic, the line card processes the traffic to determine the traffic's destination and forwards the traffic to the outgoing physical interface indicated by the line card's forwarding table. For example, a line card that receives traffic destined for the network device A determines that the traffic should be forwarded to the interface 1 as indicated in the forwarding table 101.
Unfortunately, a change in status of a next hop or a physical interface typically affects thousands of entries in the routing table. For example, if the physical interface 1 fails, then all entries in the routing table 100 that correspond to the physical interface, must be modified to a different interface. The thousands of modified entries in the routing table 100 are then downloaded to each line card. Downloading such a mass of data to each line card of a router consumes valuable resources of the router (e.g., memories in the line cards, system bus(es), etc.) and can cause packets to be dropped.
This problem is exacerbated when a route flap occurs. A poorly connected wire at a physical interface that fails intermittently typically causes a route flap. The intermittent failure causes repeated changes to entries in the routing table 100. Each change in the routing table 100 caused by the route flap prompts the router to download the modified entries of the routing table 100 to each of the router's line cards. These repeated changes and the downloading of path information for thousands of entries affected by the route flap severely impacts performance of the router, if bringing it down completely.
BGP route flap damping as described in Request for Comments (RFC) 2439 has been proposed as a solution to route flaps. Unfortunately, BGP route flap damping only limits the period of time a router will be overloaded instead of solving the problems caused by route flaps. Moreover, a router is still exposed to failure from route flapping before BGP route flap damping is triggered.