Self-Adjusting Packet Classification

09/30/2021
by   Maciej Pacut, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset