مقاله سیاست حذف بسته براساس ویژگی‌های بسته در شبکه‌های تحمل‌پذیر تأخیر

بخشی از مقاله

چکیده

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

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

کلمات کلیدی:شبکههای تحملپذیر تأخیر، مدیریت بافر، بازپخشی، نرخ حذف بسته، نرخ سربار، نرخ تحویل

-1 مقدمه

در سال 2002 میلادی، ایده شبکههای تحملپذیر تأخیر ارائه شد. شبکههای تحملپذیر تأخیر نوعی از شبکههای موردی سیار هستند که در آنها به دلیل تحرک بالا، تراکم کم و پراکندگی گرهها، اتصال کامل بین گرهها در سراسر شبکه برقرار نیست .[2] به همین دلیل الگوریتمهای مسیریابی رایج، در این نوع شبکهها قابل نیستند. معماریها و پروتکلهای موفق امروزی مانند پروتکل TCP/IP در مسیرهایی با تأخیر دائم یا طولانیمدت و یا به هنگام تکهتکه شدن توپولوژی شبکه مقاوم نیستند و بسیار ناموفق عمل میکنند .[1] همچنین تحرک گرهها بر گذارا بودن ارتباط بین گرهها میافزاید.

بهمنظور مقابله با خاصیت ناپایداری لینکها در شبکههای تحملپذیر تأخیر از رویکرد ذخیرهBحملBارسال استفاده میشود .[4] در این رویکرد، گره مبدأ پیام را دریافت میکند؛ از آنجاییکه ممکن است در همان لحظه گره بعدی برای ارسال پیام در دسترس نباشد، پیامها در بافر گرههای متحرک ذخیره شده و همراه با آنها حمل میشوند و هنگامی که فرصتی برای ارتباط با گره دیگری به وجود بیاید، به گره بعدی ارسال میشوند .[4] علاوه بر این با توجه به عدم قطعیت ارتباط بین گرهها، گره اغلب نیاز به توزیع نسخههای متعدد پیام به سایر گرههای همسایه دارد تا بدینوسیله احتمال تحویل بسته افزایش یابد.

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

· سیاستهایی که تنها به اطلاعات محلی پیامها وابسته است مانند زمان تحویل پیام، TTL3 و اندازه پیام.

·سیاستهایی که بر اساس اطلاعات کامل سطح شبکه تصمیمگیری میکنند .[5] مانند تعداد گرههای شبکه، تعداد کل کپیهای پیام، نرخ ملاقات بین دو گره.

در بین سیاستهای مدیریت بافر موجود، سیاستهای مبتنی بر اطلاعات عمومی شبکه نتایج خوبی را فراهم میکنند، اما نیازمند به کارگیری روشهای دشوار برای به دست آوردن اطلاعات عمومی شبکه نظیر - تعداد گره در شبکه، تعداد کپیهای بسته، نرخ ملاقات و غیره - هستند و پیادهسازی این روش به دلیل پراکندگی گرهها مشکل است .[8] در این مقاله، سیاست مدیریت بافر پیشنهادی به نام PDP4 مبتنی بر اطلاعات محلی شبکه است که با کاهش تعداد بستههای حذف شده از بافر احتمال تحویل بستهها را افزایش داده و با کاهش تعداد بستههای پخش شده در شبکه از اتلاف منابع شبکه نظیر بافر جلوگیری میکند.

-2 کارهای گذشته

مدیریت بهینه بافر از مسائل مطرح در شبکههای تحملپذیر تأخیر است. انتخاب صحیح سیاستهای حذف پیام تا حد زیادی عملکرد شبکههای تحملپذیر تأخیر را تحت تاثیر قرار میدهد .[2] زمانی که بافر گره پر شود و یک پیام جدید خواستار ورود به گره باشد، لازم است سیاستهای مدیریت پیام برای تصمیمگیری در مورد انتخاب حذف مناسبترین پیام اتخاذ شود .[3] محققان عملکرد برخی از سیاستهای مدیریت بافر را ارزیابی کردهاند که در ادامه به توضیح آنها پرداخته میشود. سیاستهایی که تنها از اطلاعات محلی به جای اطلاعات گستردهی سطح شبکه برای تصمیمگیری در مورد حذف پیام در صورت سرریز بافر استفاده میکنند عبارتند از:

• حذف تصادفی-:DR5 بهصورت تصادفی یکی از پیامهای موجود در صف بافر گره را حذف میکند .[4]

