Software-Defined Networking

In software-defined networking, applications are allowed to access a global view of the network so as to provide sophisticated functionalities, such as quality-oriented service delivery, automatic fault localization, and network verification. All of these functionalities commonly rely on a well-studied tech-nology, packet classification. Unlike the conventional classification problem to search for the action taken at a single switch, the global network view re-quires to identify the network-wide behavior of the packet, which is defined as a combination of switch actions. Conventional classification methods, how-ever, fail to well support network-wide behaviors, since the search space is complicatedly partitioned due to the combinations. This paper proposes a novel packet classification method that efficiently supports network-wide packet behaviors. Our method utilizes a compressed data structure named the multi-valued decision diagram, allowing it to ma-nipulate the complex search space with several algorithms. Through detailed analysis, we optimize the classification performance as well as the construc-tion of decision diagrams. Experiments with real network datasets show that our method identifies the packet behavior at 20.1 Mpps on a single CPU core with only 8.4 MB memory; by contrast, conventional methods failed to work even with 16 GB memory. We believe that our method is essential for realizing advanced applications that can fully leverage the potential of software-defined networking.