Building shape-shifting tries for fast IP lookup

Abstract

[ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI AT AUTHOR'S REQUEST.] The Internet Protocol (IP) is a protocol used to communicate data over packet-switched internet works. The currently deployed version of the Internet Protocol is IPv4. It provides a 32-bit address space which can at most address four billion nodes. IPv6, the new version of the Internet Protocol, provides a 128-bit address space which can at most address 3.4 x 10[superscript 38] nodes. An Internet router can forward incoming Internet packets by looking up their IP destination address in a routing table which then determines the output link on which the packet is sent. To achieve a competitive advantage, many routers today choose to do additional processing for a specific subset of packets, which requires that routers are able to classify packets based on packet header into corresponding classes or so-called flows. A router doing packet classification maintains a database containing rules one of which is for a certain type of flows. When a packet arrives at a router, the router look up the rule database and find a rule that matches the incoming packet headers and take corresponding actions associated to this rule. Most data structures for packet forwarding are optimized for IPv4, and less capable of handling IPv6 routing tables. Shape Shifting Trie (SST) is specifically designed to be scalable to IPv6. To reduce the worst case lookup time that is proportional to the height of SST, it is desirable to construct a minimumheight SST. Breadth-First Pruning (BFP) algorithm takes O(n[superscript 2]) time to construct a minimumheight SST, where n is the number of nodes in the binary trie corresponding to the routing table. In this thesis, we propose a Post-Order Minimum- Height Pruning (POMHP) algorithm that takes only O(n) time to construct a minimum-height SST. We further propose nodes merging algorithm to cut down SST size without affecting SST height.