Optimization of routing forwarding database in a network processor

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.

FIELD OF INVENTION

The invention generally relates to optimized route look-up in a data communication network routing device. In particular, the invention relates to a system and method for allocating network route information between a plurality of memory devices having difference access speeds and thereby reducing the route determination time in a network processor.

BACKGROUND

Multi-layer network switches and routers in data communications network sometimes employ specialized application-specific integrated circuits (ASICs) designed to perform a large number of switching and routing operations on packet data. These ASICs include network processors (NPs) adapted to perform many of the Open Systems Interconnect (OSI) data link layer (Layer 2) switching operations and network layer (Layer 3) routing operations. NPs with routing capabilities generally compile and maintain routing tables that are used to retrieve the next-hop address for thousands of routes. The routing tables, e.g., Routing Forwarding Databases (RFDs), are retained in on-chip registers that are both fast and programmable.

While the register of a NP may store thousands of network routes, this may be insufficient to accommodate all the network addresses learned by the router in the course of operation. When the number of routes exceeds the maximum capacity of the NP, an attempt to write additional routes may fail on insertion or lead to unpredictable routing behavior. As a result, contemporary routers attempt to avoid such problems by limiting the number of routes saved to the NP and deleting those routes that exceed its maximum storage capacity. This practice, however, is not a solution because it results in the deletion of valid routes even if the routes are used more frequently than routes already retained by the registers.

There is therefore a need for a system and method to augment the storage capacity of NPs in a manner that provides a NP with access to all known routes while giving precedence to the routes that are used most frequently.

SUMMARY

The present invention in the preferred embodiment features a routing device comprising a port adapted to receive a protocol data unit (PDU); a routing table adapted to store a plurality of routes in a multi-way route trie comprising a plurality of route trie nodes, the routing table comprising a first memory for caching a first set of the plurality of route trie nodes, and a second memory for caching a second set of the plurality of route trie nodes; a routing engine adapted to search the routing table for one of the plurality of routes associated with the received PDU; and a route manager adapted to relocate one or more nodes of the second set from the second memory to the first memory, wherein a utilization count for each of the nodes of the first memory is higher than each of the nodes of the second memory. In the preferred embodiment, the route manager is further adapted to relocate one or more nodes of the first set from the first memory to the second memory.

In the preferred embodiment, the first memory has an access speed higher than the second memory. The second memory may be a random access memory, for example, and the first memory may be a register memory of an application-specific integrated circuit (ASIC) such as a network processor. Using the present invention, the routing device may assign and re-assign, as needed, the most frequently searched nodes of the multi-way route trie to the fastest memory, thereby reducing the time required to search the routing table.

When the search of the routing table identifies a match using the Internet Protocol (IP) address of the PDU, for example, the routing device retrieves forwarding information including the next-hop address to which to transmit the PDU. The more frequently a node of the route trie is searched, the higher its associated utilization count. In the preferred embodiment, the utilization count for the nodes in the network processor is generally an idle time represented by the number of idle digital micro-processor clock cycles elapsed since the node was last accessed for purposes of a route search. The utilization count for a node in the second memory is preferably the frequency with which the node is searched in a period of time given by the network administrator, for example.

The invention in some embodiments is a method of caching a plurality of routes in a forwarding routing database in a routing device comprising a first memory and a second memory, each of the plurality of routes being associated with a plurality of nodes organized in the form of a multi-way route trie. The method comprises the steps of: assigning nodes associated with one or more of the plurality of routes to the first memory if memory space is available; assigning nodes associated with one or more of the plurality of routes to the second memory if memory space in the first memory is unavailable; generating a utilization count for one or more nodes assigned to the first memory and for one or more nodes assigned to the second memory; comparing the utilization count for the one or more nodes assigned to the first memory with the utilization count for the one or more nodes assigned to the second memory; and if the utilization count of at least one of the one or more nodes in the second memory exceeds the utilization count of at least one of the one or more nodes in the first memory, then reassigning the at least one node in the second memory to the first memory. In the preferred embodiment, the method further includes the step of reassigning the at least one node in the first memory to the second memory if the utilization of the at least one node in the second memory exceeds the utilization count of the at least one node in the first memory.

