فنی تخصصی

ابتدا یک توضیح اجمالی ....

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

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

اگرچه امروزه همروزه اکثر پروتکل ها ی مسیریابی multicast مورد استفاده در اینترنت مبتنی بر کوتاهترین مسیر هستند.....چرا که :اولا برای پیاده سازی آسان هستند ،ثانیا کمترین تاخیر از فرستنده به گیرنده را دارند.که این برای برنامه های کاربردی چند پخشی خصوصیتی مطلوب است .

پروتکل های مسیریابی multicast  برای wireless mobile ad hoc network  در دو دسته طبقه بندی میشوند :

1)    مبتنی بر درخت

2)    مبتنی بر شبکه

مطالعات نشان داده که در یک wireless mobile ad hoc network جاهایی که توپولوزی شبکه مدام تغییر میکند ،پروتکل مبتنی بر شبکه از مبتنی بر درخت کارآمد تر است ...چرا که : در آن زمانی که یک  یا چند  مسیر خراب شوند مبتنی بر شبکه میتواند مسیرهای دیگری را برای انتقال داده پیشنهاد کند.

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

 کوتاهترین مسیر        (Shortest path tree algorithms: SPT)                                     

کمترین هزینه                    (minimum cost tree algorithms)

درخت محدود                        (constrained tree algorithms)

                         

الگوریتم کوتاهترین مسیر (shortest path tree algorithms :SPT)

هدف الگوریتم spt ،محاسبه کردن ریشه درخت در فرستنده و و محدوده گیرنده ها به طوری که فاصله بین فرستنده و هر گیرنده در درخت کمترین باشد.

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

 هرگاه چندین منبع فرستنده برای multicast داشتیم ، به این علت که STP درهرفرستنده تعریف میشود پس برای هر فرستنده باید جداگانه باید tree  Multicast محاسبه شود.

الگوریتم بردار- فاصله :

هر مسیریاب یک جدول که نشان دهنده بهترین مسیر شناخته شده تا هر مقصد و نحوه رسیدن به آن مقصد است را ذخیره میکند.

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

 خو د می کند.

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

الگوریتم حالت لینک :

ü    هر مسیریاب باید همسایگانش را شناسایی نماید و آدرس شبکه آنها را یاد بگیرد.

ü    تاخیر و هزینه رسیدن به هر یک از همسایگانش را اندازه گیری کند.

ü    آنچه را که یاد گرفته است در قالب یک بسته اطلاعاتی در آورد واین بسته اطلاعاتی را به کلیه مسیریاب های دیگر ارسال کند.

ü    کوتاهترین مسیر تا هر یک از مسیریاب های دیگر را حساب کند .

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

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

 

الگوریتم درخت  کمترین هزینه (minimum cost tree algorithms)

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

مشکل یافتن درخت چند پخشی کمترین هزینه به کمترین  Steiner tree معروف است،کهNP-complete است. چندین راه حل  که Steiner tree تقریبی را محاسبه میکند وجود دارد.

حال شرح مختصری از راهبرد جست وجوی اگاهانهmst)) Steiner tree  minimum را بیان میکنیم.

 MST  Heuristic

برای یافتن minimum Shortest tree  داده های زیر مفروض است :

–   گراف همبند بدون جهت G=(V,E ,d)

–   sبعنوان مجموعه ای ازpoint Steiner و زیر مجموعه ای از    رئوس V که درV آن مجموعه رئوس

–  E مجموعه لبه

–  D  تابع فاصله ای که مجموعه ای از اعداد نامنفی را به لبه های گراف نگاشت میکند.

    توجه کنید گراف کامل بدون جهت G₁=(V₁,E₁,d₁) از G ساخته شده است و V₁= S ،برای هر لبه E₁ بین دو راس( v_i ,v _j) فاصله ( v_i ,v_j)  dبا کوتاهترین مسیربین دو راس v_i و v_j در گراف برابر است. توجه کنید که هر لبه در G₁ با کوتاهترین مسیر در گراف G برابر است.

