دانلود مقاله الگوریتم های مسیریابی در شبکه های کامپیوتری

الگوریتم های مسیریابی در شبکه های کامپیوتری

تعداد صفحات:

۹۲ ( نود و دو)

دسته :

کامپیوتر و IT

نوع فایل:

Word

توضیحات:

قابل استفاده جهت پروژه پایانی و شیوه ارایه مطالب

دانلود مقاله الگوریتم های مسیریابی در شبکه های کامپیوتری

دانلود مقاله الگوریتم های مسیریابی در شبکه های کامپیوتری

.

فهرست مطالب :

مقدمه

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

کلمات کلیدی

مفاهیم اولیه مسیریابی

روشهای هدایت بسته های اطلاعاتی در شبکه های کامپیوتری

روش مدار مجازی ((Virtual Circuit

روش دیتاگرام(Datagram)

معیارهای انتخاب یک مسیر مناسب برای مسیردهی توسط مسیریاب

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

روش ارسال سیل آسا

الگوریتم های LS

الگوریتم های vector Distance

مسیریابی سلسله مراتبی

مسیریابی در اینترنت

شبکه سلولی

معماریWMN

خصوصیات WMN از دیدمسیریابی

معیارهای کارایی مورد استفاده در پروتکل های مسیریابی

معیارکیفیت مسیر در مسیریابی شبکه های بیسیم چند گامه

عملیات

تغییرات اعمالی به DSDV

عملیات DSR

تغییرات اعمالی به DSR

نتایج

مسیریابی

LQSR

سربار LQSR

نتیجه

شبکه ی Mobile ad hoc (MANET)

پروتوکل های مسیر یابی (Routing Protocols)

Table driven Pro active –

DSDV

CSGR

STAR

SSR

DSR

TORA

AODV

RDMAR

Hybrid (Pro-active / Reactive)

ZRP

امنیت در شبکه های mobile ad hoc

نتیجه گیری

مقدمه ای بر

پروتوکل مسیر یابیSEAD

ARAN

نتیجه گیری

.

چکیده :

مسیریاب وسیله ای در شبکه است که برای ارسال بسته های اطلاعاتی از یک LAN به LAN دیگر با توپولوژی لایه شبکه یکسان به کار می رود. مسیریاب یک جدول مسیریابی دارد که به دو صورت ایستا و پویا ایجاد می گردد. بسته های اطلاعاتی در شبکه های کامپیوتری از طریق دو روش مدار مجازی(VC) و دیتاگرام هدایت می شوند. هر مسیریاب برای انتخاب یک مسیر معیارهایی دارد از قبیل: کوتاهترین مسیر، افزایش قابلیت اطمینان، کاهش تاخیر و… . مسیریابها برای انتخاب بهترین مسیر از الگوریتم هایی بهره می برند که باید اهدافی را تامین کنند از قبیل : درستی، سادگی، تحمل پذیری خطا، همگرایی سریع و… .
الگوریتم های مسیریابی از دو دیدگاه تقسیم بندی می شوند:
از دیدگاه روش تصمیم گیری و میزان هوشمندی.
از دیدگاه چگونگی جمع آوری و پردازش اطلاعات زیر ساخت شبکه.
از دیدگاه اول الگوریتم ها به دو دسته ایستا و پویا تقسیم می شوند.
از دیدگاه دوم الگوریتم ها را به دو دسته متمرکز (شامل الگوریتم های LS) و غیر متمرکز(شامل الگوریتم های DV) تقسیم می شوند.

کلمات کلیدی: مسیریاب(router) ، آدرسها MAC ، آدرسهای IP ، شرایط توپولوژیکی شبکه ، گام یا HOP ، شرایط ترافیکی شبکه،ازدحام یا congestion ، الگوریتم های LS (Link State ) ، الگوریتم های DV ( Distance Vector ) .

 .

مقدمه  :

یک مسیریاب دو شبکه را به همدیگر متصل میکند و یک شبکه می سازد. مسیریابها بر خلاف سوئیچ ها و پل ها در لایه شبکه مدل OSI کار میکنند در نتیجه می توانند دو LAN را که هر یک دارای پروتکل لایه پیوند-داده ای متفاوت هستند(مثلا اترنت و Token Ring) در صورتی که پروتکل های لایه شبکه همه سیستم ها یکی باشد به همدیگر متصل کنند.مسیریاب ها نسبت به پلها و هابها و سوئیچ ها دارای اختیارات گزینشی بالاتری برای انتقال بسته ها به پورت های دیگر می باشد و چون در محدوده شبکه های محلی کار میکنند، پیغام های پخش همگانی را منتقل نمی کنند مگر در مواردی بسیار خاص.

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

دو روش برای ایجاد جدول مسیریابی وجود دارد:

به صورت دستی یا ایستا:

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

به صورت دینامیک یا پویا:

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

دو مسئله مهم در مسیریابی مطرح است:

الف)هر یک از مسیریابها چگونه از پارامتر هزینه کل کانالهای شبکه مطلع شوند، تا بتوانند گراف زیر ساختی شبکه را تشکیل داده و بهترین مسیر را انتخاب نمایند؟

ب)چه الگوریتمی برای یافتن بهترین مسیر انتخاب شود تا از لحاظ سرعت پردازش و تصمیم گیری، بهینه بوده و بسته ها را با تاخیر مواجه نکند؟

