بهبود مسیریابی در داده ساختارهای توزیع شده ی مبتنی بر لیست های پرشی

در این مقاله ما به ارائه یک الگوریتم جدید و کارآمد برای مسیریابی در شبکه های P2P میپردایزم. این الگوریتم به منظور جست و جو در شبکه های رویه ای مبتنی بر لیست های پرشی طراحی شدهاست و امکان جست و جوی بازه ای روی داده های چند بعدی را نیز فراهم می کند. این الگوریتم بهبود یافته ی الگوریتم مسیریابی در داده ساختار Skip Tree می باشد که ما میزان بهبود مسیریابی در الگوریتم پیشنهادی را به صورت نظری اثبات میکنیم. دراین الگوریتم تعداد گام های مسیریابی از (log2N) به O(log rD) کاهش یافته، که برابر طول مسیر و r هم پارامتر بهبود مسیریابی می باشد. همچنین در این الگوریتم اندازه جدول مسیریابی و تعداد اشاره گرهای ذخیره شده در آن نیز کاهش یافته است. از ویژگی های دیگر این الگوریتم این است که پارامترهای دیگر شبکه از قبیل حافظه مورد نیاز و توازن بار را تحت تاثیر قرار نمی دهد و سربار خاصی را به شبکه تحمیل نمی کند. به طور کلی هزینه مسیریابی در این روش مسیریابی نسبت به نمونه های مشابه بهبود قابل ملاحظه ای یافته است.

Keywords:

شبکه های P2P , الگوریتم های مسیریابی , لیست پرشی , داده ساختارهای توزیع شده , جست و جوی بازه ای