بخشی از مقاله
چکیده
یکی از موارد مهم طراحی در مسیریابهای IP نسل جدید، مکانیزم جستجوی مسیر است. به ازای هر بسته، بخش جستجوی مسیر، باید عمل تطبیق IP مقصد، با طولانیترین پیشوند را انجام دهد تا پورت خروجی بسته مشخص شود. در این مقاله، یک روش جستجوی مسیر سریع ارائه شده است، که نیاز به یک حافظه کوچک دارد و میتواند به آسانی در سختافزار پیادهسازی شود. در این روش اکثر جستجوها به یک دسترسی به حافظه نیاز دارند و هیچ جستجویی بیش از 3
بار دسترسی نیاز ندارد، در صورت استفاده از روش خط لوله، همه جستجوها با یکبار دسترسی به حافظه انجام میشوند.
این روش اگر در حافظههای امروزی با تأخیر 10 نانوثانیه پیادهسازی شود، میتواند 100 میلیون جستجوی مسیر در ثانیه انجام دهد،که بسیار سریعتر از روشهای رایج پیادهسازی شده است. این مقاله همچنین به پیاده سازی توام سختافزاری و نرمافزاری انجام شده این روش می پردازد که برای مسیریابهای Access بهینه و برروی FPGA پیادهسازی گردیده است که حجم حافظه و اندازه گیت مصرفی در آن پایین می باشد. این روش در مقایسه با روشهای مشابه در این سطح بسیار بهینه بوده و با سرعت پالس ساعت پایین، بیش از10 میلیون جستجو در ثانیه انجام می دهد.
واژههای کلیدی
مسیریابی، مسیریاب IP، تطبیق، مسیرده، آرایه های برنامه پذیر
-1 مقدمه
ظهور وب جهانی (WWW) ترافیک شبکه اینترنت را هر چند ماه یکبار، دو برابر میکند و کاربردهایی که پهنای باند زیادی اشغال میکنند مانند آموزش از راه دور و کتابخانههای دیجیتالی، ترافیک بیشتری ایجاد میکنند. این موضوع طراحی مسیریابهایی
با کیفیت سرویس (Quality of Service) بالا را با بهبود سه چالش سرعت اتصالها، توان عملیاتی (Throughput) و سرعت ارسال بستهها روبرو ساخته است. هماکنون راهحلهایی برای دو مورد اول وجود دارد، این مقاله با راه حلهای مشکل سوم سروکار دارد و روشی برای بالابردن سرعت ارسال بستهها دربرابر با افزایش سرعت اتصالها، ارائه میدهد. هرچند در سالهای اخیر جستجوی MAC آدرس به سرعتهای 100 مگابیت در ثانیه رسیده است، اما این کار بر اساس تطبیق MAC آدرس ورودی با یکی از مدخلهای جدول مسیریابی انجام میشود در حالیکه مسیریابهای اینترنت برمبنای تطبیق طولانیترین پیشوند بین آدرس مقصد و IP های جدول مسیریابی عمل میکنند.[2][1] بنابراین روشهای تطبیق کامل و استفاده از CAM را در مورد آنها نمیتوان بکار برد.[3] بر این اساس، روش تطبیق پیشوند در سال 1990 پیشنهاد شد تا تعداد مدخلهای جدول مسیریابی کمتر شود. در این روش فضای آدرس IP به کلاسهای A، B و C تقسیم میشود که هرکدام به ترتیب 24، 16و 8 بیت برای آدرسدهی دارند. البته این روش تقسیمبندی شبکهها انعطافپذیری ندارد و فضای آدرسدهی را هدر میدهد، بخصوص در مورد کلاس .B برای حل این مشکل روش(CIDR (Classless Inter Domain Routing پیشنهاد شد که تراکم تعداد دلخواهی شبکه را مجاز میشمارد و باعث کاهش تعداد مدخلهای جدول مسیریابی میشود.[4] روش CIDR هر مسیر بوسیله زوج >طول پیشوند، <IP مشخص میشود، که طول پیشوند بین 0 تا 32 بیت است. هنگامی که یک بسته IP دریافت میشود، مسیریاب بررسی میکند تا ببیند کدامیک از پیشوندها در جدولش طولانیترین تطبیق را در مقایسه با IP مقصد در بسته ورودی دارد، سپس بسته از طریق پورت خروجی مربوط به این پیشوند ارسال میشود. در ادامه مقاله ابتدا مروری مختصر بر روشهای موجود جستجوی IP کرده، بعد طرح کلی این روش موردنظر بیان میشود. سپس طریقه پیادهسازی آن ذکر خواهد شد و در آخر کارآیی روش مورد بررسی قرار میگیرد.
تا به حال چندین روش جستجوی مسیر با سرعت زیاد ارائه شده است [12][11][10][9][8][7][6][5]، مثلاً در روشی که توسط دگرمارک و همکاران[5] ارائه شد، ساختار جدولهای جستجو بسیار کوچک است تا جایی که یک جدول با 40000 مدخل میتواند تا اندازه 150 تا 160 کیلوبایت فشرده شود. البته این یک روش نرمافزاری است، اگر توسط سخت افزار پیادهسازی شود بین
2 تا 9 دسترسی به حافظه به ازای هر جستجو لازم است. گوپتا و همکاران [7] نیز یک روش سریع ارائه دادند که از DRAM استفاده میکند و حداکثر نیاز به دو دسترسی به حافظه در یک جدول جستجوی 33 مگابایتی دارد. با اضافه کردن یک جدول میانی اندازه جدول جستجو به 9 مگابایت کاهش مییابد ولی تعداد دسترسیها به 3 تا افزایش پیدا میکند، اگر این روش در سختافزار و با استفاده از Pipeline پیادهسازی شود، دسترسیها به یکی کاهش مییابد. والدوگل و همکاران [12] نیز روشی برای جستجوی سریع برمبنای جستجوی دودویی ارائه دادند که برای جدولهای آدرس و مسیریابی بزرگ مقیاسپذیری خیلی خوبی دارد و به تعداد لگاریتم تعداد بیتهای آدرس، جستجوی Hash لازم دارد. برای مثال در پایگاهدادهای با N تا پیشوند با طول آدرس W، روش جستجوی دودویی معمولی از مرتبه W*log(N) است، ولی این روش از مرتبه W+log(N) است. البته این روش هم نرمافزاری است و در پیادهسازی در سختافزار جواب خوبی نمیدهد. روشهای متعدد دیگری هم در [13] ذکر گردیده است.
