اصل بهینگی

قبل از پرداختن به الگوریتم  توجه به مهم است که صرف نظر از توپولوژی شبکه  وتر افیکی ، می‌توان حکمی کلی راجع به مسیرهای بهینه ارائه کرد این حکم را به عنوان اصل بهینگی  شناخته می‌شود. این اصل بیا می‌کند که اگر مسیریابJ از مسیریاب I به مسیریابK در مسیریاب بهینه‌ای شناخته می‌کند آنگاه مسر بهینه‌ای از J و K نیز در مسیر مشابهی  قرار می‌گیرد. برای مشاهده این موضوع ، بخشی  از مسیر I به J  را به بنامید و بقیه را نامگذاری کنید اگر مسیری بهتر از وجود داشت می‌توانست با الحاق  شود تا مسیری از I به K  بهبود بخشد، و حکم ما را می‌گوید ?  بهینه است نقض کند.

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

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

مسیر یابی کوتاه ترین مسیر

مطالعه الگوریتمهای  مسیر یابی را با تکنیکی که به طور گسترده به شکل‌های مختلفی به کار می‌رود شروع می‌کنیم، زیرا الگوریتم ساده‌ای است ودرک آن آسان است. ایده ، ساختن گرافی از زیر شبکه است ، به طوری که ، هر گره گراف نشان دهنده مسیریاب است و هریال نشان دهنده خط ارتباطی است ( که اغلب پیوند نام دارد.) برای انتخاب  مسیری بین دو مسیریابمعین ، الگوریتم ، کوتاهترین مسیر بین آنها را درگراف می‌یابد.

در مورد کوتاهترین مسیر توضیحاتی باید ارائه شود . یک راه اندازه گیری طول مسیر ، تعداد جهش است با این معیار ، طول مسیرهای ABC,ABE در شکل 3 یکسان است.و معیار دیگر معیار دیگر فاصله جغرافیایی به کیلومتراست ، در این حالت بدیهی است که ABC خیلی طولانی تر از ABE است با فرض این که شکل با مقیاس رسم شده است.

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

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

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