Block permutations in Boolean space to minimize TCAM for packet classification

Rihua Wei, Yang Xu, H. Jonathan Chao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Packet classification is one of the major challenges in designing high-speed routers and firewalls as it involves sophisticated multi-dimensional searching. Ternary Content Addressable Memory (TCAM) has been widely used to implement packet classification thanks to its parallel search capability and constant processing speed. However, TCAM-based packet classification has the well-known range expansion problem, resulting in a huge waste of TCAM entries. In this paper, we propose a novel technique called Block Permutation (BP) to compress the packet classification rules stored in TCAMs. The compression is achieved by performing block-based permutations on the rules represented in Boolean Space. We develop an efficient heuristic approach to find the permutations for compression and design its hardware implementation. Experiments on ClassBench classifiers and ISP classifiers show that the proposed BP technique can reduce TCAM entries by 53.99% on average.

Original languageEnglish (US)
Title of host publication2012 Proceedings IEEE INFOCOM, INFOCOM 2012
Pages2561-2565
Number of pages5
DOIs
StatePublished - 2012
EventIEEE Conference on Computer Communications, INFOCOM 2012 - Orlando, FL, United States
Duration: Mar 25 2012Mar 30 2012

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherIEEE Conference on Computer Communications, INFOCOM 2012
CountryUnited States
CityOrlando, FL
Period3/25/123/30/12

Keywords

  • Classifier Minimization
  • Logic Optimization
  • Packet Classification
  • Range Expansion
  • TCAM

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Block permutations in Boolean space to minimize TCAM for packet classification'. Together they form a unique fingerprint.

  • Cite this

    Wei, R., Xu, Y., & Chao, H. J. (2012). Block permutations in Boolean space to minimize TCAM for packet classification. In 2012 Proceedings IEEE INFOCOM, INFOCOM 2012 (pp. 2561-2565). [6195653] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2012.6195653