If the first memory is a relatively fast memory and the second memory a relatively slow memory, the invention will reassign the nodes of the multi-way route trie such that the most frequently searched nodes of the route trie are assigned to the first memory. In the process, the method of the preferred embodiment of the invention is adapted to relocate frequently accessed nodes in the second memory to the first memory to minimize the average time required to execute a search of the route trie and retrieve the forwarding information associated with the inbound PDU.

DETAILED DESCRIPTION

Illustrated inFIG. 1is a functional block diagram of a multi-layer routing device for multiplexing data packets through a communications network. The routing device100is one of a plurality nodes and other addressable entities operatively coupled to a communications network such as a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), an Internet Protocol (IP) network, the Internet, or a combination thereof, for example. The routing device100preferably comprises a plurality of switching modules110operatively coupled to one another by means of a switch fabric150for transmitting protocol data units (PDUs) between switching modules. A switching module110may take the form of a switch processor, switching element, or switching blade adapted to detachably engage a slot or bus system (not shown) in the backplane152that operatively couples each of the switching modules110to one another.

Each of the plurality of switching modules110comprises at least one network interface module (NIM)102including one or more external ports103operatively coupled to a network communications link. Each of the plurality of switching modules110in the preferred embodiment further comprises one or more network processors (NPs)106generally capable of, but not limited to, at least Layer 2 switching and Layer 3 routing operations as defined in the Open Systems Interconnection (OSI) reference model. As such, each of the modules110is adapted to transmit protocol data units (PDUs) to and receive PDUs from the network via NIMs102, and to transmit PDUs to and receive PDUs from one another by means of the switch fabric150.

For purposes of this application, PDUs flowing into a switching module110from a communications link toward the switch fabric150are referred to herein as ingress PDUs, and the switching module110through which the ingress PDUs enters the routing device100is generally referred to as an ingress switching module. PDUs flowing from the switching fabric150to a communications link are referred to herein as egress PDUs, and the switching module from which they are transmitted is referred to as an egress switching module. Each of the plurality of switching modules110of the present embodiment may serve as both an ingress switching module and an egress switching module depending on the flow and its direction.

Illustrated inFIG. 2is a functional block diagram of a switching module for performing optimized multi-memory route allocation. The switching module110preferably comprises at least one NIM102, at least one NP106, a micro-processor262, and a fabric interface module208. Each of the NIMs102is operatively coupled to one or more external ports for purposes of receiving and transmitting data traffic. In the preferred embodiment, the routing device100is an IEEE 802.3-enabled switch and the NIMs102are adapted to perform physical layer and data link layer control that operably couple the routing device100to one or more communication media including wired, wireless, and optical communications links. The NP106in the preferred embodiment is a gigabit ethernet switch, model number BCM5695, produced by BROADCOM Corporation of Irvine, Calif.

Ingress PDUs received by NIMs102are transmitted via an internal data bus206to the NP106where an NP routing engine230makes switching and routing decisions based upon properties associated with the ingress PDU including, for example, the destination and source addresses, protocol type, priority information, and virtual local area network (VLAN) information including 802.1Q tags. Routing decisions are determined from among numerous routes retained in the route look-up250. The switching module110of the preferred embodiment is adapted to retain a complete record of all known routes using two or more memory stores including (1) a first memory internal to the NP106and (2) a second memory external to the NP106that augments the inherently limited memory capacity of the NP alone. The routes, costs and the associated next-hop addresses to which the ingress PDUs are to be forwarded are manually configured by the network administrator via the configuration manager264and or compiled by the micro-processor262using a dynamic routing protocol such as Open Shortest-Path-First (OPSF), for example, in combination with an Address Resolution Protocol (ARP).

