Classify-reorder algorithm for matching packets to rules. Reorganizes the data structure after matching the packet to improve performance on traffic with locality of reference.
This paper is motivated by the vision of more efficient packet classification mechanisms that self-optimize in
a demand-aware manner. At the heart of our approach lies a self-adjusting linear list data structure, where
unlike in the classic data structure, there are dependencies and some items must be in front of the others; for
example, to correctly classify packets by rules arranged in a linked list, each rule must be in front of lower
priority rules that overlap with it. After each access we can rearrange the list, similarly to Move-To-Front, but
dependencies need to be respected.
We present a 4-competitive online rearrangement algorithm, whose cost is at most four times worse than
the optimal offline algorithm; no deterministic algorithm can be better than 3-competitive. The algorithm is
simple and attractive especially for memory-limited systems, as it does not require any additional memory
(e.g., neither timestamps nor frequency statistics). This drop-in replacement for static lists of rules may enhance
existing networked systems.
Packet classification [13] is the most fundamental task in communication networks, performed by
switches, routers and middleboxes (e.g., firewalls). Existing packet classifiers are typically traffic-
oblivious: their internal data structures do not depend on the specific traffic patterns they serve. For
example, decision trees are typically designed for good performance under uniform traffic patterns.
This paper is motivated by the hypothesis that the performance of packet classification can be
improved by more adaptive approaches. Indeed, in practice, workloads are often far from uniform,
and the majority of traffic can be served with few rules [24]. If a packet classifier could identify
and optimize toward the “heavy hitter rules”, its reaction time and throughput could potentially be
improved.