مسیر یابی شبکه کامپیوتر
مسيريابي در شبکه اينترنت
هدفهاي آموزشي :
q مفاهيم اوليه مسيريابي
q الگوريتمهاي مسيريابي LS
q الگوريتمهاي مسيريابي بردار فاصله - DV -
q مسيريابي سلسله مراتبي
q پروتکل RIP
q پروتکل OSPF
q پروتکل BGP
1) مفاهيم اوليه مسيريابي
مسيرياب: ابزاري است براي برقراري ارتباط دو يا چند شبکه
زيرساخت ارتباطي: مجموعه مسيريابها و کانالهاي فيزيکي ما بين آنها
الگوريتمهاي مسيريابي : روشهايي براي پيدا کردن مسيري بهينه ميان دومسيرياب به گونه‌اي که هزينه کل مسير به حداقل برسد.
برخي اصطلاحات کليدي در مسيريابي
آدرسهاي MAC:
• آدرسهاي لايه فيزيکي جهت انتقال فريمها بر روي کانال
• اندازه آدرس وابسته به پروتکل و توپولوژي شبکه
• تغيير آدرسهاي MAC بسته‌هاي اطلاعاتي هنگام عبور از مسيريابهاي موجود در مسير
آدرسهاي IP :
• آدرسهاي جهاني و منحصر به فرد
• مشخص‌کننده يک ماشين فارغ از نوع سخت افزار و نرم افزار آن
• ثابت بودن آدرسهاي IP بسته هاي اطلاعاتي هنگام عبور از مسيريابهاي موجود در مسير
بسته IP:
• واحد اطلاعاتي با اندازه محدود
توپولوژي شبكه:
• مجموعه مسيريابها و كانالهاي فيزيكي ما بين آنها در زيرساخت ارتباطي يك شبكه
• متغير با زمان
ترافيك شبكه:
• تعداد متوسط بسته‌هاي اطلاعاتي ارسالي و يا دريافتي روي يك كانال در واحد زمان
• متغير با زمان
گام يا Hop:
• عبور بسته از يك مسيرياب = گام
• تعداد مسيريابهاي موجود در مسير يك بسته = تعداد گام = Hop Count
ازدحام يا Congestion:
بيشتر بودن تعداد متوسط بسته‌هاي ورودي به يك مسيرياب از تعداد متوسط بسته هاي خروجي
1-1) روشهاي هدايت بسته‌هاي اطلاعاتي در شبکه‌هاي کامپيوتري
الف) روش مدار مجازي Virtual Circuit (VC)
ب) روش ديتاگرام Datagram
خصوصيات روش VC
• ارسال بسته‌هاي اطلاعاتي بدون نياز به اطلاع از آدرسهاي IP مبدأ و مقصد و فقط داشتن شماره VC جهت ارسال بسته
• عدم اجراي الگوريتم مسيريابي جهت هدايت بسته‌هاي اطلاعاتي از مبدأ به مقصد
• دريافت بسته به ترتيب ارسال شده در مقصد
عدم احتمال گم‌شدن بسته‌ها در عمل مسيريابي در شبكه
خصوصيات روش ديتاگرام
• ارسال بسته‌هاي اطلاعاتي با استفاده از آدرسهاي IP مبدأ و مقصد در شبكه
• انجام مسيريابي جداگانه براي هر بسته
• توزيع و هدايت بسته‌ها روي مسيرهاي متفاوت بر اساس شرايط توپولوژيكي
و ترافيكي لحظه‌اي شبكه
• امكان دريافت بسته بدون ترتيب ارسال شده در مقصد
• لزوم نظارتهاي ويژه بر گم شدن و يا تكراري بودن بسته در لايه‌هاي بالاتر
انواع الگوريتمهاي مسيريابي
الف) از ديدگاه روش تصميم‌گيري و ميزان هوشمندي الگوريتم
ايستا
پويا
ب) از ديدگاه چگونگي جمع‌آوري و پردازش طلاعات زيرساخت ارتباطي شبكه
سراسري / متمركز
غيرمتمركز
الگوريتم ايستا
• عدم توجه به شرايط توپولوژيكي و ترافيك لحظه‌اي شبكه
• جداول ثابت مسيريابي هر مسيرياب در طول زمان
• الگوريتمهاي سريع
• تنظيم جداول مسيريابي به طور دستي در صورت تغيير توپولوژي زيرساخت شبكه
• تغيير مسيرها به کندي در اثناي زمان
الگوريتم پويا
• به هنگام سازي جداول مسيريابي به صورت دوره‌اي بر اساس آخرين وضعيت توپولوژيكي و ترافيك شبكه
• تغيير سريع مسيرها
• تصميم‌گيري بر اساس وضعيت فعلي شبكه جهت انتخاب بهترين مسير
× ايجاد تأخيرهاي بحراني هنگام تصميم‌گيري بهترين مسير به جهت پيچيدگي الگوريتم
الگوريتم سراسري
• اطلاع كامل تمام مسيريابها از همبندي شبکه و هزينه هر خط
• الگوريتمهاي Link State(LS)
الگوريتم غير متمركز
• محاسبه و ارزيابي هزينه ارتباط با مسيريابهاي همسايه (مسيريابهايي كه به صورت مستقيم و فيزيكي با آن در ارتباط هستند)
• ارسال جداول مسيريابي توسط هر مسيرياب در فواصل زماني منظم براي مسيريابهاي مجاور
• پيچيدگي زماني كم
• الگوريتمهاي Distance Vector
3-1) روش ارسال سيل آسا ( Flooding Algorithm)
• سريعترين الگوريتم براي ارسال اطلاعات به مقصد در شبكه
• جهت ارسال بسته‌هاي فراگير و كنترلي مانند اعلام جداول مسيريابي
مشكل روش سيل آسا
• ايجاد حلقه بينهايت و از كارافتادن شبكه
راه حل رفع مشكل حلقه بينهايت
1) قراردادن شماره شناسايي براي هر بستهSelective Flooding
2) قراردادن طول عمر براي بسته‌ها
الگوريتم هايLS
1- شناسايي مسيريابهاي مجاور
2- اندازه‌گيري هزينه
3- تشكيل بسته‌هاي LS
4- توزيع بسته‌هاي LS روي شبكه
5- محاسبه مسيرهاي جديد
1- شناسايي مسيريابهاي مجاور
• ارسال بسته خاصي به نام بسته سلام Hello Packet توسط مسيرياب به تمام خروجي‌ها
• پاسخگويي مسيريابهاي متصل از طريق كانال فيزيكي مستقيم به بسته ارسالي و اعلام آدرس IP خود به مسيرياب
• درج اطلاعات بسته‌هاي پاسخ در جدول مسيرياب
-2اندازه‌گيري هزينه
• اندازه‌گيري تأخير هر يك از خطوط خروجي مسيرياب توسط خود مسيرياب
• ارسال بسته خاص به نام Echo Packet روي تمام خطوط خروجي خود
• پاسخ تمام مسيريابهاي گيرنده بسته با ارسال بسته Echo Reply
• اگر مسيرياب موظف باشد كه با دريافت بستة Echo خارج از نوبت و به سرعت به آن پاسخ بدهد ، “زمان رفت و برگشت” اين بسته فقط تاخير فيزيكي بين دو مسيرياب را به عنوان معيار هزينه مشخص مي‌كند.
• اندازه‌گيري اين زمان با استفاده از زمان سنج و تقسيم آن مقدار بر عدد 2 و درج در جدول توسط مسيرياب
3- تشكيل بسته‌هاي LS
تشكيل بسته LS پس از جمع آوري اطلاعات لازم از مسيريابهاي مجاور شامل:
الف) آدرس جهاني مسيرياب توليدكنندة بسته
ب) يك شمارة ترتيب (تا بسته‌هاي تكراري از بسته‌هاي جديد تشخيص داده شوند.)
ج) طول عمر بسته (تا اطلاعات بسته ، زمان انقضاي اعتبار داشته باشد.)
د) آدرس جهاني مسيريابهاي مجاور و هزينة تخميني
4- توزيع بسته‌هايLS روي شبكه
• ارسال بسته‌هاي LS به روش سيل آسا
• وجود شماره ترتيب براي هر بسته جهت جلوگيري از بروز حلقه تكرار
• در نظرگرفتن طول عمر براي هر بسته جهت رفع مشكل دريافت بسته‌هاي تكراري
• احراز هويت ارسال‌كننده بسته LS در مسيريابها جهت جلوگيري از بسته‌هاي LS آلوده
پاسخ با نقل قول