After the next-hop destination address of an ingress PDU is identified, the routing engine230performs substantially all packet processing necessary to transmit the PDU from the routing device100. The packet processing operations may include but are not limited to header transformation for re-encapsulating data, VLAN tag pushing for appending one or more VLAN tags to a PDU, VLAN tag popping for removing one or more VLAN tags from a PDU, quality of service (QoS) for reserving network resources, billing and accounting for monitoring customer traffic, Multi-Protocol Label Switching (MPLS) management, authentication for selectively filtering PDUs, access control, higher-layer learning including Address Resolution Protocol (ARP) control, port mirroring for reproducing and redirecting PDUs for traffic analysis, source learning, class of service (CoS) for determining the relative priority with which PDUs are allocated switch resources, and coloring marking used for policing and traffic shaping, for example.

After packet processing by the routing engine230, the PDU is temporarily buffered in the ingress queue memory242by the queue manager240until the bandwidth is available to transmit the PDU through the switching fabric150. The PDU is then transmitted via the fabric interface module208to the appropriate egress switching module for transmission in the direction of the PDU's destination node.

In the preferred embodiment, the fabric interface module208is adapted to both transmit ingress PDUs to the switching fabric150as well as receive egress PDUs from each of the other one or more switching modules. In the preferred embodiment, the egress data received from the fabric interface module208is buffered in egress queue memory248, passed through the routing engine230for statistical processing, for example, and transmitted from the appropriate egress port via one of the NIMs102.

Illustrated inFIG. 3is a functional block diagram of a switching module adapted to perform optimized multi-memory route look-up by allocating route storage between a plurality of memory devices. In particular, the switching module110retains routes in a route look-up spanning the first memory, i.e., a primary route memory internal to the NP106, and a second memory, i.e., secondary route memory. The secondary route memory is typically slower than the primary route memory and may be located internal or external to the NP106. The optimum allocation of routes between the primary route memory and the secondary route memory is determined by the micro-processor262based upon route usage statistics compiled by the NP106as well as the micro-processor262.

As illustrated in greater detail inFIG. 3, the NP routing engine230of the preferred embodiment comprises a parsing engine332, a classifier333, a forwarding processor336, and an egress processor338. The parsing engine332inspects the ingress frames received from the NIMs102and extracts one or more fields relevant to identification, forwarding, and routing of the ingress PDUs. The PDU is switched to the appropriate egress port without alteration if the destination media access control (MAC) address is known. If unknown, the source MAC is added to the layer2address table334on the ingress port by the source learning335and the PDU transmitted to all associated egress ports.

If the frame includes the destination MAC address of the switching module110and the destination IP address of another node, for example, the classifier333attempts to identify the destination node, the corresponding route and the address of the next-hop on the path to the destination node. In doing so, the classifier333preferably generates an index from one or more fields of the ingress PDU with which it searches the route look-up250. If a match is detected, the route look-up250retrieves a pointer to the forwarding information in the NP forwarding table354, the forwarding information used by the forwarding processor336to encapsulate the packet with a new physical layer header including the next-hop address, and the PDU transmitted to the queue manager240. The queue manager240buffers the PDUs in the ingress memory242with the requisite class of service (CoS)/quality of service (QoS) requirements and subsequently releases the PDUs to the switching fabric150in accordance with a bandwidth allocation scheme such as strict priority or weighted fair queuing, for example.

In the preferred embodiment, the route look-up250comprises (a) relatively fast primary route memory in the NP106for retaining the most frequently utilized routes and (b) secondary route memory external to the NP106to supplement the primary route memory. In the preferred embodiment, the NP employed is a Broadcom 5695 network processor the faster primary route memory internal to the NP106is a register memory352adapted to cache approximately 3800 IPv4 routes. External to the NP is additional secondary route memory, including the random access memory (RAM)360, for storing additional routes needed to extend the capacity of the switching module110.

