Scalable Packet Classification Through Rulebase Partitioning Using the Maximum Entropy Hashing
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Choi, Lynn | - |
dc.contributor.author | Kim, Hyogon | - |
dc.contributor.author | Kim, Sunil | - |
dc.contributor.author | Kim, Moon Hae | - |
dc.date.accessioned | 2021-09-08T11:04:50Z | - |
dc.date.available | 2021-09-08T11:04:50Z | - |
dc.date.created | 2021-06-11 | - |
dc.date.issued | 2009-12 | - |
dc.identifier.issn | 1063-6692 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/118831 | - |
dc.description.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. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC | - |
dc.title | Scalable Packet Classification Through Rulebase Partitioning Using the Maximum Entropy Hashing | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Choi, Lynn | - |
dc.contributor.affiliatedAuthor | Kim, Hyogon | - |
dc.identifier.doi | 10.1109/TNET.2009.2018618 | - |
dc.identifier.scopusid | 2-s2.0-72449130427 | - |
dc.identifier.wosid | 000272844300018 | - |
dc.identifier.bibliographicCitation | IEEE-ACM TRANSACTIONS ON NETWORKING, v.17, no.6, pp.1926 - 1935 | - |
dc.relation.isPartOf | IEEE-ACM TRANSACTIONS ON NETWORKING | - |
dc.citation.title | IEEE-ACM TRANSACTIONS ON NETWORKING | - |
dc.citation.volume | 17 | - |
dc.citation.number | 6 | - |
dc.citation.startPage | 1926 | - |
dc.citation.endPage | 1935 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Engineering | - |
dc.relation.journalResearchArea | Telecommunications | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Hardware & Architecture | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Theory & Methods | - |
dc.relation.journalWebOfScienceCategory | Engineering, Electrical & Electronic | - |
dc.relation.journalWebOfScienceCategory | Telecommunications | - |
dc.subject.keywordAuthor | Computer networks | - |
dc.subject.keywordAuthor | firewalls | - |
dc.subject.keywordAuthor | network performance | - |
dc.subject.keywordAuthor | packet classification | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.