The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Packet classification using tuple space search
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The BSD packet filter: a new architecture for user-level packet capture
McCanne, S., & Jacobson, V. L. (1993) · Cited by 885
Chapman, D. B., Zwicky, E. D., & Russell, D. (1995) · CERN Document Server (European Organization for Nuclear Research) · Cited by 345
DPF: fast, flexible message demultiplexing using dynamic code generation
Engler, D., & Kaashoek, M. F. (1996) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/248156.248162 · Cited by 170
Cited by
Algorithms for packet classification
Gupta, P., & McKeown, N. (2001) · IEEE Network · doi:10.1109/65.912717 · Cited by 655
Fast hash table lookup using extended bloom filter: an aid to network processing
Song, H., Dharmapurikar, S., Turner, J., & Lockwood, J. (2005) · Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/1080091.1080114 · Cited by 328
Classifying packets with hierarchical intelligent cuttings
Gupta, P., & McKeown, N. (2000) · IEEE Micro · doi:10.1109/40.820051 · Cited by 324
Conflict classification and analysis of distributed firewall policies
Al-Shaer, E., Hamed, H., Boutaba, R., & Hasan, M. (2005) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2005.854119 · Cited by 290
eZTrust: Network-Independent Zero-Trust Perimeterization for Microservices
Zaheer, Z., Chang, H., Mukherjee, S., & Van der Merwe, J. (2019) · Proceedings of the 2019 ACM Symposium on SDN Research · doi:10.1145/3314148.3314349 · Cited by 48
Metadata
- Authors
- Srinivasan, V., Suri, S., & Varghese, G.
- Venue
- Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication
- Publisher
- ACM
- Published
- 1999-08-30
- Pages
- 135-146
- OpenAlex
- W2022106793
- Cited by
- 495
- References
- 3
- FWCI
- 14.21
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Packet classification using tuple space search. https://app.cochat.ai/papers/10.1145/316188.316216
- The paper
- Srinivasan, V., Suri, S., & Varghese, G. (1999). Packet classification using tuple space search. Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication. https://doi.org/10.1145/316188.316216
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.