As discussed in more detail below, the routes are logically organized in the form of searchable route trees, or “tries” from the word “reTRIEval,” including route trie nodes that correspond to one or more bits of the associated route. In the preferred embodiment, the bits of the destination address may be divided across route trie nodes stored in both the register352and RAM360. In the preferred embodiment, the distribution of nodes between the register352and RAM360is dynamically defined and periodically redefined in order to place the most frequently used nodes in the register. In this manner, the registers352and RAM360are able to retain all the routes of interest while minimizing the average route determination time.

The frequency with which the nodes of the search trie retained in the registers352are accessed is monitored by the NP106and recorded in the register activity table358. In the case of the Broadcom 5695 NP, the frequency, also referred to as a utilization count, is measured in the form of a hit rate acquired over a given period of time, each search of a node giving rise to a hit.

The frequency, i.e., the utilization count, with which the route trie nodes retained in the RAM360are accessed, is compiled by the micro-processor262and recorded in the form of one or more RAM activity tables364retained in the data store266. Although the same metric may used to determine the activity of nodes in RAM360and the registers352, the switching module110in the preferred embodiment measures activity of nodes in RAM360in terms of the numbers of times the nodes are accessed for purposes of a route search in a given period of time.

The RAM activity table364includes a list of each subtrie root node in the RAM trie and its utilization count. A subtrie root is a root node of a portion of the route trie that is retained only in the secondary route memory360but not the primary route memory. A subtrie may be one or more nodes in depth and be headed by a subtrie root whose parent node in the route trie is retained in the primary route memory352. For consistency, the utilization count of a subtrie root is equal to the maximum utilization count of all of its children nodes. In the preferred embodiment, the list of subtrie roots is sorted by utilization from most utilized to least utilized to facilitate the identification and relocation of the most active nodes to the primary route memory352, if necessary.

In some embodiments, the micro-processor262also maintains a register leaf list366retained in data store266. The register leaf list366is preferably a data structure used by the micro-processor262to locally track the utilization counts provided by the register activity table358. The utilization counts retained in the register leaf list366are compiled by the NP106and subsequently used by the micro-processor262to facilitate the identification and relocation of the least active nodes in the primary route memory352to the secondary route memory360.

Illustrated inFIG. 4is the route look-up comprising a multi-memory, multi-way data structure and forwarding table. The multiway data structure, also known as a retrieval tree or “trie” structure, is employed by the switching module110to search route data with one or more packet properties and retrieve an associated pointer into the forwarding table354. The trie structure includes a plurality of hierarchical arrays populating the register memory352and the RAM360, each array corresponding to one or more nodes in the route trie structure. The primary route memory, i.e., register memory352, is generally a high-speed memory of hardware-limited capacity fixed at the time the NP106is manufactured. The secondary route memory, i.e., RAM360, is typically external to the NP106and is more cost-effective that on-chip register memory352. The RAM360generally has greater storage capacity than the register memory352and can readily store all the hierarchical arrays needed to provide searchable access to all known routes in even a large network.

In some embodiments, the secondary route memory is adapted to store the complete route trie including those nodes also retained in the primary route memory. For simplicity of explanation, however, the secondary route memory illustrated in FIGS.4and7-10comprises only those nodes that are excluded from the primary route memory due to their relatively low utilization count, for example.

The number and size of the arrays in RAM360may be defined and dynamically redefined by the micro-processor262to provide the routing engine230a complete topological view of the network. Due to the faster access speeds, however, learned routes are first recorded to the register memory352when space is available, and new nodes created in RAM360by the micro-processor262if and when the register memory reaches capacity. The new nodes created in RAM360refer to the nodes excluded from the register memory352. One skilled in the art will recognize the benefit of recording all nodes of new routes in RAM360to provide a comprehensive and searchable route trie if the search in register memory352fails to produce a match.

As illustrated inFIG. 4, the register352includes a first hierarchical array A401, second hierarchical array B402, third hierarchical array C403, and fourth hierarchical array D404, which schematically represent the tiers of the route trie structure used to search a four-byte IPv4 address. Each of the arrays401-404is preferably maintained in the NP's register memory352for ready access.

