Fast packet classification algorithm for network-wide forwarding behaviors

This paper proposes a novel packet classification method that supports the fast determination of network-wide forwarding behaviors. To avoid the inefficiencies of existing methods, which are revealed for the first time by our research, we base our method on a compressed data structure named the multi-valued decision diagram. On the solid foundation of decision diagrams, several algorithms are introduced with thorough theoretical analyses, and the construction process and the classification performance are highly optimized for the new classification problem. Experiments on real network datasets show that our method identifies the network-wide forwarding behaviors at the line basic rate, e.g., 10 Mpps, on a single CPU core with only tens of MB of memory.