NDLI: Scalable Packet Classification for Enabling <newline/>Internet Differentiated Services

Content Provider	IEEE Xplore Digital Library
Author	Pi-Chung Wang Chia-Tai Chan Chun-Liang Lee Hung-Yi Chang
Copyright Year	1999
Abstract	Nowadays, IP networks are rapidly evolving toward a QoS-enabled infrastructure. The need for packet classification is increasing in accordance with emerging differentiated services. While the new differentiated services could significantly increase the number of rules, it has been demonstrated that performing packet classification on a potentially large number of rules is difficult and has poor worst-case performance. In this work, we present an enhanced tuple pruning search algorithm called "tuple pruning plus" (TPP) for packet classification, which outperforms the existing schemes on the scalability. Our main idea is to simplify the lookup procedure and to avoid unnecessary tuple probing by maintaining the least-cost property of rule through precomputation and the proposed information marker. With extra rules added for information marker, only one tuple access is required in each packet classification. In our experiments, 70 MB DRAM is used to achieve 50 million packets per second (MPPS) for a 1 M-rule set, showing a performance improvement by a factor of 50. We also present a heuristic to further reduce the required storage to about 20 MB. These results demonstrate the effectiveness of the TPP scheme to achieve high speed packet classification
Sponsorship	IEEE Signal Processing Society IEEE Circuits and Systems Society IEEE Communications Society IEEE Computer Society
Starting Page	1239
Ending Page	1249
Page Count	11
File Size	1092294
File Format	PDF
ISSN	15209210
Volume Number	8
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-12-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Web and internet services IP networks Computer science Biomedical engineering Traffic control Scalability Random access memory Multidimensional systems Internet telephony Videoconference packet classification Best matching prefix multicast multidimensional range lookup
Content Type	Text
Resource Type	Article
Subject	Signal Processing Electrical and Electronic Engineering Computer Science Applications Media Technology

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

Scalable Packet Classification for Enabling Internet Differentiated Services (2006)

Scalable, memory efficient, high-speed IP lookup algorithms

Scalable, memory efficient, high-speed IP lookup algorithms

Tradeoffs for Packet Classification (2000)

Real-time application performance in differentiated services network

SRAM based longest prefix matching approach for multigigabit IP processing

Survey and Proposal on Binary Search Algorithms for Longest Prefix Match

Fast and scalable packet classification

IP address lookup for internet routers using balanced binary search with prefix vector

Scalable Packet Classification for Enabling Internet Differentiated Services

Similar Documents

Scalable Packet Classification for Enabling Internet Differentiated Services (2006)

Scalable, memory efficient, high-speed IP lookup algorithms

Scalable, memory efficient, high-speed IP lookup algorithms

Tradeoffs for Packet Classification (2000)

Real-time application performance in differentiated services network

SRAM based longest prefix matching approach for multigigabit IP processing

Survey and Proposal on Binary Search Algorithms for Longest Prefix Match

Fast and scalable packet classification

IP address lookup for internet routers using balanced binary search with prefix vector

Scalable Packet Classification for Enabling Internet Differentiated Services