HybridCuts: A Scheme Combining Decomposition and Cutting for Packet Classification (IEEE Hot Interconnects 2013)

Abstract

Multi-field packet classification is not only an indispensable and challenging functionality of existing network devices, it also appears as flow tables lying at the heart of the forwarding plane of Software Defined Networking (SDN) age. Software based algorithmic approaches, such as decision-tree and decomposition, have been well studied for almost twenty years. But most of them are still memory and performance inefficient, falling short of the needs of high-speed networks. In this paper, we propose a decomposition-based cutting scheme called HybridCuts, which can improve storage and performance simultaneously. The decomposition part of HybridCuts can leverage the parallelism offered by modern hardware as traditional decomposition techniques, but without the trouble of aggregating results from a large number of bit vectors or a set of big lookup tables. Meanwhile, thanks to the clever partitioning of the rule set, a hybrid cutting algorithm following the decomposition can build short decision trees with significant reduction on rule replications. Our experimental results show that using ClassBench, HybridCuts achieves similar memory reduction compared to EffiCuts, a well-known memory efficient decision-tree, but it outperforms EffiCuts significantly in terms of memory accesses for packet classification.

Motivations

In this paper, we make a set of important observations on rule sets. Based on these novel observations, we can not only partition rules into a very few subsets, but also build simple and effective trees for each subset.

Observations1:

The vast majority of the rules have at least one small field.(e.g., ACL-10K, FW-10K, IPC-10K)

More results can refer to: SEED-ACL, SEED-FW, SEED-IPC, ACL-1K, FW-1K, IPC-1K, ACL-100K, FW-100K, IPC-100K

Observations2:

The vast majority of the rules have at least one small address field.(e.g., ACL-10K, FW-10K, IPC-10K)

More results can refer to: SEED-ACL, SEED-FW, SEED-IPC, ACL-1K, FW-1K, IPC-1K, ACL-100K, FW-100K, IPC-100K

Proposed HybridCuts:

Based on above observations, we propose a new decomposition-based partition algorithm to separate rules into a few subsets. This decomposition produces only N+1 subsets for a N-tuple rule set, much smaller than that 2^N-1 in EffiCuts. In fact, for typical 5-tuple rule sets, since we do not consider protocol dimension, just 5 subsets will be generated in our baseline algorithm, and this number is further reduced to 3 with an optimization. The rationale behind this strategy of decomposition is simple: by grouping rules that are small in the same field, we get a dimension in the space where the extensive replications bothering traditional cutting-based algorithms by wide overlaps are significantly reduced. In addition, subsets decomposed this way enable a simple and space-efficient one-dimensional cutting algorithm, which is called FiCuts(Fixed intelligent Cuttings) in this paper. Thus, compared to existing techniques, our work can result in more close collaboration between partitioning and decision-tree construction.

Downloads

• Paper
• Source Code

News

2017.07.05: The Source Code and Reference of this paper have been uploaded;

Contact

My Contact Info: wenjunli@pku.org.cn, wenjun0816@qq.com;