BDD-Based Algorithms for Packet Classification

Abstract

Packet classifiers are the building blocks of modern networking. A classifier determines the action to take on a packet by matching its header against a set of rules. Efficient classification is achieved by using associative memory to perform the match operation in one clock cycle. This requires compressing large rule sets to fit in the small associative memory space available in modern network switches. Failure to do so leads to increased infrastructure cost and reduced performance. We propose two symbolic rule set compression algorithms based on binary decision diagrams. Following McGeer and Yalagandula, we formalize the problem as that of obtaining a sequential cover of the rule set. We develop a simple BDD-based algorithm for computing sequential covers, which significantly outperforms state of the art algorithms in terms of compression ratio—a surprising result that highlights the unexplored potential of symbolic techniques in packet classification. Despite this improvement, very large industrial classifiers are still beyond reach. We decompose such classifiers into a pipeline of smaller classifiers over subsets of packet header fields. We then compress each classifier using the sequential cover technique. Our algorithm is able to compress industrial rule sets with hundreds of thousands rules to readily fit in the memory of network switches.