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

word قابل ویرایش
14 صفحه
4900 تومان

الگوریتم های مسیر یابی
طراحی الگوریتم
اصول عملکرد
روترها از الگوریتمهای مسیریابی،برای یافتن بهترین مسیر تا مقصد استفاده مینمایند هنگامی که ما در مورد بهترین مسیر صحبت میکنیم،پارامترهایی همانند تعداد 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 نباشد(گره مقصد)روتر به مرحله ۵باز میگردد.
اگر این گره V2 باشد،روتر گره قبلی آن را از مجموع رکورد وضعیت استخراج نموده و این کار را انجام میدهد تا به V1 برسد،این فرست از گره ها،بهترین مسیر از V1تاV2را نشان میدهد.
این مراحل بصورت یک فلوچارت در شکل نشان داده شده است ما از این الگوریتم بعنوان یک مثال در ادامه مقاله استفاده خواهیم نمود.

مثال
الگوریتم Dijkstra
در اینجا ما میخواهیم بهترین مسیر بین گره های A و E را پیدا کنیم همانطور که میبینید ۶ مسیر بین 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 تغییر کرده است.

این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید
wordقابل ویرایش - قیمت 4900 تومان در 14 صفحه
سایر مقالات موجود در این موضوع
دیدگاه خود را مطرح فرمایید . وظیفه ماست که به سوالات شما پاسخ دهیم

پاسخ دیدگاه شما ایمیل خواهد شد