مسیریابی در شبکه اینترنت

مسیریابی در شبکه اینترنت

اسلاید 1: مهر 85 مفاهيم اوليه مسيريابي الگوريتم‌هاي مسيريابي LS الگوريتم‌هاي مسيريابي بردار فاصله - DV - مسيريابي سلسله مراتبي پروتکل RIP پروتکل OSPF پروتکل BGPفصل چهارم : مسيريابي در شبکه اينترنتهدفهاي آموزشي :

اسلاید 2: مهر 851) مفاهيم اوليه مسيريابيمسيرياب: ابزاري است براي برقراري ارتباط دو يا چند شبکهزيرساخت ارتباطي: مجموعه مسيريابها و کانالهاي فيزيکي ما بين آنهاالگوريتم‌هاي مسيريابي : روشهايي براي پيدا کردن مسيري بهينه ميان دومسيرياب به گونه‌اي که هزينه کل مسير به حداقل برسد. زيرساخت ارتباطي يك شبكة فرضيABCEFD5533111222مسيرياب

اسلاید 3: مهر 85برخي اصطلاحات کليدي در مسيريابيآدرسهاي MAC: آدرسهاي لايه فيزيکي جهت انتقال فريمها بر روي کانال اندازه آدرس وابسته به پروتکل و توپولوژي شبکه تغيير آدرسهاي MAC بسته‌هاي اطلاعاتي هنگام عبور از مسيريابهاي موجود در مسيرآدرسهاي IP : آدرسهاي جهاني و منحصر به فرد مشخص‌کننده يک ماشين فارغ از نوع سخت افزار و نرم افزار آن ثابت بودن آدرسهاي IP بسته هاي اطلاعاتي هنگام عبور از مسيريابهاي موجود در مسيربسته IP: واحد اطلاعاتي با اندازه محدود

اسلاید 4: مهر 85توپولوژي شبكه: مجموعه مسيريابها و كانالهاي فيزيكي ما بين آنها در زيرساخت ارتباطي يك شبكه متغير با زمانترافيك شبكه: تعداد متوسط بسته‌هاي اطلاعاتي ارسالي و يا دريافتي روي يك كانال در واحد زمان متغير با زمانگام يا Hop: عبور بسته از يك مسيرياب = گام تعداد مسيريابهاي موجود در مسير يك بسته = تعداد گام = Hop Count ازدحام يا Congestion: بيشتر بودن تعداد متوسط بسته‌هاي ورودي به يك مسيرياب از تعداد متوسط بسته هاي خروجيبن بست Deadlock:پايان طول عمر بسته‌ها

اسلاید 5: مهر 851-1) روشهاي هدايت بسته‌هاي اطلاعاتي در شبکه‌هاي کامپيوتريالف) روش مدار مجازي Virtual Circuit (VC)ب) روش ديتاگرام Datagram خصوصيات روش VC ارسال بسته‌هاي اطلاعاتي بدون نياز به اطلاع از آدرسهاي IP مبدأ و مقصد و فقط داشتن شماره VC جهت ارسال بسته عدم اجراي الگوريتم مسيريابي جهت هدايت بسته‌هاي اطلاعاتي از مبدأ به مقصد دريافت بسته به ترتيب ارسال شده در مقصد عدم احتمال گم‌شدن بسته‌ها در عمل مسيريابي در شبكه

اسلاید 6: مهر 85applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Initiate call2. incoming call3. Accept call4. Call connected5. Data flow begins6. Receive dataروش vc

اسلاید 7: مهر 85خصوصيات روش ديتاگرام ارسال بسته‌هاي اطلاعاتي با استفاده از آدرسهاي IP مبدأ و مقصد در شبكه انجام مسيريابي جداگانه براي هر بسته توزيع و هدايت بسته‌ها روي مسيرهاي متفاوت بر اساس شرايط توپولوژيكي و ترافيكي لحظه‌اي شبكه امكان دريافت بسته بدون ترتيب ارسال شده در مقصد لزوم نظارتهاي ويژه بر گم شدن و يا تكراري بودن بسته در لايه‌هاي بالاتر

اسلاید 8: مهر 85applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Send data2. Receive dataروش Datagram

اسلاید 9: مهر 85انواع الگوريتمهاي مسيريابيايستاالف) از ديدگاه روش تصميم‌گيري و ميزان هوشمندي الگوريتمپويا ب) از ديدگاه چگونگي جمع‌آوري و پردازش طلاعات زيرساخت ارتباطي شبكهسراسري / متمركزغيرمتمركز

