صغری آقامحمدلو

تاریخ انتشار : Publish : نسخه قابل چاپ Print

پایان‌نامه برای دریافت درجه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات گرایش شبکه‌های کامپیوتری

 

 عنوان:

ارائه‌ی روش جدید تخمین کارآیی الگوریتم‌های دسته‌بندی بسته در فضای هندسی به کمک روش‌های آماری

 


استاد راهنما:

دکتر مهدی عباسی

 

اساتید داور:

دکتر محمد نصیری

دکتر یونس سیفی

 

نگارش:

صغری آقامحمدلو

 

19/11/1394


ساعت 18


چكيده:

دسته‌بندی بسته‌ها یکی از پردازش‌های اساسی در سیستم­های متنوع شبکه­ای است که اغلب توسط پردازنده‌های شبکه‌ای اجرا می­گردد. دسته‌بندی بسته­ها فرآیندی خودکار است که جریان­های ترافیکی شبکه را براساس پارامترهای متعدد از جمله درگاه‌ و آدرس فرستنده و گیرنده طبقه­بندی می­نماید. اکثر تحقیقات در حوزه دسته­بندی بسته­ها تنها سعی نموده­اند که بر اساس ارائه الگوریتم‌های جدید، مصرف حافظه را کاهش  و سرعت دسته‌بندی را افزایش دهند و هیچگاه تاثیر مشخصه­های آماری قوانین دسته­بند را در کارایی نهایی ارزیابی نکرده­اند. در این پژوهش، ابتدا نحوه محاسبه ویژگی‌های مهم آماری مهمی چون تعامد و تعمیم،  طول جفت پیشوند آدرس و انحراف  برای هر مجموعه قانون توضیح داده شده است. سپس، تاثیر هریک از شاخص­ها، به صورت منفرد و مجموع بر میزان کارایی الگوریتم­های دسته­بندی مهم به نام های Hicuts و H-Trie, AQT، در روند دسته­بندی بسته‌های آزمون ارزیابی شده است. نتایج ارزیابی نشان می­دهد با محاسبه شاخص­های مذکور در مورد قوانین دسته­بندهای مورد استفاده در الگوریتم­های مذکور، می­توان کارایی الگوریتم دسته­بند را از لحاظ میزان مصرف حافظه و سرعت دسته­بندی پیش­بینی کرد. در مورد دو الگوریتم مذکور به ترتیب، وجود تعداد زیاد قوانین با جفت پیشوند آدرس طولانی و وجود ساختارهای قائم در مجموعه قوانین، تأثیر قابل توجهی در کاهش حافظه مصرفی و افزایش سرعت دسته‌­بند دارد.

 



واژگان كليدي: الگوریتم‌های دسته‌بندی، فضای هندسی، روش‌های آماری.


Abstract:
Packet Classification is one of the basic processes in a variety of network systems,often performed by network processors. Packet Classification is An automatic process that network traffic flows are classified based on multiple parameters, such as source and destination port, source and destination address. Most research in packet classification have only tried to propose new algorithms to reduced memory consumption and increase speed classification and are never evaluated affect the characteristics of the statistical classification rules on the performance. In this study, in the first, is described a method to compute the statistically significant such as properties of orthogonality and wildcard, the address prefix pair and skew for each ruleset. Then, the effect of each indicators evaluated on the performance of important classification algorithm called Hicuts, AQT and H-Trie, in individual and aggregate.
The assessment results show these parameters with these algorithms help us to predicate memory usage and speed of classify. In these algorithms, the size of rulesets, the number of prefix pairs long and orthogonality in rulesets, have a significant impact on the speed and reduce the memory consumption Classification.