More Web Proxy on the site http://driver.im/

research-article

Memory‐efficient recursive scheme for multi‐field packet classification

Authors:

Hui LiAuthors Info & Claims

IET Communications, Volume 13, Issue 9

Pages 1319 - 1325

https://doi.org/10.1049/iet-com.2018.6038

Published: 01 June 2019 Publication History

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.

References

[1]

McKeown N., Anderson T., Balakrishnan H. et al.: ‘OpenFlow: enabling innovation in campus networks’, ACM SIGCOMM Comput. Commun. Rev., 2008, 38, (2), pp. 69–74

[2]

Liu A.X., Meiners C.R., Torng E.: ‘Packet classification using binary content addressable memory’. Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Toronto, Canada, April 2014, pp. 628–636

[3]

Liu A.X., Meiners C.R., Torng E.: ‘TCAM razor: a systematic approach towards minimizing packet classifiers in TCAMs’, IEEE/ACM Trans. Netw., 2010, 18, (2), pp. 490–500

[4]

Liu A.X., Meiners C.R., Zhou Y.: ‘All‐match based complete redundancy removal for packet classifiers in TCAMs’. Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Phoenix, USA, April 2008, pp. 111–115

[5]

Rottenstreich O., Tapolcai J.: ‘Lossy compression of packet classifiers’. Proc. ACM/IEEE Symp. on Architectures for Networking and Communications Systems (ANCS), Oakland, USA, May 2015, pp. 39–50

[6]

Rottenstreich O., Radan M., Cassuto Y. et al.: ‘Compressing forwarding tables’. Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Turin, Italy, April 2013, pp. 1231–1239

[7]

Che H., Wang Z., Zheng K.: ‘DRES: dynamic range encoding scheme for TCAM coprocessors’, IEEE Trans. Comput., 2008, 57, (7), pp. 902–915

[8]

Liu H.: ‘Efficient mapping of range classifier into ternary‐CAM’. Proc. IEEE Annual Symp. on High‐Performance Interconnects (Hot Interconnects), Stanford, USA, August 2002, pp. 95–100

[9]

Rottenstreich O., Cohen R., Raz D.: ‘Exact worst‐case TCAM rule expansion’, IEEE Trans. Comput., 2013, 62, (6), pp. 1127–1140

[10]

Rottenstreich O., Keslassy I.: ‘On the code length of TCAM coding schemes’. Proc. IEEE Annual Symp. on Information Theory (ISIT), Texas, USA, June 2010, pp. 1908–1912

[11]

Rottenstreich O., Keslassy I., Hassidim A.: ‘Optimal in/out TCAM encodings of ranges’, IEEE/ACM Trans. Netw., 2016, 24, (1), pp. 555–568

[12]

Li W., Li X., Li H.: ‘MEET‐IP: memory and energy efficient TCAM‐based IP lookup’. Proc. IEEE Int. Conf. on Computer Communication and Networks (ICCCN), Vancouver, Canada, August 2017, pp. 1–8

[13]

Li X., Lin Y., Li W.: ‘GreenTCAM: a memory‐ and energy‐efficient TCAM‐based packet classification’. Proc. IEEE Int. Conf. on Computing, Networking and Communications (ICNC), Kauai, USA, February 2016, pp. 1–6

[14]

Ma Y., Banerjee S.: ‘A smart pre‐classifier to reduce power consumption of TCAMs for multi‐dimensional packet classification’. Proc. ACM Int. Conf. on the Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), Helsinki, Finland, August 2012, pp. 335–346

[15]

Ruan Z., Li X., Li W.: ‘An energy‐efficient TCAM‐based packet classification with decision‐tree mapping’. Proc. IEEE Region 10 Conf. (TENCON), Xian, China, October 2013, pp. 1–5

[16]

Daly J., Torng E.: ‘TupleMerge: building online packet classifiers by omitting bits’. Proc. IEEE Int. Conf. on Computer Communication and Networks (ICCCN), Vancouver, Canada, August 2017, pp. 1–10

[17]

Yang T., Liu A.X., Shen Y. et al.: ‘Fast openflow table lookup with fast update’. Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Honolulu, USA, April 2018, pp. 2636–2644

[18]

Daly J., Torng E.: ‘ByteCuts: fast packet classification by interior bit extraction’. Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Honolulu, USA, April 2018, pp. 2654–2662

[19]

Fong J., Wang X., Qi Y.: ‘ParaSplit: a scalable architecture on FPGA for terabit packet classification’. Proc. IEEE Annual Symp. on High‐Performance Interconnects (Hot Interconnects), Santa Clara, USA, August 2012, pp. 1–8

