Packet classification is a network kernel function that has been widely investigated over the past decade. New networking paradigms, such as software-defined networking and server virtualization, have led to renewed interest in packet classification and its upgrade from classical five-field to many-field classification. With the increasing size of the rule sets and demands for higher throughput, performing many-field packet classification at wire-speed has become challenging. In this paper, we propose an approach to classification by integrating a probabilistic data structure called the Cuckoo filter for approximate membership queries into an R-tree data structure for high-speed, many-field packet classification. Experimental results show that the proposed classifier obtains high throughput of up to 1.5 M packets per second, and requires little memory to support large rule sets (up to 1 million rules).
W.Braun and M.Menth, Software-defined networking using OpenFlow: Protocols, applications and architectural design choices, Future Internet6(2) (2014), 302–336. doi:10.3390/fi6020302.
3.
M.Buddhikot, M.S.Suri and M.Waldvogel, Space decomposition techniques for fast layer-4 switching, in: Proc. Conf. Protoc. High Speed Netw., 1999, pp. 25–41.
4.
Y.C.Cheng and P.C.Wang, Packet classification using dynamically generated decision trees, IEEE Trans. Comput.64(2) (2015), 582–586. doi:10.1109/TC.2013.227.
5.
B.Fan, D.G.Andersen, M.Kaminsky and M.D.Mitzenmacher, Cuckoo filter: Practically better than Bloom, in: Proc. 10th ACM Int. Conf. Emerg. Netw. Exp. Technol., ACM, 2014, pp. 75–88.
6.
T.Ganegedara, J.Weirong and V.K.Prasanna, A scalable and modular architecture for high-performance packet classification, IEEE Trans. Parallel Distrib. Sys.25(5) (2014), 1135–1144. doi:10.1109/TPDS.2013.261.
7.
V.Gupta and F.Breitinger, How Cuckoo filter can improve existing approximate matching techniques, in: International Conference on Digital Forensics and Cyber Crime, Springer, 2015. doi:10.1007/978-3-319-25512-5_4.
8.
A.Guttman, R-trees: A dynamic index structure for spatial searching, ACM14(2) (1984), 47–57.
9.
L.Hyesook and S.Y.Byun, Packet classification using a Bloom filter in a leaf-pushing area-based quad-trie, in: Proc. 11th ACM/IEEE Symp. Archit. Netw. Commun. Sys., IEEE Computer Society, 2015. doi:10.1109/ANCS.2015.7110131.
10.
T.V.Lakshman and D.Stiliadis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, in: Proc. SIGCOMM ’98, 1998, pp. 203–214. doi:10.1145/285243.285283.
11.
H.Lim, H.N.Chu and C.Yim, Hierarchical binary search tree for packet classification, IEEE Commun. Lett.11(8) (2007), 689–691. doi:10.1109/LCOMM.2007.070389.
12.
H.Lim, N.Lee and G.Jin, Boundary cutting for packet classification, IEEE/ACM Trans. Netw.22(2) (2014), 443–456. doi:10.1109/TNET.2013.2254124.
13.
A.X.Liu, R.M.Chad and T.Eric, Packet classification using binary content addressable memory, Biol. Cybern.24(3) (2016), 1295–1307.
14.
Y.Manolopoulos, A.Nanopoulos, A.N.Papadopoulos and Y.Theodoridis, Introduction, in: R-Trees: Theory and Applications, Springer, London, 2006, pp. 3–13. doi:10.1007/978-1-84628-293-5_1.
15.
H.Marius, Analysing R-tree variants as solutions for IP-lookup, Albert-Ludwigs-Universitat Freiburg, 2007.
16.
R.Pagh and F.F.Rodler, Cuckoo Hashing, Springer, Berlin, 2001.
17.
W.Pak and Y.J.Choi, High performance and high scalable packet classification algorithm for network security systems, IEEE Trans. Dependable Secur. Comput.14(1) (2017), 37–49.
18.
G.Pankaj and N.McKeown, Packet classification using hierarchical intelligent cuttings, in: Proc. Hot Interconnects VII, 1999.
19.
G.Pankaj and N.McKeown, Packet classification on multiple fields, in: Proc. SIGCOMM ’99, 1999, pp. 147–160. doi:10.1145/316194.316217.
20.
L.Pauleve, H.Jegou and L.Amsaleg, Locality sensitive hashing: A comparison of hash function types and querying mechanisms, Pattern Recognit. Lett.31(11) (2010), 1348–1358. doi:10.1016/j.patrec.2010.04.004.
21.
R.Y.Qu, Z.Shijie and V.K.Prasanna, A decomposition-based approach for scalable many-field packet classification on multi-core processors, Int. J. Parallel Program.43(6) (2015), 965–987. doi:10.1007/s10766-014-0325-6.
V.Srinivasan, S.Suri and G.Varghese, Packet classification using tuple space search, in: Proc. SIGCOMM ’99, 1999, pp. 135–146. doi:10.1145/316188.316216.
24.
V.Srinivasan, S.Suri, G.Vargheseet al., Fast and scalable layer four switching, in: Proc. SIGCOMM ’98, 1998, pp. 203–227. doi:10.1145/285243.285282.
25.
V.Srinivasan, G.Varghese, S.Suri and M.Waldvogel, Fast and scalable layer four switching, ACM28(4) (1998), 191–202.
26.
Tanjent, Murmur hash first announcement, Tanjent. livejournal.com, January 2012.
27.
E.Taylor and J.S.Turner, Classbench: A packet classification benchmark, IEEE/ACM Trans. Netw.15(3) (2007), 499–511. doi:10.1109/TNET.2007.893156.
28.
P.Warkhede, S.Suri and G.Varghese, Multiway range trees: Scalable IP lookup with fast updates, Comput. Netw.44(3) (2004), 289–303. doi:10.1016/j.comnet.2003.09.004.
