پایان نامه کارشناسی ارشد خانم سعیده وثاقتی فاضل با عنوان «ارائه روشی برای بهبود الگوریتم برش بیتی با در نظر گرفتن معیار حافظه»

عنوان:

ارائه روشی برای بهبود الگوریتم برش بیتی با در نظر گرفتن معیار حافظه

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

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

اساتید ممتحن:

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

دکتر حاتم عبدلی

پژوهشگر:

سعیده وثاقتی فاضل

زمان:

دوشنبه 29/11/1397 ساعت 14:00

مکان:

آمفی تئاتر دانشکده مهندسی

BU-Ali Sina University

Faculty of Engineering

Department of Computer Engineering

Thesis submitted for Master of Science in Information Technology Engineering -        

 Computer Networks

Title

Providing a method for improving the bitcuts algorithm by taking the memory criterion

Supervisor:

Dr. Mahdi Abbasi

Supervisor:

Dr. Mohammad Nassiri

Dr. Hatam Abdoli

By:

Saeede Vesaghati Fazel

February, 18, 2019

دسته‌بندی بسته‌ها یکی از وظایف اصلی پردازنده‌های شبکه‌ای می‌باشد. مهمترین مسئله در این زمینه، استفاده از الگوریتمی است که بتواند بسته‌ها را با سرعت بالا و مصرف حافظه پایین، دسته‌بندی نماید. الگوریتم‌های دسته‌بندی به دو رده‌ی کلی نرم‌افزاری و سخت‌افزاری تقسیم می‌شوند. الگوریتم‌های مبتنی بر درخت تصمیم  یک گروه از روش‌های نرم‌افزاری دسته‌بندی بسته‌ها هستند که با به کارگیری روش‌های مختلف برای انجام برش در مدل هندسی معادل نمایش قانون‌های دسته‌بند، درخت تصمیم بهینه را می‌سازند. الگوریتم‌های موجود در این دسته، در دسته‌بندی مجموعه قوانین بزرگ عملکرد مطلوبی از خود نشان نمی‌دهند. آنها برای کاهش حافظه مصرفی، سرعت دسته‌بندی را تا حد چشمگیری افزایش می‌دهند و یا بالعکس، برای افزایش سرعت دسته‌بندی با افزایش قابل توجهی در حافظه مصرفی مواجه می‌شوند. الگوریتمBitCuts که اخیرا برای افزایش سرعت جستجو در الگوریتم‌های درختی ارائه شده است نیز از این مشکل مستثنی نشده است. ما در این پایان نامه روش جدیدی ارائه داده‌ایم که با تغییر نحوه انتخاب بیت در هر گره از درخت، حافظه مورد نیاز و تعداد دسترسی به حافظه را در الگوریتم مذکور کاهش می‌دهد. نتایج ارزیابی موید آن است که  متوسط تعداد دسترسی ها به حافظه جهت  دسته بندی بسته‌ها و میزان حافظه مصرفی در روش پیشنهادی،  به ترتیب برابر %61  و %13 روش پایه Bitcutsاست.

Packet classification is one of the fundamental tasks of network processors. The most important issue in this regard is the use of one algorithm that can classify packets at high speed with low memory consumption. Classification algorithms are divided into two general classes including hardware and software algorithms. Decision tree-based algorithms are a group of software methods of packets classification. These methods construct decision-trees by employing various geometrical considerations in cutting the geometric representation model of rules. unfortunately, the existing decision-tree algorithms cannot meet the desired performance levels on handle large scale rule-sets. They reduce the speed of packet classification significantly to reduce the memory consumption, or in order to increase the speed of the classification, they increase the memory consumption. The BitCuts algorithm recently presented for increasing the search speed of tree-based algorithms is not exempt from this problem. In this thesis, we propose a new method that reduces both the memory usage and the number of memory accesses by changing the way of the bit selection in each node of the Bitcuts tree. The evaluation results indicate that the proposed method requires only 61% of the average memory accesses and 13% memory consumption of BitCuts.

1-     مشخصات فردی

نام و نام خانوادگی: سعیده وثاقتی فاضل

پست الکترونیکی: saeede.vesaghati@gmail.com

2-     اطلاعات تحصیلی

کارشناسی مهندسی فناوری اطلاعات، دانشگاه صنعتی همدان

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

3-     مهارت‌ها

آشنایی کامل با مفاهیم شبکه‌های کامپیوتری

تسلط به زبان برنامه نویسی c و c++

آشنایی با c++، java، html&Css، JQuery، JavaScript، ASP.Net، Virtualization