تبلیغات
دانشجویان سخت افزار دانشگاه خوارزمی - الگوریتم‌های مسیریابی

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

نویسنده :دانشجو 1
تاریخ:شنبه 19 آذر 1390-06:52 ب.ظ

در شبکه‌های کوچک، و در نقاطی که انتقال اطلاعات معمولا مستقیم است، مسیریابی چندان جدی گرفته نمی‌شود. اما هنگامی که شبکه‌ها از حالت‌های ایستگاه‌های کاری خارج می‌شوند و کمی پیچیده‌تر می‌شوند، در این حالت، مسیریابی و انتخاب مسیر بهینه برای ارسال بسته‌های اطلاعاتی، به یک امر مهم بدل می‌شود. در شبکه‌های بزرگ، دستگاه‌هایی به‌عنوان مسیریاب (1)  وجود دارند که عمل مسیریابی را انجام می‌دهند.

الگوریتم مسیریابی‌ای مناسب است که 6 ویژگی زیر را داشته باشد: صحت عملکرد(2) ، سادگی(3)، قابلیت اطمینان(4)، پایداری(5)، عدالت(6) و بهینگی(7).

 

بدیهی است که الگوریتمی بهتر است که صحت عملکرد بالایی داشته باشد و در عین حال ساده باشد، اما چه الگوریتمی قابلیت اتکای خوبی دارد؟ الگوریتمی مناسب است که در گذشت زمان، با تغییر نرم‌افزارها و سخت‌افزارهای شبکه و تغییر پروتکل‌ها، همچنان مسیریابی درستی ارائه دهد. همچنین مهم است که بعد از یک مدت زمان خاص، الگوریتم مسیریابی به حالتی پایدار برسد و همزمان با آن، مسیریابی بهینه‌ای داشته باشد و در ارسال بسته‌ها عدالت را رعایت کند.



برای دیدن متن کامل,بر روی ادامه مطلب کلیک نمایید.

الگوریتم کوتاه‌ترین مسیر

ساده‌ترین روش مسیریابی، روش کوتاه‌ترین مسیر است. هدف اصلی از این الگوریتم، این است که گراف‌ زیرشبکه را طوری تشکیل بدهیم که در آن هر گره را یک مسیریاب فرض کنیم و هر یال را یک خط ارتباطی میان دو مسیریاب. در این حالت، هر یال یک وزن خواهد داشت و با توجه به الگوریتم کوتاه‌ترین مسیر دایجسترا(8) می‌توان کوتاه‌ترین مسیر ممکن را محاسبه کرد.

 

الگوریتم سیل‌آسا

در این روش، هر بسته ورودی که به یک مسیریاب می‌رسد، از تمام کانال‌های خروجی مسیریاب خارج می‌شود. بدین‌ترتیب تعداد زیادی بسته تکراری وجود خواهد داشت و عملا میزان آن بی‌نهایت خواهد بود. بنابراین باید برای خاتمه این تعداد بسته‌ها راهکاری اندیشید. راهکارهای پیشنهادی برای این روش، استفاده از یک شمارنده گام است. بدین صورت که در سرآیند(9) هر بسته یک شمارنده بگذاریم و در هر گام یک شماره از آن کم کنیم تا به صفر برسد و بسته حذف شود. در این صورت مبدا باید طول شبکه را بداند و در بدترین حالت، طول شبکه را طولانی‌ترین فاصله در نظر بگیرد.

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

الگوریتم سیل‌آسا به جز چند مورد خاص، از جمله سیستم‌های توزیعی که عملکردهای موازی در آنها نیاز است، کاربرد علمی دیگری ندارد.

 

الگوریتم بردار فاصله

 در این روش، مسیریاب‌ها در خود جدولی (برداری) ذخیره می‌کنند با عنوان بردار فاصله که در آن بهترین فاصله تا هر مسیریاب دیگر در شبکه را ذخیره می‌کنند. در این صورت، تصمیم‌گیری بهتری هنگام مسیریابی اتخاذ می‌شود. این جدول‌ها با اطلاعات مسیریاب‌های همسایه به‌روز می‌شود. هر یک از عناصر این جدول‌ها یک درایه دوبخشی دارند که یکی از آنها نشانگر خط خروجی مناسب برای رسیدن به مسیریاب مورد نظر و دیگری تخمین فاصله زمانی تا آن مسیریاب است.

 

 الگوریتم حالت لینک