The first hierarchical array, array A401, corresponds to the root node of the trie structure and comprises a plurality of elements including for example elements A1-A2. . . A100. Each of the elements A1-A2. . . A100corresponds to a string comprising the one or more most significant bits of the IPv4 destination address of the received PDU. The fourth hierarchical array, array D404, represents the leaf nodes of the route trie structure in the register352and comprises a plurality of elements including elements D1-D2. Each of the elements D1-D2corresponds to a string comprising the least significant one or more bits of the IPv4 destination address of the received PDU. A pointer450into the forwarding table354is retrieved from the leaf node when all bits of the PDU's destination IP address match one of the plurality entries in the array D404. The second hierarchical array, array B402, and third hierarchical array, array C403, correspond to intermediate nodes of the route trie structure, which are searched when traversing between the root node and leaf nodes.

The fifth hierarchical array, array B*405, sixth hierarchical array, array C*406, and seventh hierarchical array, array D*407, represent nodes of the route trie structure that are retained only in RAM360. The hierarchical arrays405-407are managed by the micro-processor262switching module software. The nodes in RAM360are generally searched if the search in the register memory352is terminated by the NP106prior to reaching a leaf of the route trie.

Illustrated inFIG. 5is a representative hierarchical array depicted in tabular form. In the preferred embodiment, each entry of the hierarchical array, i.e., each row in the table500, includes a valid_bit indicator501, a stop_bit indicator502, and an index503to a child array. Although the hierarchical array500generally has the same format independent of whether it is recorded in the register memory352or RAM360, the index503of the hierarchical array employed in the NP106may include a default value used to force the switching module110to terminate the search in the NP106and resume the search in the micro-processor262using the route data in the RAM360.

A match is detected between one or more bits of an IP address when the hierarchical array searched includes a valid entry at the position in the array given by value of the one or more bits searched. A series of one or more bits of the IP address having a value of “n,” for example, corresponds to the “nth” element in the hierarchical array500. The entry associated with the value of the one or more bits may then be retrieved by indexing into the memory using a pointer given by the sum of the base value of the array and the value of the bits searched.

When the bits of an address being tested match an entry in the hierarchical array500, the route look-up250inspects the valid_bit indicator501to initially determine whether the entry includes a valid index to a subsequent table. A value of one (1) for example, indicates that the index-1 in the third column503points to another node in a child array or the forwarding table354, while a zero (0) value or undefined value, for example, indicates the absence of a matching routing rule. In the absence of a match, the route look-up may apply a default routing rule or apply the route rule associated with the longest prefix match detected to that point in the search.

If the valid_bit indicator501is equal to one (1), the route look-up also inspects the stop_bit indicator502to determine whether to continue searching the route trie structure.

A stop_bit indicator equal to zero (0) signifies that the index in the third column503is a pointer to the next route trie node in register352to be searched. A stop_bit indicator with a value of one (1) signifies that the particular node is a leaf node. The leaf node may be either a leaf with respect to the entire route trie or a leaf with respect to the sub-trie retained in register memory352.

If the leaf node is a leaf with respect to the complete route trie, the route look-up250completes the search by retrieving the associated forwarding information from the forwarding table354with the pointer from column503. If the leaf node is a leaf with respect to the portion of the route trie retained in the primary route memory352but not the complete route trie, the search by the NP106is terminated and resumed by the micro-processor262using the secondary route memory360. A search that ends prematurely in the register352and is completed in RAM360is said to be sent to “software.” A search executed by the micro-processor262may be directed to only the route sub-tries in RAM360or traverse the complete route trie anew. In the preferred embodiment, the NP106forces the search to software and the secondary route memory360by setting the index value equal to a default index value.

Illustrated inFIG. 6is a leaf node providing pointing to a forwarding table employed in the preferred embodiment. Each row of the forwarding table354represents a forwarding table entry that is pointed to by the index503of a leaf node650in the route trie structure. In accordance with the preferred embodiment of the present invention, the plurality of leaf nodes650are distributed between both the register352and the RAM360to provide the NP106access to the most frequently used route trie nodes and thereby reduce the search times.

