NDLI: HybridCuts: A Scheme Combining Decomposition and Cutting for Packet Classification

Content Provider	IEEE Xplore Digital Library
Author	Wenjun Li Xianfeng Li
Copyright Year	2013
Description	Author affiliation: Eng. Lab. on Intell. Perception for Internet of Things (ELIP), Peking Univ., Shenzhen, China (Wenjun Li; Xianfeng Li)
Abstract	Packet classification is an enabling function for a variety of Internet applications such as access control, quality of service and differentiated services. Decision-tree and decomposition are the most well-known algorithmic approaches. Compared to architectural solutions, both approaches are memory and performance inefficient, falling short of the needs of high-speed networks. EffiCuts, the state-of-the-art decision-tree technique, significantly reduces memory overhead of classic cutting algorithms with separated trees and equidense cuts. However, it suffers from too many memory accesses and a large number of separated trees. Besides, EffiCuts needs comparator circuitry to support equidense cuts, which makes it less practical. Decomposition based schemes, such as BV, can leverage the parallelism offered by modern hardware for memory accesses, but they have poor storage scalability. In this paper, we propose Hybrid Cuts, a combination of decomposition and decision-tree techniques that improves storage and performance simultaneously. The decomposition part of Hybrid Cuts has the benefits of traditional decomposition-based techniques without the trouble of aggregating results from a large number of bit vectors or a set of big lookup tables. Meanwhile, thanks to the clever partitioning of the rule set, an efficient cutting algorithm following the decomposition can build short decision trees with significant reduction on rule replications. Using Class Bench, we show that Hybrid Cuts achieves similar memory reduction compared to EffiCuts, but it outperforms EffiCuts significantly in terms of memory accesses for packet classification. In addition, Hybrid Cuts is more practical for implementation than EffiCuts, which maintains complicated data structures and requires special hardware support for efficient cuts.
Starting Page	41
Ending Page	48
File Size	356270
Page Count	8
File Format	PDF
ISBN	9780769551036
DOI	10.1109/HOTI.2013.12
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-08-21
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Vectors Algorithm design and analysis Decision trees Classification algorithms Partitioning algorithms Hardware Scalability Performance Packet Classification Decomposition Decision-Tree Rule Replication
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in