اسلاید 10: مهر 85الگوريتم ايستا عدم توجه به شرايط توپولوژيكي و ترافيك لحظه‌اي شبكه جداول ثابت مسيريابي هر مسيرياب در طول زمان الگوريتم‌هاي سريع تنظيم جداول مسيريابي به طور دستي در صورت تغيير توپولوژي زيرساخت شبكه تغيير مسيرها به کندي در اثناي زمانالگوريتم پويا به هنگام سازي جداول مسيريابي به صورت دوره‌اي بر اساس آخرين وضعيت توپولوژيكي و ترافيك شبكه تغيير سريع مسيرها تصميم‌گيري بر اساس وضعيت فعلي شبكه جهت انتخاب بهترين مسير× ايجاد تأخيرهاي بحراني هنگام تصميم‌گيري بهترين مسير به جهت پيچيدگي الگوريتم

اسلاید 11: مهر 85الگوريتم سراسري اطلاع كامل تمام مسيريابها از همبندي شبکه و هزينه هر خطالگوريتم‌هاي Link State (LS)الگوريتم غير متمركز محاسبه و ارزيابي هزينه ارتباط با مسيريابهاي همسايه (مسيريابهايي كه به صورت مستقيم و فيزيكي با آن در ارتباط هستند) ارسال جداول مسيريابي توسط هر مسيرياب در فواصل زماني منظم براي مسيريابهاي مجاور پيچيدگي زماني كم الگوريتم‌هاي Distance Vector

اسلاید 12: مهر 853-1) روش ارسال سيل آسا ( Flooding Algorithm) سريعترين الگوريتم براي ارسال اطلاعات به مقصد در شبكه جهت ارسال بسته‌هاي فراگير و كنترلي مانند اعلام جداول مسيريابيمشكل روش سيل آسا ايجاد حلقه بينهايت و از كارافتادن شبكه

اسلاید 13: مهر 85BCDEAحلقه‌هاي بينهايت در روش سيل آساراه حل رفع مشكل حلقه بينهايت1) قراردادن شماره شناسايي براي هر بسته Selective Flooding2) قراردادن طول عمر براي بسته‌ها

اسلاید 14: مهر 85الگوريتم هاي LS1- شناسايي مسيريابهاي مجاور2- اندازه‌گيري هزينه3- تشكيل بسته‌هاي LS4- توزيع بسته‌هاي LS روي شبكه5- محاسبه مسيرهاي جديد1- شناسايي مسيريابهاي مجاور ارسال بسته خاصي به نام بسته سلام Hello Packet توسط مسيرياب به تمام خروجي‌ها پاسخگويي مسيريابهاي متصل از طريق كانال فيزيكي مستقيم به بسته ارسالي و اعلام آدرس IP خود به مسيرياب درج اطلاعات بسته‌هاي پاسخ در جدول مسيرياب

اسلاید 15: مهر 85اندازه‌گيري هزينه 2- اندازه‌گيري تأخير هر يك از خطوط خروجي مسيرياب توسط خود مسيرياب ارسال بسته خاص به نام Echo Packet روي تمام خطوط خروجي خود پاسخ تمام مسيريابهاي گيرنده بسته با ارسال بسته Echo Reply اگر مسيرياب موظف باشد كه با دريافت بستة Echo خارج از نوبت و به سرعت به آن پاسخ بدهد ، “زمان رفت و برگشت” اين بسته فقط تاخير فيزيكي بين دو مسيرياب را به عنوان معيار هزينه مشخص مي‌كند.اندازه‌گيري اين زمان با استفاده از زمان سنج و تقسيم آن مقدار بر عدد 2 و درج در جدول توسط مسيرياب

اسلاید 16: مهر 853- تشكيل بسته‌هاي LS تشكيل بسته LS پس از جمع آوري اطلاعات لازم از مسيريابهاي مجاور شامل: الف) آدرس جهاني مسيرياب توليدكنندة بستهب) يك شمارة ترتيب (تا بسته‌هاي تكراري از بسته‌هاي جديد تشخيص داده شوند.)ج) طول عمر بسته (تا اطلاعات بسته ، زمان انقضاي اعتبار داشته باشد.)د) آدرس جهاني مسيريابهاي مجاور و هزينة تخمينيبسته‌هاي LSيك زيرساخت از يك شبكه فرضيفيلد شماره ترتيبفيلد طول عمر