Each entry in the forwarding table354includes forwarding information including the next-hop address601, i.e., the MAC destination address to which the matching PDU is to be forwarded. In some embodiments, the MAC source address602and virtual local area network (VLAN) identifier603are also retrieved and included in the data link layer header of the PDU when transmitted to the next-hop. One skilled in the art will appreciate that the forwarding table600may be adapted to include additional information including the egress port103number, for example.

Illustrated inFIG. 7is a multi-way route trie structure schematically representing the route look-up embodied entirely within the primary route memory, i.e., the register memory352. The route trie structure700corresponds to a condition in which the register memory352has the capacity to locally cache and resolve each route known to the switching module110. In this example, therefore, each of the nodes of the route trie700is cached in the NP's register memory352without the NP106resorting to secondary route memory such as RAM360.

The multiway route trie structure700comprises a plurality of nodes whose logical relationship is indicted by branches connecting the nodes. The plurality of nodes includes the root node A1and intermediate nodes B1-B2, C1-C4, and leaf nodes D1-D8. In general, successive nodes are searched from the root node A1to one of the plurality of leaf nodes D1-D8that matches the IP destination address of the ingress PDU. As discussed above, the matching leaf node includes an index pointing to an entry in the forwarding table354from which the applicable forwarding information is retrieved.

Illustrated inFIG. 8is a multi-way route trie structure schematically representing the route look-up distributed across the primary route memory352and secondary route memory360. The route trie structure800corresponds to a condition in which the capacity of register352is insufficient to locally cache all the routes known to the switching module110. In this case, one or more of the nodes of the route trie800are retained in RAM360external to the NP's register memory352.

Like the multi-way route trie700discussed above in regard toFIG. 7, the trie structure800comprises a plurality of branches that stem from nodes associated with the criteria to be searched. The plurality of nodes include the root node A1and intermediate nodes B1-B2, C1-C5, each of which is cached locally in the NP's register memory352. The leaf nodes here include a first set of nodes D2-D3, D10-12, D5-D7cached locally in the NP's register memory352. The route trie also includes a second set of nodes D1*, D8*, D9* retained in RAM360. The logical boundary between those nodes retained in the register352and RAM360is illustrated by lines of demarcation802.

To enable the route look-up250to dynamically search between the register352and RAM360, each of the parent nodes associated with child nodes D1*, D8*, D9* in RAM360comprises a default index value that causes the route search in the NP106to terminate and to revert to the micro-processor262using the routing information retained in the secondary route memory. If the search of the secondary route memory360produces a match among leaf nodes D1*, D8*, D9*, a pointer to the forwarding table354is identified and the applicable forwarding information retrieved.

In the preferred embodiment, newly learned routes are committed to the secondary route memory360if the primary route memory352is at capacity. That is, the nodes corresponding to newly learned routes are incorporated into the route trie structure in RAM360and their utilization count then monitored. If and when the route manager356determines that a node in RAM360is used relatively more frequently than a node in the register, the node may be automatically relocated to the register memory352.

Illustrated inFIG. 9is a multi-way route trie structure schematically representing the route look-up including one or more sub-tries in secondary memory360to augment the register memory352. As stated above, the RAM360may be employed to store one or more leafs as well as one or more sub-tries of the multi-way route trie structure. An entire sub-trie, for example, that branches directly from the root node A1may be committed to RAM360or moved from the register352to RAM360to free space in the register352for routes that are used more frequently so as to take advantage of the relatively faster access speeds offered by the register352.

A sub-trie retained in RAM360may include any number of nodes and may incorporate as many intermediate nodes between the root node and leaf nodes. For example, the sub-trie retained in the RAM360comprises the intermediate node C5*910and child leaf nodes D10*911, D11*912, and D4*913. A sub-trie structure in RAM360may also branch directly from the root node A1or other intermediate node, as illustrated inFIG. 4by the sub-trie branching from node A100to child nodes in hierarchical array B*.

