Scalable packet classification through rulebase partitioning using the maximum entropy hashing

Lynn Choi, Hyogon Kim, Sunil Kim, Moon Hae Kim

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


In this paper, we introduce a new packet classification algorithm, which can substantially improve the performance of a classifier. The algorithm is built on the observation that a given packet matches only a few rules even in large classifiers, which suggests that most of rules are independent in any given rulebase. The algorithm hierarchically partitions the rulebase into smaller independent subrulebases based on hashing. By using the same hash key used in the partitioning a classifier only needs to look up the relevant subrulebase to which an incoming packet belongs. For an optimal partitioning of rulebases, we apply the notion of maximum entropy to the hash key selection. We performed the detailed simulations of our proposed algorithm on synthetic rulebases of size 1 K to 500 K entries using real-life packet traces. The results show that the algorithm can significantly outperform existing classifiers by reducing the size of a rulebase by more than four orders of magnitude with just two-levels of partitioning. Both the time complexity and the space complexity of the algorithm exhibit linearity in terms of the size of a rulebase. This suggests that the algorithm can be a good scalable solution for medium to large rulebases.

Original languageEnglish
Article number5238551
Pages (from-to)1926-1935
Number of pages10
JournalIEEE/ACM Transactions on Networking
Issue number6
Publication statusPublished - 2009 Dec

Bibliographical note

Funding Information:
Manuscript received November 03, 2004; revised July 17, 2006; May 03, 2007; August 18, 2008; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor M. Buddhikot. First published September 15, 2009; current version published December 16, 2009. This work was supported by the Korea Science and Engineering Foundation (KOSEF) Grant funded by the Korea Government (MOST) (R01-2007-000-20958-0).


  • Computer networks
  • Firewalls
  • Network performance
  • Packet classification

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Scalable packet classification through rulebase partitioning using the maximum entropy hashing'. Together they form a unique fingerprint.

Cite this