Name
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. 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.23919/FMCAD.2019.8894253 | 2019 Formal Methods in Computer Aided Design (FMCAD) |
Keywords | Field | DocType |
BDD-based algorithms,packet classification,packet classifiers,building blocks,modern networking,classifier,match operation,clock cycle,rule set,associative memory space,modern network switches,symbolic rule,compression algorithms,binary decision diagrams,simple BDD-based algorithm,compression ratio-a surprising result,symbolic techniques,industrial classifiers,smaller classifiers,packet header fields,sequential cover technique | Content-addressable memory,Computer science,Network packet,Binary decision diagram,Algorithm,Network switch,Header,Cycles per instruction,Data compression,Classifier (linguistics) | Conference |
ISSN | ISBN | Citations |
2641-8177 | 978-1-7281-4089-6 | 1 |
PageRank | References | Authors |
0.35 | 16 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nina Narodytska | 1 | 449 | 39.28 |
| Leonid Ryzhyk | 2 | 1 | 0.35 |
| Igor Ganichev | 3 | 1 | 1.03 |
| Soner Sevinc | 4 | 1 | 0.35 |