چکیدهدر دنیای امروز اهمیت استفاده از اینترنت و شبکههای کامپیوتری بر کسی پوشیده نیست. کاهش هزینه و صرفه جویی در وقت از مهمترین مزایای این تکنولوژی است. در این میان، انتقال دادهها بین مبدأ تا مقصد از یک مسیر بهینه اهمیت ویژهای دارد. برای یافتن یک مسیر بهینه روشهای متفاوتی تعریف شده است. ما در این پایاننامه برآنیم تا با استفاده از سه الگوریتم تکاملی که از طبیعت الهام گرفته شدهاند، مسیری بهینه را برای انتقال دادهها در یک شبکه کامپیوتری پیدا کنیم. در این مطالعه عملکرد الگوریتمهای ژنتیک، انبوه ذرات و کلونی مورچگان برای یافتن مسیر بهینه با هم مقایسه میشوند. در هر مرحله از اجرا، همواره الگوریتم بهینهسازی کلونی مورچگان کوتاهترین مسیر را کشف میکند ولی زمان اجرای آن چندین برابر دو الگوریتم دیگر است. الگوریتم ژنتیک در کمترین زمان به نسبت دو الگوریتم دیگر مسیری را معرفی میکند ولی از آنجاییکه در بهینهی محلی گیر میکند مسیر بهینه را نشان نمیدهد. الگوریتم بهینهسازی ازدحام ذرات هم زمانی نسبتاً مناسب دارد اما مسیر بهینه را نمایش نمیدهد. در همین راستا الگوریتم جدیدی را ارائه دادهایم که در آن دو الگوریتم کلونی مورچگان و ژنتیک با هم ترکیب شده اند. زمان اجرای این الگوریتم به نسبت الگوریتم کلونی مورچگان بسیار بهتر است و نیز مسیری که بر می گرداند از مسیر به دست آمده در الگوریتم ژنتیک مناسبتر میباشد.کلمات کلیدی:الگوریتم بهینهسازی ازدحام ذرات،الگوریتم بهینهسازی کلونی مورچگان، الگوریتم ژنتیک، الگوریتمهای تکاملی، شبکههای کامپیوتری، مسیریابی.فهرست مطالبفصل اول................................................................................................................ 11- مقدمه.............................................................................................................. 21-1 شبکه و مسیریابی................................................................................... 21-2 الگوریتم های تکاملی......................................................................... 41-2-1 الگوریتم ژنتیک............................................................................. 51-2-2 الگوریتم انبوه ذرات PSO...................................................... 51-2-3 الگوریتم کلونی مورچگان ACO............................................... 61-3 نوآوریهای انجام شده......................................................................... 61-4 ساختار پایان نامه.............................................................................. 7فصل دوم................................................................................................................ 82- الگوریتمهای تکاملی............................................................................. 92-1 الگوریتم ژنتیک چیست؟.................................................................... 122-1-1 فضای جستجو..................................................................................... 152-1-2 مفاهیم اولیه در الگوریتم ژنتیک................................... 162-1-3 اصول پایهای.................................................................................. 162-1-4 نمای کلی الگوریتم ژنتیک.................................................... 162-1-5 کدگذاری............................................................................................ 182-1-5-1 کدگذاری دودویی.................................................................. 192-1-5-2 کدگذاری جهشی....................................................................... 192-1-5-3 کدگذاری ارزشی..................................................................... 202-1-5-4 کدگذاری درختی..................................................................... 202-1-5-5 مسایل مربوط به کدگذاری.............................................. 212-1-6 کروموزوم.......................................................................................... 232-1-7 جمعیت ژنتیکی................................................................................ 242-1-8 تابع برازندگی............................................................................. 242-1-9 عملگر ترکیب یا جابهجایی.................................................... 252-1-9-1 ترکیب تک نقطهای................................................................ 262-1-9-2 ترکیب چند نقطهای............................................................. 262-1-9-3 ترکیب یکنواخت..................................................................... 272-1-9-4 ترکیب نگاشت جزئی............................................................. 282-1-9-5 ترکیب مرتب شده (OX)....................................................... 292-1-9-6 ترکیب چرخشی (CX)............................................................... 302-1-9-7 ترکیب مورب(DX).................................................................... 312-1-10 عملگر جهش..................................................................................... 312-1-10-1 روش تعویض............................................................................. 312-1-10-2 روش وارون سازی................................................................ 322-1-10-3 روش ژن جزئی........................................................................ 322-1-10-4 روش درجی............................................................................... 332-1-10-5 روش درهمآمیخته................................................................ 332-1-11 فرایند انتخاب........................................................................... 332-1-11-1 روش چرخ رولت................................................................... 342-1-11-2 روش دورهای.......................................................................... 352-1-12 عملگر ترمیم................................................................................ 362-1-13 نخبه کشی........................................................................................ 362-1-14 مراحل اجرای الگوریتم ژنتیک........................................... 362-1-15 محدودیتهای الگوریتم ژنتیک............................................. 402-1-16 همگرایی در الگوی ژنتیک.................................................. 402-1-17 برخي از كاربردهای الگوريتم ژنتيك............................ 412-2 الگوریتم بهینهسازی ازدحام ذرات........................................... 422-2-1 تاریخچه الگوریتم بهینهسازی انبوه ذرات................. 492-2-2 پارامترهای PSO........................................................................... 492-2-3 برخی از نسخههای تغییریافتهی PSO................................ 562-2-3-1 الگوریتم PSO دودویی..................................................... 562-2-3-2 الگوریتم PSO فازی یا FPSO...................................... 572-2-4 کاربردها.......................................................................................... 602-3 الگوریتم بهینهسازی مورچهها..................................................... 622-3-1 الگوی بهینهسازی کُلونی مورچهها..................................... 652-3-2 الگوریتم ساده شده مورچهها............................................... 662-3-3 الگوریتم مورچهها...................................................................... 692-3-4 الگوریتم مورچهها برای مساله فروشنده دورهگرد.. 762-3-5 برخی از نسخههای تغییر یافتهی الگوریتم مورچهها792-3-5-1 الگوریتم مورچهها و نخبهگرایی............................. 802-3-5-2 الگوریتم مورچهها و یادگیری تقویتی................ 802-3-6 سامانه کلونی مورچهها......................................................... 822-3-7 الگوریتم مورچهی کمینه- بیشینه (MMAS).................... 832-3-8 کاربردها....................................................................................... 84فصل سوم.............................................................................................................. 863- مسیریابی به کمک الگوریتمهای تکاملی 87فصل چهارم......................................................................................................... 924- روش پیشنهادی.......................................................................................... 93فصل پنجم........................................................................................................... 995- نتیجهگیری................................................................................................ 1005-1 الگوریتم بهینهسازی کلونی مورچگان.................................... 1005-2 الگوریتم ژنتیک................................................................................. 1005-3 الگوریتم بهینهسازی ازدحام ذرات......................................... 1005-4 الگوریتم پیشنهادی.......................................................................... 1015-5 پیشنهادات آتی.................................................................................... 101منابع:.............................................................................................................. 102 فهرست اشکالشکل 2-1: مثالی از نقاط بهینه محلی و بهینه سراسری یک تابع12شکل2-2: نمونهای از فضای جستجو [5]15شکل2-3: نمای کلی الگوریتم ژنتیک17شکل2-4 مثالی از کدگذاری دودویی19شکل2-5: مثالی برای کدگذاری جهشی19شکل2-6: مثالی از کدگذاری ارزشی20شکل2-7: مثالی از کدگذاری درختی[5]21شکل2-8: فضای کدگذاری وفضای جواب [5]21شکل2-9: رابطه بین کروموزومها و جوابها22شکل2-10: انواع جواب بین فضای جواب و فضای کدگذاری [5]23شکل2-11 : نمایش یک کروموزوم n بیتی در مبنای عددی m23شکل2-12: ترکیب تک نقطهای26شکل2-13 : ترکیب چند نقطهای27شکل2-14: ترکیب یکنواخت27شکل2-15 : ترکیب نگاشت جزئی27شکل2-16 : نحوه پر کردن حفرهها29شکل2-17 : ترکیب مرتب29شکل2-18 : نحوه پر کردن عناصر29شکل2-19 : ترکیب دوره ای30شکل2-20 : نحوه پرکردن عناصر30شکل2-21 : ترکیب مورب31شکل2-22 : روش تعویض32شکل2-23: روش وارون سازی32شکل2-24 : روش ژن جزئی32شکل2-25: روش درجی33شکل2-26 : روش درهمآمیخته33شکل2-27 : روش انتخاب چرخ رولت35شکل2-28: مراحل اجرای الگوریتم ژنتیک39شکل2-29: الگوریتم ژنتیک ارائه شده است به وسیله گرفنستت و بیکر39شکل2-30 : يكگروهازماهيهاكهخطريكشكارچيراپشتسرميگذارد [1]43شکل2-31 : چندمثالازالگوهايموجوددرطبيعت [1]45شکل2-32 : مراحل الگوریتم PSO [1]49شکل2-33 : اشکال مختلف همسایگی [1]54شکل2-34 : آمار مربوط به مقالات کاربردی الگوریتم PSO در IEEE Xplore [41]62شکل2-35 : رفتار مورچه های آرژانتینی در آزمایش گاس و همکارانش65شکل2-36 : مسیر بهینه بین لانه و مقصدی فرضی در گرافی ساده68شکل2-37 : فهرست عملیاتی که در یک مرحله از الگوریتم مورچهها انجام میشود75 فهرست جداولجدول 3-1: عملکرد الگوریتمها در 20 بار تکرار87جدول 3-2: عملکرد الگوریتمها در 100 بار تکرار88جدول 3-3: عملکرد الگوریتمها در 200 بار تکرار88جدول 4-1: عملکرد الگوریتمها در 20 بار تکرار94جدول 4-2: عملکرد الگوریتمها در 100 بار تکرار94جدول 4-3: عملکرد الگوریتمها در 200 بار تکرار95 فهرست نمودارهانمودار 3-1: مقایسه مسافت به دست آمده در تعداد تکرار 2089نمودار 3-2: مقایسه زمان به دست آمده در تعداد تکرار 2089نمودار 3-3: مقایسه مسافت به دست آمده در تعداد تکرار 10090نمودار 3-4: مقایسه زمان به دست آمده در تعداد تکرار 10090نمودار 3-5: مقایسه مسافت به دست آمده در تعداد تکرار 20091نمودار 3-6: مقایسه زمان به دست آمده در تعداد تکرار 20091نمودار 4-1: مقایسه مسافت به دست آمده در تعداد تکرار 2095نمودار 4-2: مقایسه زمان به دست آمده در تعداد تکرار 2096نمودار 4-3: مقایسه مسافت به دست آمده در تعداد تکرار 10096نمودار 4-4: مقایسه زمان به دست آمده در تعداد تکرار 10097نمودار 4-5: مقایسه مسافت به دست آمده در تعداد تکرار 20097نمودار 4-6: مقایسه زمان به دست آمده در تعداد تکرار 20098 فصل اول 1- مقدمهدر دنیای امروز اهمیت استفاده از اینترنت و شبکههای کامپیوتری بر کسی پوشیده نیست. کاهش هزینه و صرفه جویی در وقت از مهمترین مزایای این تکنولوژی است. در این میان، انتقال دادهها از مبدأ به مقصد در کمترین زمان ممکن از اهمیت ویژهای برخوردار است. در این راستا در این پایان نامه برآنیم تا با استفاده از الگوریتمهای هوش مصنوعی بهبودی در سرعت انتقال دادهها ایجاد کنیم. به همین منظور میخواهیم از الگوریتمهای تکاملی استفاده تا مسیری بهینه را برای انتقال دادهها در یک شبکه کامپیوتری پیدا کنیم.یک شبکه رایانهای که اغلب به طور خلاصه به آن شبکه گفته میشود، گروهی از رایانههاو دستگاههایی میباشد که توسط کانالهای ارتباطی به هم متصل شدهاند.شبکه رایانهای باعث تسهیل ارتباطات میان کاربران شده و اجازه میدهد کاربران منابع خود را به اشتراک بگذارند. یک شبکه رایانهای اجازه به اشتراک گذاری منابع و اطلاعات را میان دستگاههای متصل شده به هم میدهد.شبکههای رایانهای را میتوان برای اهداف مختلف استفاده کرد:مکانیزم برقراری ارتباط و تبادل داده در مقیاسهای مختلف شبکه متفاوت است. تا زمانی که در شبکههای محلی به برقراری ارتباط میپردازیم، با بعضی از مسائل از قبیل پیدا کردن مسیر از مبدأ تا مقصد، یافتن مسیر بهینه و غیره سر و کار نخواهیم داشت. اما در شرایطی که شبکهی ما یک [3]WAN بوده و یا بخواهیم ارتباطات بین شبکهای داشته باشیم، موضوع مسیریابی پیش رویمان خواهد بود.در شبکههایی در مقیاس WAN، بر خلاف شبکههای [4]LAN، بستههای داده برای رسیدن به مقصد میبایست از گرههای مختلف که شبکهها را به یکدیگر مرتبط میسازند، عبور کنند. به این گرهها مسیریاب[5] گفته میشود.
Computer Network Routing by Evolutionary Algorithmsپایان نامه مسیریابی شبکه های کامپیوتری توسط الگوریتم های تکاملی
چکیدهدر دنیای امروز اهمیت استفاده از اینترنت و شبکههای کامپیوتری بر کسی پوشیده نیست. کاهش هزینه و صرفه جویی در وقت از مهمترین مزایای این تکنولوژی است. در این میان، انتقال دادهها بین مبدأ تا مقصد از یک مسیر بهینه اهمیت ویژهای دارد. برای یافتن یک مسیر بهینه روشهای متفاوتی تعریف شده است. ما در این پایاننامه برآنیم تا با استفاده از سه الگوریتم تکاملی که از طبیعت الهام گرفته شدهاند، مسیری بهینه را برای انتقال دادهها در یک شبکه کامپیوتری پیدا کنیم. در این مطالعه عملکرد الگوریتمهای ژنتیک، انبوه ذرات و کلونی مورچگان برای یافتن مسیر بهینه با هم مقایسه میشوند. در هر مرحله از اجرا، همواره الگوریتم بهینهسازی کلونی مورچگان کوتاهترین مسیر را کشف میکند ولی زمان اجرای آن چندین برابر دو الگوریتم دیگر است. الگوریتم ژنتیک در کمترین زمان به نسبت دو الگوریتم دیگر مسیری را معرفی میکند ولی از آنجاییکه در بهینهی محلی گیر میکند مسیر بهینه را نشان نمیدهد. الگوریتم بهینهسازی ازدحام ذرات هم زمانی نسبتاً مناسب دارد اما مسیر بهینه را نمایش نمیدهد. در همین راستا الگوریتم جدیدی را ارائه دادهایم که در آن دو الگوریتم کلونی مورچگان و ژنتیک با هم ترکیب شده اند. زمان اجرای این الگوریتم به نسبت الگوریتم کلونی مورچگان بسیار بهتر است و نیز مسیری که بر می گرداند از مسیر به دست آمده در الگوریتم ژنتیک مناسبتر میباشد.کلمات کلیدی:الگوریتم بهینهسازی ازدحام ذرات،الگوریتم بهینهسازی کلونی مورچگان، الگوریتم ژنتیک، الگوریتمهای تکاملی، شبکههای کامپیوتری، مسیریابی.فهرست مطالبفصل اول................................................................................................................ 11- مقدمه.............................................................................................................. 21-1 شبکه و مسیریابی................................................................................... 21-2 الگوریتم های تکاملی......................................................................... 41-2-1 الگوریتم ژنتیک............................................................................. 51-2-2 الگوریتم انبوه ذرات PSO...................................................... 51-2-3 الگوریتم کلونی مورچگان ACO............................................... 61-3 نوآوریهای انجام شده......................................................................... 61-4 ساختار پایان نامه.............................................................................. 7فصل دوم................................................................................................................ 82- الگوریتمهای تکاملی............................................................................. 92-1 الگوریتم ژنتیک چیست؟.................................................................... 122-1-1 فضای جستجو..................................................................................... 152-1-2 مفاهیم اولیه در الگوریتم ژنتیک................................... 162-1-3 اصول پایهای.................................................................................. 162-1-4 نمای کلی الگوریتم ژنتیک.................................................... 162-1-5 کدگذاری............................................................................................ 182-1-5-1 کدگذاری دودویی.................................................................. 192-1-5-2 کدگذاری جهشی....................................................................... 192-1-5-3 کدگذاری ارزشی..................................................................... 202-1-5-4 کدگذاری درختی..................................................................... 202-1-5-5 مسایل مربوط به کدگذاری.............................................. 212-1-6 کروموزوم.......................................................................................... 232-1-7 جمعیت ژنتیکی................................................................................ 242-1-8 تابع برازندگی............................................................................. 242-1-9 عملگر ترکیب یا جابهجایی.................................................... 252-1-9-1 ترکیب تک نقطهای................................................................ 262-1-9-2 ترکیب چند نقطهای............................................................. 262-1-9-3 ترکیب یکنواخت..................................................................... 272-1-9-4 ترکیب نگاشت جزئی............................................................. 282-1-9-5 ترکیب مرتب شده (OX)....................................................... 292-1-9-6 ترکیب چرخشی (CX)............................................................... 302-1-9-7 ترکیب مورب(DX).................................................................... 312-1-10 عملگر جهش..................................................................................... 312-1-10-1 روش تعویض............................................................................. 312-1-10-2 روش وارون سازی................................................................ 322-1-10-3 روش ژن جزئی........................................................................ 322-1-10-4 روش درجی............................................................................... 332-1-10-5 روش درهمآمیخته................................................................ 332-1-11 فرایند انتخاب........................................................................... 332-1-11-1 روش چرخ رولت................................................................... 342-1-11-2 روش دورهای.......................................................................... 352-1-12 عملگر ترمیم................................................................................ 362-1-13 نخبه کشی........................................................................................ 362-1-14 مراحل اجرای الگوریتم ژنتیک........................................... 362-1-15 محدودیتهای الگوریتم ژنتیک............................................. 402-1-16 همگرایی در الگوی ژنتیک.................................................. 402-1-17 برخي از كاربردهای الگوريتم ژنتيك............................ 412-2 الگوریتم بهینهسازی ازدحام ذرات........................................... 422-2-1 تاریخچه الگوریتم بهینهسازی انبوه ذرات................. 492-2-2 پارامترهای PSO........................................................................... 492-2-3 برخی از نسخههای تغییریافتهی PSO................................ 562-2-3-1 الگوریتم PSO دودویی..................................................... 562-2-3-2 الگوریتم PSO فازی یا FPSO...................................... 572-2-4 کاربردها.......................................................................................... 602-3 الگوریتم بهینهسازی مورچهها..................................................... 622-3-1 الگوی بهینهسازی کُلونی مورچهها..................................... 652-3-2 الگوریتم ساده شده مورچهها............................................... 662-3-3 الگوریتم مورچهها...................................................................... 692-3-4 الگوریتم مورچهها برای مساله فروشنده دورهگرد.. 762-3-5 برخی از نسخههای تغییر یافتهی الگوریتم مورچهها792-3-5-1 الگوریتم مورچهها و نخبهگرایی............................. 802-3-5-2 الگوریتم مورچهها و یادگیری تقویتی................ 802-3-6 سامانه کلونی مورچهها......................................................... 822-3-7 الگوریتم مورچهی کمینه- بیشینه (MMAS).................... 832-3-8 کاربردها....................................................................................... 84فصل سوم.............................................................................................................. 863- مسیریابی به کمک الگوریتمهای تکاملی 87فصل چهارم......................................................................................................... 924- روش پیشنهادی.......................................................................................... 93فصل پنجم........................................................................................................... 995- نتیجهگیری................................................................................................ 1005-1 الگوریتم بهینهسازی کلونی مورچگان.................................... 1005-2 الگوریتم ژنتیک................................................................................. 1005-3 الگوریتم بهینهسازی ازدحام ذرات......................................... 1005-4 الگوریتم پیشنهادی.......................................................................... 1015-5 پیشنهادات آتی.................................................................................... 101منابع:.............................................................................................................. 102 فهرست اشکالشکل 2-1: مثالی از نقاط بهینه محلی و بهینه سراسری یک تابع12شکل2-2: نمونهای از فضای جستجو [5]15شکل2-3: نمای کلی الگوریتم ژنتیک17شکل2-4 مثالی از کدگذاری دودویی19شکل2-5: مثالی برای کدگذاری جهشی19شکل2-6: مثالی از کدگذاری ارزشی20شکل2-7: مثالی از کدگذاری درختی[5]21شکل2-8: فضای کدگذاری وفضای جواب [5]21شکل2-9: رابطه بین کروموزومها و جوابها22شکل2-10: انواع جواب بین فضای جواب و فضای کدگذاری [5]23شکل2-11 : نمایش یک کروموزوم n بیتی در مبنای عددی m23شکل2-12: ترکیب تک نقطهای26شکل2-13 : ترکیب چند نقطهای27شکل2-14: ترکیب یکنواخت27شکل2-15 : ترکیب نگاشت جزئی27شکل2-16 : نحوه پر کردن حفرهها29شکل2-17 : ترکیب مرتب29شکل2-18 : نحوه پر کردن عناصر29شکل2-19 : ترکیب دوره ای30شکل2-20 : نحوه پرکردن عناصر30شکل2-21 : ترکیب مورب31شکل2-22 : روش تعویض32شکل2-23: روش وارون سازی32شکل2-24 : روش ژن جزئی32شکل2-25: روش درجی33شکل2-26 : روش درهمآمیخته33شکل2-27 : روش انتخاب چرخ رولت35شکل2-28: مراحل اجرای الگوریتم ژنتیک39شکل2-29: الگوریتم ژنتیک ارائه شده است به وسیله گرفنستت و بیکر39شکل2-30 : يكگروهازماهيهاكهخطريكشكارچيراپشتسرميگذارد [1]43شکل2-31 : چندمثالازالگوهايموجوددرطبيعت [1]45شکل2-32 : مراحل الگوریتم PSO [1]49شکل2-33 : اشکال مختلف همسایگی [1]54شکل2-34 : آمار مربوط به مقالات کاربردی الگوریتم PSO در IEEE Xplore [41]62شکل2-35 : رفتار مورچه های آرژانتینی در آزمایش گاس و همکارانش65شکل2-36 : مسیر بهینه بین لانه و مقصدی فرضی در گرافی ساده68شکل2-37 : فهرست عملیاتی که در یک مرحله از الگوریتم مورچهها انجام میشود75 فهرست جداولجدول 3-1: عملکرد الگوریتمها در 20 بار تکرار87جدول 3-2: عملکرد الگوریتمها در 100 بار تکرار88جدول 3-3: عملکرد الگوریتمها در 200 بار تکرار88جدول 4-1: عملکرد الگوریتمها در 20 بار تکرار94جدول 4-2: عملکرد الگوریتمها در 100 بار تکرار94جدول 4-3: عملکرد الگوریتمها در 200 بار تکرار95 فهرست نمودارهانمودار 3-1: مقایسه مسافت به دست آمده در تعداد تکرار 2089نمودار 3-2: مقایسه زمان به دست آمده در تعداد تکرار 2089نمودار 3-3: مقایسه مسافت به دست آمده در تعداد تکرار 10090نمودار 3-4: مقایسه زمان به دست آمده در تعداد تکرار 10090نمودار 3-5: مقایسه مسافت به دست آمده در تعداد تکرار 20091نمودار 3-6: مقایسه زمان به دست آمده در تعداد تکرار 20091نمودار 4-1: مقایسه مسافت به دست آمده در تعداد تکرار 2095نمودار 4-2: مقایسه زمان به دست آمده در تعداد تکرار 2096نمودار 4-3: مقایسه مسافت به دست آمده در تعداد تکرار 10096نمودار 4-4: مقایسه زمان به دست آمده در تعداد تکرار 10097نمودار 4-5: مقایسه مسافت به دست آمده در تعداد تکرار 20097نمودار 4-6: مقایسه زمان به دست آمده در تعداد تکرار 20098 فصل اول 1- مقدمهدر دنیای امروز اهمیت استفاده از اینترنت و شبکههای کامپیوتری بر کسی پوشیده نیست. کاهش هزینه و صرفه جویی در وقت از مهمترین مزایای این تکنولوژی است. در این میان، انتقال دادهها از مبدأ به مقصد در کمترین زمان ممکن از اهمیت ویژهای برخوردار است. در این راستا در این پایان نامه برآنیم تا با استفاده از الگوریتمهای هوش مصنوعی بهبودی در سرعت انتقال دادهها ایجاد کنیم. به همین منظور میخواهیم از الگوریتمهای تکاملی استفاده تا مسیری بهینه را برای انتقال دادهها در یک شبکه کامپیوتری پیدا کنیم.یک شبکه رایانهای که اغلب به طور خلاصه به آن شبکه گفته میشود، گروهی از رایانههاو دستگاههایی میباشد که توسط کانالهای ارتباطی به هم متصل شدهاند.شبکه رایانهای باعث تسهیل ارتباطات میان کاربران شده و اجازه میدهد کاربران منابع خود را به اشتراک بگذارند. یک شبکه رایانهای اجازه به اشتراک گذاری منابع و اطلاعات را میان دستگاههای متصل شده به هم میدهد.شبکههای رایانهای را میتوان برای اهداف مختلف استفاده کرد:مکانیزم برقراری ارتباط و تبادل داده در مقیاسهای مختلف شبکه متفاوت است. تا زمانی که در شبکههای محلی به برقراری ارتباط میپردازیم، با بعضی از مسائل از قبیل پیدا کردن مسیر از مبدأ تا مقصد، یافتن مسیر بهینه و غیره سر و کار نخواهیم داشت. اما در شرایطی که شبکهی ما یک [3]WAN بوده و یا بخواهیم ارتباطات بین شبکهای داشته باشیم، موضوع مسیریابی پیش رویمان خواهد بود.در شبکههایی در مقیاس WAN، بر خلاف شبکههای [4]LAN، بستههای داده برای رسیدن به مقصد میبایست از گرههای مختلف که شبکهها را به یکدیگر مرتبط میسازند، عبور کنند. به این گرهها مسیریاب[5] گفته میشود.