Return to search

Grouper: A Packet Classification Algorithm Allowing Time-Space Tradeoffs

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 worst-case rule sets, and its extendability to
handle range rules and dynamic updates to rule sets. The contributions of this
thesis first appeared in [1].

Identiferoai:union.ndltd.org:USF/oai:scholarcommons.usf.edu:etd-4387
Date01 January 2011
CreatorsKuhn, Joshua Adam
PublisherScholar Commons
Source SetsUniversity of South Flordia
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceGraduate Theses and Dissertations
Rightsdefault

Page generated in 0.0017 seconds