الگوریتم لولئو

الگوریتم لولئو در علوم کامپیوتر، طراحی شده توسط دگرمارک و همکاران، تکنیکی برای ذخیره و جستجوی جداول مسیریابی اینترنتی به طور پربازده است. این نام از دانشگاه Luleå Technology، مؤسسه خانه / دانشگاه نویسندگان این روش گرفته شده‌است. نام الگوریتم در مقاله اصلی توصیف آن وجود ندارد، اما در پیامی از کریگ پارتریک به گروه ویژه مهندسی اینترنت در توصیف آن مقاله قبل از انتشار استفاده شده‌است.

وظیفه اصلی که باید در مسیریابی اینترنتی انجام شود، مطابقت دادن یک آدرس IPv4 معین است (به عنوان دنباله ای از ۳۲ بیت مشاهده می‌شود) با طولانی‌ترین پیشوند آدرسی که اطلاعات مسیریابی برای آن موجود است. این مشکل تطبیق پیشوند ممکن است توسط یک trie حل شود، اما ساختارهای trie از مقدار قابل توجهی فضای (گره ای برای هر بیت از هر آدرس) استفاده می‌کنند و جستجوی آنها نیاز به پیمایش دنباله ای از گره‌ها با طول متناسب با تعداد بیت‌های آدرس دارد. . الگوریتم لولئو این فرایند را با ذخیره کردن گره‌ها در سه سطح از ساختار trie، به جای ذخیره کل trie، میانبر می‌کند.

قبل از ساخت Luleå trie، ورودی‌های جدول مسیریابی باید پیش پردازش شوند. هر پیشوند بزرگتر که با پیشوند کوچکی همپوشانی داشته باشد باید بارها به پیشوندهای کوچکتر تقسیم شود و فقط پیشوندهای تقسیم شده که با پیشوند کوچکتر همپوشانی ندارند، نگهداری می‌شوند همچنین لازم است درخت پیشوند کامل باشد. اگر ورودی‌های جدول مسیریابی برای کل فضای آدرس وجود نداشته باشد، باید با افزودن نوشته‌های ساختگی، که فقط حامل اطلاعاتی است که هیچ مسیری برای آن محدوده وجود ندارد، تکمیل شود. این امکان جستجو ساده در trie لولئو را فراهم می‌کند.

مزیت اصلی الگوریتم لولئو برای کار مسیریابی این است که از حافظه بسیار کمی استفاده می‌کند، به‌طور متوسط ۴–۵ بایت در هر ورودی برای جداول مسیریابی بزرگ. این ردپای حافظه کوچک معمولاً به کل ساختار داده اجازه می‌دهد تا در حافظه نهان پردازنده مسیریاب قرار گیرد، و سرعت عمل در آن زیاد است. با این حال، این عیب دارد که نمی‌توان آن را به راحتی اصلاح کرد: تغییرات کوچک در جدول مسیریابی ممکن است نیاز به بازسازی بیشتر یا کل ساختار داده داشته باشد. یک رایانه خانگی (PC) مدرن دارای سخت‌افزار / حافظه کافی برای انجام الگوریتم است. الگوریتم Luleå در ایالات متحده ثبت اختراع شده دگرمارک و همکاران).

سطح اول

سطح اول ساختار داده شامل

