امتیاز : -24

فهرست مطالب

چکیده: 1

الگوریتم های مسیر یابی در شبکه های کامپیوتری 4

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

الگوريتم سيل‌آسا 4

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

الگوريتم حالت لينک 5

الگوریتمهای LS 6

الگوریتم Dijkstra 7

الگوریتم Dijkstra دارای مراحل ذیل میباشد 7

الگوريتمهاي DV 9

مسیریابی سلسله مراتبی 12

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

کاربردها: 14

مزيتها: 14

مسيريابي هوشمند: 20

روش های مسیر یابی روتر ها 21

مسيريابي در يك شبكة با تركيب ساده 21

پروتکل مسیریابی داینامیک روتر سیسکو 23

نحوه عملکرد روترها 24

آگاهی از مقصد يک پيام 25

پروتکل ها 27

رديابی يک پيام 27

انواع روترها 28

روترهای نرم افزاری : 29

روتر و جايگاه آن در شبكه های WAN 29

جايگاه روتر در شبكه های LAN و WAN 29

جايگاه روتر در شبكه های WAN 31

منابع 33

 

 

 

چکیده:

امروزه علم کامپيوتر به حدي پيشرفت کرده که بسياري از علوم ديگر پيشرفتشان وابسته به علم کامپيوتر مي باشد.شبکه هاي کامپيوتري به حدي پيشرفت کرده اند که توانسته اند جهان را به يک دهکده علمي کوچک تبديل نمايند.براي برقراري ارتباط بين اين شبکه ها نيازمند به يک ستون فقرات مي باشيم٬ اين شبکه زير بنايي که از تعداد زيادي مسيرياب تشکيل شده است وظيفه انتقال اطلاعات را دارد. بر روي اين مسيرياب ها بايد الگوريتم هايي اجرا شوند تا بتوانند بهترين مسير را براي انتقال اطلاعات در اين دهکده را انتخاب کنند.

در طول دهه اخير،اينترنت از پروژه هاي تحقيقاتي ارتباطات که دنياي ما را براي هميشه دچار تحول ساخته اند،فراتر رفته است.پيام هاي فوري،تلفني ،فيلم و موسیقي هاي درخواستي،بانکداري؛تنها بخشي از کاربرد هاي فراواني هستند که زندگي ما را راحتر کرده اند.اما تکنولوژي و فناوري  که ما را قادر به استفاده از اين امکانات مي کند شبکه هاي کامپيوتري و نحوه ي ارتباط بين اين شبکه ها مي باشد.اينترنت که بزرگترين ابزار براي ارائه خدمات فوق مي باشد از چندين هزار شبکه کوچک تشکيل شده است که براي برقراري ارتباط و تبادل اطلاعت بين اين شبکه ها به يک شبکه گسترده ديگر نياز دارد که backbone ناميده مي شود، و داراي device هاي مختلف از جمله router است ،نحوه ي رد و بدل شدن پيام ها بين router ها اساس کار اين backbone مي باشد،ما به دليل اهميتي که اين تکنيک ارسال و دريافت پيام از يک نتقطه به نقطه ديگر دارد روش هاي مختلف انجام اين کار را بررسي مي کنيم و در نهايت بهترين و مناسب ترين روش انجام کار را به صورت کامل بررسي مي کنيم.

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

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

روترها از الگوریتمهای مسیریابی،برای یافتن بهترین مسیر تا مقصد استفاده مینمایند هنگامی كه ما در مورد بهترین مسیر صحبت میكنیم،پارامترهایی همانند تعداد hopها (مسیری كه یك بسته از یك روتر دیگر در شبكه منتقل میشود).زمان تغییر و هزینه ارتباطی ارسال بسته را در نظر میگیریم.

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

در الگوریتم های مسیر یابی غیر متمركز،هر روتر اطلاعاتی در مورد روترهایی كه مستقیما به آنها متصل میباشند در اختیار دارد. در این روش هر روتر در مورد همه روتر های موجود در شبكه،اطلاعات در اختیار ندارد.این الگوریتمها تحت نام الگوریتمهای (DV (distance vectorمعروف هستند.در الگوریتمهای مسیریابی عمومی،هر روتر اطلاعات كاملی در مورد همه روترهای دیگر شبكه و نیز وضعیت ترافیك شبكه در اختیار دارد.این الگوریتمها تحت نام الگوریتمهای(LS(Link state معروف هستند.ما در ادامه مقاله به بررسی الگوریتمهای LS میپردازیم

 

 

الگوریتم های مسیر یابی در شبکه های کامپیوتری

 

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

 

الگوریتمهای LS

در الگوریتمهای LS ،هر روتر میبایست مراحل ذیل را به انجام رساند:

روترهای را كه به لحاظ فیزیكی به آنها متصل میباشد را شناسایی نموده و هنگامی كه شروع به كار میكند آدرسهایIP آنها بدست آورد. این روتر ابتدا یك بسته HELLO را روی شبكه ارسال میكند. هر روتری كه این بسته را دریافت میكند از طریق یك پیام كه دارای آدرس IP خود این روتر میباشد به پیام HELLO پاسخ میدهد.

زمان تاخیر مربوط به روترهای مجاور را اندازه گیری نماید(یا هر پارامتر مهم دیگری از شبكه همانند ترافیك متوسط)

برای انجام این كار ،روترها بسته های echo را روی شبكه ارسال میكنند. هر روتری كه این بسته ها را دریافت میكند با یك بسته echo reply به آن پاسخ میدهد.با تقسیم زمان مسیر رفت و برگشت به دو،روترها میتوانند زمان تاخیر را محاسبه كنند.(زمان مسیر رفت و برگشت،سنجشی از تاخیر فعلی روی یك شبكه میباشد)توجه داشته باشید كه این زمان شامل زمانهای ارسال و پردازش میباشد.

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

در این مرحله همه روترها دانش خود را با روتر های دیگر به اشتراك گذاشته و اطلاعات مربوط به شبكه را با یكدیگر مبادله میكنند.با این روش هر روتر میتواند در مورد ساختار و وضعیت شبكه اطلاعات كافی بدست آورد.

 

الگوریتم Dijkstra 

روترها بهترین مسیر تا هر گره را انتخاب میكنند.آنها این كار را با استفاده از یك الگوریتم همانند الگوریتم كوتاهترین مسیر Dijkstra انجام میدهند.در این الگوریتم،یك روتر مبتنی بر اطلاعاتی كه از سایر روترها جمع آوری نموده است،گرافی از شبكه را ایجاد مینماید.این گراف مكان روترهای موجود در شبكه و نقاط پیوند آنها را به یكدیگر نشان میدهد.هر پیوند با یك شماره به نام Costیاweight مشخص میشود.این شماره تابعی از زمان تاخیر،متوسط ترافیك و گاهی اوقات تعداد hopهای بین گره ها میباشد.برای مثال اگر دو پیوند بین یك گره و مقصد وجود داشته باشد،روتر پیوندی با كمترین Weight را انتخاب میكند.

 

  گزارش تخلف  |  افزودن به فایل های من | jikjik | تاریخ ارسال : 22 /04 /1394

شما هم می توانید در مورد این فایل نظر دهید.