سال انتشار: ۱۳۸۶

محل انتشار: پانزدهیمن کنفرانس مهندسی برق ایران

تعداد صفحات: ۶

نویسنده(ها):

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

چکیده:

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