مسیریابی بردار فاصله مسیریابی خوبی بود و حتی در شبکه آرپانت(10) تا سال 1979 نیز عملیاتی بود، اما دو مشکل اساسی داشت. نخست اینکه معیار تاخیر در این الگوریتم، طول صفی از مسیریاب‌ها بود و دوم اینکه پهنای باند هر یک از خطوط در محاسبات دخالت داده نمی‌شد. بنابراین حتی اگر جای فاصله را با پهنای باند در جداول مسیریاب عوض می‌کردند، زمان همگرایی این مسیریاب‌ها به یک نتیجه درست، به بی‌نهایت میل می‌کرد.

الگوریتم حالت لینک، ساده است و می‌توان به‌صورت زیر آن را بیان کرد:

1. هر مسیریاب باید همسایه‌های خود را شناسایی کرده و آدرس‌های شبکه‌شان را داشته باشد.

2. میزان هزینه و یا تاخیر همسایه‌های خود را بداند.

3. اطلاعاتی که از همسایه‌ها بدست آورده است را برای تمام مسیریاب‌های دیگر بفرستد.

4. کوتاه‌ترین مسیر برای رسیدن به دیگر مسیریاب‌ها را محاسبه کند.

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

برای تخمین هزینه و تاخیر همسایه‌ها، از بسته‌ای به نام Echo استفاده می‌شود. وقتی مسیریاب این بسته را برای همسایه می‌فرستد، آن مسیریاب فورا باید پاسخ آن را ارسال کند، پس از محاسبه زمان رفت و برگشت و تقسیم آن بر عدد 2، میزان نسبی تاخیر بدست می‌آید. سپس این اطلاعات را در قالب بسته‌ای برای دیگر مسیریاب‌ها ارسال می‌کند تا آنها نیز از وضعیت این مسیریاب مطلع باشند.

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



نوع مطلب : مطالب آموزشی 

