مسیریابی چند پخشی

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

ارسال پیام به چنین گروهی چند پخشی نام دارد و الگوریتم مسیریابی آن، مسیریابی چند پخشی نامیده می‌شود. در این بخش یکی از روشهای مسیریابی چند پخشی را بررسی می‌کنیم.

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

برای مسیریابی چند پخشی، هر مسیریاب، درخت پوشایی را ایجاد می‌کند که تمام مسیریابهای موجود در زیر شبکه را در بر گیرد. بعنوان مثال در شکل 13 (الف) زیر شبکه‌ای با دو گروه 1 و 2 وجود دارد. بعضی از مسیریابها به میزبانهایی دست یافتند که متعلق به یک یا هر دو گروه است (همانطور که در شکل آمده است). درخت پوشای مربوط به مسیریاب سمت چپ، در شکل 13 (ب) آمده است.

وقتی فرایندی بسته چند پخشی را به گروهی می‌فرستد، اولین مسیریاب، درخت پوشای خود را بررسی کرده آن را هرس می‌کند. برای این کار تمام خطوطی را که به میزبانهایی می‌روند که عضو این گروه نیستند حذف می‌کند. در مثال مورد نظر ما شکل 13 (ج) درخت پوشای هرس شده مربوط به گروه 1 را نشان می‌دهد. شکل 13 (د) درخت پوشای هرس شده مربوط به گروه 2 را نشان می‌دهد. بسته‌های چند بخضی فقط از طریق درخت پوشای مناسبی ارسال می‌گردند.

راه‌های گوناگونی برای هرس کردن درخت پوشا وجود دارد. ساده ترین آنها وقتی مورد استفاده قرار می‌گیرد که از مسیریاب حالت پیوند استفاده گردد و هر مسیریاب از توپولوژی کامل زیر شبکه آگاهی داشته باشد از جمله بداند کدام مسیریاب به کدام گروه‌ها تعلق دارند. سپس درخت پوشا را می‌توان با شروع از انتها هر مسیر و ادامه دادن به سمت ریشه هرس کرد برای این کار باید تمام مسیریابهایی را که متعلق به گروه مورد نظر نیستند حذف کرد.

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

یکی از عیب‌های این الگوریتم این است که در شبکه‌های بزرگ به خوبی کار نمی‌کند فرض کنید شبکه‌ای دارای n گروه است و هر گروه به طور متوسط دارای m عضو است. برای هر گروه m درخت هرس شده پوشا باید ذخیره گردد و در نتیجه تعداد کل درختها mn است. وقتی گروه‌ها بزرگ باشند حافظه زیادی برای ذخیره همه درختها لازم است.

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

مسیریابی برای میزبانهای سیار

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

مدل میانی که طراحان از آن استفاده می‌کنند در شکل 14 آمده است در اینجا یک شبکه گسترده وجود دارد که حاوی مسیریابها و میزبانها است. شبکه‌های محلی و شهری و سلول‌های بی سیم به این شبکه گسترده  متصل‌اند.

میزبان‌هایی که حرکت نمی‌کنند (ثابت اند) از طریق سیم‌های مسی یا فیبر نوری به شبکه وصل می‌شوند. بر عکس دو نوع میزبان دیگر وجود دارند. میزبانهای مهاجر میزبانهای ثابتی‌اند که گاهی از یک سایت ثابت به سایت ثابت دیگر منتقل می‌شوند اما فقط وقتی از شبکه استفاده می‌کنند که به طور فیزیکی به آن وصل باشند. میزبانهای متحرک کسانی هستند که در حال حرکت نیز به شبکه متصل اند. این دو نوع میزبان را میزبانهای سیار می‌نامند.

 

فرض می‌شود تمام میزبانها موقعیت داخلی ثابتی داشته باشند که هرگز تغییر نکند. میزبانها آدرس داخلی ثابتی نیز دارند که محل آنها را مشخص می‌کنداین حالت را با شماره تلفن [phone] مقایسه کنید که نشان دهنده ایالات متحده (کد کشور1) و جزیره مان هاتان (212) است. هدف مسیریابی در سیستمی با میزبانهای سیار، عبارت است از: ارسال بسته‌ها به میزباهای سیار به کمک آدرسهای داخلی آنها، و خواندن بسته‌ها توسط میزبانها در هر جایی که هستند.

در مدل شکل 14 جهان ( از نظر جغرافیایی) به واحدهای کوچکی تقسیم شده است. این واحدها را ناحیه می‌نامیم به طوری که هر ناحیه یک شبکه محلی یا سلول بی سیم است هر ناحیه دارای یک یا چند نمایندگی خارجی است است که فرایندهایی هستند که تمام میزبانهای سیار ناحیه را نگهداری می‌کند بعلاوه هر ناحیه دارای نمایندگی داخلی است. این نمایندگی میزبانهایی را که خانه شان در این ناحیه قرار دارد ولی فعلا با ناحیه دیگری در حال ملاقات‌اند نگهداری می‌کند.