اسلاید 17: مهر 854- توزيع بسته‌هايLS روي شبكه ارسال بسته‌هاي LS به روش سيل آسا وجود شماره ترتيب براي هر بسته جهت جلوگيري از بروز حلقه تكرار در نظرگرفتن طول عمر براي هر بسته جهت رفع مشكل دريافت بسته‌هاي تكراري احراز هويت ارسال‌كننده بسته LS در مسيريابها جهت جلوگيري از بسته‌هاي LS آلوده

اسلاید 18: مهر 855- محاسبه مسيرهاي جديد تشكيل ساختمان داده گراف زيرشبكه جهت انتخاب بهترين مسير بين دو گره هنگام دريافت بسته‌هاي LS از تمام مسيريابهاي شبكه استفاده از الگوريتم دايجكسترا جهت يافتن بهترين مسير بين دو گره( Dijkstra Shortest Path Algorithm) است. j تا i بيانگر هزينه خط ميان گره C( i , j )* هرگاه همسايگاني در مجاورت گره وجود نداشته باشند بينهايت تلقي مي شود.C( i , j ) .V هزينه فعلي مسير ميان مبدا تا گره D(v)* درست قبل ازV گره‌اي که در طول مسير از مبدا تا P(v)* واقع شده. V *N مجموعه گره‌هايي که عبور از آنها کم هزينه برآورد گشته است.

اسلاید 19: مهر 85Dijkstra’s Algorithm

اسلاید 20: مهر 85الگوريتمهاي DV يا بردار فاصله يكي از روشاي پويا در مسيريابي مورد استفاده در شبكه ARPA استفاده در مسيريابهاي كوچك نامهاي متفاوت روش DV پروتكل RIP الگوريتم مسيريابي Bellman - Ford الگوريتم مسيريابي Ford – Fulkerson الگوريتم Distance Vector Routing

اسلاید 21: مهر 85اصول كار روش DV محاسبه خطوطي را كه به صورت فيزيكي با مسيريابهاي ديگر دارد و درج در جدول مسيريابي بينهايت درنظرگرفتن هزينة خطوطي كه مسيرياب با آنها در ارتباط مستقيم نيست ارسال ستون هزينه از جدول مسيريابي براي مسيريابهاي مجاور در بازه‌هاي زماني مشخص،‌ توسط هر مسيرياب (“يعني فقط براي مسيريابهائي كه با آن در ارتباط است نه تمام مسيريابها ”). دريافت اطلاعات جديد ا زمسيريابهاي مجاور در در فواصل T ثانيه‌اي به هنگام نمودن جدول مسيريابي پس از دريافت جداول مسيريابي از مسيريابهاي مجاور ، طبق يك الگوريتم بسيار ساده

اسلاید 22: مهر 85جدول مسيريابي مربوط به مسيرياب Jزيرساخت ارتباطي يك شبكة فرضي با دوازده مسيريابالگوريتمهاي DV يا بردار فاصله

اسلاید 23: مهر 85مشكل عمده پروتكلهاي DV عدم همگرايي سريع جداول مسيريابي هنگام خرابي يك مسيرياب يا يك كانال ارتباطي = مشكل شمارش تا بينهايت راه حل : وقتي يك مسيرياب مي‌خواهد اطلاعاتي را به همسايه‌هايش بدهد هزينه رسيدن به آنهايي را كه قطعاً بايد از همان مسيرياب بگذرند را اعلام نمي‌كند. (يا  اعلام مي‌كنند)

اسلاید 24: مهر 85مسئله شمارش تا بينهايتبه خبرهاي خوب واکنش سريع ولي به خبرهاي بد واکنش کندي نشان مي دهد.

اسلاید 25: مهر 85هرگاه مسيريابي از زيرشبکه خارج شود هرکدام از ساير مسيرياب‌هاي فعال احساس مي‌كنند ‌ از طريق ديگري مسيري بهتر به آن وجود دارد.مسئله شمارش تا بينهايت

اسلاید 26: مهر 85مسيريابي سلسله‌مراتبي Hierarchical Routing رشد شبكه و زيادشدن شبكه‌هاي محلي و مسيريابها، افزايش حجم جداول مسيريابي و زيادشدن زمان لازم جهت تعيين مسير يك بسته و درنتيجه ايجاد تأخيرهاي بحراني و كاهش كارآيي شبكهدر مسيريابي سلسله‌مراتبي ، مسيريابها در گروههايي به نام ”ناحيه Region“ دسته‌بندي مي‌شوند. هر مسيرياب فقط ”نواحي” و مسيريابهاي درون ناحية خود را مي‌شناسد و هيچ اطلاعي از مسيريابهاي درون نواحي ديگر ندارد.