روش های هدایت بسته های اطلاعاتی

۱-   ایجاد بسته های اطلاعاتی :

روند ایجاد یک بسته اطلاعاتی از لایه برنامه کاربردی (محل تولید داده ها) در مدل OSI آغاز می شود.

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

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

۱-۱ آدرس دهی بسته اطلاعاتی :

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

۱-۲ هدایت بسته های اطلاعاتی :

اجزاء شبکه از اطلاعات آدرس بسته های اطلاعاتی برای هدایت آنها به مقصد و دور نگهداشتن بسته های اطلاعاتی از نقاطی که مربوط به آنها نیستند، استفاده می کند. دو وظیفه زیر در هدایت صحیح بسته های اطلاعاتی نقش کلیدی را ایفا می کنند:

ـ ارسال بسته های اطلاعاتی :

کامپیوترها می توانند بسته های اطلاعاتی را با توجه به آدرس هدر آنها به دستگاه خاصی از شبکه ارسال کنند.

ـ فیلتر کردن بسته های اطلاعاتی :

روند انتخاب برخی از بسته های اطلاعاتی از میان بسته های اطلاعاتی دیگر با توجه به آدرس آنهاست

دو روش برای انتقال بسته های اطلاعاتی در شبکه های کامپیوتری مطرح است که هر کدام از آن ها در شبکه های امروزی به نحوی مورد استفاده قرار می گیرد:

روشهای هدایت بسته های اطلاعاتی در شبکه های کامپیوتری:

۱-۳ روش مدار مجازی (Virtual Circuit):

در این روش قبل از شروع به ارسال بسته های اطلاعاتی از یک ماشین، ابتدا یک مسیر بین مبدا و مقصد برقرار می شود.به این صورت که ابتدا با ارسال یک بسته کنترلی خاص با یک شماره ویژه بر روی شبکه اعلام  می کند که خواستار برقراری ارتباط با یک مقصد خاص می باشد.

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

خصوصیات این روش(VC) را می توان به صورت زیر خلاصه کرد:

برای ارسال بسته های اطلاعاتی به آدرسهای جهانی مبدا و مقصدنیازی نیست بلکه فقط به شماره VC نیاز است.

برای هدایت بسته های اطلاعاتی از مبدا به سمت مقصد نیازی به اجرای الگوریتم مسیریابی به ازای تک تک بسته ها نیست بلکه فقط یک جستجو در جدول هر مسیریاب انجام می­شود.

