پایان نامه کارشناسی ارشد خانم هاجر رضایی با عنوان «ارتقاء عملکرد الگوریتم‎های دسته‎بندی بسته مبتنی بر درخت تصمیم گیری با استفاده از تکنیک انتقال به برگ‌ها»

Bu-Ali Sina University

Faculty of Engineering

Department of Computer Engineering

Thesis submitted for Master of Science in Information Technology Engineering-

Computer Networks

Title

Enhancing The Performance of The Decision Tree Based Packet Classification Algorithms Using Leaf-pushing Technique

Supervisor:

Mahdi Abbasi (Ph.D)

Advisor:

Mohammad Nassiri (Ph.D)

By:

Hajar Rezaee

February, 18,  2019

چکیده:

برای محافظت یک شبکه، اغلب سیستم‌‌های امن ساز شبکه از قبیل سامانه‌های تشخیص نفوذ و دیوار آتش برای کنترل و نظارت بر ترافیک شبکه راه اندازی می‌شوند . این سامانه‌ها اغلب موجب تاخیر قابل توجهی در تحلیل بسته‌های شبکه می‌شوند. با دسته‌بندی سریع بسته‌ها تاخیر ‌می‌تواندکاهش یابد، که موجب ‌‌دسته‌بندی موثر ترافیک شبکه، و همچنین افزایش سرعت تحلیل بسته‌های شبکه ‌می‌شود. بنابراین دسته‌بندی بسته یک از چالش برانگیز‌ترین عملیات های انجام شده توسط روتر‌ها در سرعت سیم برای هر بسته ورودی است. در سال‌های اخیر، محققان بسیاری روش‌های متعددی برای دسته‌بند‌های ‌‌چند‌بعدی که بسته‌بندی سریع بسته‌ها را فراهم می‌کند ارائه ‌‌کرده‌اند. برای فضاهای جستجو که متشکل از قانون‌ها متعددی است که  به صورت هندسی نشان داده شده ، الگوریتم های تجزیه فضای مختلفی برای ارائه روش های جستجو موثر مورد مطالعه قرار گرفته‌است. این روش‌ها کارایی کمی‌ دارند و در عین حال فضای ذخیره سازی زیادی نیاز دارند. در حالی که الگوریتم جستجوی دودویی چند‌بعدی روش ساده برای نشان دادن فضای جستجو هندسی به یک ساختار دو بعدی ارائه می‌دهد، کارایی دسته‌بندی بالایی  را ارائه نمی‌دهد، زیرا عملیات نگاشت فضای هندسی ناقص است. در این مقاله، روشی جهت  ‌‌دسته‌بندی بسته‌ها بر اساس درخت جستجوی دودویی ‌‌چند‌بعدی ارائه ‌‌شده‌است. این روش از فضای نمایش هندسی برای نمایش فیلد‌های مختلف استفاده ‌می‌کند و با تجزیه فضای جستجو به صورت بازگشتی سرعت جستجوی بالایی را فراهم ‌می‌آورد. همچنین این مقاله الگوریتم درخت انتقال به برگ‌های درخت جستجوی دودویی چند‌بعدی  را برای ارتقاء کارایی درخت جستجوی دودویی چند‌بعدی معرفی می‌نماید. ما همچنین  یک روش کارآمد برای الگوریتم با استفاده از یک فیلتر بلوم و یک جدول درهم‌ساز ارائه می‌کنیم. در آزمایشات از ابزار class bench استفاده شده‌است. اندازه قانون‌های تولیدی k5، k10،k50، k100 است. نتایج شبیه سازی نشان می‌دهد که درخت انتقال به برگ‌های جستجوی دودویی چندبعدی پیشنهاد شده ما عملکرد دسته‌بندی بسته‌ها را تا 24 برابر برای مجموعه‌هایی که بیش از100000 قانون دارند در مقایسه با جستجوی دودویی چند‌بعدی بهبود می بخشد. برای مقایسه با دیگر الگوریتم های تجزیه فضایی، یک ساختار بازنگری شده  روی درخت انتقال به برگ‌ها جستجوی دودویی چندبعدی نیز پیشنهاد شده‌‌است که برای کاهش دسترسی به حافظه، روی قانون‌های موجود در برگ‌های درخت، یک برش هوشمند ارائه می‌کند. نتایج شبیه سازی نشان می‌دهد که ساختار بازنگری شده پیشنهادی، نسبت به بعضی الگوریتم‌های تجزیه فضا تعداد دسترسی‌ها را بسیار کاهش می‌دهد.

Abstract:

To protect a network, secure network systems such as intrusion detection system (IDS) and firewall are often installed to control or monitor network traffic. These systems often incur substantial delay for analyzing network packets. The delay can be reduced with fast packet classification, which can effectively classify network traffic, and consequently accelerate the analysis of network packets.  Packet classification is one of the most challenging functionalities performed by routers at wire-speed for every incoming packet. In the last few years, many researchers devoted to providing fast packet classification methods for multidimensional classifier. For search spaces composed of multiple rules represented geometrically, various space decomposition algorithms have been studied to provide effective search methods. However, these methods either suffer from poor performance and huge storage requirement. While an k dimentional tree (Kd-tree) provides a simple and intuitive way of mapping the geometrical search space into a two-dimensional (2-D) trie structure, it does not provide high-speed classification performance because the mapping is incomplete. This paper proposes the method for packet classification based on a multidimensional binary search tree. This method uses the geometric space to display different fields and by decomposing the search space, provides recursive search speeds up. This paper proposes the algoritm of leaf-pushing into the Kd-tree improve the classification performance of the Kd-tree. We also discuss an efficient implementation technique for our algorithm using a Bloom filter and a hash table. Simulations using class  bench  have been performed. The size of rules that generated by class bench are 5K, 10K, 50K, 100K.  Simulation results show that our proposed leaf-pushing Kdtree improves the packet classification performance up to 24 times for sets with up to 100,000 rules compared with the Kdtree. To be compared with other space decomposition algorithms, a refined structure of the leaf-pushing Kd-treeto provide a HiCuts on the rules of the tree leaves to reduce memory access is also proposed. The simulation results show that the proposed refined structure significantly reduces the number of memory access than some space decompression algorithms.

رزومه:

Hajar rezaee