لوگوی سایت نوآوران گرمی
نوآوران گرمی | مرجع فیلم های آموزشی و همیار دانشجو

شماره های پشتیبانی

09194751295 - 09365442247

NoavaranGermi@gmail.com

پیدا کردن بهترین مسیر در شبکه با پروتکل مسیریابی Link State

paper link state 16563 1 پیدا کردن بهترین مسیر در شبکه با پروتکل مسیریابی Link State

پیدا کردن بهترین مسیر در شبکه با پروتکل Link State

در این پست با یک مقاله آموزشی کوتاه با عنوان پیدا کردن بهترین مسیر در شبکه با پروتکل Link State یا LS در خدمت شما دوستان عزیز هستیم که امیدواریم مطالعه این مقاله کوتاه بتواند بر دانش شما در زمینه شبکه های کامپیوتری بیفزاید.

پروتکل مسیریابی Link State:

پروتکل مسیریابی Link State یا LS از لحاظ تئوری بسیار ساده است. پس از آنکه بسته های Link State به روش سیل آسا ارسال شدند و هر مسیریاب با دریافت نسخه های از آنها پایگاه اطلاعات توپولوژی شبکه را تشکیل می دهد، در حقیقت مشخصات یک گراف را در اختیار دارد که گراف همان مسیریاب ها، خطوط گراف، لینک های فیزیکی بین مسیریاب ها هستند. هزینه هر لینک نیز مشخص است. برای پیدا کردن بهترین مسیر بین دو نقطه کافی است که الگوریتم کوتاهترین مسیر دایجسترا استفاده شود. هر چه تعداد مسیریاب های شبکه افزایش یابد، پیچیدگی زمانی این الگوریتم نیز افزایش خواهد یافت و زمان پیدا شدن مسیر های بهینه از حد متعادل خارج خواهد شد.

توضیحات بیشتر پیدا کردن بهترین مسیر در شبکه با پروتکل Link State در ادامه مطلب.

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

از گراف می توان برای نمایش مسیر های یک شبکه استفاده کرد، که در آن رأس های گراف نماینده گره های شبکه و یال ها نمایانگر مسیر های ارتباطی هستند. بدین ترتیب می توان با یال ها وزن داد، این وزن می تواند فاصله بین دو مقصد و یا میانگین زمان لازم برای طی این فاصله باشد؛ یک بسته می خواهد از مقصد A به B برود و مایل است پاسخ سوالات زیر را بداند:

  • آیا مسیری از A به B وجود دارد؟
  • اگر بیش از یک مسیر از A به B وجو داشته باشد کوتاهترین مسیر کدام است؟

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

مسئله: یک مبدا چند مقصد، یال هایی با هزینه غیر منفی:

در این مسئله گراف جهت دار G=(V,E)، تابع طول length (i,j)، lenght(i, j) > 0 برای یال های G و راس مبدا V به بقیه راس ها در G است. به عنوان مثال، گراف جهت دار شکل زیر را در نظر بگیرید.

paper link state 16563 2 پیدا کردن بهترین مسیر در شبکه با پروتکل مسیریابی Link State

(نمایش گراف)

اعداد روی یال ها نشان دهنده طول ها هستند. اگر a رأس مبدا گراف باشد اعداد روی لبه ها نشان دهنده وزن آنها هستند. اگر a رأس مبدا باشد آنگاه کوتاهترین مسیر از a به b ، e ، f هیچ مسیری وجود ندارد. مراحل مختلف اجرای الگوریتم در جدول زیر نشان داده شده است.

paper link state 16563 3 پیدا کردن بهترین مسیر در شبکه با پروتکل مسیریابی Link Statepaper link state 16563 4 پیدا کردن بهترین مسیر در شبکه با پروتکل مسیریابی Link State

(مراحل مختلف اجرای الگوریتم)

در مثال بالا کوتاهترین مسیرها از راس a به بقیه رئوس، درخت پوشای زیر می باشد.

paper link state 16563 5 پیدا کردن بهترین مسیر در شبکه با پروتکل مسیریابی Link State

(درخت پوشای کوتاهترین مسیر به مبدا رأس a برای گراف)

الگوریتم حریصانه:

یک الگوریتم حریصانه کوتاهترین مسیرها را تولید می کند؛ فرض کنید که s مجموعه راس ها (از جمله مبدا V) باشد که دارای کوتاهترین مسیری است که تاکنون به دست آمده است. برای W که در S نمی باشد. dist[w] طول کوتاهترین مسیر از مبدا V خواهد بود. به طوری که از راس هایی می گذرد که در S هستند و به W ختم می شود. ملاحظه می کنیم وقتی مسیرها به ترتیب غیر نزولی طول ایجاد می شوند.

اگر کوتاه ترین مسیر بعدی به راس u آنگاه مسیری از V آغاز شده و به u ختم می شود، فقط از راس هایی می گذرد که در S وجود دارند. برای اثبات این مطلب باید نشان دهیم که تمام راس های میانی روی کوتاهترین مسیر به U باید در S باشند. فرض کنید راسی مانند W روی این مسیر است که در S وجود ندارد. آنگاه مسیر V به U شامل مسیری از V به W است که طول آن کمتر از مسیر V به W می باشد.

