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