بسته ها الزاما به ترتیب به مقصد خواهند رسید.

احتمال گم شدن بسته ها ناشی از اشتباه در عمل مسیریابی در شبکه وجود ندارد.

۱-۴ روش دیتاگرام (Datagram) :

در این روش هر ماشین میزبان پس از آنکه بسته ای را تولید کرد تحویل اولین مسیریاب در دسترس می دهد.مسیریابها مختارند بر اساس شرایط فیزیکی وتوپولوژیکی زیر ساخت ارتباطی شبکه، مسیری را برای آن بسته انتخاب کرده و آن بسته را روی آن مسیر ارسال نمایند.بنابراین هیچ مسیر ثابت و از قبل مشخصی برای بسته های متوالی وجود ندارد.

یعنی وقتی دو بسته از یک مبدا تولید و به سمت یک مقصد واحد ارسال می شود ممکن است مسیرهای متفاوتی را طی نمایند، در ضمن ممکن است بسته ها به ترتیبی که تولید می شوند به مقصد نرسند.

خصوصیات این روش را می توان به صورت زیر خلاصه کرد:

هر بسته اطلاعاتی به آدرسهای جهانی مبدا ومقصد نیازمنداست.

برای هر بسته باید مسیریابی جداگانه انجام شود.

توزیع و هدایت بسته ها روی مسیرهای متفاوت، بر اساس شرایط توپولوژیکی و ترافیکی لحظه ای شبکه خواهد بود.

چون بسته ها به ترتیب نمی رسند باید فرآیندی برای تنظیم ترتیب بسته ها اتخاذ شود.

در لایه بالاتر باید نظارتهای ویژه بر گم شدن یا دوبله شدن بسته ها انجام شود.

معیارهای انتخاب یک مسیر مناسب برای مسیردهی توسط

۱-۵ مسیریاب:

۱( کوتاهترین مسیر(کاهش Hop count):

یعنی مسیری انتخاب شود که تعداد پرش کمتری از مبدا تا مقصد را داشته باشد.

۲) افزایش قابلیت اطمینان :

بایستی مسیری انتخاب شود تا احتمال نرخ خرابی در بیت را کاهش دهد مثلا مسیرهای مبتنی بر کانال فیبر نوری قابلیت بیشتری نسبت به کانال زوج سیم است.

۳) کاهش تاخیر:

تاخیر به عوامل مختلفی بستگی دارد.نوع کانال، پهنای باندکانال، صف فرآیندهای منتظر در هر پورت مسیریاب، ازدحام شبکه در کانالهای میانی شبکه و فاصله فیزیکی فرستنده و گیرنده.

۴) پهنای باند:

پهنای باند مقدار ظرفیت داده و ترافیکی است که یک کانال میتواند حمل نماید.مثلا پهنای باند فیبر نوری بسیار بالاتر از زوج سیم است.

۵) ترافیک داده:

یعنی مسیر انتخاب شده ترافیک کانال یا درجه شلوغی مسیریاب کمتری داشته باشد.

۶) هزینه ارتباطی:

مسیرها و کانال های مختلف دارای هزینه های متفاوتی هستند مثلا معمولا هزینه استفاده از ماهواره نسبت به زوج سیم بیشتر است.

مسیریابها برای انتخاب مسیر بر اساس معیارهای فوق از نرم افزاری به عنوان الگوریتم مسیریابی بهره می برند  و این الگوریتم ها بایستی اهداف زیر و یا بعضی از آن ها را برآورده سازند:

۱)درستی: یعنی الگوریتم به درستی عمل کند چرا که اگر اشتباه عمل کند مسیردهی اشتباه می شود.

۲)سادگی:   الگوریتم پیچیده نباشد زیرا زمان پردازش اجرای آن توسط مسیریاب زیاد می شود.

