  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). Our
approach can simply be deployed as a drop-in replacement for a static
datastructure, potentially benefitting many existing networks.
  We evaluate our self-adjusting list packet classifier on realistic ruleset
and traffic instances. We find that our classifier performs similarly to a
static list for low-locality traffic, but significantly outperforms Efficuts
(by a factor 7x), CutSplit (3.6x), and the static list (14x) for high locality
and small rulesets. Memory consumption is 10x lower on average compared to
Efficuts and CutSplit.
