بهبود کارآیی درختواره های سطح فشرده به کمک پردازنده ی گرافیکی

مسیریاب های اینترنت برای هدایت بسته های داده به سمت مقصد موردنظر از اطلاعات جداول مسیریابی استفاده می کنند. در این جداول آدرس های مقصد با بهترین مسیر ارسال هرکدام ذخیره شده اند. عملیات جستجو در این جداول مسیریابی و یافتن بهترین مسیر متناظر با آدرس مقصد یک بسته ی ورودی را عملیات Lookup می نامیم. هرچه عمل جستجوی آدرس سریع تر انجام شود، ارسال بسته سریع تر شده و سرعت انتقال داده در اینترنت افزایش پیدا خواهد کرد. یکی از بهترین ساختارهای نرم افزاری موجود برای مسئله ی Lookup درختواره ی سطح فشرده است. این ساختار دارای ارتفاع کمی بوده و عملیات جستجوی پیشوند را با کمترین تعداد دسترسی به حافظه انجام می دهد و بنابراین بسیار سریع است. درعوض در عملیات های اضافه و حذف کردن پیشوند ضعیف است و باعث می-شود این الگوریتم تنها روی جداول مسیریابی ایستا قابل بکارگیری باشد. در این مقاله راه کارهایی برای حل مشکلات این ساختار ارائه شده است. این راه کارها مبتنی بر همکاری پردازنده های مرکزی و گرافیکی می باشند و سعی شده است که تاخیرهای تشکیل و به-روزرسانی جدول مسیریابی در عمل پنهان شده و نقطه ضعف درختواره ی سطح فشرده پوشش داده شود. طرح پیشنهادی روی جدول مسیریابی واقعی AS۴۶۳۷ پیاده سازی شده و نتایج آزمایشات نشان داده است که عملکرد درختواره ی سطح فشرده بهبود محسوسی داشته است.

Keywords:

Lookup , به روزرسانی جداول مسیریابی , درختواره سطح فشرده , پردازنده ی گرافیکی , کودا , OpenMP