Graduation Year

2011

Document Type

Thesis

Degree

M.S.C.S.

Degree Granting Department

Engineering Computer Science

Major Professor

Jay Ligatti

Keywords

Algorithms, Computer Networks, Network Algorithms, Network Security, Security

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 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].

Share

COinS