NDLI: Packet classification via improved space decomposition techniques

Content Provider	IEEE Xplore Digital Library
Author	Geraci, F. Pellegrini, M. Pisati, P. Rizzo, L.
Copyright Year	2005
Description	Author affiliation: Ist. di Informatica e Telematica, Consignlio Nazionale delle Ricerche, Pisa, Italy (Geraci, F.; Pellegrini, M.; Pisati, P.)
Abstract	Packet classification is a common task in modern Internet routers. The goal is to classify packets into "classes" or "flows" according to some ruleset that looks at multiple fields of each packet. Differentiated actions can then be applied to the traffic depending on the result of the classification. Even though rulesets can be expressed in a relatively compact way by using high level languages, the resulting decision trees can partition the search space (the set of possible attribute values) in a potentially very large (106 and more) number of regions. This calls for methods that scale to such large problem sizes, though the only scalable proposal in the literature so far is the one based on a fat inverted segment tree (A. Feldmann and S. Muthukrishnan). In this paper we propose a new geometric technique called G-filter for packet classification on d dimensions. G-filter is based on an improved space decomposition technique. In addition to a theoretical analysis showing that classification in G-filter has O(1) time complexity and slightly super-linear space in the number of rules, we provide thorough experiments showing that the constants involved are extremely small on a wide range of problem sizes, and that G-filter improve the best results in the literature for large problem sizes, and is competitive for small sizes as well.
Starting Page	304
Ending Page	312
File Size	1840733
Page Count	9
File Format	PDF
ISBN	0780389689
ISSN	0743166X
DOI	10.1109/INFCOM.2005.1497901
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-03-13
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Traffic control Decision trees Filters Telecommunication traffic Internet High level languages Marketing and sales Filtering Network address translation Multidimensional systems
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

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

Multidimensional packet classification with improved cutting

Packet Classification Decomposition Techniques via Improved Space

Markers-based space decomposition algorithm: a new algorithm for multi-fields packet classification

Geometric packet classification algorithm

Spatial-Temporal Characteristics of Internet Malicious Sources

Packet classification for core routers: is there an alternative to CAMs?

Adaptive Statistical Optimization Techniques for Firewall Packet Filtering

On IPv6 traceback

Decision Tree Network Traffic Classifier Via Adaptive Hierarchical Clustering for Imperfect Training Dataset

Packet classification via improved space decomposition techniques

Similar Documents

Multidimensional packet classification with improved cutting

Packet Classification Decomposition Techniques via Improved Space

Markers-based space decomposition algorithm: a new algorithm for multi-fields packet classification

Geometric packet classification algorithm

Spatial-Temporal Characteristics of Internet Malicious Sources

Packet classification for core routers: is there an alternative to CAMs?

Adaptive Statistical Optimization Techniques for Firewall Packet Filtering

On IPv6 traceback

Decision Tree Network Traffic Classifier Via Adaptive Hierarchical Clustering for Imperfect Training Dataset

Packet classification via improved space decomposition techniques