Memory‐efficient recursive scheme for multi‐field packet classification
Open Access
- 1 June 2019
- journal article
- research article
- Published by Institution of Engineering and Technology (IET) in IET Communications
- Vol. 13 (9) , 1319-1325
Abstract
Multi‐field packet classification is not only an indispensable and challenging functionality of existing network devices, but it also appears as flow tables lying at the heart of the forwarding plane of software defined networking age. Despite almost two decades of research, algorithmic solutions still fall short of meeting the line‐speed of high‐performance network devices. Although decomposition‐based approaches, such as cross‐producting and recursive flow classification (RFC), can achieve high lookup rate by performing a parallel search on chunks of the packet header, both of them suffer from memory explosion problem during aggregation. In this study, the authors propose an HybridRFC, a memory‐efficient recursive scheme for multi‐field packet classification. By addressing the embedded problem of the RFC caused by uncontrollably expanded cross‐product tables, HybridRFC can not only reduce the memory consumption to a practical level but also improve pre‐processing performance significantly. Experimental results show that the memory requirement of HybridRFC is two orders of magnitude less than RFC, as well as three orders of speed‐up on the performance of table building on average.Keywords
Funding Information
- National Natural Science Foundation of China (61671001)
This publication has 30 references indexed in Scilit:
- Lossy compression of packet classifiers2015
- Optimal In/Out TCAM Encodings of RangesIEEE/ACM Transactions on Networking, 2015
- Meta-algorithms for Software-Based Packet Classification2014
- Packet classification using binary Content Addressable Memory2014
- An energy-efficient TCAM-based packet classification with decision-tree mapping2013
- HybridCuts: A Scheme Combining Decomposition and Cutting for Packet Classification2013
- Compressing forwarding tables2013
- A smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classification2012
- EffiCutsACM SIGCOMM Computer Communication Review, 2010
- OpenFlowACM SIGCOMM Computer Communication Review, 2008