۳)پایداری و تحمل پزیری خطا:  در شرایط خرابی مسیریاب و یا قطع بعضی از کانال ها الگوریتم بایستی بتواند در حضور خطا به کار خود به درستی ادامه دهد.

۴)همگرایی سریع: در صورت تغییر در توپولوژی شبکه بایستی الگوریتم بتواند سریعا مسیرهای جدید را در جدول مسیریابی خود قرار دهد.

۵)عدالت :الگوریتم تمامی بسته های دریافتی را با شرایط یکسان مسیریابی کند.

۶)اولویت :این گزینه در مقابل عدالت است یعنی الگوریتم بعضی از بسته ها(مثلا کارهای بلادرنگ)را سریعتر پردازش و مسیریابی نماید.

۷)بهینگی :الگوریتم باید سعی نماید تا معیارهای انتخاب مسیر را بهینه نماید.

 

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

الگوریتم های مسیریابی رابا دو دیدگاه می توان دسته بندی کرد:

الف) از دیدگاه روش تصمیم گیری و میزان هوشمندی الگوریتم.

ب ) از دیدگاه چگونگی جمع آوری و پردازش اطلاعات زیر ساخت ارتباطی شبکه.

با دیدگاه اول الگوریتم های مسیریابی را می توان به دو دسته”ایستا”و “پویا” تقسیم بندی کرد. در الگوریتم های ایستا هیچ اعتنایی به شرایط توپولوژیکی و  ترافیک لحظه ای شبکه نمی شود.معمولا در این الگوریتم ها برای هدایت یک بسته، هر مسیریاب از جداولی استفاده می کند که در هنگام برپایی شبکه تنظیم شده و در طول زمان ثابت است.در هنگام وقوع هر گونه تغییر در توپولوژی زیر ساخت شبکه، این جداول باید توسط مسئول شبکه به صورت دستی مجددا تنظیم شود.اگر چه این الگوریتم ها بسیار سریعند ولی چون ترافیک لحظه ای شبکه متغیر است، نمیتوانند بهترین مسیر را انتخاب کنند و هر گونه تغییر در توپولوژی زیر ساخت شبکه، یک مشکل عمده و جدی ایجاد خواهد کرد.

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

از دیدگاه دوم الگوریتم های مسیریابی به دو دسته “سراسری/متمرکز” و “غیر متمرکز” تقسیم میشود. در الگوریتم های متمرکز هر مسیریاب باید اطلاعات کاملی از زیر ساخت ارتباطی شبکه داشته باشد.یعنی هر مسیریاب باید تمامی مسیریابهای دیگر, ارتباطات بین آن ها و هزینه هر خط را دقیقا شناسایی نماید.سپس با جمع آوری این اطلاعات ساختمان داده مربوط به گراف زیر ساخت شبکه را تشکیل بدهد.در چنین شرایطی برای یافتن بهترین مسیر بین هر دو مسیریاب، از الگوریتم های کوتاهترین مسیر نظیر”الگوریتم دایجکسترا” استفاده میشود.به چنین الگوریتم هایی که برای مسیریابی به اطلاعات کاملی از زیر ساخت شبکه و هزینه ارتباط بین هر دو مسیریاب نیازمندند اختصارا الگوریتم های LS گفته می شود و در مسیریابهای مدرن و جدید از آن استفاده می شود.

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

فایل کامل این تحقیق ۹۲ صفحه بصورت ورد WORD قابل ویرایش می باشد.
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه

 

توجه مهم :

*دوست عزیز در صورت نداشتن رمز پویا یا قطع بودن درگاه بانکی ، لطفا نام پروژه درخواستی خود را جهت هماهنگی برای دریافت شماره کارت واریزی و دریافت لینک دانلود، به واتساپ پشتیبانی سایت  ۰۹۳۹۲۷۶۱۶۳۰  ارسال کنید *(از ساعت ۸ الی ۲۳)

Related posts

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *