NDLI: Packet classification using tuple space search

Please wait, while we are loading the content...

A readable TCP in the Prolac protocol language

A model, analysis, and protocol framework for soft state-based communication

The impact of multicast layering on network fairness

Scaling of multicast trees: comments on the Chuang-Sirbu scaling law

KHIP—a scalable protocol for secure multicast routing

IP multicast channels: EXPRESS support for large-scale single-source applications

Providing guaranteed services without per flow management

A flexible model for resource management in virtual private networks

Proportional differentiated services: delay differentiation and packet scheduling

BPF+: exploiting global data-flow optimization in a generalized packet filter architecture

Packet classification using tuple space search

Packet classification on multiple fields

A scalable Web cache consistency architecture

An integrated congestion management architecture for Internet hosts

Quality adaptation for congestion controlled video playback over the Internet

Routing with a clue

Load-sensitive routing of long-lived IP flows

A simple approximation to minimum-delay routing

Using pathchar to estimate Internet link characteristics

On power-law relationships of the Internet topology

On estimating end-to-end network path properties

An analysis of BGP convergence properties

The end-to-end effects of Internet path selection

Dynamics of IP traffic: a study of the role of variability and the impact of control

Packet classification using tuple space search

Content Provider	ACM Digital Library
Author	Suri, S. Srinivasan, V. Varghese, G.
Abstract	Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and QoS routing. Packet classification requires matching each packet against a database of filters (or rules), and forwarding the packet according to the highest priority filter. Existing filter schemes with fast lookup time do not scale to large filter databases. Other more scalable schemes work for 2-dimensional filters, but their lookup times degrade quickly with each additional dimension. While there exist good hardware solutions, our new schemes are geared towards software implementation.We introduce a generic packet classification algorithm, called Tuple Space Search (TSS). Because real databases typically use only a small number of distinct field lengths, by mapping filters to tuples even a simple linear search of the tuple space can provide significant speedup over naive linear search over the filters. Each tuple is maintained as a hash table that can be searched in one memory access. We then introduce techniques for further refining the search of the tuple space, and demonstrate their effectiveness on some firewall databases. For example, a real database of 278 filters had a tuple space of 41 which our algorithm prunes to 11 tuples. Even as we increased the filter database size from 1K to 100K (using a random two-dimensional filter generation model), the number of tuples grew from 53 to only 186, and the pruned tuples only grew from 1 to 4. Our Pruned Tuple Space search is also the only scheme known to us that allows fast updates and fast search times. We also show a lower bound on the general tuple space search problem, and describe an optimal algorithm, called Rectangle Search, for two-dimensional filters.
Starting Page	135
Ending Page	146
Page Count	12
File Format	PDF
ISBN	1581131356
DOI	10.1145/316188.316216
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1999-08-30
Publisher Place	New York
Access Restriction	Subscribed
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

Packet classification using tuple space search (1999)

Packet classification using tuple space search

Modified Collision Packet Classification Using Counting Bloom Filter in Tuple Space (2007)

Packet Classification using Tuple Space Search (1999)

Tuple Pruning Using Bloom Filters for Packet Classification

Packet Classification using Tuple Space Search (1999)

Hashing functions performance in packet classification.

Packet classification using coarse-grained tuple spaces

A Fast Packet Classification by Using Enhanced Tuple Pruning

Packet classification using tuple space search

Similar Documents

Packet classification using tuple space search (1999)

Packet classification using tuple space search

Modified Collision Packet Classification Using Counting Bloom Filter in Tuple Space (2007)

Packet Classification using Tuple Space Search (1999)

Tuple Pruning Using Bloom Filters for Packet Classification

Packet Classification using Tuple Space Search (1999)

Hashing functions performance in packet classification.

Packet classification using coarse-grained tuple spaces

A Fast Packet Classification by Using Enhanced Tuple Pruning

Packet classification using tuple space search