SkipTrie: Fast IPv6 Lookup with Sub-Trie Skipping

摘要

IP route lookup, a critical function in routers, switches, and cloud gateways, directly determining packet forwarding performance. However, IPv6 lookup faces significant performance challenges compared to IPv4 due to longer addresses and rapidly expanding Forwarding Information Bases (FIBs), resulting in slower speeds and higher memory consumption. Existing trie-and hash-based solutions fail to holistically accelerate lookup speed and reduce memory footprint.This paper introduces SkipTrie, a novel IPv6 route lookup scheme addressing these challenges through an innovative multi-bit trie search framework. SkipTrie employs sub-trie skipping that promotes indices of child nodes to their ancestors, eliminating intermediate node accesses during the tree traversal. This effectively increases search stride while reducing computation and memory accesses. Furthermore, to maximize stride with minimal per-node storage, SkipTrie features a node compression technique. This exploits the inherent sparsity of tries representing IPv6 FIBs, and leverages a dynamic programming algorithm to automatically select optimal node configurations. Extensive evaluation with FIBs from backbone and cloud networks demonstrates that SkipTrie is 1.5 ∼ 5.2× faster than state-of-the-art alternatives. In addition, it maintains excellent scalability across diverse FIB sizes, future FIB growth, and multi-core systems.