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

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

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

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

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

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

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