  Due to the emergence of new network applications, current IP lookup engines
must support high-bandwidth, low lookup latency and the ongoing growth of IPv6
networks. However, existing solutions are not designed to address jointly those
three requirements. This paper introduces SHIP, an IPv6 lookup algorithm that
exploits prefix characteristics to build a two-level data structure designed to
meet future application requirements. Using both prefix length distribution and
prefix density, SHIP first clusters prefixes into groups sharing similar
characteristics, then it builds a hybrid trie-tree for each prefix group. The
compact and scalable data structure built can be stored in on-chip low-latency
memories, and allows the traversal process to be parallelized and pipelined at
each level in order to support high packet bandwidth. Evaluated on real and
synthetic prefix tables holding up to 580 k IPv6 prefixes, SHIP has a
logarithmic scaling factor in terms of the number of memory accesses, and a
linear memory consumption scaling. Using the largest synthetic prefix table,
simulations show that compared to other well-known approaches, SHIP uses at
least 44% less memory per prefix, while reducing the memory latency by 61%.

Data Structures and Algorithms