[20]

He P., Xie G., Salamatian K. et al.: ‘Meta‐algorithms for software based packet classification’. Proc. IEEE Int. Conf. on Network Protocols (ICNP), Raleigh, USA, October 2014, pp. 308–319

[21]

Li W., Li X., Li H. et al.: ‘CutSplit: a decision‐tree combining cutting and splitting for scalable packet classification’. Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Honolulu, USA, April 2018, pp. 2645–2653

[22]

Li W., Li X.: ‘HybridCuts: a scheme combining decomposition and cutting for packet classification’. Proc. IEEE Annual Symp. on High‐Performance Interconnects (Hot Interconnects), Santa Clara, USA, August 2013, pp. 41–48

[23]

Li X., Lin Y.: ‘TaPaC: a TCAM‐assisted algorithmic packet classification with bounded worst‐case performance’. Proc. IEEE Global Communications Conf. (GLOBECOM), Washington, USA, December 2016, pp. 1–6

[24]

Qi Y., Xu L., Yang B. et al.: ‘Packet classification algorithms: from theory to practice’. Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, April 2009, pp. 648–656

[25]

Vamanan B., Voskuilen G., Vijaykumar T.N.: ‘EffiCuts: optimizing packet classification for memory and throughput’. Proc. ACM Int. Conf. on the Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), New Delhi, India, September 2010, pp. 207–218

[26]

Yang T., Xie G., Liu A.X.: ‘Constant IP lookup with FIB explosion’, IEEE/ACM Trans. Netw., 2018, 26, (4), pp. 1821–1836

[27]

Pak W., Bahk S.: ‘FRFC: fast table building algorithm for recursive flow classification’, IEEE Communication Letters, 2010, 14, (12), pp. 1082–1084

[28]

Tayor D.E., Turner J.S.: ‘Scalable packet classification using distributed crossproducting of field labels’. Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Miami, USA, March 2005, pp. 269–280

[29]

Xu B., Jiang D., Li J.: ‘HSM: a fast packet classification algorithm’. Proc. IEEE Int. Conf. on HSM: a Fast Packet Classification Algorithm (AINA), Taipei, Taiwan, March 2005, pp. 987–992

[30]

Srinivasan V., Varghese G., Suri S. et al.: ‘Fast and scalable layer four switching’. Proc. ACM Int. Conf. on the Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), British Columbia, Canada, September 1998, pp. 191–202

[31]

Gupta P., McKeown N.: ‘Packet classification on multiple fields’. Proc. ACM Int. Conf. on the Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), Cambridge, USA, September 1999, pp. 147–160

[32]

Tayor D.E., Turner J.S.: ‘Classbench: a packet classification benchmark’. Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Miami, USA, March 2005, pp. 2068–2079

Cited By

Liu YXin YLi WSong HRottenstreich OXie GLi WWang Y(2022)HybridTSS: A Recursive Scheme Combining Coarse- and Fine- Grained Tuples for Packet ClassificationProceedings of the 6th Asia-Pacific Workshop on Networking10.1145/3542637.3542644(43-49)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1145/3542637.3542644

Recommendations

Many-field packet classification using CR-tree

Packet classification is a network kernel function that has been widely investigated over the past decade. New networking paradigms, such as software-defined networking and server virtualization, have led to renewed interest in packet classification and ...
Improving performance of TCP for wireless network using SDN
ICDCN '19: Proceedings of the 20th International Conference on Distributed Computing and Networking

This paper addresses the problem of non-optimal performance of Transmission Control Protocol (TCP) over Wi-Fi networks. TCP considers packet loss as a signal for congestion leading to reduced sending rate. This idea works well for the wired networks ...
Scalable Many-Field Packet Classification on Multi-core Processors
SBAC-PAD '13: Proceedings of the 2013 25th International Symposium on Computer Architecture and High Performance Computing

Packet classification matches a packet header against the predefined rules in a rule set, it is a kernel function that has been studied for decades. A recent trend in packet classification is to match a large number of packet header fields. For example, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IET Communications

IET Communications Volume 13, Issue 9

June 2019

185 pages

EISSN:1751-8636

DOI:10.1049/cmu2.v13.9

Issue’s Table of Contents

© 2021 The Institution of Engineering and Technology.

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 June 2019

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YXin YLi WSong HRottenstreich OXie GLi WWang Y(2022)HybridTSS: A Recursive Scheme Combining Coarse- and Fine- Grained Tuples for Packet ClassificationProceedings of the 6th Asia-Pacific Workshop on Networking10.1145/3542637.3542644(43-49)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1145/3542637.3542644

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents