Survey and taxonomy of ip address lookup algorithms <s> Multibit Tries and Compression <s> For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry with the longest matching prefix, a task that has been thought to require hardware support at lookup frequencies of millions per second.We present a forwarding table data structure designed for quick routing lookups. Forwarding tables are small enough to fit in the cache of a conventional general purpose processor. With the table in cache, a 200 MHz Pentium Pro or a 333 MHz Alpha 21164 can perform a few million lookups per second. This means that it is feasible to do a full routing lookup for each IP packet at gigabit speeds without special hardware.The forwarding tables are very small, a large routing table with 40,000 routing entries can be compacted to a forwarding table of 150-160 Kbytes. A lookup typically requires less than 100 instructions on an Alpha, using eight memory references accessing a total of 14 bytes. <s> BIB001 </s> Survey and taxonomy of ip address lookup algorithms <s> Multibit Tries and Compression <s> The increased bandwidth in the Internet puts great demands on network routers; for example, to route minimum sized Gigabit Ethernet packets, an IP router must process about 1.5/spl times/10/sup 6/ packets per second per port. Using the "rule-of-thumb" that it takes roughly 1000 packets per second for every 10/sup 6/ bits per second of line rate, an OC-192 line requires 10/spl times/10/sup 6/ routing lookups per second; well above current router capabilities. One limitation of router performance is the route lookup mechanism. IP routing requires that a router perform a longest-prefix-match address lookup for each incoming datagram in order to determine the datagram's next hop. We present a route lookup mechanism that when implemented in a pipelined fashion in hardware, can achieve one route lookup every memory access. With current 50 ns DRAM, this corresponds to approximately 20/spl times/10/sup 6/ packets per second; much faster than current commercially available routing lookup schemes. We also present novel schemes for performing quick updates to the forwarding table in hardware. We demonstrate using real routing update patterns that the routing tables can be updated with negligible overhead to the central processor. <s> BIB002
Expansion creates several prefixes that all inherit the forwarding information of the original prefix. Thus, if we use multibit tries with large strides, we will have a great number of contiguous nodes with the same BMP. We can use this fact and compress the redundant information, which will allow saving memory and make the search operation faster because of the small height of the trie. One example of this approach is the full expansion/compression scheme proposed by Crescenzi et al.  . We will illustrate their method with a small example where we do a maximal expansion supposing 5-bit addresses and use a twolevel multibit trie. The first level uses a stride of 2 bits, the second level a stride of 3 bits, as shown in Fig. 16 . The idea is to compress each of the subtries at the second level. In Fig. 17 we can see how the leaves of each second-level subtrie have been placed vertically. Each column corresponds to one of the second-level subtries. The goal is to compress the repeated occurrences of the BMPs. Nevertheless, the compression is done in such a way that at each step the number of compressed symbols is the same for each column. With this strategy the compression is not optimal for all columns, but since the compression is made in a synchronized way for all the columns, accessing any of the compressed subtries can be made with one common additional table of pointers, as shown in Fig. 17 . To find the BMP of a given address we traverse the first level of the multibit trie as usual; that is, the first 2 bits of the address are used to choose the correct subtrie at the second level. Then the last 3 bits of the address are used to find the pointer in the additional table. With this pointer we can readily find the BMP in the compressed subtrie. For example, searching for the address 10110 will guide us to the third subtrie (column) in the compressed structure; and using the s Figure 16 . A two-level fully expanded multibit trie. s Figure 17 . A full expansion parallel compression scheme. In the actual scheme proposed by Crescenzi, prefixes are expanded to 32 bits. A multibit trie of two levels is also used, but the stride of the first and second levels is 16 bits. It is worth noting that even though compression is done, the resulting structure is not small enough to fit in the cache memory. Nevertheless, because of the way to access the information, search always takes only three memory accesses. The reported memory size for a typical backbone forwarding table is 1.2 Mbytes. Another scheme that combines multibit tries with the compression idea has been dubbed the Lulea algorithm BIB001 . In this scheme, a multibit trie with fixed stride lengths is used. The strides are  BIB002 BIB002 , for the first, second, and third level respectively, which gives a trie of height 3. In order to do efficient compression, the Lulea scheme must use a set of disjoint prefixes; hence, the Lulea scheme first transforms the set of prefixes into a disjoint-prefix set. Then the prefixes are expanded in order to meet the stride constraints of the multibit trie. Additionally, in order to save memory, prefixes are not allowed at internal nodes of the multibit trie ; thus, leaf pushing is used. Again, the idea is to compress the prefix information in the subtries by suppressing repeated occurrences of consecutive BMPs. Nevertheless, contrary to the last scheme, each subtrie is compressed independent of the others. Once a subtrie is compressed, a clever decoding mechanism allows the access to the BMPs. Due to lack of space we do not give the details of the decoding mechanism. While the trie height in the Lulea scheme is 3, actually more than three memory references are needed because of the decoding required to access the compressed data structure. Searching at each level of the multibit trie needs, in general, four memory references. This means that in the worst case 12 memory references are needed for IPv4. The advantage of the Lulea scheme, however, is that these references are almost always to the cache memory because the whole data structure is very small. For instance, for a forwarding table containing 32,732 prefixes the reported size of the data structure is 160 kbytes. Schemes using multibit tries and compression give very fast search times. However, compression and the leaf pushing technique used do not allow incremental updates. Rebuilding the whole structure is the only solution. A different scheme using compression is the Full Tree Bit Map by Eatherton  . Leaf pushing is avoided, so incremental updates are allowed.