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

بخشی از پاورپوینت

اسلاید 2 :

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

اسلاید 3 :

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

اسلاید 4 :

ادامه:
الگوریتم های مسیریابی براساس دو دیدگاه طبقه بندی می شوند :
دیدگاه اول براساس تصمیم گیری و میزان هوشمندی: الگوریتم های ایستا و پویا
دیدگاه دوم براساس نوع جمع آوری اطلاعات و پردازش آن ها : الگوریتم های متمرکز و غیر متمرکز
در الگوریتم های ایستا هیچ گونه هوشمندی وجود ندارد و هیچ اعتنایی به توپولوژی و ترافیک شبکه ندارد و هنگام پیکربندی مسیریاب ها توسط مسئول شبکه تنظیم می شود اما در الگوریتم های پویا ، مسیریابی براساس آخرین وضعیت شبکه از لحاظ ترافیک و توپولوژی انجام می شود و هر مدت زمانی معینی جداول مسیریابی به روز می شوند. الگوریتم های BGP- OSPF – RIP از نوع الگوریتم های پویا هستند

اسلاید 5 :

در الگوریتم های متمرکز یا Global Routing ، هر روتر یا مسیریاب باید اطلاعات کاملی از زیرساخت شبکه یا توپولوژی شبکه داشته باشد یعنی می بایست در خصوص تمامی روتر ها ، ارتباطات آنها و هزینه هر خط اطلاعات کاملی داشته باشد. به این نوع الگوریتم ها ، الگوریتم های Link State نیز گفته می شود. مثل الگوریتم دایجسترا. پروتکل هایی مثل OSPF و IS-IS از این نوع هستند.
در الگوریتم های غیرمتمرکز یا Decenterlized Routing ، هر روتر می بایست فقط اطلاعاتی در خصوص مسیریاب های همسایه خود داشته باشد. به این نوع الگوریتم ها ، الگوریتم های Distance Vector گفته می شود پروتکل هایی مثل BGP – RIPنیز از این نوع هستتند.

اسلاید 6 :

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

اسلاید 7 :

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

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

• الگوریتم دیکسترا

• الگوریتم بلمن فورد

• الگوریتم فلوید  وارشال

اسلاید 8 :

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

اسلاید 9 :

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

اسلاید 10 :

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

اسلاید 11 :

الگوریتم حالت لینک:
1 .هر مسیریاب باید همسایههای خود را شناسایی کرده و آدرسهای شبکهشان را داشته باشد.
.2 میزان هزینه و یا تاخیر همسایههای خود را بداند.
3 .اطلاعاتی که از همسایهها بدست آورده است را برای تمام مسیریابهای دیگر بفرستد.
4 .کوتاهترین مسیر برای رسیدن به دیگر مسیریابها را محاسبه کند.

اسلاید 12 :

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

اسلاید 13 :

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

اسلاید 14 :

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

اسلاید 16 :

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