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.
A.Abdulhassan and M.Ahmadi, Parallel Many Fields Packet Classification Technique Using R-Tree, Annual Conference on New Trends in Information and Communications Technology Applications (NTICT 2017), IEEE, 2017. doi:10.1109/NTICT.2017.7976137.
3.
J.Alakuijala and J.Wassenberg, HighwayHash on Github, 3-2016.
4.
M.A.Bender, M.Farach-Colton, R.Johnson, R.Kraner, B.C.Kuszmaul, D.Medjedovic and E.Zadok, Don’t thrash: How to cache your hash on flash, in: Proceedings of the VLDB Endowment, 2012, pp. 1627–1637.
F.Breitinger, B.Guttman, M.McCarrin, V.Roussev and D.White, Approximate matching: definition and terminology, NIST Special Publication 800-168, https://nvlpubs.nist.gov/nistpubs/specialpublications/nist.sp.800-168.pdf.
7.
J.D.Burman, Software-Defined Networks (SDN): What systems integrators need to know, 2013.
8.
Y.Chang, C.Lee and C.Su, Multi-field range encoding for packet classification in TCAM, in: Proceedings IEEE (INFOCOM 2011), IEEE, 2011, pp. 196–200. doi:10.1109/INFCOM.2011.5935001.
9.
Y.C.Cheng and P.C.Wang, Packet classification using dynamically generated decision trees, IEEE Transactions on Computers64(2) (2015), 582–586. doi:10.1109/TC.2013.227.
10.
R.Cohen and D.Raz, Simple efficient TCAM based range classification, in: INFOCOM, 2010 Proceedings IEEE, 2010, pp. 1–5.
11.
R.Dobai, J.Korenek and L.Sekanina, Evolutionary design of hash function pairs for network filters, Applied Soft Computing56 (2017), 173–181. doi:10.1016/j.asoc.2017.03.009.
12.
B.Fan, D.G.Andersen, M.Kaminsky and M.D.Mitzenmacher, Cuckoo filter: Practically better than bloom, in: Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, ACM, 2014, pp. 75–88.
13.
P.Francesco and U.Fiore, A nonlinear, recurrence-based approach to traffic classification, Computer Networks53(6) (2009), 761–773. doi:10.1016/j.comnet.2008.12.015.
14.
T.Ganegedara, W.Jiang and V.K.Prasanna, A scalable and modular architecture for high-performance packet classification, IEEE Transactions on Parallel and Distributed Systems25(5) (2014), 1135–1144. doi:10.1109/TPDS.2013.261.
15.
P.Goudarzi, H.Tabatabaei and M.Ahmadi, Khorramshahr: A scalable peer to peer architecture for port warehouse management system, Journal of Network and Computer Applications76 (2016), 49–59. doi:10.1016/j.jnca.2016.09.015.
16.
P.Gupta and N.McKeown, Packet classification on multiple fields, ACM SIGCOMM Computer Communication Review29(4) (1999), 147–160. doi:10.1145/316194.316217.
17.
V.Gupta and F.Breitinger, How Cuckoo Filter Can Improve Existing Approximate Matching Techniques, International Conference on Digital Forensics and Cyber Crime, Springer International Publishing, 2015.
18.
A.Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, Vol. 14, ACM, 1984.
19.
Y.Hua, B.Xiao and J.Wang, BR-tree: A scalable prototype for supporting multiple queries of multidimensional data, IEEE Transactions on Computers58(12) (2009), 1585–1598. doi:10.1109/TC.2009.97.
20.
L.Hyesook and S.Young Byun, Packet Classification Using a Bloom Filter in a Leaf-Pushing Area-Based Quad-Trie, Proceedings of the Eleventh ACM/IEEE Symposium on Architectures for Networking and Communications Systems, IEEE Computer Society, 2015.
21.
R.Imam and A.W.Muhammad, Network packet classification using neural network based on training function and hidden layer neuron number variation, International Journal of Advanced Computer Science and Applications8(6) (2017), 248–252.
22.
T.Inoue, T.Mano, K.Mizutani, S.I.Minato and O.Akashi, Rethinking packet classification for global network view of software-defined networking, in: 2014 IEEE 22nd International Conference on Network Protocols (ICNP), IEEE, 2014, pp. 296–307. doi:10.1109/ICNP.2014.52.
23.
W.Jiang and V.K.Prasanna, Field-split parallel architecture for high performance multi-match packet classification using FPGAs, in: Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures, ACM, 2009, pp. 188–196.
24.
T.Kaler, Cache efficient bloom filters for shared memory machines, https://pdfs.semanticscholar.org/465b/0d7872764bba2a6daadffa9a169d056b8c7c.pdf.
25.
K.Kogan, S.Nikolenko, O.Rottenstreich, W.Culhane and P.Eugster, SAX-PAC (Scalable and Expressive Packet Classification.), in: ACM SIGCOMM Computer Communication Review, ACM, 2014, pp. 15–26.
26.
T.V.Lakshman and D.Stiliadis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, in: ACM SIGCOMM Computer Communication Review, ACM, 1998, pp. 203–214.
27.
A.X.Liu, R.M.Chad and T.Eric, Packet classification using binary content addressable memory, Biological Cybernetics24(3) (2016), P:1295–P:1307.
28.
Z.Liu, S.Sun, H.Zhu, J.Gao and J.Li, BitCuts: A fast packet classification algorithm using bit-level cutting, Computer Communications109 (2017), 38–52. doi:10.1016/j.comcom.2017.05.001.
29.
H.Lu and S.Sahni, O (logW) multidimensional packet classification, IEEE/ACM Transactions on Networking (TON)15(2) (2007), 462–472. doi:10.1109/TNET.2007.892845.
30.
N.McKeown, T.Anderson, H.Balakrishnan, G.Parulkar, L.Peterson and J.Rexford, OpenFlow: Enabling innovation in campus networks, ACM SIGCOMM Computer Communication Review38(2) (2008), 69–74. doi:10.1145/1355734.1355746.
31.
J.Mitra and N.Tapan, Reconfigurable very high throughput low latency VLSI (FPGA) design architecture of CRC 32, Integration, the VLSI Journal56 (2017), 1–14. doi:10.1016/j.vlsi.2016.09.005.
32.
A.Pagh, R.Pagh and S.S.Rao, An optimal Bloom filter replacement, in: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2005, pp. 823–829.
33.
R.Pagh and F.F.Rodler, Cuckoo Hashing, Springer, Berlin, 2001.
34.
R.Y.Qu, Z.Shijie and K.P.Viktor, A decomposition-based approach for scalable many-field packet classification on multi-core processors, International Journal of Parallel Programming43(6) (2015), 965–987. doi:10.1007/s10766-014-0325-6.
35.
R.Y.Qu and K.P.Viktor, High-performance and dynamically updatable packet classification engine on FPGA, IEEE Transactions on Parallel and Distributed Systems27(1) (2016), 197–209. doi:10.1109/TPDS.2015.2389239.
36.
S.Singh, F.Baboescu, G.Varghese and J.Wang, Packet classification using multidimensional cutting, in: Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM’03), ACM, New York, 2003, pp. 213–224. doi:10.1145/863955.863980.
37.
Specification, OpenFlow Switch, Version 1.4. 0, October 14, 2013.
D.E.Taylor, Survey and taxonomy of packet classification techniques, ACM Computing Surveys (CSUR)37(3) (2005), 238–275. doi:10.1145/1108956.1108958.
40.
D.E.Taylor and J.S.Turner, Scalable packet classification using distributed crossproducing of field labels, in: 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005), Proceedings IEEE, IEEE, 2005, pp. 269–280. doi:10.1109/INFCOM.2005.1497898.
41.
D.E.Taylor and J.S.Turner, Classbench: A packet classification benchmark, IEEE/ACM Transactions on Networking15(3) (2007), 499–511. doi:10.1109/TNET.2007.893156.
42.
M.Varvello, R.Laufer, F.Zhang and T.V.Lakshman, Multilayer packet classification with graphics processing units, IEEE/ACM Transactions on Networking24(5) (2016), 2728–2741. doi:10.1109/TNET.2015.2491265.
43.
G.S.Walia and R.Kapoor, Particle filter based on cuckoo search for non-linear state estimation, in: Advance Computing Conference (IACC), 2013 IEEE 3rd International, IEEE, 2013, pp. 918–924. doi:10.1109/IAdCC.2013.6514349.
P.Warkhede, S.Suri and G.Varghese, Multiway range trees: Scalable IP lookup with fast updates, Computer Networks, 44(3) (2004), 289–303. doi:10.1016/j.comnet.2003.09.004.
46.
J.Wee and P.Wooguil, Fast packet classification based on hybrid cutting, IEEE Communications Letters21(5) (2017), 1011–1014. doi:10.1109/LCOMM.2017.2658605.
47.
P.Zhong, An IPv6 address lookup algorithm based on recursive balanced multi-way range trees with efficient search and update, in: Proceedings of the International Conference on Computer Science and Service System (CSSS), 2011, pp. 2059–2063.
