مسیریابی

مسیریابی (الگوریتم). مسیر یابی یک الگوریتم برای برنامه های کامپیوتری است که هدف آن یافتن ( غالبا ) کوتاه ترین مسیر بین دو نقطه است. مسیر یابی یک راه کاربردی برای حل هزارتو ها است.
مسیر یابی به مقدار زیادی به مسئلهٔ کوتاه ترین مسیر در نظریهٔ گراف ها ارتباط دارد؛ که در واقع این مسئله به این موضوع می پردازد که چگونه سریع ترین، ارزان ترین ( از لحاظ تعداد راس ها ) و کوتاه ترین مسیر را بین دو نقطه در یک شبکهٔ بزرگ بیابیم. [ ۱]
ردیابی تاریخچه مسئله مسیریابی و کوتاهترین مسیر دشوار است. می توان تصور کرد که حتی در جوامع بسیار بدوی ( حتی حیوانات ) نیز این کار بسیار ضروری بوده است ( به عنوان مثال برای یافتن غذا ) . تحقیقات ریاضی دربارهٔ این مسئله نسبت به مسئله های معروف دیگر دیر شروع شد. از اولین الگوریتم هایی که برای این مسئله ارائه شد می توان به الگوریتم جستجوی اول سطح اشاره کرد. [ ۲]
با توجه به پیشرفت کامپیوترها و ظهور مسائل جدید، این مسئله به تدریج از اواسط قرن بیستم مورد توجه قرار گرفت و با ایجاد شبکهٔ جهانی اینترنت، بیش از پیش به آن پرداخته شد. بازی های کامپیوتری و نقشه های آنلاین، امروزه از پیشرفته ترین الگوریتم های مسیریابی استفاده می کنند.
مسیریابی عبارت است از پیدا کردن یک مسیر بین دو نقطه از فضا که ممکن است مابین آنها موانعی وجود داشته باشد. مسئلهٔ مسیریابی به دو زیرمسالهٔ زیر قابل تقسیم است:[ ۳]
• ایجاد یک گراف
• یافتن مسیر مطلوب روی گراف با طراحی یک الگوریتم مسیریابی
در مرحلهٔ اول سعی بر این است که فضای پیوسته به فضایی گسسته نگاشته شود. به این ترتیب یک گراف G ( V , E ) به وجود می آید که در آن V ( مجموعهٔ رئوس گراف ) نمایندهٔ نقاطی از فضای پیوسته و E ( مجموعهٔ یالهای گراف ) نمایندهٔ وجود یا عدم وجود ارتباط بدون واسطه بین دو نقطه از فضای پیوسته است.
این گراف در مرحلهٔ دوم به عنوان ورودی به یک الگوریتم مسیریابی داده می شود. خروجی این الگوریتم یک آرایه ی مرتب از راس ها است که برای رسیدن به راس هدف باید آن ها را به ترتیب و بدون واسطه طی کرد. الگوریتم های مسیریابی معمولاً علاوه بر این که می خواهند یک مسیر پیدا کنند، در پی مسیری هستند که بر اساس معیار خاصی ( مثلا طول مسیر ) بهینه باشد. [ ۴]
متد مسیریابی با شروع از یک راس و جستجو در راس های مجاور آن تا زمان رسیدن به راس مقصد، یک گراف را جستجو می کند؛ که معمولاً هدف آن یافتن سریع ترین مسیر است. در حقیقت هدف الگوریتم مسیر یابی عموماً یافتن مسیری با کمترین تعداد راس استفاده شده ( در گراف های فاقد وزن ) ، یا کمترین جمع اوزان مشاهده شده ( در گراف های وزن دار ) است. به عنوان مثال می توان گفت که الگوریتم مد نظر، همانند شخصی است که قصد دارد از نقطه ای به نقطهٔ دیگری برسد؛ به جای این که این شخص تمام مسیرهای موجود را بررسی کند، در یک مسیر حرکت می کند و فقط زمانی از مسیر خود منحرف می شود که مانعی بر سر راه وی وجود داشته باشد.

مسیریابی (شبکه). مسیریابی ( به انگلیسی: Routing ) فرآیندی برای انتخاب بهترین مسیر در شبکه های داخلی و خارجی است و نقش مؤثری در ارسال داده ها در یک شبکه دارد. پروتکلهای مسیریابی می تواند بین انواع مختلفی از شبکه ها، مثل شبکه تلفن و اینترنت برقرار شوند. این مسیریابی می تواند عامل ارسال بسته های منطقی از مبدأ به مقصد باشد[ ۱] . سخت افزارهای به کار رفته در یک شبکه شامل مسیریاب یا روتر ( به انگلیسی: Router ) ، پل ( Bridge ) ، دیوار آتش یا فایروال ( به انگلیسی: Firewall ) و سوئیچ می شوند. کامپیوترهایی که کارت شبکه دارند می توانند بسته ها را ارسال کنند. این روند عامل ارسال براساس جداول می باشد و می تواند ثبت ها را در مقصد نگهداری کند. این جداول در حافظه دستگاه تشکیل می شوند. [ ۲]
شبکه های کوچک دارای جداول دستی هستند. شبکه های بزرگ توپولوژی پیچیده ای دارند و به سرعت تغییر می کنند. به این طریق ساختار جداول غیرقابل طراحی خواهد شد. بیشتر این شبکه های تلفنی کلیدی ( pstn ) از این جداول استفاده می کنند و نقایص در مسیر این سیستم شناخته و رفع خواهند شد. مسیر یابی دینامیکی تلاشی برای حل مسئله و تشکیل ساختار خودکار جداول است. این براساس اطلاعات پروتکل مسیریابی عملی است. به این طریق شبکه ها از هر نقص ایمن خواهند شد. این دینامیک در اینترنت نقش فعال دارد. طراحی پروتکل ها به یک تماس ماهرانه نیاز دارد. نباید فرض کرد که شبکه سازی به نقطه اتوماسیون کامل رسیده است.
در این الگوریتم از الگوریتم bellman – ford استفاده می شود و می توان یک رقم و هزینه را برای هر لینک بین گروه های شبکه تعیین نمود. گره ها می توانند اطلاعات را از A به B بفرستند؛ و این از طریق مسیر کم هزینه عملی است. این الگوریتم خیلی ساده عمل می کند. ابتدا باید راه اندازی انجام شود. بخش های همجوار نیز باید شناخته شوند. هر گره به طور منظم می تواند هزینه کل را به مقصد بفرستد. گره های همجوار به بررسی اطلاعات و مقایسه یافته ها می پردازند. این عامل پیشرفت در جداول مسیریابی خواهد بود. تمام گره ها بهترین حلقه را کشف می کنند. وقتی یکی از گره ها کاهش یافت آنهایی که در همجوار هستند می توانند ورودی را خالی کنند و به مقصد بروند. به این طریق اطلاعات جدول ارائه خواهند شد. آن ها می توانند اطلاعات را در اختیار گره های مجاور قرار دهند. در نهایت اطلاعات ارتقا یافته دریافت می شوند و مسیر جدید شناخته خواهد شد.