اسلاید 27: مهر 85مسيريابي سلسله‌مراتبيناحيه 1ناحيه 2

اسلاید 28: مهر 85مقايسه اندازه جدول مسيريابي در روشهاي سلسله ‌مراتبي تعداد ركورد در جدولتعداد مسيريابتعداد حوزهZonesتعداد دستهClustersتعداد ناحيهRegions720720--1مسيريابي DV بدون سلسله‌مراتب5330--24مسيريابي DV با سلسله‌مراتب دو‌سطحي2510-89مسيريابي DV با سلسله‌مراتب سه‌سطحي194459مسيريابي DV با سلسله‌مراتب سه‌سطحيمشكل روش سلسله مراتبيبه دليل مشخص‌نبودن كل توپولوژي زيرشبكه براي هر مسيرياب :ممكن است مسير انتخابي جهت ارسال بسته به يك مسيرياب خاص درون يك ناحيه بهينه نباشد. مزيت استفاده از روشهاي سلسله‌ مراتبي: صرفه جويي در اندازه جداول مسيريابي

اسلاید 29: مهر 85مسيريابي در اينترنتاينترنت مجموعه‌اي از شبكه‌هاي خودمختار Autonomous و ”مستقل” است كه به نحوي به هم متصل شده‌اند. شبكة خودمختار كه اختصاراًAS ناميده مي‌شود، شبكه‌اي است كه تحت نظارت و سرپرستي يك مجموعه يا سازمان خاص پياده و اداره مي‌شود. مثلاً يك دانشگاهمسئول شبكة خودمختار مي‌تواند بر روي شبكة تحت نظارت خود “حاكميّت” داشته باشد يعني مي‌تواند بر روي تك‌تك اجزاي شبكه (ماشينهاي ميزبان)، توپولوژي كل شبكه‌، سيستم عامل‌، طراحي زيرساخت ارتباطي و طريقة اتصال شبكه‌هاي محلي و نوع پروتكل مسيريابي اعمال نفوذ كرده و نظرات خود را پياده نمايد.

اسلاید 30: مهر 85مسيريابي در شبكه هاي خود مختارمسيريابي بسته‌هاي IP در درون يك شبكة خودمختار بيشتر تابع پارامترهايي نظير سرعت و قابل اعتماد بودن الگوريتم مسيريابي است .دروازه‌هاي مرزي Border Gateway :مسيريابهايي كه ارتباط دو شبكة خودمختار متفاوت را برقرار مي‌كنند و تمامي ارتباطات بين‌شبكه‌اي از طريق آنها انجام مي‌شود .دروازه‌هاي مرزي Interior Gateway مسيريابهايي كه ارتباط دو شبكة خودمختار متفاوت را برقرار مي‌كنند و تمامي ارتباطات بين‌شبكه‌اي از طريق آنها انجام مي‌شود. مسيريابهاي مرزي و ساختار ارتباطي بين آنها تابع قواعد “مسيريابي بروني” مسيريابهاي داخلي تابع الگوريتمهاي “مسيريابي دروني” مرزي مسيريابهاي مرزي = مسيريابهاي BGP

اسلاید 31: مهر 85مثالي از چهار شبكة AS متصل به هم مسيريابهاي مرزيمثال: اگر يك ماشين ميزبان در شبكة 1 بخواهد بسته‌اي براي ماشين ديگر در شبكة 4 بفرستد سه مرحله مسيريابي لازم است: مسيريابي در درون شبكة 1 تا رسيدن بسته به مسيرياب مرزي مسيريابي روي خطوط ارتباطي بين‌شبكه‌اي تا رسيدن به شبكة 4 مسيريابي درون شبكة 4 تا رسيدن به ماشين مقصد

اسلاید 32: مهر 85پروتكل RIP در مسيريابي دروني : Routing Information Protocol اولين پروتکل مسيريابي دروني (1982) مبتني بر الگوريتم بردار فاصله DV معيار هزينه = تعداد گام مبادله جداول مسيريابي هر 30 ثانيه يكبار بين مسيريابهاي مجاور حداكثر تعداد طول مسير = 15 استفاده از پروتكل UDP و پورت شماره 250 جهت مبادله جداول مسيريابي

اسلاید 33: مهر 85routedRouting tableجداول مسيريابي در لايه دوم جهت مسيريابي بسته‌هاي IPمبادله جداول و عمليات به هنگام‌سازي توسط برنامه كاربردي لايه چهارمپروتكل RIP در لاية كاربرد Application LayerIP LayerTransport Layer(UDP)Host To NeworkApplication LayerIP LayerTransport Layer(UDP)Host To NeworkroutedRouting tableroutedRouting table

