Optimization of routing forwarding database in a network processor

• US 20060056412A1
• Filed: 09/14/2004
• Published: 03/16/2006
• Est. Priority Date: 09/14/2004
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Page, Gregory
• Granted Patent: US 7,706,302 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric

Abstract

A routing device and associated method for allocating the nodes of a multi-way trie of a forwarding routing table between two or more memory devices is disclosed. In the preferred embodiment, the routing device comprises a routing table for storing a plurality of routes in a multiway trie in a first memory for caching a first set of the plurality of trie nodes and a second memory for caching a second set of the plurality of trie nodes; and a route manager adapted to relocate one or more nodes of the second set from the second memory to the first memory such that the a utilization count for each of the nodes of the first memory is higher than each of the nodes of the second memory.

Claims

1. A routing device comprising:

a port adapted to receive a protocol data unit (PDU);

a routing table for storing a plurality of routes in a multi-way trie having a plurality of nodes, the routing table comprising;

a first route memory for caching a first set of the plurality of nodes; and

a second route memory for caching a second set of the plurality of nodes;

a routing engine adapted to search the routing table for one of the plurality of routes associated with the PDU; and

a route manager adapted to relocate one or more nodes of the second set from the second route memory to the first route memory, wherein a utilization count for each of the nodes of the first route memory is higher than each of the nodes of the second route memory.

2. The routing device of claim 1, wherein the route manager is further adapted to relocate one or more nodes of the first set from the first route memory to the second route memory.

3. The routing device of claim 1, wherein the first route memory has an access speed higher than the second route memory.

4. The routing device of claim 3, wherein the second route memory is a random access memory.

5. The routing device of claim 3, wherein the first route memory is a register memory.

6. The routing device of claim 5, wherein the routing engine and register memory are embodied in an application-specific integrated circuit (ASIC).

7. The routing device of claim 6, wherein the ASIC is a network processor.

8. The routing device of claim 1, wherein the search of the routing table comprises a search of an Internet Protocol (IP) address of the PDU.

9. The routing device of claim 1, wherein the utilization count for each of the plurality of nodes is a measure of search activity for each node.

10. The routing device of claim 1, wherein the routing device further comprises a forwarding table from which forwarding information is retrieved if one of the plurality of routes associated with the PDU is identified by the routing engine.

11. The routing device of claim 10, wherein each of the plurality of nodes comprises a pointer to either a child node of the multi-way trie or a pointer to associated forwarding information in the forwarding table.

12. The routing device of claim 11, wherein the routing device is adapted to make a pointer of a parent node point directly to the forwarding table if each of the one or more child nodes of the parent node are associated with the same forwarding information.

13. The routing device of claim 1, wherein the routing device is adapted to maintain:

a first route memory activity list comprising at least one sub-trie leaf nodes; and

a second route memory activity list comprising at least one sub-trie root nodes;

wherein each of the at least one sub-trie leaf nodes is a parent node of one or more of the at least one sub-trie root nodes, and each of the at least one sub-trie root nodes is a child node of one of the at least one sub-trie leaf nodes.

14. The routing device of claim 13, wherein one or more nodes of the second set relocated from the second route memory to the first route memory is removed from the second route memory activity list and added to the first route memory activity list.

15. The routing device of claim 1, wherein the route manager is adapted to relocate one or more nodes at an update interval between one tenth of a second and one second.

19. The method of claim 10, wherein the utilization count for nodes assigned to the second route memory is given by the number of times the node is searched in a period of time.

16. A method of caching a plurality of routes in a forwarding routing database of a routing device, the routing device comprising a first route memory and a second route memory, each of the plurality of routes being associated with a plurality of nodes organized in the form of a multi-way trie, the method comprising the steps of:

assigning nodes associated with one or more of the plurality of routes to the first route memory if memory space is available;

assigning nodes associated with one or more of the plurality of routes to the second route memory if memory space in the first route memory is unavailable;

generating a utilization count for one or more nodes assigned to the first route memory and for one or more nodes assigned to the second route memory;

comparing the utilization count for the one or more nodes assigned to the first route memory with the utilization count for the one or more nodes assigned to the second route memory; and

if the utilization count of at least one of the one or more nodes in the second route memory exceeds the utilization count of at least one of the one or more nodes in the first route memory, then reassigning the at least one of the one or more nodes in the second route memory to the first route memory.

17. The method of claim 16, wherein the method further includes the step of:

reassigning the at least one of the one or more nodes in the first route memory to the second route memory if the utilization of the at least one node in the second route memory exceeds the utilization count of the at least one node in the first route memory.

18. The method of claim 16, wherein the utilization count for nodes assigned to the first route memory is an idle time between route lookups.

20. The method of claim 16, wherein the first route memory is characterized by a higher access speed than the second route memory.

21. The method of claim 16, wherein the second route memory is a random access memory.

22. The method of claim 16, wherein the first route memory is a network processor memory.

23. The method of claim 16, wherein the method further includes the step of assigning one or more nodes associated with newly learned routes to the second route memory.

24. A routing device comprising:

a port adapted to receive a of protocol data unit (PDU) characterized by one or more PDU properties;

a route memory adapted to store a plurality of routes in a multiway trie, the route memory comprising;

a first memory for caching a plurality of nodes of the trie; and

a second memory for caching at least one node of the trie;

a forwarding table adapted to store forwarding information associated with the PDU;

a route manager adapted to;

generate a utilization count for the plurality of nodes of the first memory and for the at least one node of the second memory;

compare the utilization count for the plurality of nodes of the first memory with the utilization count for the at least one node of the second memory; and

if the utilization count of a second node in the second memory exceeds the utilization count of a first node having the lowest utilization count in the first memory, then store the second node in the first memory.

25. The method of claim 24, the first memory is embodied in a register memory of a network processor.