سجاد میرزایی

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

دانشکده مهندسی

گروه آموزشی مهندسی کامپیوتر

 

 

عنوان:

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

 

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

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

 

استاد مشاور:

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

 

پژوهشگر:

سجاد میرزایی

چکیده:

یکی از وظایف­ اصلی پردازنده­های شبکه­ای طبقه­بندی بسته­ها[1] است. مهمترین مسئله در این زمینه، استفاده از الگوریتمی است که بتواند بسته­ها را با سرعتی در حد سرعت شبکه طبقه­بندی کند و همچنین، از حافظه در دسترس به صورت بهینه استفاده نماید. الگوریتمArea based quad-tree(AQT)، یکی از الگوریتم­های  مطرح در این زمینه است. دراین الگوریتم، یک جستجو برای یافتن بهترین قانون منطبق با طبقه­بندی بسته­ها بر اساس تصمیم­گیری به ازای یک بیت آدرس IP مبدأ و یک بیت آدرس IP مقصد انجام می­شود. به علت ثابت بودن نقاط برش در الگوریتم مذکور، درختی حاصل نامتوازن است. بنابراین، سرعت اجرای الگوریتم بسیار پایین می­باشد. در این تحقیق به ساخت درخت AQT با استفاده از برنامه­ ریزی پویا پرداخته شده است. پیاده­سازی الگوریتم پیشنهادی و ارزیابی طبقه­بندی بسته­های تولید شده توسط ابزار ClassBench نشان می­دهد که با متوازن شدن درخت، افزایش قابل توجهی در سرعت جستجو و کاهشی در حافظه مورد نیاز بدست می­آید.

 

زمان: شنبه   29/6/1393 ساعت 16 

مکان: سمینار 2 دانشکده مهندسی



[1] Packet classification