• یک بردار بیتی متشکل از 2 ¹⁶ = ۶۵٬۵۳۶ بیت، با یک ورودی برای هر پیشوند ۱۶ بیتی از آدرس IPv4. اگر اطلاعات مسیریابی مرتبط با آن پیشوند یا دنباله طولانی trie که با آن پیشوند آغاز می‌شود، یا اگر پیشوند داده شده اولین موردی است که با اطلاعات مسیریابی در سطح بالاتر از trie مرتبط است، بیتی در این جدول تنظیم می‌شود. در غیر این صورت روی صفر تنظیم می‌شود.
• آرایه ای از کلمات ۱۶ بیتی برای هر بیت غیر صفر در بردار بیت. هر داده یا نمایه ای را ارائه می‌دهد که به شی ساختار داده سطح دوم برای پیشوند مربوطه اشاره می‌کند، یا اطلاعات مسیریابی آن پیشوند را مستقیماً تأمین می‌کند.
• آرایه ای از «شاخص‌های پایه»، یکی برای هر دنباله متوالی ۶۴ بیتی در بردار بیت، که به اولین داده مرتبط با یک بیت غیر صفر در آن دنباله اشاره دارد.
• آرایه ای از «شاخص‌های پایه»، یکی برای هر دنباله متوالی از ۱۶ بیت در بردار بیت. هر کلمه رمز ۱۶ بیت است و از یک «مقدار» ۱۰ بیتی و «جبران» ۶ بیت تشکیل شده‌است. مجموع جبران و شاخص پایه مربوطه به اولین داده مرتبط با یک بیت غیر صفر در دنباله ۱۶ بیتی داده شده، اشاره گر می‌دهد. مقدار ۱۰ بیتی نمایه ای را در یک «قابل تطبیق» ارائه می‌دهد که از آن می‌توان موقعیت دقیق داده مناسب را پیدا کرد.
• قابل تطبیق از آنجا که لازم است درخت پیشوند کامل باشد، فقط مقدار محدودی از مقادیر بیت ماسک ۱۶ بیتی ممکن است در بردار بیت، ۶۷۸ وجود داشته باشد. ردیف‌های قابل انطباق با این ۶۷۸ ترکیب ۱۶ بیتی مطابقت دارد و تعداد بیت‌های تنظیم شده در ماسک bit را در محل بیت مربوط به ستون، منفی ۱ ستون می‌کند؛ بنابراین ستون ۶ برای bitmask 101010101010101010 دارای مقدار ۲ خواهد بود. قابلیت تغییر برای هر محتوای جدول مسیریابی ثابت است.

برای جستجوی داده برای آدرس داده شده x در اولین سطح ساختار داده، الگوریتم لولئو سه مقدار را محاسبه می‌کند:

1. شاخص پایه در موقعیت آرایه شاخص پایه که توسط ۱۰ بیت اول x نمایه می‌شود
2. جابجایی در موقعیت در آرایه کلمه کد که با ۱۲ بیت اول x نمایه می‌شود
3. مقدار قابل تطبیق [y] [z]، جایی که y شاخص قابل انعطاف از آرایه کلمه کد است و z بیت‌های ۱۳–۱۶ از x است

مجموع این سه مقدار شاخصی را برای استفاده در x در آرایه موارد فراهم می‌کند.

سطح دوم و سوم

سطح دوم و سوم ساختار داده‌ها به‌طور مشابه با یکدیگر ساختار یافته‌اند. در هر یک از این سطح‌ها الگوریتم لولئو باید تطبیق پیشوندی را روی مقادیر ۸ بیتی انجام دهد (به ترتیب بیت‌های ۱۷–۲۴ و ۲۵–۳۲ آدرس). ساختار داده در "تکه"‌ها ساخته شده‌است، که هر یک از آنها امکان انجام این کار تطبیق پیشوند را در برخی از دنباله‌های فضای آدرس فراهم می‌کند. موارد داده از سطح اول این ساختمان داده به این تکه‌ها اشاره می‌کنند.

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

منابع

• Degermark, Mikael; Brodnik, Andrej; Carlsson, Svante; Pink, Stephen (1997), "Small forwarding tables for fast routing lookups", Proceedings of the ACM SIGCOMM '97 conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp. 3–14, doi:10.1145/263105.263133.
• [۱], "Fast routing lookup system using complete prefix tree, bit vector, and pointers in a routing table for determining where to route IP datagrams" .
• Medhi, Deepankar; Ramasamy, Karthikeyan (2007), Network Routing: Algorithms, Protocols, and Architectures, Elsevier, pp. 510–513, ISBN 978-0-12-088588-6.
• Sundström, Mikael (2007), "Time and Space Efficient Algorithms for Packet Classification and Forwarding", Doctoral Thesis, ISSN 1402-1544.