High Speed Routing Table Lookups for Current and Next Generation Internet Routing

This dissertation develops a new and efficient method of routing table lookups for the current and next generation Internet Protocols (IP). A router performs a table lookup to determine the next hop address on a data packet\u27s path to its destination host. Next hop data is aggregated on variable-length prefixes that are derived from a destination host\u27s network and sub-network (subnet) identifiers based on the Classless Inter-Domain Routing (CIDR) strategy. Since CIDR prefix length is arbitrary, a longest matching prefix (LMP) search must be performed to determine the next hop. Conventional search techniques do not work well for LMP search. However, if lookups are not done efficiently, a bottleneck develops at the router, and the performance of the network is degraded. Although research into lookup strategies has progressed over the last decade, no method has been proven to perform well for both current IP routing, IP version 4 (IPv4), and next generation IP (IPng or IPv6). Furthermore, most researchers ignore dynamic updates to the routing table and their effect on the actual throughput rate. The method advanced in this dissertation is based in software, scales well with regards to the length of the address, and supports multi-gigabit routing even with updates included. To achieve this notable improvement, an original scheme called PHASE, for perfect hashing across segmented expansions, was constructed. PHASE stores prefixes in a hierarchy of segment tables, partitioning each prefix into discrete segments. The algorithm expands each segment such that every segment in a table is of uniform length. A search progresses by segmenting the target address and using single-displacement perfect hashing to perform lookups across the segment tables. The result is a bounded worst-case performance of two accesses for IPv4 and eight accesses for IPv6. The IPv6 worst-case is comparable to that of some contemporary IPv4 techniques. Additionally, PHASE provides a dynamic update method that performs two orders of magnitude better than other suggested techniques, and eliminates memory fragmentation