The advent of Software Defined Networking (SDN) and Network Function Virtualization (NFV) has revolutionized the deployment of software-based routing and forwarding devices in cloud and network systems. Yet, the performance of IPv6 route lookup in these devices remains a significant challenge due to two main factors: 1) the longer IPv6 addresses, which hinder high-speed lookup, and 2) the huge IPv6 IP address space, necessitates adaptability to varied length-based prefix distributions across various network scenarios. Existing IP lookup algorithms fall short in addressing these IPv6-specific challenges. To address these challenges, this paper proposes a novel Heuristic Binary Search (HBS) scheme. Building on the classical “Binary Search on Prefix Lengths” scheme, HBS employs three innovative techniques to achieve adaptive and fast IPv6 lookups with incremental updates: 1) a heuristic binary search method for fast lookup; 2) a tree rotation method for dynamic adjustment of binary search tree shapes in response to changes in prefix distribution; and 3) the introduction of the Associated Marker List (AML), a new data structure aimed at facilitating rapid incremental prefix updates. Our theoretical proofs and comprehensive evaluations demonstrate HBS’s superiority in lookup performance, dynamic adaptability, update speed, and memory efficiency.
1 January 2026 in IEEE Transactions on Network and Service Management
Packet classification is a fundamental operation in modern network systems, playing a central role in traffic management, security enforcement, and policy execution. While traditional algorithms have achieved low lookup latency in static scenarios, emerging applications impose more demanding requirements—not only fast lookup, but also high-frequency online updates and strong scalability. Existing approaches often struggle to handle large rule sets or support rules with an increasing number of matching fields, making them unsuitable for dynamic and large-scale network environments. In this work, we propose TupleChain for fast on-line update table lookup with multifaceted scalability. We group rules based on their masks, each maintained using a hash table, and explore the connections among rule groups to skip unnecessary hash probes for faster searches. We show via theoretical analysis and extensive experiments that the proposed scheme offers competitive computational complexity, strong scalability, and high performance in both search and update operations. TupleChain can process millions of packets per second, while simultaneously handling millions of on-line updates per second at the same time, and its lookup speed remains stable even when processing large flow table with 10 million rules or entries containing up to 100 match fields.