موضوع مقاله: الگوریتم لولئو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم لولئو | مقدمه: الگوریتم لولئو در علوم کامپیوتر، طراحی شده توسط دگرمارک و همکاران، تکنیکی برای ذخیره و جستجوی جداول مسیریابی اینترنتی به طور پربازده است. | ## بخش 1: الگوریتم لولئو | وظیفه اصلی که باید در مسیریابی اینترنتی انجام شود، مطابقت دادن یک آدرس IPv4 معین است (به عنوان دنباله ای از ۳۲ بیت مشاهده می‌شود) با طولانی‌ترین پیشوند آدرسی که اطلاعات مسیریابی برای آن موجود است. این مشکل تطبیق پیشوند ممکن است توسط یک trie حل شود، اما ساختارهای trie از مقدار قابل توجهی فضای (گره ای برای هر بیت از هر آدرس) استفاده می‌کنند و جستجوی آنها نیاز به پیمایش دنباله ای از گره‌ها با طول متناسب با تعداد بیت‌های آدرس دارد. الگوریتم لولئو این فرایند را با ذخیره کردن گره‌ها در سه سطح از ساختار trie، به جای ذخیره کل trie، میانبر می‌کند. هر پیشوند بزرگتر که با پیشوند کوچکی همپوشانی داشته باشد باید بارها به پیشوندهای کوچکتر تقسیم شود و فقط پیشوندهای تقسیم شده که با پیشوند کوچکتر همپوشانی ندارند، نگهداری می‌شوند همچنین لازم است درخت پیشوند کامل باشد. اگر ورودی‌های جدول مسیریابی برای کل فضای آدرس وجود نداشته باشد، باید با افزودن نوشته‌های ساختگی، که فقط حامل اطلاعاتی است که هیچ مسیری برای آن محدوده وجود ندارد، تکمیل شود. مزیت اصلی الگوریتم لولئو برای کار مسیریابی این است که از حافظه بسیار کمی استفاده می‌کند، به‌طور متوسط ۴–۵ بایت در هر ورودی برای جداول مسیریابی بزرگ. این ردپای حافظه کوچک معمولاً به کل ساختار داده اجازه می‌دهد تا در حافظه نهان پردازنده مسیریاب قرار گیرد، و سرعت عمل در آن زیاد است. | ## بخش 2: الگوریتم لولئو | با این حال، این عیب دارد که نمی‌توان آن را به راحتی اصلاح کرد: تغییرات کوچک در جدول مسیریابی ممکن است نیاز به بازسازی بیشتر یا کل ساختار داده داشته باشد. سطح اول سطح اول ساختار داده شامل یک بردار بیتی متشکل از 2 16 = ۶۵٬۵۳۶ بیت، با یک ورودی برای هر پیشوند ۱۶ بیتی از آدرس IPv4. اگر اطلاعات مسیریابی مرتبط با آن پیشوند یا دنباله طولانی trie که با آن پیشوند آغاز می‌شود، یا اگر پیشوند داده شده اولین موردی است که با اطلاعات مسیریابی در سطح بالاتر از trie مرتبط است، بیتی در این جدول تنظیم می‌شود. هر داده یا نمایه ای را ارائه می‌دهد که به شی ساختار داده سطح دوم برای پیشوند مربوطه اشاره می‌کند، یا اطلاعات مسیریابی آن پیشوند را مستقیماً تأمین می‌کند. آرایه ای از «شاخص‌های پایه»، یکی برای هر دنباله متوالی ۶۴ بیتی در بردار بیت، که به اولین داده مرتبط با یک بیت غیر صفر در آن دنباله اشاره دارد. مجموع جبران و شاخص پایه مربوطه به اولین داده مرتبط با یک بیت غیر صفر در دنباله ۱۶ بیتی داده شده، اشاره گر می‌دهد. مقدار ۱۰ بیتی نمایه ای را در یک «قابل تطبیق» ارائه می‌دهد که از آن می‌توان موقعیت دقیق داده مناسب را پیدا کرد. | ## بخش 3: الگوریتم لولئو | قابل تطبیق از آنجا که لازم است درخت پیشوند کامل باشد، فقط مقدار محدودی از مقادیر بیت ماسک ۱۶ بیتی ممکن است در بردار بیت، ۶۷۸ وجود داشته باشد. ردیف‌های قابل انطباق با این ۶۷۸ ترکیب ۱۶ بیتی مطابقت دارد و تعداد بیت‌های تنظیم شده در ماسک bit را در محل بیت مربوط به ستون، منفی ۱ ستون می‌کند؛ بنابراین ستون ۶ برای bitmask 101010101010101010 دارای مقدار ۲ خواهد بود. برای جستجوی داده برای آدرس داده شده x در اولین سطح ساختار داده، الگوریتم لولئو سه مقدار را محاسبه می‌کند: شاخص پایه در موقعیت آرایه شاخص پایه که توسط ۱۰ بیت اول x نمایه می‌شود جابجایی در موقعیت در آرایه کلمه کد که با ۱۲ بیت اول x نمایه می‌شود مقدار قابل تطبیق [y] [z]، جایی که y شاخص قابل انعطاف از آرایه کلمه کد است و z بیت‌های ۱۳–۱۶ از x است مجموع این سه مقدار شاخصی را برای استفاده در x در آرایه موارد فراهم می‌کند. سطح دوم و سوم سطح دوم و سوم ساختار داده‌ها به‌طور مشابه با یکدیگر ساختار یافته‌اند. در هر یک از این سطح‌ها الگوریتم لولئو باید تطبیق پیشوندی را روی مقادیر ۸ بیتی انجام دهد (به ترتیب بیت‌های ۱۷–۲۴ و ۲۵–۳۲ آدرس). ساختار داده در "تکه"‌ها ساخته شده‌است، که هر یک از آنها امکان انجام این کار تطبیق پیشوند را در برخی از دنباله‌های فضای آدرس فراهم می‌کند. | ## جمع‌بندی | اگر چند به اندازه کافی تکه‌های مختلف از اطلاعات مسیریابی در ارتباط با یک تکه وجود دارد، تکه فقط ذخیره لیستی از این راه، و جستجو از طریق آنها را با یک قدم از جستجوی دودویی به دنبال یک جستجوی ترتیبی.