Title : NPC: Rethinking Dataplane through Network-aware Packet Classification
Authors : Xinyi Zhang, Qianrui Qiu (Computer Network Information Center, CAS; University of Chinese Academy of Sciences); Zhiyuan Xu (University of Chinese Academy of Sciences); Peng He (Independent Researcher); Xilai Liu (Institute of Computing Technology, CAS; University of Chinese Academy of Sciences); Kavé Salamatian (LISTIC; Université Savoie Mont Blanc) ; Changhua Pei, Gaogang Xie (Computer Network Information Center, CAS; University of Chinese Academy of Sciences)
Scribe: Xuanhao Liu(Xiamen University)
Introduction
The efficiency of packet classification is a critical problem. This issue is important and interesting because packet classification serves as the cornerstone for building key network functions such as virtual switches, firewalls, and Network Intrusion Detection Systems (NIDS). Its performance directly dictates the processing capability of the entire network. As network scale and complexity grow, classification rulesets become increasingly large and are updated more frequently, presenting significant challenges to existing classification algorithms. Current software solutions primarily focus on optimizing data structures (like decision trees or hash tables) based on the static characteristics of the ruleset. However, they generally overlook a crucial factor: the dynamic characteristics of actual network traffic. Real-world network traffic distribution is highly skewed and follows the Pareto principle, meaning a few “elephant flows” constitute the vast majority of traffic. Existing systems have failed to fully leverage this property to optimize the classification process, thereby limiting their performance potential.To address this issue, this paper revisits the network dataplane by integrating the network measurement module with the packet classification module and proposes an innovative Network-aware Packet Classification (NPC) system. This system utilizes sketch techniques to extract network traffic features, which then guide the construction of decision trees, enabling efficient and adaptable packet classification across diverse network environments.
Key idea and contribution :
NPC (Network-aware Packet Classification) is an innovative system. Its core idea is to deeply integrate the traditional network measurement module with the packet classification module to create a unified framework that can simultaneously perceive both ruleset characteristics and traffic dynamics. To achieve this, a new type of decision tree called TRD-Tree (Traffic-Rule Dual-driven packet classification data structure) was designed.
The construction process of the TRD-Tree incorporates traffic-aware capabilities in several key steps:
Dimension Selection: When constructing each node of the decision tree, the system selects the optimal dimension for partitioning by comprehensively evaluating two metrics: first, the degree of rule overlap to reduce memory consumption, and second, the uniformity of traffic distribution along that dimension to create a more balanced tree, thereby reducing the average lookup depth.
Splitting Point / Number of Cuts Selection: For splitting-based algorithms, the TRD-Tree chooses a splitting point that balances both traffic and rule distribution. For cutting-based algorithms, it dynamically determines the number of cuts based on the node’s “popularity” (i.e., traffic access frequency)—applying more cuts to high-traffic nodes to accelerate lookups and fewer cuts to low-traffic nodes to save memory.
Dynamic Leaf Node Threshold: The system sets a dynamic leaf node threshold for each node. For nodes with dense traffic, a smaller threshold is applied to reduce the overhead of linear searches. Conversely, for nodes with sparse traffic, a larger threshold is used to consolidate more leaf nodes, thus conserving memory.
Furthermore, the NPC system includes an attack-aware updater module that continuously monitors changes in traffic and rules, dynamically rebuilding the decision tree when necessary. This module can also distinguish between normal traffic fluctuations and malicious attack traffic (such as DDoS attacks), which prevents unnecessary system updates and ensures the stability and robustness of the system.
Evaluation
The authors conducted a comprehensive evaluation of the NPC system on a dual-server platform equipped with 100G NICs, comparing it against several state-of-the-art algorithms (such as HyperSplit, HiCuts, EffiCuts, etc.). The experiments utilized IPv4 and IPv6 rulesets and traffic generated by the ClassBench tool, covering various application scenarios (ACL, FW, IPC).
The experimental results showed that the NPC system has significant performance advantages:
Lookup Performance: In terms of average memory accesses, NPC achieved a performance improvement of 1.86 to 23.88 times compared to other algorithms.
System Overhead: While significantly improving lookup speed, NPC also effectively reduced memory footprint and data structure construction time.
Dynamic Adaptability: The experiments demonstrated that when network traffic patterns change, NPC can rapidly adapt through its dynamic update mechanism and consistently maintain performance superior to other algorithms. At the same time, its attack-aware mechanism can effectively defend against malicious traffic attacks.
Practical Application: After integrating NPC into the mainstream open-source virtual switch, Open vSwitch (OVS), the system’s throughput improved by 10.71 to 13.01 times compared to the native OVS.
This result is significant because it proves that by enabling the packet classification system to “perceive” real-world traffic patterns, it is possible to achieve an order-of-magnitude performance improvement on general-purpose CPU platforms without relying on expensive specialized hardware. This finding challenges the traditional optimization approach that focuses solely on the static characteristics of rulesets, opening up a more comprehensive and efficient new direction for network dataplane performance optimization.
Q : As you mentioned, when comparing the speedup for IPv4 and IPv6, it seems the performance improvement for IPv6 is significantly less than for IPv4. Do you have any insights as to why that is?
A : I believe this is caused by the dataset we use. The dataset for IPv6 is smaller, and the performance is highly dependent on the characteristics of the rule set. Therefore, the improvement may differ across various datasets.
Q：For the dataset used in your evaluation, where does the traffic come from? Is it synthetic, or is it from real-world captured traces?
A：The traffic we use is derived from the rule dataset. Much like ClassBench, it includes a tool to generate traffic based on the rule set. We can also use different parameters to adjust the locality of the traffic. So, the traffic used in our evaluation is also sourced from the dataset we use.
Personal thoughts
The merits of this paper lie in its clear approach, complete design, and comprehensive evaluation. It innovatively introduces traffic characteristics into the classification structure’s design, accurately addressing a blind spot in existing research and demonstrating its effectiveness through thorough experiments. The authors not only proposed the core TRD-Tree algorithm but also built a complete NPC system around it, including mechanisms for dynamic updates and attack defense. In particular, its integration with Open vSwitch greatly enhances the practical significance and credibility of the work. Furthermore, the evaluation, which covers multiple dimensions such as performance, overhead, and dynamic adaptability, makes the conclusions very solid and reliable.
Nevertheless, the research still has aspects that merit further discussion and improvement. First, the key parameters pfac and spfac must be set manually; a future mechanism to automatically adjust them based on system load would make the system more intelligent and robust. Second, the paper does not deeply explore the specific overhead of module deployment. The processing bottleneck of the traffic measurement module itself, especially in ultra-high-speed network environments, is a critical issue for practical implementation. Future directions worth exploring include combining the system with AI techniques like reinforcement learning to dynamically optimize the decision tree construction process, and researching how to adapt the system to the growing prevalence of encrypted traffic (like QUIC), which might be achieved by analyzing metadata features such as traffic volume and timing.