•حذف آخرین بسته دریافت شده :DLR6- در اینروش بسته با مدت زمان اقامت طولانی در بافر حذف میشود.[4]

•حذف قدیمیترین بسته :DOA7- بسته با طول عمر

کوتاهتر - TTL - برای حذف انتخاب میشود. ایده این است که اگر - TTL - بسته کوچک است یعنی برای مدت زمان طولانی در بافر است، در نتیجه به احتمال بالا در حال حاضر تحویل داده شده است، پس حذف میشود .[4]

·حذف آخرین بسته :DL8- آخرین بسته دریافتی در این روش حذف میشود .[4]

• حذف اولین بسته :DF9- در این روش بستهای که به اول صف میرود اولین بستهای است که حذف میشود .[4] این سیاست از رویکرد FIFO - اولین ورودی، اولین خروجی - بر اساس زمان دریافت پیامها پیروی میکند. اولین پیامی که وارد صف بافر شده است، اولین پیامی است که در صورت سرریز از صف بافر گره حذف میشود.

•  حذف بسته با N بار ارسال :N- DROP در این سیاست، پیامی که N بار به گرههای دیگر ارسالشده است، حذف میشود. اگر تعداد دفعات ارسال هیچکدام از پیامها به مقدار N نرسیده باشد، آخرین پیامی که وارد صف شده است را حذف میکند. در این روش انتخاب صحیح مقدار N از اهمیت ویژهای برخوردار است .[7]

• حذف بزرگترین بسته-:DLA10 این روش بسته با اندازه بزرگ را حذف میکند .[6]

•حذف بسته با بیشترین تعداد ارسال:MOFO11 دراین سیاست بستهای که به حداکثر تعداد بار ارسال شده است، حذف میشود .[2] به منظور به حداکثر رساندن پراکندگی پیامها در شبکه، این سیاست مستلزم این است که عاملهای مسیریابی تعداد دفعات ارسال هرکدام از پیامها را نگهداری و ثبت نمایند. پیامی که بیشترین تعداد ارسال را داشته باشد، در صورت ازدحام در بافر زودتر حذف میشود؛ بنابراین به پیامها با تعداد دفعات ارسال کمتر شانس بیشتری جهت ارسال به سایر گرهها داده میشود. بنابراین سیاستهای مبتنی بر اطلاعات محلی مطرح میشود. در بین سیاستهای مدیریت بافر مبتنی بر اطلاعات محلی، سیاست MOFO به دلیل نرخ تحویل بالا بسیار مورد توجه است. در این روش با حذف پیامهایی که در حال حاضر به بسیاری از گرههای دیگر ارسال شدهاند، میتوان اطمینان حاصل کرد که پیامهایی حذف شدهاند که بیشتر در شبکه پخش شدهاند و خطر حذف پیام را بدون اینکه حتی یک بار ارسال شده باشد را کاهش میدهد و احتمال رسیدن پیام به مقصد را افزایش میدهد [2]، این روش در حذف بستهها اندازه آنها را در نظر نمیگیرد، در حالیکه به نظر میرسد با در نظرگیری اندازه بستهها به همراه تعداد تکرار آنها تعداد بستههای حذف شده کاهش یابد.

•  حذف بسته با بالاترین پیشبینی ارسال -:MOPR12 در این سیاست برای هر پیام موجود در صف بافر گره احتمال ارسال FP13 پیشبینی میشود. در ابتدا مقدار FP برای هر پیام صفر تعیینشده است. با هر بار ارسال پیام مقدار FP تغییر میکند، مقدار P احتمال تحویل پیام به گره دریافتکننده است .[2] در صورت سرریز بافر، ابتدا پیام با حداکثر مقدار FP برای حذف انتخاب میشود. سیاست MOPR را میتوان بهعنوان نسخهی وزن دهی شدهی MOFO در نظر گرفت. در این سیاست بهجای افزایش عددی تعداد دفعات ارسال هر پیام، احتمال تحویل پیام به سایر گرهها جهت رسیدن به مقصد محاسبه میشود.

•  حذف بسته با کوتاهترین طول عمر :SHLI14- این سیاست بسته با کوچکترین TTL را حذف میکند .[2] در معماری شبکههای تحملپذیر تأخیر، هر پیام دارای طول عمر مشخصی است که نشان میدهد از آن زمان به بعد پیام قابل استفاده نیست و باید حذف شود. در صورت استفاده از این سیاست پیامی که کمترین TTL را دارد، برای حذف انتخاب میشود.

