پروژه بررسی الگوریتم های مسیر یابی در 140 صفحه ورد قابل ویرایش
مقدمه الگوریتمهای مسیریابی
در هریک از سه قرم گذشته فناوری خاصی رونق داشته باشد قرن هجدهم زمان توسعه سیستم های مکانیکی بزرگ به همراه انقلاب صنعتی بود. قرن نوزدهم عصر موتور بخار بود. قرن بیستم زمان جمع آو ری ،پردازش ، و توزیع اطلاعات بودو در بین سایر پیشرفت ها ،شاهد نصب شبکه های جهانی تلفن، اختراع رادیو و تلویزیون ، تولید و رشد بی سایقه صنعت کامپیوتر و پرتاب ماهواره های ارتباطی بوده ایم.
با پیشرفت فناوری این موارد د رحال همگرایی است و تفاوت هایی بین جمع آوری ، انتثال ذخیره و پردازش اطلاعات به شدت در حال محو شدن است سازمان هایی با صدها شعبه در نقاط مختلف جغرافیایی ،ب فشردن کلید وضعیت فعلی را حتی در دورترین نقاط بررسی می کنند. با افزایش فدرت جمع آوری، پردازش و توزیع اطلاعات، تقاضای پردازش اطلاعات پیچیده تر نیز افزایش می یابد
-
الگوریتمهای مسیر یابی
وظیفه اصلی لایه شبکه ، هدایت بسته‌ها از ماشین منبع به ماشین مقصد است در اغلب زیر شبکه‌ها ، بسته‌ها باید چند جهش انجام دهند. تا به مقصد برسند. برای شبکه‌های پخشی،استثنایی وجود دارد، وای در اینجا نیز اگر منبع و مقصد در یک شبکه نباشد مسیر یابی مشکل محسوب می‌شود. الگورتیم هایی که مسیرها و ساختمان داده‌های مربوط به آن را انتخاب میکنند، موضوع مهم را طراحی لایه شبکه اند.
الگوریتم مسیر یابی بخشی از نرم افزار لایه شبکه است که تعیین میکند بسته ورودی باید به کدام خط خروجی منتقل شود. اگر زیر شبکه از داده‌ها گرام‌ها استفاده کند، این تصمیم گیری دوباره باید برای هر بسته ورودی تکرار شود ،چون تا آن موقع امکان دارد بهترین مسیر، تغییر کند اگر زیر شبکه از مدارهای مجازی استفاده کند ، تصمیمات مسیر یابی وقتی اتخاذ میشوند که مدار مجازی جدیدی استفاده گردد. از آن پس ، بسته‌های داده‌ها فقط از مسیر ایجاد شده قبلی منتقل میشوند.حالت دوم گاهی مسیر یابی تماس دارد ، زیرا مسیر در طول مدت تمسا کاربر باقی می‌ماند ( مثل کار کردن با پایانه یا انتقال فایل ) صرف نظر از این که آیا مسیرها برای هر بسته به طور مستقل انتخاب میشوند یا فقط وقتی که اتصال جدیدی برقرار می‌شود انتخاب می‌گردند، خواصی وجود دارند. که در الگوریتمهای مسیر یابی مطلوب‌اند صحت ، سهولت تحمل عیب، پایداری ، عدالت و بهینگی صخت وسهولت نیازی به توضیح ندارند، اما نیاز به تحمل عیب چندان روشن نیست. انتظار می‌رود که شبکه‌های بزرگ ، سال‌ها بدون عیب کلی سیستم به کار خود ادامه دهند. در این مدت ممکن است اشکالات سخت افزاری و نرم افزاری گوناگونی به وجود آید. میزبان‌ها مسیر یاب‌ها مسیر یاب‌ها بدون نیاز به توقف انجام انجام کارها در مسیر یاب‌ها و راه اندازی مجدد شبکه در هر بار متلاشی شدن مسیریاباز عهده تغییرات در توپولوژی و ترافیک برآید.
پایداری نیز برای الگوریتم مسیر یابی هدف مهمی است. الگوریتمهای مسیر یابی وجود دارند که هرگز وجود دارندکه هرگز به حالت پایداری نمی‌رسند.مدت زمان اجرای آن بی تاثیر است عدالت وبهینگی مممکن است ساده به نظر می‌رسند یقیینا کسی با آن مخالف نیست. اماهمان طور که روشن است اهداف متناقضی دارند به عنوان مثال از این تناقض ، شکل 1 را بینید. فرض کنید ترافیک کافی بین A و ش، بین B,B وبین C, C وجود دارد تا پیوندهای افقی را اشباع نماید برای بیشینه کردن کل جریان ترافیک X, X باید کاملا از بین برود. متاسفانه از نظر X وX عادلانه نیست بدیهی است که توافقی بین کارایی کلی و عدالت اتصال‌های منفرد لازم است.
قبل از اینکه به متوزان کردن عدالت وبهینگی بپردازیم . باید تصمیم بگیریم که چه چیزی را بهینه کنیم . بدیهی است تاخیر بسته باید کمینه شود ولی توان شبکه باید بیشینه شود. علاوه براین این دو هدف نیز با هم تضاد دارند، زیرا عملکرد هر سیستم صف بندی در حد ظرفیت تاخیر صف بندی را زیاد ی کند. اغلب شبکه‌ها سعی میکنند تعدداد جهشهای بسته‌های را کمینه نمایند زیرا کاهش تعدادجهش موجب بهبود تاخیر و نیزکاهش میزان پهنای باند مصرفی است که منجر به بهبود توان عملیاتی می‌شود.
الگوریتمهای مسیر یابی درکاربرد
در forword جستجوی الگوریتم ، عملکرد تمرکز یافته مناسب تری ادعا کرده می شود در back ward جستجوی الگوریتم ها می توانست فقط ارزش منطقه یا نیم منطقه اطلاعاتی پیروی شده را که بلافاصله را از node های مجاور است را اداره کند.
ارزش پارامتر کاربردی در مسیر یابی الگوریتم ها ممکن است یک پارامترهای جهانی گوناگونی را بازتاب کند که شامل مخابرات واقعی تاخیری و فضای میانگیر مورد نیاز بوسیله لینگ drivel می باشد همچنین آن ممکن است در فرمول محاسبه ارزش کاربر ملین شده استفاده گردد و.در برخی شبکه های کاربردی در ارزش (قیمت) یک لینگ یک کارکرد دینامیکی میزان و ماهیت ترافیک بر روی شبکه وجود داردوبنابراین ان مطلوب در دوبار حساب کردن جداول مسیریابی در فواصل مناسب است .و ترافیک داده ها در گردآوری بالا در داده های مورد نیاز برای جدول محاسبه مجدد و انتقال نتایج به nodeها (گره ها ) که می توانند به تراکم بیشتر منتج می شود وارد گردید آن بایستی همچنین شود که هر دو جدول مسیر یابی الگوریتم یک پیچیدگی را دارند.
پروتوکل اینترنت :
در پروتوکل اینترنت ip)) یک پروتکل جهت دار داده بوسیله منبع و مقصد hot ها برای مکاتبه داده ای عبوری یک packet –switched inerntwork به کار برده می شود.
داده اه دریک ip intrenrtwork در قالبهای ارجاعی مثل بسته ها یا داتا گرام ها در دوره های بطور اساسی در ip مترداف هستند فرستاده می شوند بویژه درIP هیچ SETUP نیاز نمی شود. قبل از اینکه یک HOST مترداف هستند فرستاده می شوند بویژه در تلاش برای فرستادن بسته ها به یک HOST کنند آن قبلا کنند آن قبلا ابلاغ شده است. در پروتوکل اینترنت IP یک سرویس داتاگرام تا مطئمن ایجاد شد (همچنین بهترین تلاش نامیده شد) آن تقریبا گارانتی در اطراف جعبه ایجاد می کند بسته ممکن است آسیب دیده برسد آن ممکن نادست و در هم برهم گردد مقایسه شد با دیگر بسته های ارسالی در هر دو HOST مشابه آن ممکن است دو نسخه ای المثنی گرددویا کاملا رها شده وبیفتد اگر یک کاربرد نیاز به اعتبار داشته باشد ، آن توسط دیگر وسایل اماده گردیده می شود.
packet switches یا مسیر یابهای internetwork ، داتاگرام های forward IP از میان لایه شبکه های بهم متصل شدندو در فقدان تحویل برخی گارانتی ها ، طرحی از packet switches در نظر گرفته می شود. که بسیار ساده تر ساخته شده است.( توضیح اینکه اگر شبکه سقوط ،نگارش دوباره یا در غیر اینصورت بسیاری از بسته ها آسیب ببیند در اجرا دیده شده بوسیله کاربر، سست خواهند شد . بنابراین اغلب عناصرشبکه به سختی تلاش می کنند این چیزها – از این پس در دوره بهترین تلاش انجام نشود.)
ip عنصر متعارف و معمول در اینترنت عمومی امروزه ،پیدا شد.پروتوکل رایج وعمومی ترین لایه شبکه در استفاده امروزه ipv4 است این نسخه پروتوکل ، نسخه 4 را انتقال داده میکندو ipv6 جانشین ipv4 در نظر گرفته می شود در اینترنت تدریجا آدرسها را تمام می کند و ipv6 ، منبع 128-bit و عنوان مقصدها رادارد ، بیشتر ازعناوین آدرس ipv4 یا منبع 32-bit عناوین فراهم میکند. نسخه 5برای یک جریان پروتوکل های آزمایشی تعیین کرده شده اند دیگر شماره نسخه معمولا برای پروتکل های آزمایشی تعیین کرده شده اند اما بطور وسیعی استفاده نشده اند. IPaddressing و مسیر یابی : شاید بیشترین نمودهای مجموعه IP مسیر یابی و آدرس های هستد addrerring به اینکه چگونه انتهای hot ها به صورت IPaddresses تعیین می گردد و اینکه چگونه و اینکه چگونه زیر شبکه های addresses تقسیم کرده شوند و به یکدیگر طبقه بندی می کردند تخصص داده می شوند مسیر یابی ip بوسیله تمام host ها انجام گردیده می شود اما بطور مهمترین بوسیله مسیر یابل interetwork که به طور نمونه هم در مدخل درونی پروتوکل ها IGPS , و هم در مدخل خروجی پروتکل ها EGPS به کار می روند که کمک به ساختن تصمیمات Forwarding داتاگرام IP از میان شبکه های اتصالی IP می کنند