Network routers for packet-based communications protocols such as Internet Protocol (IP) direct incoming information to the next neighbor along a route to the intended destination for the packet. To do this, typically each router along the route must perform route address prefix (normally referred to as just “prefix”) lookup operations on a prefix (or routing) table to determine the appropriate next hop address for the destination IP prefix. Such operations are performed by either an embedded network processor or, more commonly, by a separate network search engine.
Originally the hardware for network search engines employed content addressable memory (CAM), a type of memory consisting of a bit comparator and two memory elements, one for storing data and the other storing a compare mask. The CAM compares incoming data with the value stored in the data memory under the control of the mask value, which may be programmed to override the comparison result to “always match” (i.e., “don't care”). In operation, a CAM-based network search engine functions by storing all prefixes of a routing table in a CAM array in a specific, prioritized order, with each prefix's associated next hop information stored in a corresponding (linked) location in another memory. During prefix lookup, a key is placed on the comparand (compare operand) bus of the CAM array and compared against all prefixes in the memory. The array of match results from all comparisons is sent through a priority logic unit to determine the highest priority match, with the winning match used to address the next hop memory from which the corresponding next hop information is read and returned.
More recently, software based network search engines employing a general-purpose processor and a normal memory have been developed. Within such devices, the processor performs prefix searches with a series of memory read and comparison operations. The routing table prefixes and next hop information are typically stored in the memory in data structures built according to one of various software algorithms developed to reduce memory usage in storing the routing table and the number of memory accesses during lookup. For these purposes, a multi-bit trie and the corresponding algorithm are among the data structures and algorithms that achieve the best data compression with a bounded number of memory accesses for search operations.
A trie (from the middle four letters of “retrieve”) is a tree-based data structure built to represent binary strings, where each bit or group of bits in the string determines the direction taken among branches within the tree. A binary (unibit or single bit) trie proceeds bit-by-bit and has at most two branches from each node, while a multi-bit consumes multiple bits at a time and has several branches at each node, each branch leading to the next level. The number of bits consumed or examined during branch selection at each node is referred to as a stride. A uniform width stride trie is a trie with all strides having the same width, except possibly the last stride, which may be the remainder of the prefix length after being divided by the stride width.
Generally, the multi-bit trie algorithm works by storing and retrieving prefixes in a uniform stride width trie, grouping all branches in the same level with the same parent (next higher stride level) stride value into a table, referred to as a trie table. At each level, the corresponding stride value provides an index into a trie table entry containing the information needed to get to the next level. A multi-bit trie has the advantage that prefixes with common high order bits (strides) will share the same parent trie tables, reducing the memory required to store the prefixes.
If a prefix of length l is divided into m strides each of n bits, the maximum possible number of entries within the next level trie table is 2n. The algorithm encodes all next level stride values from the same parent into a 2n bit data field stored in the entry within the parent trie table, along with a pointer containing the base address of the next level (child) trie table, in a data structure referred to as a trie node. Table compression is achieved by allocating memory for the actual number of table entries that exist, instead of the maximum size 2n. For the last stride of each prefix, a similar type of data structure, referred to as an end node, is used, except in this case the pointer points to a table containing next hop information instead of a next level trie table.
Routing table lookup is also performed in same width strides, with the value of the next level stride from the input search key (typically an IP address of 32 or 64 bits) decoded and processed together with the associated data field in the stride value's parent table entry. If a stored route with the same prefix stride value is determined to exist within the trie, an index is calculated using the information in the parent table, then the search continues using the table pointer and the calculated index to form an address leading to the next level trie table entry. If a match is not found, the search terminates without success. If a search reaches an end node and a match is found, the search is successful and the associated next hop information is read from the next hop table.
Successfully completing a lookup in a multi-bit trie requires multiple levels of the trie to be traversed. At each level, the tree node is accessed from memory and used, along with the stride value, to determine the address of the trie node at the next level.
However, latencies within hardware multi-bit trie network search engines can contribute to the overall latencies within the network router, and therefore within the network itself.
There is, therefore, a need in the art for an improved multi-bit trie network search engine.