Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-07-30
2004-01-13
Vanderpuye, Kenneth (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S351000
Reexamination Certificate
active
06678274
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to routing packets in a packet-based network, and more particularly to a method and system for updating forwarding tables that are maintained by network routers.
BACKGROUND OF THE INVENTION
An internetwork such as a transmission control protocol/Internet protocol (TCP/IP) based intranet or the Internet consists of many interconnected routers. The internetwork has a network topology that must be mapped out, so that the interconnected routers can properly forward packets to other network nodes. Information concerning the topology of networks is stored by routers in forwarding tables and the forwarding tables are consulted by the respective routers each time packets are forwarded.
As the topology of networks change, routers communicate the topology changes to each others. The communicated changes are then incorporated into the forwarding table of each individual router. While updating a single entry in a forwarding table of a router does not present significant difficulties, in many cases the entire forwarding table must be updated. During the time that is required to update a forwarding table, inconsistencies in the table may develop and packets may be incorrectly forwarded because of the table inconsistencies. In order to ensure that a forwarding table is free of inconsistencies before packets are forwarded, it is best to forward packets only after the forwarding table has been completely updated. Although it is best to completely update the forwarding table before forwarding packets, as the rate of packets arriving at a router increases, the time available for updating the forwarding table decreases. As a result, packets must either be forwarded according to a forwarding table that has not been completely updated, or delayed until the forwarding table can be completely updated.
FIG. 1
represents a conventional forwarding table lookup engine
12
and forwarding table memory
14
that is used in an IP-based router to forward packets. When a packet enters the lookup engine, the destination IP address within the packet header is utilized to lookup a next hop address in the forwarding table. In order to properly reflect the current topology of the network, the forwarding table of the router is periodically updated with new route entries. A relatively long period of time is required to update a large portion of the forwarding table, and while the update is in progress, some portions of the forwarding table may not be consistent with the intended forwarding logic. As stated above, during the periods of inconsistency with the intended forwarding logic, it is possible that some packets will be incorrectly forwarded. In order to minimize periods of inconsistency within forwarding tables, it is desirable to update the forwarding tables as fast as possible during periods when no packets are arriving at the router.
One technique for increasing the speed of forwarding table updates involves equipping routers with faster central processing units (CPUs). Although faster CPUs may provide some performance benefits, when network traffic is heavy, faster CPUs are still not be able to complete large forwarding table updates during breaks between packets. As a result, packets must be forwarded utilizing an outdated or potentially inconsistent forwarding table, or packets must be delayed until the forwarding table update is complete, neither of which are desirable outcomes.
Another technique for increasing the speed of forwarding table updates involves making a working copy of a forwarding table before any updates have been made to the forwarding table. Updates are then made to the working copy of the forwarding table while the original forwarding table is utilized to forward packets. Once the working copy has been completely updated, the updated working copy is written over the original forwarding table in order to replace the original forwarding table with the updated working copy. Although this technique may speed up the update process, writing the working copy of the forwarding table over the original copy of the forwarding table takes a significant period of time. During periods of heavy network traffic, writing large forwarding table updates over the original forwarding table may require incoming packets to be forwarded according to an inconsistent forwarding table, or delayed until the forwarding table update is complete.
In view of the need to continuously update forwarding tables in routers and the need to avoid inconsistencies in forwarding tables, what is needed is a system and a method that allow a forwarding table to be updated at speeds provided by conventional CPUs, while eliminating inconsistencies in the forwarding tables that are being utilized to forward packets.
SUMMARY OF THE INVENTION
A system and a method for managing forwarding table lookups and updates involve maintaining a first forwarding table in a first memory and a second forwarding table in a second memory, and then utilizing the first forwarding table to forward packets while the second forwarding table is updated with current route entries. The second forwarding table is updated in the background and therefore conventional CPU speeds do not cause performance problems. Once the second forwarding table is completely updated, a forwarding table pointer is switched and the second forwarding table is utilized to forward packets while the first forwarding table is updated. Because the second forwarding table has been completely updated in the background, switching the forwarding table pointer causes newly arriving packets to be forwarded according to a forwarding table that is free of inconsistencies.
In a preferred embodiment, the system includes a lookup engine, a forwarding table pointer, two distinct blocks of forwarding table memory, and an update engine. The lookup engine receives incoming packets and looks at the packet headers to determine the destination of the incoming packets. After the destination of an incoming packet is identified, the lookup engine accesses one of the two forwarding tables to determine the best route (next hop) for the packet, based on the ultimate destination of the packet. Once the best route for the present packet is identified, the packet is forwarded to a switch fabric that is contained within the router.
The two distinct blocks of forwarding table memory allow for the simultaneous storage of two different forwarding tables. That is, the first forwarding table memory stores a first version of a forwarding table, and the second forwarding table memory stores a second version of a forwarding table. Typically, one version of the forwarding table is an updated version of the other forwarding table, although this is not critical. In a preferred embodiment, the two forwarding table memories have identical structure, so that the two forwarding table memories are interchangeable with each other.
The forwarding table pointer identifies which forwarding table memory is active. The active forwarding table memory stores the forwarding table that is accessed by the lookup engine to forward packets. When there are only two possible memories, a one-bit register can be used to identify either of the two forwarding table memories.
The forwarding table update engine coordinates the updates of the two forwarding tables that are stored in the respective forwarding table memories. The preferred forwarding table update engine utilizes conventional techniques to update the forwarding tables and is supported by a standard speed CPU.
In operation, the forwarding table pointer may identify the first forwarding table memory as the active forwarding table memory. The active forwarding table memory stores the forwarding table that is currently being utilized by the lookup engine to route incoming packets. The forwarding table memory that is not identified by the forwarding table pointer is not utilized by the lookup engine to route incoming packets, and is referred to as a secondary forwarding table memory.
While the first forwarding table is being accessed b
Jain Sanjay
Walia Lakhinder
Riverstone Networks, Inc.
Vanderpuye Kenneth
Wilson Mark A.
LandOfFree
Method and system for managing forwarding tables does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for managing forwarding tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for managing forwarding tables will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3187090