TupleChain: Fast Flow Table Lookup With Efficient On-Line Updates and Scalability

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.