بنا به فرض، کوتاهترین مسیرها به ترتیب غیرنزولی طول هایش تولید می شوند و لذا، مسیر کوتاه تر از V به W قبلا تولید شده است. بنابراین، هیچ راس میانی نمی تواند وجود داشته باشد که در S موجود نباشد.

بین همه راس هایی که در S نیستند، مقصد مسیر تولید شده بعدی باید راس U باشد زیر این راس دارای کمترین فاصل (dist[w]) بنابراین این مطلب از تعریف dist و نکته اولی که ذکر شد، نتیجه می شود در حالتی که چندین راس با dist مساوی وجود داشته باشد که در S نباشد، آنگاه ممکن است هر کدام از آنها انتخاب شوند.

  1. با انتخاب یک راس U در مرحله دوم و تولید کوتاهترین مسیر از V به U ، U در S ذخیره و یا در واقع به عنوان عضوی از S در نظر گرفته می شود. اضافه کردن U به S می تواند طول کوتاهترین مسیر های را کاهش دهد که از V آغاز شده و فقط از راس های موجود در S می گذرند و به راسی مانند W که در S ختم می شود (یعنی مقدار dist[w] ممکن است تغییر کند.) اگر این طول تغییر کند آنگاه بایستی کوتاهترین مسیری باشد که از V آغاز شده و با گذشتن از U به W می رسد.
  2. تمام راس های میانی روی مسیر V به U و مسیر U به W باید در S وجود داشته باشند. بعلاوه مسیر V تا U باید کوتاهترین مسیر باشد، در غیر اینصورت dist[w] درست تعریف نشده است. همچنین مسیر U به W می تواند طوری انتخاب شود که شامل هیچ راس میانی نباشد. بنابراین میتوانیم نتیجه بگیریم که اگر dist[w] تغییر کند (یعنی کاهش یابد)، آنگاه مسیر از V به U و سپس W تغییر می کند، که در آن مسیر V به U کوتاهترین مسیر است و مسیر از U به W یال <U,W> است. مسلما طول این مسیر برابر dist[U]+length(<V,W>) است.
  3. الگوریتم Shortest Path که اولین بار توسط دیجکسترا (Edsger Dijkstra) ارائه شده با بهره گیری از این مشاهدات توانست طول کوتاهترین مسیرها از V به دیگر راس های G را محاسبه کند تولید مسیرها تعمیم کوچکتری از این الگوریتم است. برای ایجاد و پیاده سازی الگوریتم دایجسترا، فرض می کنیم n راس یک گراف از ۰ تا n-1 شماره گذاری شده اند.

مجموعه S به صورت یک آرایه بولین (Boolean) نگهداری می شود. اگر راس i در S نباشد S[i]=FALSE و در غیر این صورت S[i]=TRUE است. برنامه زیر این الگوریتم را شرح می دهد.

کلاس Graph به صورت زیر نشان داده می شود:

class Graph
{
private:
int length[nmax][nmax];
int dist[nmax];
boolean s[nmax];
public:
void ShortestPath(const int,const int);
int choose(const int);
};
socket programing آموزش برنامه نویسی بازی تحت شبکه بازی تحت شبکه برای درس مهندسی اینترنت بازی تحت شبکه به زبان سی شارپ برنامه تحت شبکه با سی شارپ برنامه نویسی ترجمه مقاله شبکه خرید سورس بازی تحت شبکه دانلود بازی تحت شبکه دانلود رایگان پروژه های دانشجویی دانلود سورس برنامه دانلود سورس رایگان دانلود نرم افزار دانلود پروژه دانشجویی دانلود پروژه رایگان دانلود پروژه های دانشجویی دانلود کتاب دانلود کتاب آموزشی دانلود کتاب اموزشی سورس بازی با socket programing سورس رایگان سورس کد بازی تحت شبکه سورس کد بازی تحت شبکه با C# سورس کد بازی تحت شبکه چند نفره سوکت پروگرمین نحوه نوشتن برنامه تحت شبکه نحوه نوشتن برنامه تحت شبکه به زبان سی شارپ پروژه arena پروژه matlab پروژه ns2 پروژه opnet پروژه برای درس مهندسی اینترنت پروژه تحت شبکه به زبان سی شارپ پروژه رایگان matlab پروژه سیمولینک matlab پروژه مهندسی صنایع پروژه مهندسی صنایع با ارنا پروژه های آماده با OpenGL پروژه های آماده با OpenGL در سی پلاس پلاس پروژه های آماده برای درس گرافیک کامپیوتری پروژه هوش مصنوعی پروژه پردازش تصویر matlab پروژه پردازش سیگنال matlab پروژه کارشناسی به همراه داکیومنت

خوشحال خواهیم شد اگر نظر خودتون رو در باره این مطلب ثبت کنید

    گفتگوی آنلاین سایت نوآوران گرمی