مراحل الگوریتم هیوریستیک mst عبارتند از :

1.   گراف کامل بدون جهت G₁=(V₁,E₁,d₁) را از Gو S بسازید.

2.   مینی موم درخت پوشای T₁ از G₁ را بیابید.

3.   زیر گراف G_s از G را با جایگزین کردن هر لبه T₁ بوسیله مشابه کوتاهترین مسیر آن در G بسازید .

4.   مینی موم درخت پوشای T_s از G_s را بیابید.

5.درخت Steiner  ، T_hرا از T_s بوسیله پاک کردن لبه ها در T_s بسازید.

 

      الگوریتم درخت محدودیت    (constrined tree algorithms)

الگوریتم کوتاهترین مسیر سعی میکند فاصله بین گیرنده وفرستنده را به حداقل برساند و دیگر اینکه سعی میکند تا تاخیر انتها به انتها را کمینه کند.

الگوریتم mst تلاش میکند تا هزینه کلی درخت را کمترین کند.برای ما مطلوب است که هر دو کمینه باشند.

حال پروتکل های مسیریابی در که مورد استفاده (یا پیشنهاد شده) در اینترنت هستند را بیان میکنیم :

Ë          DVMRP

Ë          MOSPF

Ë          PIM

Ë          CBT

 1-   در رترها هرگز جدول مسیریابی ایجاد نمیشود.

2-   DVMRP پروتکلی است که برای ساخت tree Multicast ازاتشار سیل مانند ((flooding و از هرس (pruning) استفاده میکند.

3-    مراحل چهارگانه الگوریتم DVMRP

1.  : Floodingدر این مرحله بسته ها broadcasts میشوند که این باعث ایجاد   loopدر سیستم میشود.
2. Reverse Path Forwarding (RPF) : حلقه های ایجاد شده در مرحله Flooding را حذف میکند.
3. Reverse Path Broadcasting (RPB):  RPBدرخت کوتاهترین مسیر  broadcast را از فرستنده تا هر گیرنده پیدا میکندو نیز تضمین میکند هر گیرنده تنها یک کپی از بسته را دریافت میکند.
4. Reverse Path Multicasting (RPM): به منظور ایجاد کوتاه ترین مسیر درخت با توجه به تغییرات داینامیک شبکه  RPM مسیرهایی از درخت را به درخت اضافهgraft)  ) یا از آن کم (هرس: prune) میکند.

 

 MOSPF

(Multicast Extensions to Open Path First)

 

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

بعد از اعلام رترها در مورد وضعیت اتصالشان به شبکه،Link State Database ایجاد میشود، که حاوی: شناسه رتر ، رترهای همسایه ،هزینه تا هر رتر همسایه میباشد.

MOSPF :

˜  توسعه یافته OSPF است.

˜   اطلاعات لینک وضعیت شامل اعضای گره است.

˜   هر رتر توپولوژی کامل مسیریابی شبکه را میداند.

˜   کوتاهترین مسیر درخت ها بنا بر درخواست ایجاد می شوند( زمانی که اولین بسته می رسد.)

˜  وقتی بسته برای ارسال میرسد ،چنانچه آن بسته در گروه باشد الگوریتم کوتاهترین مسیر را محاسبه میکند ونتایج محاسبات ذخیره میشود.

˜  یک پرتوکل مسیریابی از نوع حالت لینک (Ls) می باشد .

˜    معیار هزینه تعداد گام نیست .

˜     در این پرتوکل حجم بار و پهنای باند لینک یک مسیریاب در محاسبه ی بهترین مسیر    دخالت داده می شود .

   این پروتکل دارای خاصیت پخش بار می باشد که برای کاهش حجم پردازش شبکه را به چندین ناحیه (Area) تقسیم می کند. هر ناحیه با یک شماره مشخص می شود.