Illustrated inFIG. 10is the multi-way route trie structure ofFIG. 9after the trie has been pruned to exploit redundancy in the forwarding information. In particular, the switching module110of the preferred embodiment is adapted to identify sub-tries having a plurality of leaf nodes as well as intermediate nodes that are associated with identical forwarding information. If the forwarding information is identical for each of the child nodes having a common parent node, the switching module110in the preferred embodiment introduce a new entry in the forwarding table354that causes the parent node to point directly to the forwarding table354, thereby resolving the forwarding information without traversing the route trie structure to a true leaf.

If the leaf nodes D10*911and D11*912inFIG. 9, for example, are associated with the same forwarding information, node C5* is converted from an intermediate node to a quasi-leaf node by forcing it to point directly to the forwarding table354. That is, if the MAC destination address (DA-10equals DA-11), MAC source address (SA-10equals SA-11), and VLAN (VLAN-10equals VLAN-11) are the same for D10*911and D11*912, the node C5*910is altered to terminate the search early and point directly1010to the forwarding table354. In particular, the value of the stop_bit indicator502associated with the leaf node C5*910is changed from zero (0) to one (1) and a new pointer indexing into the applicable forwarding information inserted in the third column503of the of the corresponding entry in the hierarchical array. The entry with the new pointer is represented by the quasi-leaf node C5*910in the listing of leaf nodes650and points to the pre-existing entry in the forwarding table for either D10*911or D11*912.

In the preferred embodiment, the pruning module359is charged with periodically monitoring the register leaf list366and the RAM activity table364to identify redundancies and collapse sub-tries to increase memory and or reduce search times. The pruning may be applied to sub-tries in the register352, in RAM360, or between the register352and RAM360.

One skilled in the art will recognize that the act of making node C5*910a quasi-leaf node causes the nodes D10*911and D11*912to bypassed in the route search process. As a result, nodes D10*911and D11*912will become inactive and their utilizations counts drop to zero (0). If the nodes D10* and D11* were recorded in the register memory352prior to node C5*910being made a quasi-leaf, the route look-up250would automatically relocate the nodes D10*911and D11*912to RAM360when there activity levels drops below that of the most active nodes in the secondary memory360. In some embodiments, the redundant nodes, including D10*911and D11*912, may be subsequently removed from the multi-way route trie by a standard route aging mechanism.

Illustrated inFIG. 11is flowchart of the process by which the switching module monitors and updates the route look-up. The switching module110, like other routers, dynamically learn (step1102) new routes from other routers through various route exchange protocols including OSPF, for example, or are manually configured with static routes by the network administrator. The route manager356immediately determines (step1104) where the one or more nodes of the new route is to be inserted in the multi-way route trie structure representing the topology of the network about the routing device100. In the process of inserting the one or more nodes, the route manager356logically links any new nodes to a parent node sharing a common IP address prefix.

The route manager356determines (step1106) the availability of space for the new route in the NP's register memory352. If memory is available, the register memory determination step (testing step1108) is answered in the affirmative and the one or more nodes of the new route introduced in the register352using a new index503inserted (step1110) into the parent node to account for the new branch. If the new node constitutes a new leaf node in the register352, the new leaf determination step (testing step1112) is answered in the affirmative and the route added (step1114) to a register leaf list366used to track the activity of nodes recorded in the register352and compare their activity to nodes in RAM360. The utilization count statistics in the register leaf list366are preferably a subset of the statistics compiled by the network processor106and compiled in the register activity table358. The nodes in the register leaf list366may be sorted and listed from the most to least active to facilitate the identification and transition of nodes from the register memory352to the RAM memory360.

