Scalable GPU-Accelerated IPv6 Lookup Using Hierarchical Perfect Hashing

IPv6 has been proposed to fulfil the increasing demand of IP addresses. As the data rate and volume of network traffic keep increasing and the Internet evolves, high-speed IPv6 lookup for large routing tables is essential. In this paper, we propose a novel IPv6 lookup approach based on hierarchical perfect hashing. The lookup complexity of the proposed algorithm is O(1) in the worst case. The performance is independent of the prefix distribution or the size of the routing table. Each lookup is performed by examining up to 3 perfect hash tables. Each hash table uses a range of bits of the input IP address as lookup key. We develop a simple scheme to choose appropriate key length for each hash table, which can efficiently reduce the total memory requirement. We implement our design on a state- of-the-art Compute Unified Device Architecture (CUDA) platform. Experimental results show that our GPU-accelerated lookup engine is scalable to sustain a high throughput of over 1.6 billion lookups per second (GLPS) for routing tables from 10K to 1M. This corresponds to 80% of the peak throughput of the target platform. Compared with a state-of-the-art GPU-based IPv6 lookup engine, our design demonstrates 2x improvement with respect to throughput for large tables.