داغ کن - کلوب دات کام
نظرات() 
Robert's BJ boy
دوشنبه 20 فروردین 1397 11:09 ب.ظ
Ahead of the film arrived on the scene, my overview of the trailer was met with flagrant opposition.
Robert's Blow Boy
دوشنبه 20 فروردین 1397 08:00 ب.ظ
University student, wanting to sort out it.
I began at Cracker Barrel a few months ago as a grill cook,
it is nothing exciting and almost ALWAYS frustrating.
joma jewellery bride
دوشنبه 20 فروردین 1397 06:09 ب.ظ
You may get quick drying varnish that saves
time, you too can get spray varnish which wont smudge a painted design.
garciniacambogiapremium.net
شنبه 18 فروردین 1397 05:41 ب.ظ
Have actually been taking little over a month.
Hilda
پنجشنبه 16 فروردین 1397 04:38 ب.ظ
Simply want to say your article is as astonishing.
The clearness in your post is just nice and i can assume you're an expert on this subject.
Fine with your permission leet me to grab your feed to keep up to date with forthcoming post.
Thanks a million and please continue the gratifyiong
work.
joma jewellery buddha
چهارشنبه 15 فروردین 1397 10:55 ب.ظ
Again, this is without doubt one of the causes that people typically send
incomplete work to the assay office - understanding
that they should re-polish it upon it's return.
garciniacambogiapremium.net
شنبه 11 فروردین 1397 12:55 ب.ظ
Have actually been taking little over a month.
Janette
شنبه 11 فروردین 1397 12:55 ب.ظ
Way earlier than the discovery of valuable metals like gold, silver, copper or bronze etc.
ladies knew tips on how to adorn themselves.
Blundering Ben
شنبه 11 فروردین 1397 10:47 ق.ظ
It's important that each and every business educates its workforce on how to manage staff relations tasks
capably.
www.sy1255.com
شنبه 11 فروردین 1397 09:57 ق.ظ
The size of this diamond is about 5.528 grams. I am in my
50's and I've Bracelets that were given to me in the 1970's, When I lived in Rhodesia.
garcinia cambogia gnc
شنبه 11 فروردین 1397 09:14 ق.ظ
Have been taking little over a month.
Joma Jewellery Stockists
شنبه 11 فروردین 1397 08:24 ق.ظ
Tungsten: Also referred to as wolfram, is fashioned
from tremendous dense alloys and is utilized in merchandise
starting from golf membership heads to weapons.
jocuri cu mario
پنجشنبه 10 اسفند 1396 04:12 ب.ظ
نقاط فوق العاده در مجموع، شما به سادگی دریافت یک نشانه جدید خواننده.
چه چیزی ممکن است شما را در رابطه با درخواست شما پیشنهاد دهد
شما چند روز پیش ساخته اید؟ هر کدوم
spirit guardian vanguard rush cheats
یکشنبه 6 اسفند 1396 01:54 ق.ظ
من کنجکاو هستم که بلاگ پلتفرم شما را استفاده کنم؟
من با آخرین وبسایت من مشکلات امنیتی جزئی دارم
و من می خواهم چیزی امن تر پیدا کنم.
آیاشما هیچ توصیهای دارید؟
slugterra dark waters cheats
جمعه 4 اسفند 1396 08:40 ب.ظ
سایت فوق العاده اینجا اطلاعات مفید زیادی وجود دارد. من
من آن را به چند دوست فرستادم و علاوه بر خواندن نیز به اشتراک گذاشتم.
و به طور طبیعی، با تشکر از شما برای عرق شما!
Thomas
جمعه 17 آذر 1396 09:47 ب.ظ
Does your blog have a contact page? I'm having a tough time locating it but, I'd like to shoot
you an email. I've got some creative ideas for your blog you
might be interested in hearing. Either way, great website and I look forward to seeing it grow over time.
Can you have an operation to make you taller?
شنبه 1 مهر 1396 09:48 ق.ظ
Thanks , I have just been looking for information approximately this topic for
ages and yours is the greatest I've discovered so far.
But, what about the bottom line? Are you sure concerning the source?
feet complaints
یکشنبه 26 شهریور 1396 06:48 ق.ظ
Hi! Do you use Twitter? I'd like to follow you if that would be ok.
I'm undoubtedly enjoying your blog and look forward to new updates.
feet issues
شنبه 18 شهریور 1396 08:02 ق.ظ
Wow! In the end I got a weblog from where I be capable of really obtain valuable information regarding my study and knowledge.
What makes you grow taller during puberty?
دوشنبه 16 مرداد 1396 01:17 ق.ظ
I've been surfing online greater than 3 hours these days, but
I never found any fascinating article like yours. It's pretty
value enough for me. In my view, if all website owners and bloggers made just right content material as you
probably did, the internet might be much more helpful than ever before.
What causes painful Achilles tendon?
شنبه 14 مرداد 1396 11:06 ب.ظ
A person essentially help to make significantly articles I'd state.
This is the very first time I frequented your web page
and to this point? I surprised with the analysis you made
to make this particular post incredible. Magnificent process!
Foot Problems
شنبه 7 مرداد 1396 08:12 ب.ظ
Outstanding story there. What occurred after?
Thanks!
manicure
جمعه 8 اردیبهشت 1396 11:50 ق.ظ
It's hard to come by well-informed people on this subject,
however, you sound like you know what you're talking about!
Thanks
manicure
جمعه 8 اردیبهشت 1396 11:40 ق.ظ
I have read so many articles or reviews about the blogger lovers except this article is in fact
a pleasant piece of writing, keep it up.
BHW
جمعه 25 فروردین 1396 01:02 ب.ظ
Touche. Sound arguments. Keep up the amazing work.
manicure
سه شنبه 22 فروردین 1396 05:00 ق.ظ
Greetings I am so glad I found your blog page, I really found you by mistake, while I was browsing on Yahoo for something else, Anyhow I am here now and would just like to say many thanks for a marvelous post and a all round thrilling blog (I also love the theme/design), I don’t have
time to look over it all at the minute but I have saved it and also added your RSS feeds, so when I have time I will be back to read a great deal more, Please do keep up the excellent jo.
manicure
شنبه 19 فروردین 1396 02:15 ب.ظ
Simply desire to say your article is as astonishing.
The clarity in your post is simply cool and i can assume you are an expert
on this subject. Fine with your permission let me to grab your feed
to keep updated with forthcoming post. Thanks a million and please carry on the rewarding work.
manicure
سه شنبه 15 فروردین 1396 12:49 ب.ظ
This is my first time pay a quick visit at here and i am
genuinely pleassant to read everthing at one place.
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر




Admin Logo
themebox Logo