به نام خالق هستی

این فایل ورد و آماده پرینت میباشد

موضوع گزارش کارآموزی : الگوریتم های مسیریابی

فهرست مطالب:

مقدمه الگوریتمهای مسیریابی
الگوریتمهای مسیر یابی
اصل بهینگی
مسیر یابی کوتاه ترین مسیر
الگوریتم غرق کردن
مسیر یابی بردار فاصله
مسئله بی نهایت گرایی
مسیر یابی حالت پیوند
کسب اطلاعاتی راجع به همسایه‌ها
اندازه گیری هزینه خط
ساخت  بسته‌های حالت پیوند
توزیع بسته‌های حالت پیوند
محاسبه مسیرهای جدید
مسیریابی سلسله مراتبی
مسیریابی پخشی
مسیریابی چند پخشی
مسیریابی برای میزبانهای سیار
مسیریابی در شبکه‌های موقتی
کشف مسیر
نگهداری مسیر
جست و جوی گره در شبکه‌های نظیر به نظیر
الگوریتم کنترل ازدحام
اصول کلی کنترل ازدحام
سیاست‌های جلوگیری از ازدحام
کنترل ازدحام در زیرشبکه‌های مدار مجازی
کنترل ازدحام در زیرشبکه‌های داده گرام
تخلیه بار
بیت اخطار
تشخیص زودرس تصادفی
کنترل لرزش
‌مسیر یابی منبع دینامیک (۱)
مشکل مسیر یابی
یافتن انبوهی ازکوتاهترین راهها
مسیر یابی نیاز به مسیر یابی
Forward در جستجوی الگوریتم
الگوریتمهای مسیر یابی درکاربرد
مسیر یابی قائم
مسیر یاب peer to peer
مسیر یابی Guntella
رده بندی یک به یک الگوریتم های مسیریابی
مسیریابی adaptive از Biocrawler

مقدمه الگوريتمهاي مسيريابي

در هريك از سه قرم گذشته فناوري خاصي رونق داشته باشد قرن هجدهم زمان توسعه سيستم هاي مكانيكي بزرگ به همراه  انقلاب صنعتي بود. قرن نوزدهم عصر موتور بخار بود. قرن بيستم زمان جمع آو ري ،پردازش ، و توزيع اطلاعات بودو در بين ساير پيشرفت ها ،شاهد نصب شبكه هاي جهاني تلفن، اختراع راديو و تلويزيون ، توليد و رشد بي سايقه صنعت كامپيوتر و پرتاب ماهواره هاي ارتباطي  بوده ايم.

با پيشرفت فناوري  اين موارد د رحال همگرايي است و تفاوت هايي بين جمع آوري ، انتثال ذخيره و پردازش اطلاعات به شدت در حال محو شدن است سازمان هايي با صدها شعبه در نقاط مختلف جغرافيايي ،ب فشردن كليد وضعيت فعلي را حتي در دورترين نقاط بررسي مي كنند. با افزايش فدرت جمع آوري، پردازش و توزيع اطلاعات، تقاضاي پردازش اطلاعات پيچيده تر نيز افزايش مي يابد

الگوريتمهاي مسير يابي

وظيفه اصلي لايه شبكه ، هدايت بسته‌ها از ماشين منبع به ماشين مقصد است در اغلب زير شبكه‌ها ، بسته‌ها بايد چند جهش انجام دهند. تا به مقصد برسند. براي شبكه‌هاي پخشي،استثنايي وجود دارد، واي در اينجا نيز اگر منبع و مقصد در يك شبكه نباشد مسير يابي مشكل محسوب مي‌شود. الگورتيم هايي كه مسيرها و ساختمان داده‌هاي مربوط به آن را انتخاب مي‌كنند، موضوع مهم را طراحي لايه شبكه اند.

الگوريتم مسير يابي بخشي از نرم افزار لايه شبكه است كه تعيين مي‌كند بسته ورودي بايد به كدام خط خروجي منتقل شود. اگر زير شبكه از داده‌ها گرام‌ها استفاده كند، اين تصميم گيري دوباره بايد براي هر بسته  ورودي تكرار شود ،چون تا آن موقع امكان دارد بهترين مسير، تغيير كند اگر زير شبكه از مدارهاي مجازي استفاده كند ، تصميمات مسير يابي وقتي اتخاذ مي‌شوند كه مدار مجازي جديدي استفاده گردد. از آن پس ، بسته‌هاي داده‌ها فقط از مسير ايجاد شده قبلي منتقل مي‌شوند.حالت دوم گاهي مسير يابي تماس دارد ، زيرا مسير در طول مدت تمسا كاربر باقي مي‌ماند ( مثل كار كردن با پايانه يا انتقال فايل ) صرف نظر از اين كه آيا مسيرها براي هر بسته به طور مستقل انتخاب ميشوند  يا فقط وقتي كه اتصال جديدي برقرار مي‌شود انتخاب مي‌گردند، خواصي  وجود دارند. كه در الگوريتم‌هاي مسير يابي مطلوب‌اند صحت ، سهولت تحمل عيب، پايداري ، عدالت و بهينگي صخت وسهولت نيازي به توضيح ندارند، اما نياز به تحمل عيب چندان روشن نيست. انتظار مي‌رود كه شبكه‌هاي بزرگ ، سال‌ها بدون عيب كلي سيستم  به كار خود ادامه دهند. در اين مدت ممكن است اشكالات سخت افزاري و نرم افزاري  گوناگوني به وجود آيد. ميزبان‌ها مسير ياب‌ها مسير ياب‌ها بدون نياز به توقف انجام انجام كارها در مسير ياب‌ها و راه اندازي مجدد شبكه در هر بار متلاشي شدن مسيرياباز عهده تغييرات در توپولوژي و ترافيك برآيد.

