Scalable Packet Classification Through Rulebase Partitioning Using the Maximum Entropy Hashing
- Authors
- Choi, Lynn; Kim, Hyogon; Kim, Sunil; Kim, Moon Hae
- Issue Date
- 12월-2009
- Publisher
- IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
- Keywords
- Computer networks; firewalls; network performance; packet classification
- Citation
- IEEE-ACM TRANSACTIONS ON NETWORKING, v.17, no.6, pp.1926 - 1935
- Indexed
- SCIE
SCOPUS
- Journal Title
- IEEE-ACM TRANSACTIONS ON NETWORKING
- Volume
- 17
- Number
- 6
- Start Page
- 1926
- End Page
- 1935
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/118831
- DOI
- 10.1109/TNET.2009.2018618
- ISSN
- 1063-6692
- 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 1K 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.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - College of Engineering > School of Electrical Engineering > 1. Journal Articles
- Graduate School > Department of Computer Science and Engineering > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.