Survey and taxonomy of ip address lookup algorithms <s> Prefix Range Search <s> IP address lookup is becoming critical because of increasing routing table sizes, speed, and traffic in the Internet. Given a set S of prefixes and an IP address D, the IP address lookup problem is to find the longest matching prefix of D in set S. This paper shows how binary search can be adapted for solving the best-matching prefix problem. Next, we show how to improve the performance of any best-matching prefix scheme using an initial array indexed by the first X bits of the address. We then describe how to take advantage of cache line size to do a multiway search with six-way branching. Finally, we show how to extend the binary search solution and the multiway search solution for IPv6. For a database of N prefixes with address length W, naive binary search would take O(W*log N); we show how to reduce this to O(W+log N) using multiple-column binary search. Measurements using a practical (Mae-East) database of 38000 entries yield a worst-case lookup time of 490 ns, five times faster than the Patricia trie scheme used in BSD UNIX. Our scheme is attractive for IPv6 because of its small storage requirement (2N nodes) and speed (estimated worst case of 7 cache line reads per lookup). <s> BIB001 </s> Survey and taxonomy of ip address lookup algorithms <s> Prefix Range Search <s> In this paper, we introduce a new IP lookup scheme with worst-case search and update time of O(log n), where n is the number of prefixes in the forwarding table. Our scheme is based on a new data structure, a multiway range tree. While existing lookup schemes are good for IPv4, they do not scale well in both lookup speed and update costs when addresses grow longer as in the IPv6 proposal. Thus our lookup scheme is the first lookup scheme to offer fast lookups and updates for IPv6 while remaining competitive for IPv4. <s> BIB002
A search on values only, to find the longest matching prefix, is possible if we can get rid of the length dimension. One way of doing so is to transform the prefixes to a unique length. Since prefixes are of arbitrary lengths, we need to do a full expansion, transforming all prefixes to 32-bit-length prefixes in the case of IPv4. While a binary search on values could be done now, this approach needs a huge amount of memory. Fortunately, it is not necessary to store all of the 2 32 entries. Since a full expansion has been done, information redundancy exists. A prefix represents an aggregation of contiguous addresses; in other words, a prefix determines a well-defined range of addresses. For example, supposing 5-bit-length addresses, prefix a = 0* defines the range of addresses [0, BIB002 . So why not simple store the range endpoints instead of every single address? The BMP of the endpoints is, in theory, the same for all the addresses in the interval; and search of the BMP for a given address would be reduced to finding any of the endpoints of the corresponding interval (e.g., the predecessor, which is the greatest endpoint smaller than or equal to a given address). The BMP problem would be readily solved, because finding the predecessor of a given address can be performed with a classical binary search method. Unfortunately, this approach may not work because prefix ranges may overlap (i.e., prefix ranges may be included in other prefix ranges; Fig.  4 ). For example, Fig. 19 shows the full expansion of prefixes assuming 5-bit-length addresses. The same figure shows the endpoints of the different prefix ranges, in binary as well as decimal form. There we can see that the predecessor of address value 9, for instance, is endpoint value 8; nevertheless, the BMP of address 9 is not associated with endpoint 8 (b), but with endpoint 0 (a) instead. Clearly, the fact that a range may be contained in another range does not allow this approach to work. One solution is to avoid interval overlap. In fact, by observing the endpoints we can see that these values divide the total address space into disjoint basic intervals. In a basic interval, every address actually has the same BMP. Figure 19 shows the BMP for each basic interval of our example. Note that for each basic interval, its BMP is the BMP of the shortest prefix range enclosing the basic interval. The BMP of a given address can now be found by using the endpoints of the basic intervals. Nevertheless, we can observe in Fig. 19 that some basic intervals do not have explicit endpoints (e.g., I 3 and I 6 ). In these cases, we can associate the basic interval with the closer endpoint to its left. As a result, some endpoints need to be associated to two basic intervals, and thus endpoints must maintain in general two BMPs, one for the interval they belong to and one for the potential next basic interval. For instance, endpoint value 8 will be associated with basic intervals I2 and I3, and must maintain BMPs b and a. Figure 20 shows the search tree indicating the steps of the binary search algorithm. The leaves correspond to the endpoints, which store the two BMPs (= and >). For example, if we search the BMP for address 10110 (22), we begin comparing the address with key 26; since 22 is smaller than 26, we take the left branch in the search tree. Then we compare 22 with key 16 and go to the right; then at node 24 we go to the left arriving at s Figure 19 . Binary range search. (22) is greater than 19, the BMP is the value associated with > (i.e., d). As for traditional binary search, the implementation of this scheme can be made by explicitly building the binary search tree. Moreover, instead of a binary search tree, a multiway search tree can be used to reduce the height of the tree and thus make the search faster. The idea is similar to the use of multibit tries instead of binary tries. In a multiway search tree, internal nodes have k branches and k -1 keys; this is especially attractive if an entire node fits into a single cache line because search in the node will be negligible compared to normal memory accesses. As previously mentioned, the BMP for each basic interval needs to be precomputed by finding the shortest range (longest prefix) enclosing the basic interval. The problem with this approach, which was proposed by Lampson et al. BIB001 , is that inserting or deleting a single prefix may require recomputing the BMP for many basic intervals. In general, every prefix range spans several basic intervals. The more basic intervals a prefix range covers, the higher the number of BMPs to potentially recompute. In fact, in the worst case we would need to update the BMP for N basic intervals, N as usual being the number of prefixes. This is the case when all 2N endpoints are different and one prefix contains all the other prefixes. One idea to reduce the number of intervals covered by a prefix range is to use larger, yet still disjoint, intervals. The leaves of the tree in Fig. 20 correspond to basic intervals. A crucial observation is that internal nodes correspond to intervals that are the union of basic intervals (Fig. 21) . Also, all the nodes at a given level form a set of disjoint intervals. For example, at the second level the nodes marked 12, 24, and 28 correspond to the intervals [0, BIB002 ,  25] , and [26, 29] , respectively. So why store BMPs only at leaves? For instance, if we store a at the node marked 12 in the second level, we will not need to store a at leaves, and update performance will be better. In other words, instead of decomposing prefix ranges into basic intervals, we decompose prefix ranges into disjoint intervals as large as possible. Figure 21 shows how prefixes can be stored using this idea. Search operation is almost the same, except that now it needs to keep track of the BMP encountered when traversing the path to the leaves. We can compare the basic scheme to using leaf pushing and the new method to not doing so. Again, we can see that pushing information to leaves makes update difficult, because the number of entries to modify grows. The multiway range tree approach BIB002 presents and develops this idea to allow incremental updates.