Xiaojun Nie and Yiqiang Q. Zhao, Carleton University

TITLE: IPv6 Routing Table Lookup and Packet Classification

Abstract: Next generation network Internet Protocol version 6 (IPv6) is
designed to provide more advanced features than current IPv4 does, such as
simplified header architecture, built-in security, true mobility, and
address auto-configuration. However, IPv6 cannot solve all problems of
IPv4, such as IP lookup and packet classification in the packet
forwarding. In IPv6 packet headers, source and destination addresses are
128-bit long, four times longer than ones in IPv4, which not only increase
the demand for memory access in lookup and packet classification, but also
enlarge the size of the routing table or the rule table as more and more
IP addresses are assigned.  This unsettled issue can be solved by
designing high performance and cost efficient search schemes. This talk
presents an IP lookup scheme that speeds up the search rate and reduces
the memory requirement by deploying small amount fast on-chip memory such
as SRAM and efficient data structure, dynamic hash tables. The key
technique in this approach is to predict the search key length by
employing a mathematical model. A packet classification algorithm that
reduces the high-dimensional classification into a simpler lower or one
dimensional search by using bit characteristics is also introduced in the
talk.