{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-4387"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-4387","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Grouper: A Packet Classification Algorithm Allowing Time-Space Tradeoffs","abstract":"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].","abstract_html":"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].","abstract_has_math":false,"creators":["Kuhn, Joshua Adam"],"institution":"University of South Florida","degree_name":null,"degree_level":"Thesis","degree_discipline":"Engineering Computer Science","degree_department":null,"school":null,"contributors":["Jay Ligatti, Ph.D.","Adriana Iamnitchi, Ph.D.","Ken Christensen, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-01-01T08:00:00Z","date_published":"2011-01-01T08:00:00Z","updated_at":"2026-11-19T08:34:51Z","subjects":[": Network Algorithms","Security","Network Security","Computer Networks","Algorithms","American Studies","Arts and Humanities","Computer Sciences"],"languages":["EN-US"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/3192","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/3192","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-4387","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jay Ligatti, Ph.D.","Adriana Iamnitchi, Ph.D.","Ken Christensen, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Kuhn, Joshua Adam"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis","M.S.C.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":[": Network Algorithms","Security","Network Security","Computer Networks","Algorithms","American Studies","Arts and Humanities","Computer Sciences"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["EN-US"]},{"key":"dc:rights.license","label":"Dc Rights License","values":["default"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/3192"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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]."]},{"key":"dc:title","label":"Title","values":["Grouper: A Packet Classification Algorithm Allowing Time-Space Tradeoffs"]}]}],"canonical_facts":{"dc:contributor":["Jay Ligatti, Ph.D.","Adriana Iamnitchi, Ph.D.","Ken Christensen, Ph.D."],"dc:creator":["Kuhn, Joshua Adam"],"dc:date":["2011-01-01T08:00:00Z"],"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]."],"dc:identifier":["https://digitalcommons.usf.edu/etd/3192"],"dc:language":["EN-US"],"dc:rights.license":["default"],"dc:subject":[": Network Algorithms","Security","Network Security","Computer Networks","Algorithms","American Studies","Arts and Humanities","Computer Sciences"],"dc:title":["Grouper: A Packet Classification Algorithm Allowing Time-Space Tradeoffs"],"thesis:degree_discipline":["Engineering Computer Science"],"thesis:degree_level":["Thesis","M.S.C.S."],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:34:51Z"}