name: A. J. McAuley title: Algorithms and Architectures for Fast Hierarchical Routing Table Lookup affiliation: Bellcore postal address: MCC 1B248B, Bellcore, 445 South Street, Morristown, NJ 07960 email address: mcauley@bellcore.com phone: +1 201 829 4698 fax: +1 201 829 2504 Algorithms and Architectures for Fast Hierarchical Routing Table Lookup ----------------------------------------------------------------------- The Next Generation Internet will have high speed forwarding engines. An important factor of these forwarding engines, is the speed and cost of doing route table lookup on unicast and multicast hierarchical IPv4 and IPv6 addresses. Although searching a database for an exact match is a well studied problem, more research is needed on search algorithms and architectures for the best software and hardware solutions for hierarchical routing table lookup. Importance ---------- Whether forwarding engines in the Next Generation Internet (NGI) will be Multigigabit routers, IP switches, Tag Switches, or ATM switches is currently unclear. There is no technical reason why the NGI forwarding engines cannot be Multigigabit IP routers. The Multigigabit Router (MGR) project at BBN, for example, has 50Gb/s of internal bandwidth. It is, however, cheaper to build products like IP switches, Tag Switches, or ATM switches, because the do not require IP processing for every IP packet. A key aspect of the choice among these alternatives is the speed and cost of doing route table lookup on hierarchical IPv4 and IPv6 addresses. As part of the larger question of which approach to forwarding engines is best, it is important to quantify the speed and cost of one important factor in IP processing: doing route lookup on hierarchical IP addresses (especially with IPv6). Current Approaches to Hierarchical Routing Table Lookup ----------------- -------------------------------------- Hierarchical addresses allow backbone routing tables to grow only logarithmically with the number of users instead of linearly as they would with flat addresses. Thus, Table 1 shows a simplified phone network routing table, with the "X" digit being a wild card (any digit matches that position). Address Next Hop ------------ -------- 201-829-XXXX Port A 201-876-XXXX Port B 201-XXX-XXXX Port C 908-XXX-XXXX Port D XXX-XXX-XXXX Port E TABLE 1 EXAMPLE ROUTING TABLE Unfortunately, although hierarchical addresses reduce routing table size (as has been seen with the introduction of CIDR), routing lookup becomes harder than with the same sized flat addresses. Route lookup requires searching a database for the "best" match. The input to a route lookup function is a packet's destination address, possibly with other information such as source address and QOS information. The output of the lookup function specifies where to send the packet and possibly other information such as what QOS to provide. Searching for an exact match in a table is a well studied problem. Knuth [1] describes solutions based on binary searching of a sorted list, index lookup (trie, patricia tree), and hashing. More recently, Content Addressable Memories (CAMs) have been proposed. Hierarchical addresses need two modifications to basic searching. First, we must allow wildcard digits that are don't cares in a search (usually we restrict the wildcards to a contiguous series starting at the least significant digit (e.g., see Table 1). Second, there can be multiple matches to the same search string, and so the matches must be prioritized. Thus, a packet with address 201-829-4698 matches three of the entries in Table 1 (201-829- XXXX, 201-XXX-XXXX, and XXX-XXX-XXXX). The best match is the one that matches on the most digits; thus the 201-829-XXXX represents the best route, and perhaps the only correct route. Possible Alternatives --------------------- Many existing solutions can do lookup of W bit addresses with H (H <= W) levels of hierarchy from a routing table with N entires. Many solutions, however, require worst case search time of O(log N) or O(H) [2], that is unacceptable for high speed networking. A modified hashing scheme requires O(log H) search time, but requires slow insertion and deletion time and requires O(N.W) memory words. A ternary CAM can, incredibly, offer O(1) search time with just O(N) memory words, but requires slow insertion and deletion times [3]. Adding a sorting (priority) mechanism could eliminate the slow insertion and deletion times but would add significant additional hardware costs. As a piece of specialized piece of hardware, however, the CAM would not keep pace with processor and RAM improvements. The best solution will clearly depend a lot on factors that are still uncertain: such as how much traffic will be multicast, how strict will the hierarchy be in IPv6, and how much (user and router) mobility will exist. It is important therefore not to simply look at one possible solution in isolation, but to look at the overall search problem and quantify the pros and cons of the different solutions (much as was done by Knuth for exact searches). Factors would include speed (search time, insertion time, deletion time) and cost (when implemented in a general purpose processor with RAM or when implemented as a dedicated piece of hardware). References ---------- [1] D. E Knuth, "The Art of Computer Programming Volume 3: Sorting and Searching," Addison Wesley, 1973. [2] R. Perlman, "Inteconnections, Bridges and Routers," Addison Wesley, 1992. [3] A. McAuley & P. Francis, "Fast Routing Table Lookup Using CAMs," Proceeding of INFOCOM, pp. 1382-1391, March-April 1993.