Abstract-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. The possibility of a global Internet with addressable appliances has motivated a proposal to move from the older Internet Ipv4 routing protocol with 32 bit addresses to a new protocol, IPv6 with 128 bit addresses. While there is uncertainty about IPv6, any future Internet protocol will require at least 64 bit, and possibly even 128 bit addresses as in IPv6. Thus for this paper we simply use IPv6 and 128 bits to refer to the next generation IP protocol and its address length. Our paper deals with address lookup, a key bottleneck for Internet routers. Our paper describes the first IP lookup scheme that scales well as address lengths increase as in IPv6, while providing fast search times and fast update times. There are four requirements for a good lookup scheme: search time, memory, scalability, and update time. Search time is important for lookup to not be a bottleneck. Schemes that are memory-efficient lead to faster search because compact data structures fit in fast but expensive Static RAM. Scalability in both number of prefixes and address length is important because prefix databases are growing, and a switch to IPv6 will increase address prefix lengths. Finally, schemes with fast update time are desirable because i) instabilities in backbone protocols [4] can cause rapid insertion and deletion of prefixes. ii) multicast forwarding support requires route entries to be added as part of the forwarding process and not by a separate routing protocol iii) Any lookup scheme that does not support fast incremental updates will require two copies of the lookup structure in fast memory, one for updates and one for lookup. The main drawback of existing lookup schemes is their lack of both scalability and fast update. Current IP lookup schemes come in two categories: those that use precomputation, and those that do not. Schemes like "binary search on prefix lengths" [9] , "Lulea compressed tries" [1], or "binary search on intervals" [5] perform precomputation to speed up search; however, adding a prefix can cause the data structure to be rebuilt. Thus, precomputation-based schemes have a worst-case update time of (n). On the other hand, triebased schemes (e.g., [8] , [7] ) do not use precomputation; however, their search time grows linearly with the prefix length. We introduce a new IP lookup scheme whose worst-case search and update time is 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, which achieves the optimal lookup time of binary search, but can also be updated fast when a prefix is added or deleted. (By contrast, ordinary binary search [5] is a precomputation-based scheme whose worst-case update time is (n).) Our main contribution is to modify binary search for prefixes to provide fast update times. In standard binary search [5] , each prefix maps to an address range. A set of n prefixes partition the address line into at most 2n intervals. We build a tree, whose leaves correspond to interval endpoints. All packet headers mapped to an interval have the same longest prefix match. Search time is O(log n). The problem is update: a prefix range can be split into (n) intervals, which need to be updated when the prefix is added or deleted. Thus our first idea is associating an address span with every tree node v; the span of v is the maximal range of addresses into which the final search can fall after reaching v. Thus the root span is the entire address range. We then associate with every node v the set of prefixes that contain the span of v. However, this results in storing redundant prefixes. To remove this redundancy, we store a prefix with a node v if and only if the same prefix is not stored at the parent w of the node. Since the span of v is a subrange of the span of w, any prefix that contains the span of w, will contain the span of v. Using this compression rule we can prove that only a small number of prefixes need be precomputed and stored; thus updates change information only at O(log n) nodes. By increasing the arity of the tree, we can reduce the height of the tree to O(log d n), for any integer d. We pick d so that the entire node can fit in one cache line. For instance, a 256 bit cache line and arity-14 yields a tree height of about 5 or 6 for the largest IPv4 databases. Our third contribution is to extend multiway range trees to IPv6. On a 32-bit machine, a single 128-bit address will require 4 memory accesses. Thus, an IP lookup scheme designed for IPv4 could slow down by a factor of 4 when used for IPv6. In practice, since we are assuming wide memories of at least 128 bits, we can handle such wide prefixes in one memory access. Unfortunately, the use of 128 bit addresses result in the use of a small branching factor and hence large tree heights. To avoid this problem, we generalize our scheme 0-7803-7206-9/01/$17.00
The search time of oðlog m NÞ can be achieved in a tree of degree m. In REF , a B-tree-based MRT is proposed to find the longest matching prefix in oðlog m NÞ time, and insert or delete a prefix in oðm log m NÞ time.
Multiway range trees: scalable IP lookup with fast updates
GLOBECOM'01. IEEE Global Telecommunications Conference (Cat. No.01CH37270)
GLOBECOM'01. IEEE Global Telecommunications Conference (Cat. No.01CH37270)
Computer Science