Shakoor Vakilian

اینترنت گسترده ترین شبکه مبتنی بر سوئیچینگ بسته ای است. در تجهیزات و ابزارهای مورد استفاده برای پردازش بسته ها در این شبکه مخصوصا در شاهراه های اینترنت نیاز به پردازش های خاص و با سرعت بالا است. طیف وسیعی از ابزارهای پردازشگر بسته ها شامل مسیریاب ها، دیواره های آتش، سیستم های تشخیص نفوذ، سیستم های مدیریت حساب کاربرانو ... از دسته بندی بسته ها استفاده می کنند. به عنوان یک راهکار در پیاده سازی های سخت افزاری الگوریتم های دسته بندی بسته ها، از حافظه های تداعیگر سه وضعیتی (TCAM)به منظور جست و جوی موازی استفاده می شود. با وجود قابلیت دستیابی به سرعت جست وجوی بالا، یکی از مشکلات اصلی در استفاده از TCAMها، توان مصرفی بالای آنها می باشد.در این پایان نامه، معماری جدید برای کاهش توان مصرفی در بلوک های TCAMمورد استفاده در دسته بند سخت افزاری ارائه شده است. در معماری دسته بند پیشنهادی، نخست درخت های تصمیم گیری ایجاد شده و قوانین دسته بند بین برگ های آن توزیع می شوند. ساخت درخت تصمیم گیری با توجه به فیلد های آدرس IPمبدا و آدرس IPمقصد، انجام می گیرد. در این مرحله هر برگ درخت، متناظر با یک بلوک TCAMمی باشد. در مرحله دوم، متناظر با ساختار درخت، بخش دوم از قوانین، شامل محدوده پورت های مبدا و مقصد، در بلوک های متفاوتی از TCAMجای می گیرند. در این معماری یک بلوک TCAMاضافی به عنوان بلوک عمومیاستفاده می شود. این بلوک دربردارنده قوانین مشترک در میان برگ های درخت تصمیم است؛ بنابراین، به منظور دسته بندی، این ساختار،جهت انطباق با هر بسته،در دو مرحله ذکر شده، جستجو می شود. معماری های موجود با ساختار فوق، به دلیل توزیع نامتوازن قوانین در بلوک های TCAMاصلی و افزایش تعداد قوانین تکراری در بلوک عمومی و همچنین مشکلات ذخیره فیلدهای محدوده در TCAM،دچار مشکل اتلاف حافظه و افزایش توان مصرفی هستند. بدین منظور، برای کاهش مصرف توان در طرح پیشنهادی، الگوریتم درختی برای بهینه کردن توزیع قانون ها در بلوک های TCAMدر مرحله اول پیشنهاد شده است. ایده کلیدی برای ساخت درخت بهینه در مرحله اول، انتخاب بیت هایی برای برش در فضای ژئومتریک است.این کار باعث می شود قانون ها به صورت متوازن تربین بلوک های TCAMدر مرحله دوم توزیع شوند.توزیع متوازن قانون ها منجر به کاهش تکرارها و در نهایت کاهش تعداد قوانین موجود در بلوک عمومی