(58 امتیاز از 12 رای)
Loading...
پیدا کردن بهترین مسیر در شبکه با پروتکل 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 است. به عنوان مثال، گراف جهت دار شکل زیر را در نظر بگیرید.
(نمایش گراف)
اعداد روی یال ها نشان دهنده طول ها هستند. اگر a رأس مبدا گراف باشد اعداد روی لبه ها نشان دهنده وزن آنها هستند. اگر a رأس مبدا باشد آنگاه کوتاهترین مسیر از a به b ، e ، f هیچ مسیری وجود ندارد. مراحل مختلف اجرای الگوریتم در جدول زیر نشان داده شده است.
(مراحل مختلف اجراي الگوریتم)
در مثال بالا کوتاهترین مسیرها از راس a به بقیه رئوس، درخت پوشای زیر می باشد.
(درخت پوشای کوتاهترین مسیر به مبدا رأس 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 نباشد، آنگاه ممکن است هر کدام از آنها انتخاب شوند.
- با انتخاب یک راس U در مرحله دوم و تولید کوتاهترین مسیر از V به U ، U در S ذخیره و یا در واقع به عنوان عضوی از S در نظر گرفته می شود. اضافه کردن U به S می تواند طول کوتاهترین مسیر های را کاهش دهد که از V آغاز شده و فقط از راس های موجود در S می گذرند و به راسی مانند W که در S ختم می شود (یعنی مقدار dist[w] ممکن است تغییر کند.) اگر این طول تغییر کند آنگاه بایستی کوتاهترین مسیری باشد که از V آغاز شده و با گذشتن از U به W می رسد.
- تمام راس های میانی روی مسیر V به U و مسیر U به W باید در S وجود داشته باشند. بعلاوه مسیر V تا U باید کوتاهترین مسیر باشد، در غیر اینصورت dist[w] درست تعریف نشده است. همچنین مسیر U به W می تواند طوری انتخاب شود که شامل هیچ راس میانی نباشد. بنابراین میتوانیم نتیجه بگیریم که اگر dist[w] تغییر کند (یعنی کاهش یابد)، آنگاه مسیر از V به U و سپس W تغییر می کند، که در آن مسیر V به U کوتاهترین مسیر است و مسیر از U به W یال
- الگوریتم Shortest Path که اولین بار توسط دیجکسترا (Edsger Dijkstra) ارائه شده با بهره گیری از این مشاهدات توانست طول کوتاهترین مسیرها از V به دیگر راس های G را محاسبه کند تولید مسیرها تعمیم کوچکتری از این الگوریتم است. برای ایجاد و پیاده سازی الگوریتم دایجسترا، فرض می کنیم n راس یک گراف از 0 تا n-1 شماره گذاری شده اند.
مجموعه S به صورت یک آرایه بولین (Boolean) نگهداری می شود. اگر راس i در S نباشد S[i]=FALSE و در غیر این صورت S[i]=TRUE است. برنامه زیر این الگوریتم را شرح می دهد.
کلاس Graph به صورت زیر نشان داده می شود:
1 2 3 4 5 6 7 8 9 10 | class Graph { private: int length[nmax][nmax]; int dist[nmax]; boolean s[nmax]; public: void ShortestPath(const int,const int); int choose(const int); }; |
سلام به نظرم خیلی جالب بود.چون کاربرد یکی از الگوریتم ها رو یعنی الگوریتم دایجکسترا رو به صورت واقعی که در مسیر یابی شبکه بکار رفته.دیدیم.ممنون.اگه بازم از این مطالب که به صورت کاربردی هست.تو سایت بذارین.