Abstract
NAT gateway is an important network system in today's IPv4 network when translating a private IPv4 address to a public address. However, traditional NAT system based on Linux Netfilter cannot achieve high network throughput to meet modern requirements such as data centers. To address this challenge, we improve the network performance of NAT system by three ways. First, we leverage DPDK to enable polling and zero-copy delivery, so as to reduce the cost of interrupt and packet copies. Second, we enable multiple CPU cores to process in parallel and use lock-free hash table to minimize the contention between CPU cores. Third, we use hash search instead of sequential search when looking up the NAT rule table. Evaluation shows that our Quick NAT system significantly improves the performance of NAT on commodity platforms.
Introduction
Quick NAT is a high-performance Network Address Translation (NAT) system designed to overcome the throughput bottlenecks of traditional Linux-based systems. By leveraging DPDK for user-space processing and a novel $O(1)$ search algorithm called QNS, it achieves constant-time rule lookups, making it capable of handling the high-speed demands of modern 10G/100G data center environments.
Despite the push for IPv6, IPv4 remains dominant, making NAT a critical technology for managing address exhaustion. However, traditional NAT implementations—specifically those built on the Linux Netfilter framework—struggle to keep up with modern hardware. The authors identify three primary bottlenecks in standard NAT: kernel overhead from interrupts and packet copying, search inefficiency due to linear rule lookups ($O(N)$), and multi-core contention caused by locking mechanisms. On commodity servers, these issues often limit NAT throughput to less than 1Gbps for small packets, creating a massive gap between software performance and 10G/100G hardware capabilities.
System Architecture and Methodology
The researchers built Quick NAT using three core architectural improvements:
- DPDK Integration: By using the Data Plane Development Kit (DPDK), Quick NAT bypasses the Linux kernel entirely. It uses "polling" instead of interrupts and "zero-copy" delivery (manipulating packets via pointers) to eliminate the overhead of moving data across the kernel-user boundary.
- The QNS (Quick NAT Search) Algorithm: This is the primary algorithmic contribution. Instead of one giant table, Quick NAT uses 64 small hash tables (32 for DNAT and 32 for SNAT), categorized by subnet mask length. It searches these tables in order of decreasing mask length (most specific to least specific). Because it uses hashing, the lookup within each table is $O(1)$.
- Lock-free Parallelism: To utilize modern multi-core CPUs, the system uses Receive-side Scaling (RSS) to distribute traffic. It employs a lock-free hash table for connection records, allowing multiple cores to share data without the performance penalty of traditional mutexes or locks.
Key Insights
- The Power of "No": Each small NAT rule table includes a single-bit flag indicating if it contains any rules. If the flag is zero, the system skips that table entirely without performing a hash calculation, significantly speeding up the search process for sparse rule sets.
- Constant Time vs. Linear Time: By restructuring the search into a series of hash lookups based on prefix length, the authors turned a scaling problem into a constant-time operation.
- User-Space is King: The results reinforce the trend in high-performance networking that moving the data plane out of the general-purpose OS kernel is essential for hitting 10Gbps+ speeds.
Evaluation and Results
The evaluation focused on the efficiency of the QNS algorithm compared to the standard Netfilter linear search. The paper uses a controlled experimental testbed with Wind River’s DPDK-pktgen for traffic generation and Intel 10G Dual Port NICs.
The QNS algorithm maintained a near-constant lookup time of approximately 43–45 nanoseconds, regardless of whether there were 100 rules or 10,000 rules. In contrast, Netfilter’s linear search performance degraded sharply as rules were added. At 10,000 rules, Netfilter took 30,120 ns per lookup—roughly 700 times slower than Quick NAT. These results confirm that QNS achieves $O(1)$ complexity for rule lookups, whereas traditional methods are $O(N)$.
Conclusion and Future Work
While Quick NAT demonstrates a massive improvement in rule lookup time, there are areas for further exploration. The current evaluation provides less detail on aggregate system throughput (Gbps) or packets-per-second (PPS) under complex, stateful traffic patterns involving millions of concurrent connections. Additionally, the system is heavily optimized for Intel-based commodity platforms using DPDK; its portability to other architectures is not discussed. Future work could also explore the overhead of updating or adding rules to these 64 distributed hash tables in real-time.
Summary updated