مسیریابی
الگوریتمهای مسیریابی
پروتکل های مسیریابی
مقدمه :
برای برقراری ارتباط بین یک مبدائ و مقصد ،به مکانیزمی نیاز است تا اهداف اساسی هر
پروتکل مسیریابی محقق گردد .این اهداف عبارتند از :
1: بیشینه ساختن کارایی شبکه
2: کمینه کردن هزینه شبکه با توجه به ظرفیت آن
سیکل مسیریابی به شرح زیر میباشد :
تولید مسیر : مسیرها را مطابق با اطلاعات جمع آوری و توزیع شده از وضعیت شبکه تولید
میکند .
انتخاب مسیر : مسیرهای مناسب را بر اساس اطلاعات وضعیت شبکه انتخاب می کند.
ارسال داده به جلو : ترافیک کاربر را در امتداد مسیر انتخاب شده به جلو ارسال می کند.
نگهداری مسیر : که مسئول نگهداری مسیر انتخاب شده می باشد.
مسیریابی :
تعریف مسیر یابی :
مکانیزمی است که به وسیله آن ترافیک کاربر به صورت مستقیم یا با واسطه از مبدا به مقصد
هدایت شود و مسیریابها تجهیزاتی هستند که این عمل را انجام میدهند .
پارامترهای مسیر یابی :
تعداد گام ، تاخیر ، توان عملیاتی ، نرخ ریزش ، استحکام و هزینه و …
گاهی تمایز قائل شدن بین فرآیند مسیریابی که به تصمیم گیری در خصوص مسیرهای بهینه
اطلاق میشود و فرایند هدایت (forwarding) آنچه با ورود بسته اتفاق میفتد مفید است .
میتوان بدینگونه اندیشید که هر مسیریاب دارای دو پروسه در درون خود است :
یکی از آنها بسته ها را به محض ورود پردازش کرده و از طریق جدول مسیریابی یک خط خروجی
مناسب برای آنها انتخاب مینماید این پروسه همان forwarding است .
پروسه دیگر ، موظف به پرکردن و بهنگام سازی محتویات جدول مسیریابی است .این همان
جاییست که الگوریتمهای مسیریابی(Routing algorithm) به میدان میایند .
الگوریتمهای مسیریابی :
وظیفه اصلی لایه شبکه ،مسیریابی و هدایت بسته های داده از ماشین مبدا به ماشین مقصد است . در اکثر زیر شبکه ها ، بسته ها برای طی مسیر خود باید چندین گام (Hop) راه بپیمایند.الگوریتمی که این مسیرها را انتخاب میکند و همچنین ساختمان داده مورد استفاده ،یکی از زمینه های مهم در طراحی لایه شبکه محسوب میشود .
الگوریتمهای مسیریابی آن بخش از نرم افزار شبکه هستند که مسئولیت دارند در خصوص خط خروجی یک بسته ورودی که باید بر روی آن ارسال شود تصمیم گیری کنند. اگر در داخل یک زیر شبکه از روش دیتاگرام استفاده شده باشد این تصمیم گیری باید به ازای هر بسته دریافتی از نو تکرار شود . چرا که در هر لحظه ممکن است بهترین مسیر تغییر کند .اگر زیر شبکه از روش مدار مجازی استفاده کند ،تصمیم گیری در خصوص مسیرها فقط یکبار آنهم در هنگام تنظیم و ایجاد هر مدار مجازی جدید صورت میگیرد .
ویژگیهای یک الگوریتم مسیریابی :
1 : صحت عملکرد (correctness)
2 : سادگی (simplicity)
3 : قابلیت تحمل (Robustness)
4 : پایداری (stability)
5 : مساوات (Fairness)
6 : بهینگی (Optimality)
انواع الگوریتمهای مسیریابی :
الگوریتمهای مسیر یابی به دو رده کلی تقسیم بندی میشوند :
1 : static routing :
در این روش یک مسیر از قبل بصورت آفلاین محاسبه شده و در هنگام راه اندازی شبکه درون مسیریابها بارگذاری میشود. به این روال اغلب مسیریابی ایستا گفته میشود
2 : dynamic routing
در این روش، تصمیم گیری در خصوص مسیریابی بر اساس تغییرات توپولوژی و عموما ترافیک لحظه ای بصورت هوشمند انجام میگیرد .
الگوریتم سیل آسا (flooding)
یکی از الگوریتمهای ایستا میباشد . بر اساس آن هر بسته ورودی به یک مسیریاب ،بر روی
تمام خطوط خروجی (به استثنای خطی که بسته از طریق آن دریافت شده ) ارسال میشود
این فرایند بوضوح منجر به تولید تعداد بسیار زیادی بسته های تکراری (و در حقیقت بینهایت
بسته) خواهد شد مگر آنکه برای خاتمه آن سنجشی صورت گیرد . یکی از معیارهای سنجش
قراردادن Hop Counter میباشد که در هر گام یک واحد از آن کم میشود .
مزایا: در چنین حالتی این تضمین وجود دارد که اولآ هر بسته ی اطلاعاتی به تمام مسیرهای زیر شبکه خواهد رسید ، دوما سریعترین الگوریتم مسیر یابی است.
معایب : اگر قاعده بر این باشد که همه ی مسیریابها یک بسته ی نوع فراگیر تمام خروجی های خود ارسال کند ممکن است پس از چند لحظه خودشان آن بسته را دریافت کرده وچون مجددا آنرا روی خروجی های خود ارسال می کنند این عمل تا بینهایت ادامه خواهد یافت.
الگوریتم بردار فاصله (Distance Vector Routing)
شبکه های کامپیوتری مدرن ، عموما بجای استفاده از روشهای ایستا از روشهای پویا
(Dynamic) بهره میگیرند .زیرا الگوریتمهای ایستا بار فعلی شبکه را در محاسبات مربوط به
بهترین مسیرها دخالت نمیدهند .یکی از دو الگوریتم پویا که از رایجترین روشهای موجود هستند
الگوریتم مسیریابی بردار فاصله یا (ِِDVR) میباشد .
در این روش هر مسیریاب جدولی را در خود نگه میدارد(به عبارتی یک بردار را) که در ان بهترین
فاصله تا هر مسیریاب مقصد (یا بعبارتی کمترین هزینه رسیدن به هر مسیریاب در زیر شبکه) و
خطی که برای رسیدن به آن مقصد باید مورد استفاده قرار گیرد درج شده است
این جدول با مبادله اطلاعات بین مسیریابهای همسایه ، بهنگام سازی میشود
مزایا : مزیت این روش در حجم پردازش کم آن می باشد.
معایب : عیب آن کند بودن انتشار اطلاعات یا به عبارت دیگر عدم همگرایی سریع جداول مسیریابی در هنگام خرابی یک کانال ارتباطی می باشد.
== پروتکل های RIP، IGRP،IIGRP وBGP از DV استفاده می کنند ==
الگوریتم مسیریابی حالت لینک (Link State Routing)
دو مشکل اساسی منجر به زوال DVR شد :
1 : همگرایی بسیار زمانبر
2 : در نظر نگرفتن معیار پهنای باند در محاسبات انتخاب مسیر
بهمین دلایل با الگوریتم جدیدی بنام مسیریابی حالت لینک (LS) جایگزین شد
ایده اصلی LS را میتوان در پنج بند بیان کرد :
1 : همسایه های خود را شناسایی کرده و ادرسهای شبکه آنها را بدست میاورد
2 : تاخیر یا هزینه هریک از همسایه های خود را اندازه گیری میکند
3 : بسته ای میسازد و اطلاعاتی که از همسایه ها کسب کرده را در آن جاسازی میکند
4 : این بسته را برای تمام مسیریابهای دیگر میفرستد
5 : کوتاهترین مسیر رسیدن به دیگر مسیریابها را محاسبه مینماید
بدین ترتیب توپولوژی کامل زیرشبکه و تمام تاخیرها اندازه گیری شده و بین تمام مسیریابها توزیع میشود .
== پروتکل های OSPF ،IS-IS از الگوریتم های LS استفاده می کنند.==
مسیریابی سلسله مراتبی (Hierachial Routing)
با رشد اندازه شبکه ، جداول مسیریابی به همان اندازه رشد میکنند .جداول مسیریابی رو به
رشد نه تنها حافظه زیادی مصرف میکنند بلکه به زمان پردازش بیشتری برای پویش و جستجوی
این جدول و همچنین پهنای باند زیادتری برای ارسال بسته های LS (بسته های گزارش وضعیت
لینک) نیاز خواهد بود .و این دلایل کافیست تا مسیریاب مجبور به مسیریابی سلسله مراتبی
(همانند شبکه تلفن همراه) شود .
وقتی از مسیریابی سلسله مراتبی استفاده میشود مسیریابها به تعدادی منطقه (Region)
تقسیم میشوند هر مسیریاب تمام جزئیات منطقه خود و مسیرهای دقیق رسیدن به هر مقصد
در منطقه خود را میداند ولی چیزی در مورد ساختار داخلی مناطق دیگر نمیداند .و بر اساس
پروتکل های خاص خود با دیگر منطق ارتباط برقرار میکند.
مسیریابی مختلط (Hybrid)
این دسته از پرتکلها خصوصیاتی دارند که هم مشابه با پرتکلهای (بردار فاصله) وهم مشابه با
پرتوکلهای (حالت لینک) عمل میکنند .
شبکه های خودمختار(AS )
یک AS شامل گروهی از دستگاه هاست که به طور واحد مدیریت می شود. این گروه می تواند
شامل دستگاه های موجود در یک کمپانی و یا چند کمپانی باشد. ISPها خود نیز یک ASهستند.
یک AS دارای سیاست ها و خط مشی مربوط به خود در مسیریابی است که می تواند با دیگر ASها متفاوت باشد. این AS می تواند دارای یک شبکه باشد یا اینکه چندین شبکه که همه این شبکه ها دارای یک مدیر مشترک هستند.
مسیریابی درونی و بیرونی
به مسیریابی روترها در داخل یک AS، مسیریابی درونی( Interior Gateway Protocol)یا IGP
گفته می شود. برای مسیریابی درونی می توان از پروتکل های زیر استفاده کرد.
RIP
OSPF
IS_IS
IGRP
EIGRP
به مسیریابی بین روترهای مرزی ASها که باعث می شود اطلاعات بین AS ها ردوبدل شود مسیریابی برونی(EGP)گویند. BGP یک پروتکل مسیریابی برونی است.
نکته :
مسیریابی بسته های IP درون یک AS ،تابع پارامترهایی نظیر سرعت و قابل اعتماد بودن
الگوریتم مسیریابی میباشد . ولی مسیریابی بسته های اطلاعاتی بر روی شاهراه هایی که
شبکه های AS را به هم متصل کرده مسائلی کاملا متفاوت با مسیریابی در درون یک
شبکه خود مختار دارد. در مسیریابی بین شبکه های AS مسائلی نظیر امنیت، پرداخت حق
اشتراک و سیاست نیز می تواند در انتخاب بهترین مسیر دخیل باشد.
برای مشخص کردن یک AS از بین دیگر ASها آن ها را می توان به وسیله اعداد 0 تا 65535
شماره گذاری کرد. که به این اعداد ASN می گویند. البته از 64512 تا 65535 برای استفاده
اختصاصی کنار گذاشته شده است .سازمان IANA مسئول تعیین کردن این شماره ها
میباشد .
نکته :
در حال حاضر برای مسیریابی بین AS ها در اینترنت یا از default route که نوعی مسیریابی ایستا است، استفاده می کنیم یا از BGP.
پروتکل مسیریابی درونی RIP
) RIPبرگرفته شده از Routing Information Protocol) به معنی واقعی یک پروتکل
distance-vector است .پروتکل فوق در هر 30 ثانیه تمام اطلاعات موجود در جدول روتینگ
را برای تمامی اینترفیسهای فعال ارسال میکند . RIP صرفا از تعداد hop برای تعیین بهترین
مسیر استفاده به شبکه راه دور استفاده میکند حداکثر تعداد hop ها میتوتند عدد 15 را
داشته باشد و نسبت دهی عددی بالاتر از 15 به منزله غیرقابل دسترس بودن شبکه است.
RIP در شبکه های کوچک به خوبی کار میکند ولی برای شبکه های بزرگ که دارای لینک
ارتباطی WAN و تعداد بسیار زیادی روتر هستند کند و نامناسب میباشد .
در نسخه شماره یک RIP صرفا" از روتینگ classful استفاده می گردد . این بدان معنی
است که تمامی دستگاه های موجود در شبکه می بایست از subnet mask مشابهی
استفاده نمایند . محدودیت فوق به دلیل ماهیت ارسال اطلاعات بهنگام می باشد. در نسخه
شماره یک RIP ، اطلاعات بهنگام ارسال شامل اطلاعات subnet mask نمی باشند .
در RIP نسخه دو ، ویژگی جدیدی به نام روتینگ Prefix ارائه شده است که به کمک آن امکان ارسال اطلاعات subnet mask به همراه مسیرهای بهنگام شده فراهم می گردد . به این نوع روتینگ ، اصطلاحا" روتینگ classless گفته می شود .
پروتکل مسیریابی درونی RIP
RIP از سه نوع تایمر مختلف برای تنظیم کارآئی خود استفاده می نماید :
Route update timer ،
فاصله زمانی ارسال یک نسخه کامل از اطلاعات بهنگام روتینگ را مشخص می نماید . در بازه
زمانی فوق ، روتر یک نسخه کامل از اطلاعات موجود در جدول روتینگ خود را برای تمامی
همسایگان ارسال می نماید . این زمان معمولا" 30 ثانیه در نظر گرفته می شود .
Route invalid timer
مدت زمانی را مشخص می نماید که پس از سپری شدن آن ، روتر به این نتیجه خواهید رسید که یک مسیر غیرمعتبر است . این زمان معمولا" 180 ثانیه در نظر گرفته می شود و اگر یک روتر در
بازه زمانی فوق هیچگونه اطلاعات جدیدی را در خصوص یک مسیر خاص دریافت ننماید ، آن مسیر
را غیرمعتبر می نماید . در صورت تحقق چنین شرایطی ، روتر اقدام به ارسال اطلاعات بهنگام
برای تمامی همسایگان خود می نماید تا به آنها بگوید که مسیر غیرمعتبر است .
Route flush timer ،
مدت زمان بین غیرمعتبر اعلام شدن یک مسیر و حذف آن از جدول روتینگ را مشخص می نماید . این زمان معمولا" 240 ثانیه در نظر گرفته می شود . قبل از این که یک مسیر از جدول روتینگ حذف گردد ، روتر این موضوع را به اطلاع همسایگان خود می رساند . مقدار Route invalid timer می بایست کمتر از route flush timer باشد تا روتر زمان کافی جهت اطلاع به همسایگان خود را قبل از بهنگام سازی جدول در اختیار داشته باشد .
پروتکل مسیریابی درونی oSPF
OSPF مخفف OPEN SHORTEST FIRST PROTOCOL می باشد :
– دارای سرعت همگرایی بالایی هست .
– ا ز 6 مسیر با هزینه یکسان پشتیبانی می کند.
– این پروتکل فقط برای کار با IP طراحی شده است.
– از دسته پروتکل های LINK STATE می باشد.
– متریک OSPF بر اساس پهنای باند می باشد .
پروتکل OSPF برای شبکه های بزرگ بوجود آمد لذا این پروتکل شبکه را به قسمت های
مختلفی می شکند در واقع این پروتکل برای ساختارهای سلسله مراتبی طراحی شده است.
-OSPF از MULTICAST برای اعلام تغییرات استفاده می کند.
(exterior) پروتکل بیرونی BGP
پروتکل BGP مسئول انتقال اطلاعات و انتخاب بهترین مسیرهای منتهی به مقاصد مختلف در
محیط اینترنت می باشند. زمانی که دو AS اقدام به برقراری ارتباط با یکدیگر می کنند به طور
معمول از BGP برای تبادل اطلاعات routing استفاده می کنند.
در حال حاضر جدیدترین نسخه این پروتکل BGP4 است که این نسخه از ادرس دهی classless
پشتیبانی می کند.
این پروتکل برای ردوبدل کردن پیام های خود بین روترها از یک اتصال قابل اعتماد استفاده می کند
برای این کار از پروتکل TCP و پورت 179 استفاده می کند.
پروتکل BGP یک پروتکل مسیریابی (path vector protocol) است بدین معنی که هر روتر
اطلاعات کامل مسیر ،تا یک مقصد خاص را به روتر همسایه ی خود می فرستد
BGP از دو پروتکل مکمل EBGP و IBGP تشکیل شده است.
BGPپروتکل مکمل (Interior Border Gateway Protocol ) IBGP
ارسال اطلاعات به سمت اینترنت در شرایطی که تنها یک روتر در مرز بین سازمان و اینترنت قرار
دارد کاری بسیار اسان است. در این شرایط کافی است که روتر مرزی یک default route را از
طریق پروتکل مسیریابی درونی(IGP) برای دیگر دستگاه های داخلی ارسال کند تا آن ها تمامی
پیام های مقصد خارجی را برای روتر مرزی بفرستند.
اما در صورت استفاده از چندین روتر مختلف برای برقراری ارتباط با اینترنت مسائل مختلفی را باید مد نظر قرار داد. به منظور برطرف کردن مشکل احتمالی و همچنین بهره گیری از امکانات بیشتر می توان از IBGP در بین روترهای مرزی استفاده کرد.
در واقع (IBGP) برای این است که مسیریابها مرزی درون یک AS بتوانند اطلاعات خود را ردوبدل کنندو به این ترتیب همه مسیریابها از تمام راه های مرزی مطلع هستند و میتوانند بهترین مسیر خروجی را پیدا کنند .
BGPپروتکل مکمل (Exterior Border Gateway Protocol ) EBGP
زمانیکه روترهای همسایه در ASهای جداگانه باشند برای برقراری ارتباط و ردو بدل کردن اطلاعات مسیریابی ، از (EBGP) استقاده میشود .
هریک از routerهای BGP از سه جدول برای نگهداری اطلاعات پروتکل BGPاستفاده می کند
که این جدول ها به شرح زیر می باشند:
Routing table: شامل اطلاعاتی است که باید طی پیام Update مبادله شود.
Neighbor table: همسایه های روتر در این جدول نگهداری می شوند.
BGP table: اطلاعات دریافتی از بقیه مسیریاب ها و نیز دیگر path attributeها در این جدول ذخیره می شوند.
مسیریابی در شبکه های ویژه(Routing Ad Hoc Networks)
تاکنون روشهای مسیریابی در محیطهایی را که ماشینهای میزبان متحرکند ولی مسیریابها
ثابتند را بررسی کرده ایم . یک حالت استثنایی آن است که مسیریابها نیز خودشان متحرک
باشند .از چنین محیطهایی میتوان به موارد زیر اشاره کرد :
1 : وسائل نقلیه نظامی در صحنه نبرد بدون دسترسی به هیچگونه زیرساخت ارتباطی
2 : ناوگان دریایی بر روی دریاها
3 : نیروی امداد در شرایط اظطراری مثل سیل زلزله و … که کلیه زیرساختها نابود شده است
4 : گردهمایی افراد با کامپیوترهای کیفی در ناحیه ای بدون شبکه بیسیم 802.11
در تمام این موارد هرگره شامل یک مسیریاب و یک ماشین میزبان میباشد که اغلب هردوی
آنهابرروی یک ماشین قرار میگیرند .شبکه ای از این گره ها که در کنار هم قرار میگیرند
(MANET)یا شبکه ویژه نامیده میشوند .
مسیریابی در شبکه های ویژه(Routing Ad Hoc Networks)
آنچه شبکه های ویژه را از شبکه های سیمی متمایز میسازد آنست که تمام قوائد طبیعی در
خصوص توپولوژی ثابت ،همسایه های شناخته شده ثابت ،تناظر دائم بین موقعیت فیزیکی
ماشینها و مواردی از این قبیل در خصوص شبکه ویژه صادق نیست .
مسیریابها در رفت وآمد هستند و ممکن است در هر لحظه از محل جدید سر در بیاورند.
در یک شبکه سیمی هرگاه یک مسیریاب ، مسیری معتبر به برخی نقاط مقصد در شبکه
داشته باشد آن مسیر تا ابد معتبر خواهد بود(مگر اینکه در جایی از سیستم خرابی بوجود آید)
ولی در یک شبکه ویژه توپولوژی شبکه بطور دائم در حال تغییر است .لذا اعتبار مسیرها و
بهینگی آنها ،به ناگاه و بی هیچ هشدار قبلی تغییر میکند .
آشکار است با چنین وضعیتی ،مسیریابی در شبکه های ویژه کاملا متفاوت از شبکه های ثابت میباشد .
الگوریتم ADOVبرای شبکه های MANET
گونه متعددی از الگوریتمهای مسیریابی برای شبکه های ویژه پیشنهاد شده است .از جالبترین
آنها،الگوریتم مسیریابی ADOV است .(Ad Hoc On-demand distance Vector)
این الگوریتم گونه ای از الگوریتمهای بردار فاصله است که برای کار در محیطهای متحرک تطبیق
داده شده ودر آن پهنای باند محدود و عمر کم باطری ماشینها در نظر گرفته شده است .
یکی دیگر ار ویژگیهای این روش آنست که الگوریتم بر حسب تقاضا (on-demand)عمل میکند
بدین معنی که مسیر رسیدن به برخی از نقاط مقصد فقط وقتی تعیین میشود که کسی
بخواهدبسته ای را بدان مقصد بفرستد
از دیگر پروتکل های شبکه های MANET میتوان به DSR و DSDV و OLSR اشاره کرد .
by : davood pourkhorsandi
کشف مسیر در الگوریتم AODV
در پروسه کشف مسیر ،اگر دو ماشین بتوانند از طریق سیستم رادیویی خود مستقیما با یکدیگر ارتباط برقرار کنند میگوییم این دو گره بهم متصلند .از انجاییکه امکان دارد یکی از این دو ماشین فرستنده قدرتمندتری نسبت به دیگری داشته باشد لذا این امکان وجود دارد که ارتباط از A به Bبرقرار باشد ولی باعکس میسر نباشد .
همچنین باید به این نقطه اشاره کرد که هرگاه دو گره در برد رادیویی یکدیگر باشند ،تضمینی وجود ندارد که ارتباط آنها برقرار باشد ممکن است بین آنها ساختمان تپه .. وجود داشته یاشد که مانع ارتباط شود .
A
D
B
C
I
E
G
F
H
کشف مسیر در الگوریتم AODV
ساخته و آنرا منتشر میکند .Route Request جهت مسیریابی ،گره مبدا یک بسته خام بنام
این بسته شامل آدرس مبدا و آدرس مقصد است و مشخص میکند چه کسی در جستجوی
چه کسی است .(عمومااز ادرسهای Ip استفاده میشود) .
این بسته همچنین حاوی Request ID است این شناسه در حقیقت یک شمارنده محلی
است که در هرگره وجود دارد و هرگاه یک بسته Route Request منتشر گردید یک واحد به
آن اضافه میشود . ترکیب آدرس مبدا و فیلد Request ID هویت Route Request را بصورت
منحصر بفرد تععین کرده و بدین ترتیب گره ها قادرند بسته های که احتمالا بصورت تکراری
دریافت میشوند را تشخیص داده و حذف کنند .
نگهداری مسیر (Rout maintenance)
از آنجاییکه گره ها میتوانند جابجا شده یا کلا خاموش شوندلذا توپولوژی شبکه گاه به گاه تغییر میکند اگر گرهی خاموش شود گره های بعدی نخواهند فهمید مسیری که برای رسیدن به گره مذکور بود دیگر برقرار نیست.این الگوریتم باید بتواند این مسئله را حل کند .
هرگره در شبکه بطور متناوب (Hello message) منتشر میکند . انتظار میرود که همسایه ها به این پیغام پاسخ دهند.اگر پاسخی برنگشت ، منتشر کننده پیام آگاه میشود که همسایه او از بردش خارج شده است و ارتباط برقرار نیست .از این اطلاعات میتوان برای پاک کردن مسیرهایی که کار نمیکنند بهره گرفت .
از دیگر پروتکل ها میتوان به DSR –DSDV – OLSR اشاره کرد .
by : davood pourkhorsandi -Dec 2012
The End