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

طراحی الگوریتم

اصول عملکرد

روترها از الگوریتمهای مسیریابی،برای یافتن بهترین مسیر تا مقصد استفاده مینمایند هنگامی که ما در مورد بهترین مسیر صحبت میکنیم،پارامترهایی همانند تعداد hopها (مسیری که یک بسته از یک روتر دیگر در شبکه منتقل میشود).زمان تغییر و هزینه ارتباطی ارسال بسته را در نظر میگیریم.

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

در الگوریتم های مسیر یابی غیر متمرکز،هر روتر اطلاعاتی در مورد روترهایی که مستقیما به آنها متصل میباشند در اختیار دارد. در این روش هر روتر در مورد همه روتر های موجود در شبکه،اطلاعات در اختیار ندارد.این الگوریتمها تحت نام الگوریتمهای (DV (distance vectorمعروف هستند.در الگوریتمهای مسیریابی عمومی،هر روتر اطلاعات کاملی در مورد همه روترهای دیگر شبکه و نیز وضعیت ترافیک شبکه در اختیار دارد.این الگوریتمها تحت نام الگوریتمهای(LS(Link state معروف هستند.ما در ادامه مقاله به بررسی الگوریتمهای LS میپردازیم.

الگوریتمهای LS

در الگوریتمهای LS ،هر روتر میبایست مراحل ذیل را به انجام رساند:

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

زمان تاخیر مربوط به روترهای مجاور را اندازه گیری نماید(یا هر پارامتر مهم دیگری از شبکه همانند ترافیک متوسط)

برای انجام این کار ،روترها بسته های echo را روی شبکه ارسال میکنند. هر روتری که این بسته ها را دریافت میکند با یک بسته echo reply به آن پاسخ میدهد.با تقسیم زمان مسیر رفت و برگشت به دو،روترها میتوانند زمان تاخیر را محاسبه کنند.(زمان مسیر رفت و برگشت،سنجشی از تاخیر فعلی روی یک شبکه میباشد)توجه داشته باشید که این زمان شامل زمانهای ارسال و پردازش میباشد.

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

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

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

در این مرحله،روترها بهترین مسیر تا هر گره را انتخاب میکنند.آنها این کار را با استفاده از یک الگوریتم همانند الگوریتم کوتاهترین مسیر Dijkstra انجام میدهند.در این الگوریتم،یک روتر مبتنی بر اطلاعاتی که از سایر روترها جمع آوری نموده است،گرافی از شبکه را ایجاد مینماید.این گراف مکان روترهای موجود در شبکه و نقاط پیوند آنها را به یکدیگر نشان میدهد.هر پیوند با یک شماره به نام Costیاweight مشخص میشود.این شماره تابعی از زمان تاخیر،متوسط ترافیک و گاهی اوقات تعداد hopهای بین گره ها میباشد.برای مثال اگر دو پیوند بین یک گره و مقصد وجود داشته باشد،روتر پیوندی با کمترین Weight را انتخاب میکند.

الگوریتم Dijkstra دارای مراحل ذیل میباشد:

روتر گرافی از شبکه را ایجاد نموده و گره های منبع و مقصد(برای مثال V1 وV2)را شناسایی میکند.سپس یک ماتریس به نام ماتریس adjacency را میسازد.در این ماتریس یک مختصه مبین Weight میباشد.برای مثال[i,j]،وزن یک پیوند بین Viو Vj میباشد.در صورتی که هیچ پیوند مستقیمی بین Vi وVj وجود نداشته باشد این وزن (ویت) بصورت infinity در نظر گرفته میشود.

روتر یک مجموعه رکورد وضعیت را برای هر گره روی شبکه ایجاد مینماید این رکورد دارای سه فیلد میباشد:

فیلد Predecessor:اولین فیلدی که گره قبلی را نشان میدهد.

فیلد Length:فیلد دوم که جمع وزنهای از منبع تا آن گره را نشان میدهد.

فیلد Label:آخرین فیلد که وضعیت گره را نشان میدهد.هر گره میتواند دارای یک مود وضعیت باشد:tentative یا permanent

روتر،پارامترهای مجموعه رکورد وضعیت برای همه گره ها را آماده سازی اولیه نموده و طول آنها را در حالت infinity و Labelآن را در وضعیت tentative قرار میدهد.

روتر،یک گره T را ایجاد میکند.برای مثال اگر V1 میبایست گره T منبع باشد،روتر برچسب V1را در وضعیت permanent قرار میدهد.هنگامی که یک Label به حالت permanent تغییر میکند دیگر هرگز تغییر نخواهد کرد. یک گره T در واقع یک agent میباشد.

روتر،مجموع رکورد وضعیت مربوط به همه گره های Tentative را که مستقیما به گره T منبع متصل هستند،روز آمد مینماید.

روتر همه گره های Tentative را بررسی نموده و گرهای را که وزن آن تا V1 کمترین مقدار را دارد انتخاب میکند.سپس این گره،گره Tمقصد خواهد بود

اگر این گره،V2 نباشد(گره مقصد)روتر به مرحله 5باز میگردد.

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

این مراحل بصورت یک فلوچارت در شکل نشان داده شده است ما از این الگوریتم بعنوان یک مثال در ادامه مقاله استفاده خواهیم نمود.

مثال

الگوریتم Dijkstra

در اینجا ما میخواهیم بهترین مسیر بین گره های A و E را پیدا کنیم همانطور که میبینید 6 مسیر بین A و E وجود دارد.(ACDBE ،ABDCE ، ACDE، ABDE، ACE،ABE)و واضح است که ABDEبهترین مسیر میباشد زیرا کمترین وزن را دارد اما همیشه به این سادگی نیست و برخی موارد پیچیده وجود دارد که در آن ما مجبوریم از الگوریتم هایی برای یافتن بهترین مسیر استفاده کنیم.

همانطور که در تصویر ذیل مشاهده میکنید،گره منبع(A)بعنوان گره Tانتخواب شده و بنابراین برچسب آن، Permanent میباشد. (ما گره های Permanent را با دایره های تو پر و گره های Tرا با یک پیکان نشان میدهیم)

در این مرحله شما میبینید که مجموع رکورد وضعیت گره های Tentative که مستقیما به گره(T (C،Bمتصل شده اند،تغییر یافته است.همچنین از آنجایی که گره Bکمترین وزن را دارد،بعنوان گره T انتخاب شده و برچسب آن به حالت Permanent تغییر کرده است.

در این مرحله همانند مرحله قبل دو مجموعه رکورد وضعیت گره هایی که Tentative دارای اتصال مستقیم به گره T میباشد(E،D)تغییر کرده است.همچنین از آنجایی که گره D وزن کمتری دارد،بعنوان گره T انتخاب شده و برچسب آن به وضعیت Permanent تغییر کرده است.

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

E گره مقصد بوده بنابر این کار ما در اینجا تمام میشود.اکنون ما کار شناسایی مسیر را به انتها رسانده ایم.گره قبلی Eگره D،گره B میباشد و گره قبلی B،گره A میباشد.بنابر این بهترین مسیر ABDE است در این مورد وزن کل مسیر،(1+2+1)4میباشد.

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

الگوریتم های DV

الگوریتمهای DVبا نامهای الگوریتمهای مسیریابی Bellman-Ford و ford-fulkerson نیز یاد میشوند.در این الگوریتمها،هر روتر دارای یک جدول مسیریابی میباشد که بهترین مسیر تا هر مقصد را نشان میدهد.یک گراف معمولی و جدول مسیریابی مربوط به روتر G در شکل زیر نشان داده شده است.

همانطور که در جدول مشاهده میکنید،اگر روتر G بخواهد بسته هایی را به روتر D ارسال کند،میبایست آنها را به روتر H ارسال نماید.هنگامی که بسته ها به روتر H رسیدند،این روتر جدول خود را بررسی نموده و روی چگونگی ارسال بسته ها به D تصمیم گیری می کند.