مقاله الگوریتم های پیشرفته مسیریابی در شبکه های کامپیوتری

این مقاله به معرفی و بررسی الگوریتم های پیشرفته مسیریابی در شبکه های کامپیوتری از جمله الگوریتم های Link State و Dijkstra می پردازد.

الگوریتم های مسیریابی

روترها با استفاده از الگوریتم های مسیریابی بهترین مسیر برای ارسال داده ها به مقصد را تعیین می کنند. هنگام انتخاب بهترین مسیر عواملی مانند تعداد پرش ها (hop) که بسته های داده از یک روتر به روتر دیگر عبور می کنند زمان تاخیر و هزینه ارسال داده ها مورد توجه قرار می گیرند.

بر اساس نحوه جمع آوری و تحلیل اطلاعات درباره ساختار شبکه توسط روترها دو نوع الگوریتم اصلی مسیریابی وجود دارد: الگوریتم های مسیریابی غیرمتمرکز و الگوریتم های مسیریابی متمرکز.

در الگوریتم های غیرمتمرکز هر روتر تنها اطلاعات مربوط به روترهایی که مستقیماً به آن متصل هستند را در اختیار دارد و اطلاعات کامل شبکه را ندارد. این الگوریتم ها به الگوریتم های «بردار فاصله» (Distance Vector) معروف هستند. اما در الگوریتم های متمرکز هر روتر اطلاعات جامع و کاملی درباره تمام روترهای شبکه و وضعیت ترافیک آنها دارد که به الگوریتم های «وضعیت لینک» (Link State) شناخته می شوند. در ادامه این مقاله به بررسی جزئی تر الگوریتم های Link State خواهیم پرداخت.

الگوریتم های LS (Link State)

در الگوریتم های LS هر روتر باید چند مرحله کلیدی را طی کند تا بتواند بهترین مسیر را تعیین نماید:

اول روترهای فیزیکی متصل به خود را شناسایی کرده و آدرس های IP آن ها را دریافت می کند. برای این منظور روتر ابتدا یک بسته مخصوص به نام «HELLO» را در شبکه منتشر می کند. هر روتر دریافت کننده این پیام با ارسال پاسخ حاوی آدرس IP خود به بسته HELLO واکنش نشان می دهد.

سپس روتر زمان تاخیر بین خود و روترهای مجاور را اندازه گیری می کند یا دیگر پارامترهای مهم شبکه مثل ترافیک میانگین را ارزیابی می نماید. این کار با ارسال بسته های «echo» انجام می شود؛ هر روتر که این بسته ها را دریافت کند با ارسال «echo reply» پاسخ می دهد. با محاسبه زمان رفت و برگشت این بسته ها و تقسیم آن بر دو روتر می تواند تاخیر واقعی مسیر را برآورد کند. این زمان شامل فرآیندهای ارسال و پردازش داده ها است.

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

با داشتن این اطلاعات کامل روترها بهترین مسیر بین هر دو نقطه در شبکه را شناسایی می کنند. این انتخاب مسیر معمولاً با استفاده از الگوریتم هایی مانند الگوریتم کوتاه ترین مسیر «Dijkstra» انجام می شود. در این روش هر روتر با توجه به داده های جمع آوری شده یک گراف از شبکه می سازد که در آن موقعیت روترها و ارتباط بین آن ها مشخص است. هر ارتباط دارای یک عدد به نام «وزن» (Weight) است که نشان دهنده میزان تاخیر متوسط ترافیک یا حتی تعداد پرش ها (hop) بین دو نقطه است. روتر مسیر با کمترین وزن را به عنوان بهترین انتخاب می کند.

الگوریتم های پیشرفته مسیریابی مانند Link State و Dijkstra به روترها کمک می کنند تا مسیرهای بهینه و کارآمد را در شبکه های پیچیده بیابند و انتقال داده را بهبود بخشند.

مراحل الگوریتم Dijkstra:

1- روتر گراف شبکه را ایجاد و نقاط مبدا و مقصد (مثلاً V1 و V2) را مشخص می کند. سپس ماتریسی به نام «ماتریس مجاورت» (adjacency matrix) می سازد که وزن هر اتصال بین نقاط را نمایش می دهد. اگر اتصال مستقیمی بین دو نقطه نباشد وزن آن به صورت بی نهایت در نظر گرفته می شود.

2- برای هر گره رکورد وضعیت با سه فیلد زیر ساخته می شود:

• Predecessor: نشان دهنده گره قبلی در مسیر
• Length: مجموع وزن مسیر از مبدا تا آن گره
• Label: وضعیت گره که می تواند موقت (tentative) یا دائمی (permanent) باشد

3- مقادیر اولیه رکوردها تنظیم می شوند طول ها روی بی نهایت قرار می گیرند و همه برچسب ها موقت هستند.
4- یک گره شروع (T) انتخاب می شود و برچسب آن دائمی می شود (مثلاً اگر V1 مبدا باشد برچسب V1 دائمی می شود). گره هایی که برچسب دائمی دارند دیگر تغییر نمی کنند.
5- رکوردهای گره های موقت که مستقیماً به گره T متصل اند بروزرسانی می شوند.
6- از بین گره های موقت آن که کمترین وزن را دارد انتخاب و برچسب آن دائمی می شود و این گره جدید به عنوان گره T در نظر گرفته می شود.
7- این روند تا رسیدن به گره مقصد (مثلاً V2) تکرار می شود.
8- پس از رسیدن به مقصد مسیر به عقب دنبال می شود تا بهترین مسیر از مبدا تا مقصد استخراج شود.

مثال عملی: الگوریتم Dijkstra

فرض کنید قصد داریم بهترین مسیر بین گره های A و E را پیدا کنیم. همانطور که مشاهده می شود چند مسیر مختلف بین این دو گره وجود دارد مانند ACDBE ABDCE ACDE ABDE ACE و ABE. در این مثال مسیر ABDE بهترین انتخاب است چون کمترین وزن را دارد اما همیشه انتخاب مسیر به این سادگی نیست و در موارد پیچیده تر باید از الگوریتم های مسیریابی استفاده کرد.

در روند اجرا گره منبع (A) ابتدا برچسب دائمی می گیرد و به عنوان گره T شناخته می شود. سپس رکوردهای گره های مجاور مانند C و B به روزرسانی می شوند. گره ای که وزن کمتری دارد (در اینجا B) به عنوان گره T انتخاب شده و برچسب دائمی می شود.

سپس همین فرآیند برای گره های بعدی (مانند D و E) ادامه می یابد تا بهترین مسیر کامل مشخص شود.

الگوریتم های پیشرفته مسیریابی پایه و اساس عملکرد بهینه شبکه های کامپیوتری مدرن را تشکیل می دهند.