پايداري نيز براي الگوريتم مسير يابي هدف مهمي است. الگوريتم‌هاي مسير يابي وجود دارند كه هرگز وجود دارندكه هرگز به حالت پايداري نمي‌رسند.مدت زمان اجراي آن بي تاثير است عدالت وبهينگي مممكن است ساده به نظر مي‌رسند يقيينا  كسي با آن مخالف نيست. اماهمان طور كه روشن است اهداف متناقضي دارند به عنوان مثال از اين تناقض ، شكل 1 را بينيد. فرض كنيد ترافيك كافي بين Aو ش، بين B,Bوبين C, C  وجود دارد تا پيوندهاي افقي را اشباع نمايد براي بيشينه كردن كل جريان ترافيك  X, Xبايد كاملا از بين برود. متاسفانه از نظر XوXعادلانه نيست بديهي است كه توافقي  بين كارايي كلي و عدالت اتصال‌هاي منفرد لازم است.

قبل از اينكه به متوزان كردن عدالت وبهينگي بپردازيم . بايد تصميم بگيريم كه چه چيزي را بهينه كنيم . بديهي است تاخير بسته بايد كمينه  شود ولي توان شبكه بايد بيشينه شود. علاوه براين اين دو هدف نيز با هم تضاد دارند، زيرا عملكرد هر سيستم  صف بندي در حد ظرفيت تاخير صف بندي را زياد ي كند. اغلب شبكه‌ها سعي ميكنند تعدداد جهشهاي بسته‌هاي را كمينه نمايند زيرا  كاهش تعدادجهش موجب بهبود تاخير و نيزكاهش ميزان پهناي باند مصرفي است كه منجر به بهبود توان عملياتي مي‌شود.

الگوريتم‌هاي مسير يابي  به مي‌توانند به دو دسته تقسيم شوند غير وفقي و وفقي  الگوريتم‌هاي غير وفقي تصميات مسير يابي خود را بر اندازه گيري يا تخمين  توپولوژي و ترافيك فعلي بنا نمي‌نهند بلكه براي انتخاب مسري جهت رسيدن از I  به Jبراي تمام I  را به تمام Jاز قبل  محاسبه مي‌شود در حالت OFF-LINEو هنگام راه اندازي شبكه به مسير ياب‌ها بار مي‌شود اين روند گاهي مسير يابي ايستا نام دارد.

