یک روش ترافیک‌آگاه برای دسته‌بندی بسته‌ها با هدف کاهش تعداد دفعات دسترسی به حافظه
الموضوعات :سعید اسدروز 1 , محمد نصیری 2 , مهدی عباسی 3 , حاتم عبدلی 4
1 - دانشگاه بوعلی سینا
2 - دانشگاه بوعلی سینا
3 - دانشگاه بوعلی سینا همدان
4 - دانشگاه بوعلی سینا
الکلمات المفتاحية: ترافیک‌آگاهدرخت AVLدسته‌بندی بسته‌هامحلی‌بودن مراجعات,
ملخص المقالة :
دسته‌بندی بسته‌ها نقش بسزایی در بهبود عملکرد تجهیزات شبکه‌ای از جمله مسیریاب‌ها، دیواره‌های آتش و سیستم‌های تشخیص نفوذ ایفا می‌کند. الگوریتم‌های دسته‌بندی بسته عموماً مبتنی بر ساختار داده‌ای ایستا هستند که الگوی رفتاری ترافیک ورودی را در بهینه‌سازی ساختار جستجو در نظر نمی‌گیرند. در این پژوهش، ویژگی‌های آماری ترافیک ورودی در نظر گرفته شده و از ساختمان داده‌های کمکی ترافیک‌آگاه در کنار ساختارهای اصلی استفاده شده است. از آنجا که حجم غالب ترافیک اینترنت، مربوط به جریان‌های بلندمدت است، برای مدت‌زمانی نه چندان کوتاه، اکثر مطابقت‌های قوانین در زیردرخت‌های مشخصی از درخت جستجو قرار دارند. برای بهره‌گیری از این ویژگی، در این پژوهش از ساختار داده درخت AVL برای نگهداری قوانین دسته‌بند و از حدهای بالا و پایین مجموعه قوانین به عنوان گره‌های درخت جستجو استفاده شده است. ارزیابی‌ها نشان می‌دهد که با افزایش چولگی بسته‌های آزمون، تعداد دفعات دسترسی به حافظه الگوریتم دسته‌بندی ترافیک‌آگاه نسبت به الگوریتم دسته‌بندی پایه کاهش قابل توجهی دارد. بر اساس ارزیابی‌ها، دسته‌بندی بسته ترافیک‌آگاه با استفاده از قوانین پرتکرار می‌تواند میانگین کل تعداد دفعات دسترسی به حافظه و در نتیجه زمان جستجو را بیش از 40 درصد کاهش دهد.
[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.
