محبوبترینها
نمایش جنگ دینامیت شو در تهران [از بیوگرافی میلاد صالح پور تا خرید بلیط]
9 روش جرم گیری ماشین لباسشویی سامسونگ برای از بین بردن بوی بد
ساندویچ پانل: بهترین گزینه برای ساخت و ساز سریع
خرید بیمه، استعلام و مقایسه انواع بیمه درمان ✅?
پروازهای مشهد به دبی چه زمانی ارزان می‌شوند؟
تجربه غذاهای فرانسوی در قلب پاریس بهترین رستوران‌ها و کافه‌ها
دلایل زنگ زدن فلزات و روش های جلوگیری از آن
خرید بلیط چارتر هواپیمایی ماهان _ ماهان گشت
سیگنال در ترید چیست؟ بررسی انواع سیگنال در ترید
بهترین هدیه تولد برای متولدین زمستان: هدیه‌های کاربردی برای روزهای سرد
در خرید پارچه برزنتی به چه نکاتی باید توجه کنیم؟
صفحه اول
آرشیو مطالب
ورود/عضویت
هواشناسی
قیمت طلا سکه و ارز
قیمت خودرو
مطالب در سایت شما
تبادل لینک
ارتباط با ما
مطالب سایت سرگرمی سبک زندگی سینما و تلویزیون فرهنگ و هنر پزشکی و سلامت اجتماع و خانواده تصویری دین و اندیشه ورزش اقتصادی سیاسی حوادث علم و فناوری سایتهای دانلود گوناگون
مطالب سایت سرگرمی سبک زندگی سینما و تلویزیون فرهنگ و هنر پزشکی و سلامت اجتماع و خانواده تصویری دین و اندیشه ورزش اقتصادی سیاسی حوادث علم و فناوری سایتهای دانلود گوناگون
آمار وبسایت
تعداد کل بازدیدها :
1827582621
الگوریتمهای مسیریابی در شبکه -
واضح آرشیو وب فارسی:سایت ریسک: الگوریتمهای مسیریابی در شبکه Ashiyane 12 اسفند 1384, 01:56اصول عملكرد روترها از الگوريتمهاي مسيريابي،براي يافتن بهترين مسير تا مقصد استفاده مينمايند هنگامي آه ما در مورد بهترين مسير صحبت ميكنيم،پارامترهايي همانند تعداد hop ها ( مسيري آه يك بسته از يك روتر ديگر در شبكه منتقل ميشود ). زمان تغيير و هزينه ارتباطي ارسال بسته را در نظر ميگيريم . مبتني بر اينكه روترها چگونه اطلاعاتي در مورد ساختار يك شبكه جمع آوري مينمايند و نيز تحليل آنها از اطلاعات براي تعيين بهترين مسير،ما دو الگوريتم مسير يابي اصلي را در اختيار داريم : الگوريتم مسير يابي عمومي و الگوريتمهاي مسير يابي غير متمرآز . در الگوريتم هاي مسير يابي غير متمرآز،هر روتر اطلاعاتي در مورد روترهايي آه مستقيما به آنها متصل ميباشند در اختيار دارد . در اين روش هر روتر در مورد همه روتر DV ( هاي موجود در شبكه،اطلاعات در اختيار ندارد . اين الگوريتمها تحت نام الگوريتمهاي معروف هستند . در الگوريتمهاي مسيريابي عمومي،هر روتر اطلاعات (distance vector آاملي در مورد همه روترهاي ديگر شبكه و نيز وضعيت ترافيك شبكه در اختيار دارد . اين الگوريتمها تحت نام الگوريتمهاي LS(Link state) معروف هستند . ما در ادامه مقاله به بررسي الگوريتمهاي LS ميپردازيم . LS الگوريتمهاي در الگوريتمهاي LS ،هر روتر ميبايست مراحل ذيل را به انجام رساند : روترهاي را آه به لحاظ فيزيكي به آنها متصل ميباشد را شناسايي نموده و هنگامي آه شروع به آار ميكند آدرسهاي IP آنها بدست آورد . اين روتر ابتدا يك بسته HELLO را روي شبكه ارسال ميكند . هر روتري آه اين بسته را دريافت ميكند از طريق يك پيام آه داراي آدرس IP خود اين روتر ميباشد به پيام HELLO پاسخ ميدهد . ------------------------------------------------------------------------------------------------------- زمان تاخير مربوط به روترهاي مجاور را اندازه گيري نمايد ( يا هر پارامتر مهم ديگري از شبكه همانند ترافيك متوسط ) براي انجام اين آار ،روترها بسته هاي echo را روي شبكه ارسال ميكنند . هر روتري آه اين بسته ها را دريافت ميكند با يك بسته echo reply به آن پاسخ ميدهد . با تقسيم زمان مسير رفت و برگشت به دو،روترها ميتوانند زمان تاخير را محاسبه آنند .( زمان مسير رفت و برگشت،سنجشي از تاخير فعلي روي يك شبكه ميباشد ) توجه داشته باشيد آه اين زمان شامل زمانهاي ارسال و پردازش ميباشد . اطلاعات خود را در مورد شبكه،براي استفاده ساير روترها منتشر نموده و اطلاعات روترهاي ديگر را دريافت آند . در اين مرحله همه روترها دانش خود را با روتر هاي ديگر به اشتراك گذاشته و اطلاعات مربوط به شبكه را با يكديگر مبادله ميكنند . با اين روش هر روتر ميتواند در مورد ساختار و وضعيت شبكه اطلاعات آافي بدست آورد . با استفاده از اين الگوريتم مناسب،بهترين مسير بين هر دو گره از شبكه راشناسايي آند . در اين مرحله،روترها بهترين مسير تا هر گره را انتخاب ميكنند . آنها اين آار را با استفاده از يك الگوريتم همانند الگوريتم آوتاهترين مسير Dijkstra انجام ميدهند . در اين الگوريتم،يك روتر مبتني بر اطلاعاتي آه از ساير روترها جمع آوري نموده است،گرافي از شبكه را ايجاد مينمايد . اين گراف مكان روترهاي موجود در شبكه و نقاط پيوند آنها را به يكديگر نشان ميدهد . هر پيوند با يك شماره به نام Cost يا weight مشخص ميشود . اين شماره تابعي از زمان تاخير،متوسط ترافيك و گاهي اوقات تعداد hop هاي بين گره ها ميباشد . براي مثال اگر دو پيوند بين يك گره و مقصد وجود داشته باشد،روتر پيوندي با آمترين Weight را انتخاب ميكند . الگوريتم Dijkstra داراي مراحل ذيل ميباشد : روتر گرافي از شبكه را ايجاد نموده و گره هاي منبع و مقصد ( براي مثال V1 و (V2 را شناسايي ميكند . سپس يك ماتريس به نام ماتريس adjacency را ميسازد . در اين Vj وVi ،وزن يك پيوند بين [i,j] ميباشد . براي مثال Weight ماتريس يك مختصه مبين ميباشد . در صورتي آه هيچ پيوند مستقيمي بين Vi و Vj وجود نداشته باشد اين وزن ( ويت ) بصورت infinity در نظر گرفته ميشود . روتر يك مجموعه رآورد وضعيت را براي هر گره روي شبكه ايجاد مينمايد اين رآورد داراي سه فيلد ميباشد : فيلد :Predecessor اولين فيلدي آه گره قبلي را نشان ميدهد . فيلد :Length فيلد دوم آه جمع وزنهاي از منبع تا آن گره را نشان ميدهد . فيلد :Label آخرين فيلد آه وضعيت گره را نشان ميدهد . هر گره ميتواند داراي يك مود permanent يا tentative: وضعيت باشد روتر،پارامترهاي مجموعه رآورد وضعيت براي همه گره ها را آماده سازي اوليه نموده و طول آنها را در حالت infinity و Label آن را در وضعيت tentative قرار ميدهد . روتر،يك گره T را ايجاد ميكند . براي مثال اگر V1 ميبايست گره T منبع باشد،روتر برچسب V1 را در وضعيت permanent قرار ميدهد . هنگامي آه يك Label به حالت agent در واقع يك T تغيير ميكند ديگر هرگز تغيير نخواهد آرد . يك گره permanent ميباشد . T را آه مستقيما به گره Tentative روتر،مجموع رآورد وضعيت مربوط به همه گره هاي منبع متصل هستند،روز آمد مينمايد . روتر همه گره هاي Tentative را بررسي نموده و گرهاي را آه وزن آن تا V1 آمترين مقدار را دارد انتخاب ميكند . سپس اين گره،گره T مقصد خواهد بود اگر اين گره، V2 نباشد ( گره مقصد ) روتر به مرحله 5 باز ميگردد . اگر اين گره V2 باشد،روتر گره قبلي آن را از مجموع رآورد وضعيت استخراج نموده و اين آار را انجام ميدهد تا به V1 برسد،اين فرست از گره ها،بهترين مسير از V1 تا V2 را نشان ميدهد . اين مراحل بصورت يك فلوچارت در شكل نشان داده شده است ما از اين الگوريتم بعنوان يك مثال در ادامه مقاله استفاده خواهيم نمود . مثالDijkstraالگوريتم در اينجا ما ميخواهيم بهترين مسير بين گره هاي A و E را پيدا آنيم همانطور آه ميبينيد 6 مسير بين A و E وجود دارد .) ACDBE ، ABDCE ، ACDE ، ABDE ، ACE ، (ABE و واضح است آه ABDE بهترين مسير ميباشد زيرا آمترين وزن را دارد اما هميشه به اين سادگي نيست و برخي موارد پيچيده وجود دارد آه در آن ما مجبوريم از الگوريتم هايي براي يافتن بهترين مسير استفاده آنيم . همانطور آه در تصوير ذيل مشاهده ميكنيد،گره منبع (A) بعنوان گره T انتخواب شده و بنابراين برچسب آن، Permanent ميباشد . ( ما گره هاي Permanent را با دايره هاي تو پر و گره هاي T را با يك پيكان نشان ميدهيم ) در اين مرحله شما ميبينيد آه مجموع رآورد وضعيت گره هاي Tentative آه مستقيما به گره T (C) ، B متصل شده اند،تغيير يافته است . همچنين از آنجايي آه گره B آمترين وزن را دارد،بعنوان گره T انتخاب شده و برچسب آن به حالت Permanent تغيير آرده است . Tentative در اين مرحله همانند مرحله قبل دو مجموعه رآورد وضعيت گره هايي آه داراي اتصال مستقيم به گره T ميباشد E) ، (D تغيير آرده است . همچنين از آنجايي آه Permanent انتخاب شده و برچسب آن به وضعيت T وزن آمتري دارد،بعنوان گره Dگره تغيير آرده است . در اين مرحله ما هيچ گره Tentative نداريم بنابراين فقط گره T بعدي را شناسايي ميكنيم . از آنجايي آه E داراي آمترين وزن ميباشد بعنوان گره T انتخاب ميشود . گره مقصد بوده بنابر اين آار ما در اينجا تمام ميشود . اآنون ما آار شناسايي مسير را E به انتها رسانده ايم . گره قبلي E گره D ،گره B ميباشد و گره قبلي B ،گره A ميباشد . بنابر اين بهترين مسير ABDE است در اين مورد وزن آل مسير، 4(1+2+1) ميباشد . با وجودي آه اين الگوريتم بخوبي آار ميكند اما آنقدر پيچيده است آه زمان پردازش آن براي روتر طولاني بوده و راندمان شبكه را آاهش ميدهد . همچنين اگر يك روتر اطلاعات غلطي را به روترهاي ديگر بدهد،همه تصميمات مسير يابي نادرست خواهد بود . DVالگوريتمهاي الگوريتمهاي DV با نامهاي الگوريتمهاي مسيريابي Bellman-Ford و ford-fulkerson نيز ياد ميشوند . در اين الگوريتمها،هر روتر داراي يك جدول مسيريابي ميباشد آه بهترين مسير تا هر مقصد را نشان ميدهد . يك گراف معمولي و جدول مسيريابي مربوط به روتر . در شكل زير نشان داده شده است G در الگوريتمهاي DV ،هر روتر ميبايست مراحل ذيل را انجام دهد : وزن لينكهاي مستقيما متصل به آن را اندازه گرفته و اين اطلاعات را در جدول خود ذخيره آند . در يك دوره زماني خواص،روتر جدول خود را به روترهاي مجاور ارسال نموده و جدول مسيريابي هر يك از روترهاي مجاور خود را دريافت ميكند . مبتني بر اطلاعات بدست آمده از جداول مسيريابي روترهاي مجاور،جدول خود را روز آمدسازي مينمايد . Count to infinity ،مشكلDV يكي از مهمترين مشكلات،هنگام آار با الگوريتمهاي اجازه بدهيد اين مشكل را با ذآر يك مثال روشن آنيم . همانطور آه در قسمت ذيل نشان داده شده است يك شبكه را در ذهن خود تصور آنيد . همانطور آه در اين جدول ميبينيد،فقط يك پيوند بين A و ساير بخشهاي شبكه وجود دارد . در اينجا شما ميتوانيد،اين گراف و جدول مسيريابي همه گره ها را مشاهده آنيد : D C B A 3,D 2,B 1,A 0,- A 3,D 2,C 0,- 1,B B 1,C 0,- 1,C 2,B C 0,- 1,D 2,C 3,B D اآنون تصور آنيد آه پيوند بين A و B قطع شود . در اين هنگام، B جدول خود را تصحيح ميكند بعد از يك مدت زمان خاص،روترها جداول خود را مبادله نموده و بنابراين B جدول B و A نميداند چه اتفاقي براي پيوند بين C را دريافت ميكند . از آنجايي آه Cمسيريابي رخ داده است اين اطلاعات را حفظ ميكند B. اين جدول را دريافت نموده و فكر ميكند آه infinity وجود دارد،بنابراين جدول خود را تصحيح نموده مقدار A وC يك پيوند جداگانه بين را به 3 تغيير ميدهد . به همين شكل دوباره روترها جداول خود را مبادله ميكنند . هنگامي آه C ،جدول مسيريابي B را دريافت ميكند،مشاهده ميكنيد آه B وزن پيوند خود تا A را از 1 به 3 تغيير داده است،بنابراين C ،جدول خود را روزآمد نموده و وزن پيوند خود تا A را به 4 تغيير ميدهد . اين پروسه تكرار ميشود تا همه گره ها وزن پيوند خود را تا A در وضعيت infinity قرار دهند . اين وضعيت در جدول زير نشان داده شده است . D C B 3,C 2,B ∞,A Sum of weight to A after link cut 3,C 2,B 3,C Sum of weight to B after 1st updating 3,C 4,B 3,C Sum of weight to A after 2nd updating 5,C 4,B 5,C Sum of weight to A after 3rd updating 5,C 6,B 5,C Sum of weight to A after 4th updating 7,C 6,B 7,C Sum of weight to A after 5th updating در اين روش متخصصين ميگويند،الگوريتمهاي DV داراي يك سرعت همگرايي پايين هستند . يك روش براي حل اين مشكل در مورد روترها،ارسال اطلاعات فقط به روترهايي ميباشد آه داراي پيوند انحصاري تا مقصد نيستند . براي مثال در اين مورد، C نميبايست هيچ اطلاعاتي را به گره B در مورد A ارسال آند زيرا B فقط يك مسير تا A را در اختيار دارد . مسيريابي سلسله مراتبي همانطور آه شما ميبينيد،در هر دو الگوريتم LS و DV ،هر روتر مجبور به ذخيره نمودن اطلاعات مربوط به روترهاي ديگر ميباشد . هنگامي آه اندازه شبكه رشد ميكند،تعداد روترهاي شبكه افزايش مي يابد در نتيجه اندازه جداول مسيريابي نيز افزايش مي يابد و روترها نميوانند ترافيك شبكه را به طور موثر آنترل آنند . ما از مسيريابي سلسله مراتبي براي برطرف آردن اين مشكل استفاده ميكنيم . اجازه بدهيد اين موضوع با ذآر يك مثال روشن آنيم :ما نشان داده شده در ذيل،هر گره از شبكه مجبور به نگهداري يك جدول مسيريابي با 17 رآورد ميباشد . در اينجا يك گراف معمولي و جدول مسيريابي مربوط به A ارائه شده است . Weight Line Destination - - A 1 B B 1 C C 2 B D 3 B E 3 B F 4 B G 5 B H 5 C I J 6 C J 5 C K 4 C L 4 C M 3 C N 4 C O 2 C P 3 C Q در مسيريابي سلسله مراتبي،روترها در گروههايي به نام regions طبقه بندي ميشوند . هر روتر داراي اطلاعاتي فقط در مورد روترهايي آه در region آنها قرار دارد در اختيار داشته و هيچ گونه اطلاعاتي در مورد region هاي ديگر ندارند . در اين مثال ما شبكه خود را به پنج region تقسيم ميكنيم . اگر A بخواهد بسته ها را به هر روتر در region2 ارسال آند،آنها را به B ارسال ميكند و الي آخر . در اين نوع مسيريابي،جداول را ميتوان خلاصه نمود بنابراين راندمان شبكه بهبود مييابد . مثال بالا مسيريابي سلسله مراتبي دو سطحي را نشان ميدهد همچنين ميتوان مسيريابي سلسله مراتبي 3 سطحي،شبكه به تعدادي آلاستر تقسيم بندي ميشود . هر آلاستر متشكل از تعدادي region و هر region داراي تعدادي روتر ميباشد . مسيريابي سلسله مراتبي به طور وسيعي در مسيريابي اينترنت مورد استفاده قرار ميگيرد و استفاده از چندين پروتكل مسيريابي را ممكن مي سازد . Ashiyane 12 اسفند 1384, 02:07؟؟؟؟ dark-man 12 اسفند 1384, 08:42فکر نکنم چیزی بفهمید شاید حذفش کنم فکر نکنم این لحن حرف زدن قشنگ باشه ... توجه داشته باش اینجا کسایی هستن که خیلی خیلی بیشتر از این چیزهایی که تو فکر کنی بلدند ولی نه پز می دهند و نه فخر می فروشند و ........ از قدیم گفتن درخت هر چی بارش بیشتر ...افتاده تر BeHnAm_akb 12 اسفند 1384, 09:17دوست عزیز فکر نمی کنم تو بحث شبکه routing خیلی بحث پیشرفته ایی باشه ! اگر هم کسی چیزی نفهمید ممکنه به خاطر نوع متن باشه ولی در کل زیاد متنشم خیلی بد نبود. به هر حال ممنون Ashiyane 12 اسفند 1384, 09:30عزیز من نه اینکه کسی نفهمیده باشه من طرز نوشتن رو گفتم (اگر منظور من رو بد فهمیدید از همگی معظرت می خوام)
این صفحه را در گوگل محبوب کنید
[ارسال شده از: سایت ریسک]
[مشاهده در: www.ri3k.eu]
[تعداد بازديد از اين مطلب: 4226]
-
گوناگون
پربازدیدترینها