برعكس الگوريتم‌هاي وقفي تصميات مسير يابي خود را براساس تغييرات توپولوژي و ترافيك تغيير مي‌دهند الگوريتم‌هاي وفقي ، وقتي كه مسيرها را عوض مي‌كنند. مثلا هر ثانيه وقتي  بار تغيير مي‌كند، با وقتي توپولوژي تغيير مي‌كند از نظر جايي كه اطلاعات را مي‌گيرند مثلا محلي از مسيريابهمجوار يا تمام مسيريابومعيارهايي كه براي بهينه سازي مورد استفاده قرارمي گيرند. (مثلا ، محلي از مسيرياب همجواريا تمام مسير ياب‌ها و معيارهايي كه براي بهينه سازي مورد استفاده قرار مي‌گيرند (مثلاً فاصله ، تعداد جهشها يا زمان انتقال تقريبي با يكديگر متفاوت‌اند . در بخش‌هاي بعدي الگوريتم‌هاي الگوريتمهاي گوناگوني  را چه ايستا و چه پويا ،مورد بررسي قرار مي‌دهيم.

اصل بهينگي

قبل از پرداختن به الگوريتم  توجه به مهم است كه صرف نظر از توپولوژي شبكه  وتر افيكي ، مي‌توان حكمي كلي راجع به مسيرهاي بهينه ارائه كرد اين حكم را به عنوان اصل بهينگي  شناخته مي‌شود. اين اصل بيا مي‌كند كه اگر مسيريابJاز مسيرياب Iبه مسيريابKدر مسيرياب بهينه‌اي شناخته مي‌كند آنگاه مسر بهينه‌اي از Jو Kنيز در مسير مشابهي  قرار مي‌گيرد. براي مشاهده اين موضوع ، بخشي  از مسير Iبه J  را به بناميد و بقيه را نامگذاري كنيد اگر مسيري بهتر از وجود داشت مي‌توانست با الحاق  شود تا مسيري از Iبه K  بهبود بخشد، و حكم ما را مي‌گويد ?  بهينه است نقض كند.

از اصل بهينگي مي‌توان نتيجه گرفت كه مجموعه‌اي از مسيرهاي بهينه از تمام منابع به مقصدي معين ، درختي را تشكيل ميد هد كه ريشه اش مقصد است چنين درختي، درخت بايگاني  نام دارد.شكل 2 در اين درخت مقياس فاصله تعداد جهش‌ها است توجه داشته باشيد. كه درخت‌هاي ديگري با همان طول مسير وجود داشته باشند هدف الگوريتم‌هاي مسير يابي، يافتن درخت‌هاي بايگاني و استفاده از انها براي تمام مسير ياب‌ها است .

چون درخت بايگاني يك درخت است، فاقد هرگونه حلقه است. لذا هر بسته در تعداد مشخصي از جهش‌هاي دريافت مي‌شود. در عمل هميشه به اين سادگي نيست.در اثناي كار، پيوندهاي  ومسيريابمي‌توانند به طرف پايين بروند وبه طرف بالا برگردند. بنابراين امكان دارد مسير ياب‌هاي مختلف راجع بع توپولوژي فعلي ايده‌هاي متفاوتي داشته باشند .همچنين سوال ديگري كه مطرح بود اين بود كه آيا هر مسيريابمجبور است به طور انفرادي اطلاعات مورد نياز جهت محاسبه درخت بايگاني را به دست آورد يا اين اطلاعات توسط وسايل ديگري جمع آوري مي‌شوند در ادامه به طور مختصر به اين موضوع مي‌پردازيم با اين وجود، اصل بهينگي ودرخت  بايگاني‌هاي معيارهايي را تهيه كردند كه ساير الگوريتم‌هاي مسير يابي مي‌توانند براساس آنها ارزيابي شوند.

مسير يابي كوتاه ترين مسير

مطالعه الگوريتمهاي  مسير يابي را با تكنيكي كه به طور گسترده به شكل‌هاي مختلفي به كار مي‌رود شروع مي‌كنيم، زيرا الگوريتم ساده‌اي است ودرك آن آسان است. ايده ، ساختن گرافي از زير شبكه است ، به طوري كه ، هر گره گراف نشان دهنده مسيرياب است و هريال نشان دهنده خط ارتباطي است ( كه اغلب پيوند نام دارد.) براي انتخاب  مسيري بين دو مسيريابمعين ، الگوريتم ، كوتاهترين مسير بين آنها را درگراف مي‌يابد.

در مورد كوتاهترين مسير توضيحاتي بايد ارائه شود . يك راه اندازه گيري طول مسير ، تعداد جهش است با اين معيار ، طول مسيرهاي ABC,ABEدر شكل 3 يكسان است.و معيار ديگر معيار ديگر فاصله جغرافيايي به كيلومتراست ، در اين حالت بديهي است كه ABCخيلي طولاني تر از ABEاست با فرض اين كه شكل با مقياس رسم شده است.

علاوه بر جهش‌ها و فاصله فيزيكي معيارهاي ديگري نيز قابل  استفاده‌اند به عنوان مثال هريال مي‌تواند به ميانگين تاخير صف بندي و انتقال براي بعضي از بسته‌هاي آزمايشي  برچسب گذاري شود. با اين برچسب گذاري، كوتاهترين مسير به جاي مسيري به جاي مسيري كه با كمترين يال يا فاصله  سريع تر مسير است.

در حالت كلي، برچسب‌هاي يال‌ها بايد به صورت تابعي از فاصله ، پهناي باند، ميانگين ترافيك هزينه ارتباط ميانگين طول صف تاخير اندازه گيري شده و ساير عوامل محاسبه  شود. با تغيير تابع وزني ، الگوريتم ،كوتاهترين مسير وزن دار را براساس هريك از معيارهاي فوق يا تركيبي از آنها محاسبه  مي‌كند. 



• تاثیر شخصیت پدر ومادر بر فرزندان
• دانلود رايگان نمونه سوالات پيام نور درس معادلات دیفرانسیل نيمسال اول 93-92
• دانلود رايگان نمونه سوالات پيام نور درس روش های محاسبات عددی,محاسبات عددی نيمسال اول 93-92
• دانلود رايگان نمونه سوالات پيام نور درس ریاضی عمومی 1 نيمسال اول 93-92
• دانلود رايگان نمونه سوالات پيام نور درس ریاضی 2,ریاضی عمومی 2,ریاضی کاربردی 1 نيمسال اول 93-92
• دانلود رايگان نمونه سوالات پيام نور درس شیمی عمومی 1,شیمی1 نيمسال اول 93-92