•  حذف بسته بر اساس مقدار آستانه:T-DROP در این روش در محدودهی اندازهی پیامها یک مقدار آستانه تعریف میشود. پیامی که به مقدار آستانه نزدیکتر است، برای حذف انتخاب میشود.[8]در سال 2008، Krifa و همکاران استراتژی مطلوب مدیریت بافر مبتنی بر اطلاعات عمومی سطح شبکه را ارائه دادند .[9] آنها با استفاده از یک الگوریتم توزیعشده و یادگیری آماری تابع سودمندی هر پیام را استخراج میکردند. مقدار سودمندی تابعی از وضعیت عمومی پیام در شبکه است. تابع سودمندی بر اساس دو پارامتر محاسبه میشود: حداکثر متوسط نرخ تأخیر و حداقل متوسط نرخ تحویل. سیاستهای مبتنی بر اطلاعات عمومی شبکه عبارتند از:

•سیاست:GBD15 این سیاست حذف پیام براساس اطلاعات عمومی GBSD با استفاده از اطلاعات عمومی شبکه، تابع سودمندی پیام را محاسبه میکند.    پیادهسازی این روش نسبتاً دشوار است. GBSD دارای دو بخش اصلی است: - 1 زمانبندی که نحوهی ارسال پیام بر اساس متریکهای مشخص شده را تعیین میکند. - 2 در صورت سرریز بافر پیام مناسب برای حذف را انتخاب میکند.

•سیاست :HBD16 این سیاست مبتنی بر پیشینه، نسخهی قابل پیادهسازی GBD است که توسط Krifa ارائه شده است. در این روش برای بهینه کردن متریکهای یک مسیریابی خاص با استفاده از GBD نیاز به اطلاعات عمومی سطح شبکه و نحوه توزیع پیامها است.[9] در عمل برای هر پیام موجود در بافر گره، لازم است تعداد گرههایی که تاکنون پیام را مشاهده کردهاند و تعداد گرههایی که دارای نسخهای از آن پیام هستند، تخمین زده شود.

·سیاست :FBD17 اساس متریکهای متوسط نرخ تحویل پیام و متوسط تأخیر پیام محاسبه میکند. سیاست FBD با ارسال سیلآسای اطلاعات در سطح شبکه بدون در نظر گرفتن پیشینهی پیام و نحوهی ارتباط با دیگر پیامها تابع سودمندی را محاسبه میکند .[9]در بین سیاستهای مدیریت بافر موجود، سیاستهای مبتنی بر اطلاعات عمومی شبکه نتایج خوبی را فراهم میکنند، اما نیازمند به کارگیری روشهای بسیار پیچیده برای به دست آوردن اطلاعات عمومی شبکه نظیر - تعداد گره در شبکه، تعداد کپیهای بسته، نرخ ملاقات و غیره - هستند و پیاده سازی این روش دشوار است .[8] در بین سیاستهای مدیریت بافر مبتنی بر اطلاعات محلی، سیاست MOFO بهترین عملکرد را از نظر تأخیر تحویل و نرخ تحویل دارد، اما این روش پخش بالای پیام و افزایش تعداد گام را به دنبال دارد و نیازمند برخی بهبودها است. در ادامه به شرح روش پیشنهادی پرداخته میشود.

-3 روش پیشنهادی

در شبکههای تحملپذیر تأخیر وجود تعداد زیادی نسخه از پیام در شبکه احتمال تحویل را افزایش میدهد اما موجب اتلاف منابع شبکه نظیر بافر میشود. بنابراین وجود سیاست مدیریت بافر ضروری است. در این بخش سیاست مدیریت بافر PDP ارائه شده است که براساس اندازه بسته ورودی و تعداد ارسالهای قبلی پیامها، بستهای را حذف میکند. در روش پیشنهادی به ازای ورود یک بسته، احتمال حذف فقط یک بسته وجود دارد، بنابراین تعداد بستههای حذف شده کم و احتمال تحویل افزایش مییابد. همچنین روش پیشنهادی PDP با در نظر گرفتن تعداد ارسالهای بسته، اطمینان حاصل میکند که بستهای حذف شود که در سطح شبکه بیشتر منتشر شده است و خطر حذف پیام، بدون اینکه حتی یک بار در شبکه فرستاده شده باشد، را کاهش میدهد.