Abstract
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 language | English |
---|---|
Article number | 5238551 |
Pages (from-to) | 1926-1935 |
Number of pages | 10 |
Journal | IEEE/ACM Transactions on Networking |
Volume | 17 |
Issue number | 6 |
DOIs | |
Publication status | Published - 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).
Keywords
- Computer networks
- Firewalls
- Network performance
- Packet classification
ASJC Scopus subject areas
- Software
- Computer Science Applications
- Computer Networks and Communications
- Electrical and Electronic Engineering