Survey and taxonomy of ip address lookup algorithms <s> Multibit Tries with the Path Compression Technique <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> BIB001 </s> Survey and taxonomy of ip address lookup algorithms <s> Multibit Tries with the Path Compression Technique <s> There has been a notable interest in the organization of routing information to enable fast lookup of IP addresses. The interest is primarily motivated by the goal of building multigigabit routers for the Internet, without having to rely on multilayer switching techniques. We address this problem by using an LC-trie, a trie structure with combined path and level compression. This data structure enables us to build efficient, compact, and easily searchable implementations of an IP-routing table. The structure can store both unicast and multicast addresses with the same average search times. The search depth increases as /spl Theta/(log log n) with the number of entries in the table for a large class of distributions, and it is independent of the length of the addresses. A node in the trie can be coded with four bytes. Only the size of the base vector, which contains the search strings, grows linearly with the length of the addresses when extended from 4 to 16 bytes, as mandated by the shift from IP version 4 to IP version 6. We present the basic structure as well as an adaptive version that roughly doubles the number of lookups/s. More general classifications of packets that are needed for link sharing, quality-of-service provisioning, and multicast and multipath routing are also discussed. Our experimental results compare favorably with those reported previously in the research literature. <s> BIB002
Nilsson et al. BIB002 recursively transform a binary trie with prefixes into a multibit trie. Starting at the root, they replace the largest full binary subtrie with a corresponding one-level multibit subtrie. This process is repeated recursively with the children of the multibit subtrie obtained. Additionally, one-child paths are compressed. Since we replace at each step a binary subtrie of several levels with a multibit trie of one level, the process can be viewed as a compression of the levels of the original binary trie. Level-compressed (LC) is the name given by Nilsson to these multibit tries. Nevertheless, letting the structure of the binary trie strictly determine the choice of strides does not allow control of the height of the resulting multibit trie. One way to further reduce the height of the multibit trie is to let the structure of the trie only guide, not determine, the choice of strides. In other words, we will replace nearly full binary subtries with a multibit subtrie (i.e., binary subtries where only few nodes are missing). Nilsson proposes replacing a nearly full binary subtrie with a multibit subtrie of stride k if the nearly full binary subtrie has a sufficient fraction of the 2 k nodes at level k, where a sufficient fraction of nodes is defined using a single parameter called fill factor x, with 0 < x £ 1. For instance, in Fig. 7 , if the fill factor is 0.5, the fraction of nodes at the fourth level is not enough to choose a stride of 4, since only 5 of the 16 possible nodes are present. Instead, there are enough nodes at the third level (5 of the 8 possible nodes) for a multibit subtrie of stride 3. In order to save memory space, all the nodes of the LC trie are stored in a single array: first the root, then all the nodes at the second level, then all the nodes at the third level, and so s Figure 15 . The hardware scheme of BIB001 . on. Moreover, internal nodes are not allowed to store prefixes. Instead, each leaf has a linear list with prefixes, in case the path to the leaf should have one or several prefixes (less specific prefixes). As a result, a search in an LC trie proceeds as follows. The LC trie is traversed as is the basic multibit trie. Nevertheless, since path compression is used, an explicit comparison must be performed when arriving at a leaf. In case of mismatch, a search of the list of prefixes must be performed (less specific prefixes, i.e., prefixes in internal nodes in the original binary trie). Since the LC trie is implemented using a single array of consecutive memory locations and a list of prefixes must be maintained at leaves, incremental updates are very difficult.