A Traffic-Aware Packet Classification Method to Reduce Memory Accesses
Subject Areas : electrical and computer engineeringSaeid Asadrooz 1 , Mohammad Nassiri 2 , M. A. 3 , 4 *
1 -
2 -
3 -
4 -
Keywords: AVL treelocality of referencepacket classificationtraffic-aware,
Abstract :
Packet classification plays a critical role in improving the performance of many network devices including routers, firewalls and intrusion detection systems. Due to the increasing number of classification rules, high traffic volume and high bandwidth network links, designing an efficient packet classifier becomes more challenging. Packet classification algorithms that use static data structure do not consider the pattern of the incoming traffic in optimizing their search mechanism. Therefore, we use some statistical characteristics of the incoming traffic to propose a traffic aware data structure. Since most Internet traffic volume belong to long-live flows, the majority of the packets are matched to the rules in a few sub trees. To take the advantage of this feature, AVL tree data structure is served for storing classification rules where the upper and lower limits of the rule-set are used as nodes. Our evaluation have shown that with increasing the skewness of data packets, the average number of memory accesses are significantly decreased compared to the basic case. Finally, evaluation results show that the traffic-aware packet classification with high frequency rules can decrease more than 40% of the average number of memory accesses and consequently the lookup time.
[1] P. Gupta and N. McKeown, "Algorithms for packet classification," IEEE Network, vol. 15, no. 2, pp. 24-32, Mar. 2001.
[2] H. Oudah, B. Ghita, and T. Bakhshi, "A novel features set for internet traffic classification using burstiness," in Proc. Int. Conf. ICISSP, pp. 397-404, Prague, Czech Republic, 23-25 Feb.
[3] L. Ding, J. Liu, T. Qin, and H. Li, "Internet traffic classification based on expanding vector of flow," COMPUT. NETW, vol. 129, no. 1, pp. 178-192, Dec. 2017.
[4] H. Kim, et al., "Internet traffic classification demystified: myths, caveats, and the best practices," in Proc. Int. Conf. ACM CoNEXT, Article 11, pp. 1-12, Dec. 2008.
[5] A. Bergamini and L. Kencl, "Network of shortcuts: an adaptive data structure for tree-based search methods," in Proc. Int. Conf. Networking, pp. 523-535, May 2005.
[6] A. El-Atawy, T. Samak, E. Al-Shaer, and H. Li, "Using online traffic statistical matching for optimizing packet filtering performance," in Proc. IEEE Int. Conf., on Computer Communications, pp. 866-874, Anchorage, AK, USA, 6-12 May 2007.
[7] H. Hamed and E. Al-Shaer, "Dynamic rule-ordering optimization for high-speed firewall filtering," in Proc. Int. Conf. ASIACCS, pp. 332-342, Taipei Taiwan, 21 Mar.2006.
[8] E. Cohen and C. Lund, "Packet classification in large ISPs: design and evaluation of decision tree classifiers," in Proc. Int. Conf. ACM SIGMETRICS, pp. 73-84, Jun. 2005.
[9] W. Yu, S. Sivakumar, and D. Pao, "Pseudo-TCAM: SRAM-based architecture for packet classification in one memory access," IEEE Networking Letters, vol. 1, no. 2, pp. 89-92, Feb. 2019.
[10] S. S. Vegesna, A. C. Nara, and N. M. Sk, "A novel rule mapping on TCAM for power efficient packet classification," ACM Trans. on Design Automation of Electronic Systems (TODAES), vol. 24, no. 5, pp. 1-23, Jun. 2019.
[11] Z. Liu, S. Sun, H. Zhu, J. Gao, and J. Li, "BitCuts: a fast packet classification algorithm using bit-level cutting," Computer Communications, vol. 109, no. 1, pp. 38-52, Sept. 2017.
[12] M. Abbasi, S. V. Fazel, and M. Rafiee, "MBitCuts: optimal bit-level cutting in geometric space packet classification," The J. of Supercomputing, vol. 76, no. 4, pp. 3105-3128, Apr. 2020.
[13] W. Li, X. Li, H. Li, and G. Xie, "Cutsplit: a decision-tree combining cutting and splitting for scalable packet classification," in Prof. IEEE Conf. on Computer Communications, INFOCOM'18, pp. 2645-2653, Honolulu, USA, 16-19 Apr. 2018.
[14] C. L. Hsieh, N. Weng, and W. Wei, "Scalable many-field packet classification for traffic steering in SDN switches," IEEE Trans. on Network and Service Management, vol. 16, no. 1, pp. 348-361, Sept. 2018.
[15] W. Li, D. Li, Y. Bai, W. Le, and H. Li, "Memory-efficient recursive scheme for multi-field packet classification," IET Communications, vol. 13, no. 9, pp. 1319-1325, Feb. 2019.
[16] X. Dong, M. Qian, and R. Jiang, "Packet classification based on the decision tree with information entropy," The J. of Supercomputing, vol. 76, no. 6, pp. 4117-4131, Jun. 2020.
[17] A. A. Abdulhassan and M. Ahmadi, "Cuckoo filter-based many-field packet classification using X-tree," The J. of Supercomputing, vol. 75, no. 9, pp. 5667-5687, Sept. 2019.
[18] S. Greenberg, T. Sheps, D. A. Leon, and Y. Ben-Shimol, "Packet classification using GPU and one-level entropy-based hashing," IEEE Access, vol. 8, [18] pp. 80610-80623, Apr. 2020.
[19] B. Xiong, Z. Hu, Y. Luo, and J. Wang, "Cuckooflow: achieving fast packet classification for virtual openflow switching by exploiting network traffic locality," in Proc. IEEE Intl Conf. on Parallel & Distributed Processing, pp. 1123-1130, Xiamen, China, 16-18 Dec. 2019.
[20] A. El-Atawy, H. Hamed, and E. Al-Shaer, Adaptive Statistical Optimization Techniques for Firewall Packet Filtering, DePaul Univ., Chicago, IL, Tech. Rep. CTI-TR-05-019, 2005.
[21] S. Acharya, J. Wang, Z. Ge, T. F. Znati, and A. Greenberg, "Traffic-aware firewall optimization strategies," in Proc. IEEE Int. Conf. ICC'06, vol. 5, pp. 2225-2230, Istanbul, Turkey, 11-15 Jun. 2006.
[22] S. Acharya, et al., "OPTWALL: a hierarchical traffic-aware firewall," in Proc. Int. Conf. NDSS, 11 pp., San Diego, CA, USA, 28 Feb. 2007.
[23] S. H. Shaikot and M. S. Kim, "NPF: A simple, traffic-adaptive packet classifier using on-line reorganization of rule trees," in Proc. IEEE Int. Conf. LCN, pp. 899-906, Zurich, Switzerland, 20-23 Oct. 2009.
[24] S. H. Shaikot and M. S. Kim, "Lightweight traffic-aware packet classification for continuous operation," in Proc. IEEE Int. Conf. Int. Symp. on Applications and the Internet, pp. 59-67, Seoul, Korea (South), 19-23 Jul. 2010.
[25] A. S. Sairam, R. Kumar, and P. Biswas, "Implementation of an adaptive traffic-aware firewall," in Proc. Int. Conf. SINCONF, pp. 385-391, , Glasgow, Scotland UK, 9 Sept. 2014.
[26] D. E. Taylor and J. S. Turner, "Classbench: a packet classification benchmark," IEEE/ACM Trans. on Networking, vol. 15, no. 3, pp. 499-511, Jun. 2007.
[27] L. Zhang, "Virtual clock: a new traffic control algorithm for packet switching networks," in Proc. Int. Conf. SIGCOMM, pp. 19-29, Philadelphia, PA, USA, 1 Aug. 1990.
[28] R. Jain and S. Routhier, "Packet trains--measurements and a new model for computer network traffic," IEEE J. SEL AREA COMM., vol. 4, no. 6, pp. 986-995, Sept. 1986.
[29] N. Alborz and L. Trajkovic, "Implementation of virtualclock scheduling algorithm in OPNET," in Proc. Int. Conf. OPNETWORK, 7 pp., Aug. 2001.
[30] D. E. Knuth, The Art of Computer Programming 3: Sorting and Searching, AddisonWesley, MA, 1973.
[31] T. Srinivasan, M. Nivedita, and V. Mahadevan, "Efficient packet classification using splay tree models," in Proc. Int. Conf. IJCSNS, vol. 6, pp. 28-35, Seoul, Korea (South), May 2006.