Tradeoffs for packet classification

TLDR

The authors propose an algorithmic framework that solves packet classification while trading off access time against memory usage. The framework reduces multidimensional packet classification to multiple one-dimensional IP lookups and is evaluated experimentally on two-dimensional datasets from AT&T WorldNet. It delivers the best known lookup performance with moderately large memory and supports efficient rule additions and deletions without performance loss.

Abstract

We present an algorithmic framework for solving the packet classification problem that allows various access time versus memory tradeoffs. It reduces the multidimensional packet classification problem to solving a few instances of the one-dimensional IP lookup problem. It gives the best known lookup performance with moderately large memory space. Furthermore, it efficiently supports a reasonable number of additions and deletions to the rulesets without degrading the lookup performance. We perform a thorough experimental study of the tradeoffs for the two-dimensional packet classification problem on rulesets derived from datasets collected from AT&T WorldNet, an Internet service provider.