Back to search

University of South Florida

Grouper: A Packet Classification Algorithm Allowing Time-Space Tradeoffs

Abstract

dc:description

This thesis presents an algorithm for classifying packets according to arbitrary (including noncontiguous) bitmask rules. As its principal novelty, the algorithm is parameterized by the amount of memory available and can customize its data structures to optimize classification time without exceeding the given memory bound. The algorithm thus automatically trades time for space efficiency as needed. The two extremes of this time-space tradeoff (linear search through the rules versus a single table that maps every possible packet to its class number) are special cases of the general algorithm we present. Additional features of the algorithm include its simplicity, its open-source prototype implementation, its good performance even with worstcase rule sets, and its extendability to handle range rules and dynamic updates to rule sets. The contributions of this thesis first appeared in [1].

Degree

thesis:*
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Engineering Computer Science
Grantor
University of South Florida
Year dc:date
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kuhn, Joshua Adam
Contributors dc:contributor
  • Jay Ligatti, Ph.D.
  • Adriana Iamnitchi, Ph.D.
  • Ken Christensen, Ph.D.

Subjects

dc:subject × 8

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/3192

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kuhn, Joshua Adam. Grouper: A Packet Classification Algorithm Allowing Time-Space Tradeoffs. Thesis thesis, University of South Florida, 2011. https://digitalcommons.usf.edu/etd/3192