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

مسيرياب هاي اينترنت براي هدايت بسته هاي داده به سمت مقصد موردنظر از اطلاعات جداول مسيريابي استفاده مي كنند. در اين جداول آدرس هاي مقصد با بهترين مسير ارسال هركدام ذخيره شده اند. عمليات جستجو در اين جداول مسيريابي و يافتن بهترين مسير متناظر با آدرس مقصد يك بسته ي ورودي را عمليات Lookup مي ناميم. هرچه عمل جستجوي آدرس سريع تر انجام شود، ارسال بسته سريع تر شده و سرعت انتقال داده در اينترنت افزايش پيدا خواهد كرد. يكي از بهترين ساختارهاي نرم افزاري موجود براي مسئله ي Lookup درختواره ي سطح فشرده است. اين ساختار داراي ارتفاع كمي بوده و عمليات جستجوي پيشوند را با كمترين تعداد دسترسي به حافظه انجام مي دهد و بنابراين بسيار سريع است. درعوض در عمليات هاي اضافه و حذف كردن پيشوند ضعيف است و باعث مي شود اين الگوريتم تنها روي جداول مسيريابي ايستا قابل بكارگيري باشد. در اين مقاله راه كارهايي براي حل مشكلات اين ساختار ارائه شده است. اين راه كارها مبتني بر همكاري پردازنده هاي مركزي و گرافيكي مي باشند و سعي شده است كه تاخيرهاي تشكيل و به روزرساني جدول مسيريابي در عمل پنهان شده و نقطه ضعف درختواره ي سطح فشرده پوشش داده شود. طرح پيشنهادي روي جدول مسيريابي واقعي AS4637 پياده سازي شده و نتايج آزمايشات نشان داده است كه عملكرد درختواره ي سطح فشرده بهبود محسوسي داشته است.