Many-field packet classification using AMQ-R-tree

Article type: Research Article

Authors: Abdulhassan, Aladdin | Ahmadi, Mahmood^{; *}

Affiliations: Department of Computer Engineering and Information Technology, Razi University, Kermanshah, Iran

Correspondence: [*] Corresponding author. E-mail: [email protected].

Abstract: In recent years, a modern networking paradigm called Software-Defined Networking (SDN) has been introduced to manage the large networks and datacenters. This paradigm was introduced to keep pace with the rapid growth rates on the Internet and to support advanced network applications. SDN uses an open standard protocol called OpenFlow to manage the network traffic. In OpenFlow switches, the software control plane has been decoupled from the hardware data plane and placed in a controller which has a network-wide view. OpenFlow process all incoming packets that have the same characteristics (lie in the same class) in the same manner. In this paper, we propose and use a generalized extension of BR-tree data structure called AMQ-R tree to organize the rule-sets in a multi-dimensional tree integrated with approximate membership query data structures including Bloom, Quotient and Cuckoo filters in order to get higher quality packet classification performance. Three types of approximate membership query filters integrated with the R-tree have been designed and implemented. Also, a multi-threading technique has been used to accelerate the packet classification by querying the tree in a parallel manner. The experimental results using simulated rule-sets show that this technique can classify incoming packets in up to 1.4 MPPS (Mega Packet per Second) with very small memory requirements.

Keywords: Software defined networking, OpenFlow, many-field packet classification, R-tree, approximate membership query, Cuckoo filter

DOI: 10.3233/JHS-180592

Journal: Journal of High Speed Networks, vol. 24, no. 3, pp. 219-241, 2018