NDLI: Scalable Many-Field Packet Classification on Multi-core Processors

Content Provider	IEEE Xplore Digital Library
Author	Qu, Y.R. Shijie Zhou Prasanna, V.K.
Copyright Year	2013
Description	Author affiliation: Ming Hsieh Dept. of Electr. Eng., Univ. of Southern California, Los Angeles, CA, USA (Qu, Y.R.; Shijie Zhou; Prasanna, V.K.)
Abstract	Packet classification matches a packet header against the predefined rules in a rule set, it is a kernel function that has been studied for decades. A recent trend in packet classification is to match a large number of packet header fields. For example, the flow table lookup in Software Defined Networking (SDN) requires 15 fields of the packet header to be examined. Another trend in packet classification is to use software-based solutions employing multi-core general purpose processors and virtual machines. Although packet classification has been widely studied, most existing solutions on multi-core systems target the classic 5-field packet classification, their performance cannot be easily scaled up for a larger number of packet header fields. In this paper, we propose a decomposition-based packet classification approach, it supports large rule sets consisting of a large number of packet header fields. We first use range-tree and hashing to search each field of the input packet header individually in parallel. The partial results from all the fields are represented by bit vectors, they are merged in parallel to produce the final packet header match. We also balance the search and merge latencies, and employ software pipelining to further enhance the overall performance. We implement our approach on state-of-the-art multi-core processors, we evaluate its performance with respect to throughput and latency for rule set size ranging from 1K to 32K. Experimental results show that, for a 32K rule set, our algorithms can achieve an average processing latency of 2000 ns per packet and an overall throughput of 30 million packets per second on a state-of-the-art 16-core platform.
Starting Page	33
Ending Page	40
File Size	701434
Page Count	8
File Format	PDF
e-ISBN	9781479929283
DOI	10.1109/SBAC-PAD.2013.29
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-10-23
Publisher Place	Brazil
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Program processors Multicore processing Throughput Impedance matching Vectors Field programmable gate arrays performance packet classification multi-core
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