اسلاید 34: مهر 85قالب پيامها در پروتكل RIP ….Metric (Hop Count )Must be zero for InternetMust be zero for InternetIP AddressAddress FamilyReserved ( 0 )CommandVersionReserved ( 0 )32

اسلاید 35: مهر 85پروتكل OSPFدر مسيريابي دروني Open Shortest Path First مقايسه پروتكل OSPF با RIP استفاده از الگوريتم LS براي محاسبة بهترين مسير بر خلاف پروتكل RIP و عدم وجود مشكل “شمارش تا بينهايت” توانايي در نظر گرفتن چندين معيار هزينه در انتخاب بهترين مسير برخلاف پروتكل RIP در نظرگرفتن حجم بار و ترافيك يك مسيرياب در محاسبة بهترين مسير بر خلاف پروتكل RIP و همگرايي سريع جداول مسيريابي در هنگام خرابي يك مسيرياب انتخاب مسير مناسب براي يك بسته بر اساس نوع سرويس درخواستي با توجه به فيلد Type of Service در بستة IP بر خلاف پروتكل RIP

اسلاید 36: مهر 85مقايسه پروتكل OSPF با RIP هدايت نكردن تمام بسته‌هاي ارسالي براي يك مقصد خاص، روي بهترين مسير و ارسال درصدي از بسته‌ها روي مسيرهاي در رتبه 2و 3 و ... از نظر هزينه، بر خلاف پروتكل RIP = موازنه = Load Balancing پشتيباني از مسيريابي سلسله‌مراتبي برخلاف پروتكل RIP عدم قبول جداول مسيريابي مسيريابها توسط هر مسيرياب بدون احراز هويت ارسال‌كنندة آن استفاده مستقيم از پروتكل IP برخلاف پروتكل RIP ( استفاده از پروتكل UDP در لايه انتقال)

اسلاید 37: مهر 85 تقسيم يك شبكه خود مختار به تعدادي ناحيه و اطلاع تمام مسيريابهاي درون يك ناحيه از مسيريابهاي هم ناحيه و هزينه ارتباط بين آنها و ذخيره آن در جدول ارسال جداول براي تمام مسيريابهاي هم ناحيه در زمانهاي بهنگام‌سازيسلسله‌مراتب مسيريابي در پروتكل OSPF مسيريابهاي مرزي برقراركننده ارتباط نواحيناحيه 1ناحيه 2ناحيه 3مجموعه مسيريابهاي مرزي + سيريابهاي خارج از هر ناحيه + ساختار ارتباطي بين اين مسيريابها

اسلاید 38: مهر 85پروتكل BGP : پروتكل مسيريابي بروني The Exterior Gateway Routing Protocol الگوريتمهاي مسيريابي بين شبكه‌هاي خود مختار در اينترنت : BGP به جاي مبادله جداول مسيريابي و هزينه‌ها در پروتكل BGP بين مسيريابهاي مجاور، ارسال فهرستي از مسيرهاي كامل بين هر دو مسيرياب در شبكه براي مسيريابهاي مجاور در بازه‌هايزماني T ثانيه‌اي ( بدون تعيين هزينه )

اسلاید 39: مهر 85ساختار فرضي از ارتباط بين مسيريابهاي BGP دريافت اطلاعات توسط مسيرياب F در مورد مسيرياب D از مسيريابهاي مجاورتعيين مسير رسيده از Bتعيين مسير رسيده از Gتعيين مسير رسيده از Iتعيين مسير رسيده از B

اسلاید 40: مهر 85الگوريتمهائي كه در تبادل اطلاعات با همسايگان مسيرهاي كامل را به اطلاع يكديگر مي‌رسانند: اولاً : مشكل “شمارش تا بينهايت” را نخواهد داشت. مانند پروتكل BGP ثانياً : مسيريابهاي ديگر مي‌توانند بر روي كل مسير ، بررسي‌هاي امنيتي ، اقتصادي ، سياسي و ملي انجام دهند و بر اساس اين پارامترها مسير مناسب را انتخاب نمايند. مانند پروتكل BGPتبادل اطلاعات مسيريابي ( فهرست مسيرها) در پروتكل BGP در قالب پيامانواع پيام تعريف شده در پروتكل BGP: پيام OPEN پيام KEEPALIVE پيام NOTIFICATION پيام UPDATE