If there is no available memory in the register352, the register memory determination step (testing step1108) is answered in the negative and the new node is recorded (step1115) in RAM360. New routes recorded to RAM360may also be monitored to determine if and when their utilization count is high enough to warrant relocation to the register memory352. If the new node is also a new “sub-trie root node”, the new root determination (testing step1116) is answered in the affirmative and the node added (step1118) to the RAM activity table364. The term “sub-trie root node” refers to a route trie node in RAM360whose parent resides in the register memory352. The sub-trie roots in RAM360lie at the logical boundary between the primary and secondary route memories and are candidates for relocation into the register memory352depending on the frequency with which the nodes are searched relative to the frequency of nodes in the register352.

Illustrated inFIG. 12is a flowchart of the process1200by which the switching module monitors route activity and selectively relocates nodes in the route look-up to either the primary route memory352or the secondary route memory360. In the preferred embodiment, the search activity, i.e., utilization count statistic, is the primary factor in determining whether the node is retained in the relatively-fast register memory352of the NP106or the relatively-slow external RAM362. In accordance with the preferred embodiment, the nodes that pertain directly to relatively inactive routes are allocated to the relatively slower RAM360while the nodes pertaining to relatively active nodes are allocated to relatively fast register memory352.

In the preferred embodiment, the route look-up250determines (step1202) the utilization count of the leaf nodes listed from the register leaf list366and the utilization count of the sub-trie root nodes in from the RAM activity table364. In the NP106of the preferred embodiment, the utilization count of route trie nodes in register memory352is automatically tracked by the NP106using a preconfigured algorithm. In the preferred embodiment, the NP106is configured to increment a “hit bit,” i.e., a one-bit counter, associated with a node each time the node is accessed for purposes of a route search. The NP106or micro-processor262periodically inspects the hit bits of various nodes in the register352to determine which hit bits are set. If a hit bit is set, the hit bit is initialized to zero. If the hit bit is not set, a counter tracking the number of idle cycles for the node is incremented. The number of idle cycles per unit time is therefore the measure of activity. Inactive routes may be deleted or “aged out” when not used for a determined period of time. The number of hits required to maintain a route before is it is deleted is preferably a programmable hit threshold determined by the network administrator.

The route manager356determines the activity of the route trie nodes retained exclusively in RAM362and particularly the sub-trie roots in the activity table364. For these nodes, the utilization count is a measure of frequency given by the number of times the nodes are searched in a given period of time. In the preferred embodiment, the machine readable instructions executed by the micro-processor262cause the route manager356to increment a use counter in the RAM activity table364when a node is used for purposes of a route search. The period of time over which the use statistics are accumulated is preferably a programmable period of time provided by the network administrator. In the preferred embodiment, the utilization count of a sub-trie root in RAM360is equal to the utilization count of its most active child node.

If there are one or more routes in RAM360that are used more frequently than the register352, the relative activity determination test (testing step1204) is answered in the affirmative and at least one relatively inactive node relocated (step1206) from the register352to RAM360. With memory now available in the register352, at least one relatively active route is concurrently relocated from RAM360to the register352(step1208). In the preferred, the switching module110periodically repeats the process1200of relocating nodes, as needed, at an update interval on the order of a one tenth of a second to one second.

In the process1200of relocating the nodes between register memory352or the RAM360, the switching module110preserves the overall topological organization of trie structure in the route look-up250. In general, relocation of a node entails: the (a) the creation of an entry in a hierarchical array in the register memory352or RAM360to which the node is moved; (b) the creation of a pointer in the new entry linking it to the appropriate forwarding information; and (c) the deletion of the existing entry of the array in the memory from which the node is moved.

In addition to there being available memory in the register352, a node in some embodiments must have an activity level in excess of an idle cycle threshold before the node may be relocated to the register352. The number of cycles necessary to qualify a route for relocation is preferably a programmable idle cycle threshold determined by the network administrator.

Although the description above contains many specifications, these should not be construed as limiting the scope of the invention but as merely providing illustrations of some of the presently preferred embodiments of this invention.

Therefore, the invention has been disclosed by way of example and not limitation, and reference should be made to the following claims to determine the scope of the present invention.