پایان نامه الگوریتم های مسیر یابی

پایان نامه الگوریتم های مسیر یابی

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

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

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

مسئله بی نهایت گرایی

مسیر یابی بردار فاصله از نظرو تئوری كار می‌كند، اما در عمل مشكل جدی دارد با این كه پاسخ صحیح می‌دهد، ولی به كندی عمل میكند به ویژه به خبرهای خوب، واكنش سریع ولی به خبرهای بد واكنش نشان می‌دهد مسیر یابی را در نظر بگیرید كه بهترین مسیر آن را به X بزرگ باشد، ادگر در مبادله بعدی ، همسایه A ناگهان تاخیر اندكی به X را گزارش كند، مسیریاباز خطی كه به A می‌آید برای ارسال ترافیك به X استفاده می‌كند در یك مبادله بردار، اخبار خوب پردازش می‌شوند.