بخشی از مقاله
چکیده
دستهبندی بستهها یکی از پردازشهای اساسی در بسیاری از سیستمهای شبکهای است که توسط پردازندههای شبکهای اجرا میگردد. دستهبندی بستهها فرآیندی خودکار است که جریانهای ترافیکی شبکه را بر اساس قانونهایی مشتمل بر پارامترهای متعدد از جمله پورت و آدرس فرستنده و گیرنده دستهبندی مینماید. مهمترین شاخص کارایی الگوریتمهای دستهبندی بستهها، سرعت جستجو جهت یافتن بهترین قانون منطبق بر اطلاعات سرآیند بسته میباشد. دستهبندهای موجود تنها از ایده کاهش پیچیدگی الگوریتم جستجو برای افزایش سرعت دستهبندی بستهها استفاده میکنند؛ نگاهی به عملکرد دستهبندهای بسته، در یک بازه زمانی نشان میدهد که فراوانی تطابقهای هر قانون دستهبند با بستههای ورودی در گذر زمان متغیر است.
این مشاهده کلیدی انگیزه اصلی برای طراحی دستهبندهای ترافیک-آگاه است. در این پژوهش روش ترافیک -آگاه جدیدی برای دستهبندی بستهها، با هدف کاهش تعداد دسترسیها به حافظه و در نتیجه افزایش سرعت جستجو ارائه شده است. در روش ارائه شده قانونها در یک درخت تاشونده1قرار گرفته و از ویژگیهای آماری بستههای ورودی در کنار ویژگیهای ساختاری مجموعه قانونها، برای تغییر ساختار آن با هدف تسریع تطبیق با قانونهای پرتطبیق استفاده شده است. نتایج ارزیابی روش پیشنهادی با مجموعه قانونها و بستههای آزمون نشان میدهد که میانگین تعداد دسترسیها به حافظه برای دستهبندی بستهها تا حد قابل ملاحظهای کاهش یافته است.
واژگان کلیدی: دسته بندی بسته ها، درخت تاشونده، چرخش.
مقدمه
فرایند اختصاص یک برچسب نوع یا جریان به بستهها را، دستهبندی بستهها می نامند - Srinivasan et al, . - 2006 عملیات دستهبندی بسته به ازای هر بسته و بر اساس اطلاعات موجود در سرآیند بسته صورت میگیرد. اطلاعات موجود در فیلدهای مشخص سرآیند بسته با قوانینی با اولویتهای متفاوت انطباق داده شده و در نهایت به بسته مذکور یک برچسب نوع یا جریان داده میشود. نمایی از چگونگی انجام عمل دستهبندی بسته در شکل 1 امده است. طیف وسیعی از ابزارهای پرداشگر بستهها شامل دیوارههای آتش، سیستمهای تشخیص نفوذ، مسیریابها، سیستمهای مدیریت شبکه و سیستمهای مدیریت حساب کاربران از دستهبندی بستهها استفاده میکنند.
با رشد چشمگیر سرعت شبکه و افزایش تعداد کاربران اینترنت، افزایش سرعت تصمیمگیری در مورد بستههای دریافتی در ابزارهای پردازشگر بستههای اینترنتی امری ضروری است. بیشتر الگوریتمهای دستهبندی بسته فعلی از ویژگیهای مجموعه قوانین دستهبند بدون در نظر گرفتن رفتار ترافیک بستههای ورودی، برای افزایش سرعت جستجو در ساختار دادهی خود استفاده میکنند . تحقیقات نشان میدهد که جریانهای بستههای اینترنت دارای ویژگیهایی هستند که میتوان از این ویژگیها در افزایش سرعت جستجو در دستهبند بستهها استفاده کرد - . - Lan & Heidemann, 2003 مطالعات آماری انجام شده روی ردیابیهای مختلف ترافیک اینترنت نشان میدهدکه بخش عظیمی از ترافیک اینترنت توسط تعداد کمی از جریانهای بلندمدت یا جریانهایی با تعداد بستههای زیاد حمل میشود و در نتیجه بخش مهمی از ترافیک اینترنت فقط با زیرمجموعهای کوچکی از قوانین دستهبند بستهها مطابقت دارد - -El-Atawy, Hamed, & Al . - Shaer, 2005
در صورتی که قوانین مذکور با تعداد دسترسیهای حافظه کمتری در حافظه سیستم دستهبند در دسترس باشند، زمان دستهبندی بستهها کاهش مییابد. از این رو طراحی الگوریتم آگاه از ترافیک که ساختار داده قوانین در آن با توجه به سابقه ترافیک بستهها با هدف کاهش دسترسی به قوانین پرکاربرد بهروز شود اهمیت زیادی دارد. بنابراین، در این مقاله روشی برای کاهش تعداد دسترسیها به حافظه ارائه خواهیم کرد. روش ارائه شده مبتنی بر درخت تاشونده میباشد و ساختار آن بهصورت پویا متناسب با الگوی ترافیک بستههای ورودی تغییر میکند.ساختار مقاله بدین صورت میباشد که در بخش دوم کارهای انجام شده بررسی خواهد شد. بخش سوم روش پیشنهادی و جزئیات پیاده سازی آن توضیح داده میشود. در بخش چهارم نتایج ارزیابیها مورد بررسی قرار میگیرد. در نهایت، در بخش آخر نتیجهگیری و سوی کارهای آتی مطرح میشود.
کارهای انجام شده
پژوهشهای متنوعی در زمینهی استفاده از ویژگیهای جریانهای ترافیک اینترنت، برای افزایش سرعت جستجو در دستهبندی بستهها صورت گرفته است. - Bergamini & Kencl, 2005 - برای افزایش سرعت جستجو، روشی به نام شبکهای از میانبرها را در ساختاردادههای درختی ارائه دادند. در روش پیشنهادی آنها، برای قرار دادن میانبرها بر روی درخت از یک الگوریتم مکاشفهای استفاده میشود تا تعداد دسترسیها به حافظه کاهش یابد. - Srinivasan et al, 2006 - برای کاهش میانگین زمان دستهبندی بستهها از مدل درخت تاشونده و روش تبدیل پیشوند آدرس آی پی مبدا و مقصد به مقادیر عددی استفاده کردند. در درخت تاشونده هر گرهای که مورد دسترسی قرار میگیرد بلافاصله به ریشه درخت منتقل میشود.
- El-Atawy et al, 2005 - برای افزایش سرعت جستجو یک درخت الفبایی به ازای هرفیلد از قوانین ایجاد کردند. این درخت های الفبایی به منظور ایجاد یک درخت آماری بهینه با یکدیگر ترکیب میشوند. درخت الفبایی به صورت دوره ای بروزرسانی میشود. - Hamed & Al-Shaer, 2006 - برای کاهش میانگین زمان جستجو روش مرتب سازی پویای قوانین را ارائه دادند. در این روش به هر قانون بر حسب 2 فاکتور فراوانی انطباق و تازگی قانون یک وزن داده میشود. سپس یک درخت Max-Heep از قوانین بر اساس وزن آنها ساخته میشود. ساختار درخت Max-Heep بصورت دورهای بروزرسانی و قوانین دارای وزن بیشتر در بالای درخت قرار میگیرند. - El-Atawy et al, 2007 - برای افزایش سرعت جستجو از قطعهبندی فضای ترافیک برای ایجاد یک درخت هافمن بر روی قطعهها استفاده کردند.
در این روش فضای ترافیک به زیر مجموعهای از قطعههای مجزا تقسیم میشود. به هر قطعه یک وزن اختصاص داده میشود. هر گاه بستهای با قطعهای تطبیق یابد، وزن قطعه افزایش میابد. درخت هافمن با توجه به وزن جدید قطعهها بصورت دورهای بازسازیشده و قطعههای دارای وزن بیشتر به سمت بالای درخت انتقال پیدا میکنند. - Shaikot & Kim, 2009 - الگوریتم NPF را برای کاهش میانگین زمان جستجو ارائه دادند. این الگوریتم از روش چرخش بر روی درخت دودویی برای سازگاری عمل دستهبندی بستهها با الگوی ترافیک بستههای ورودی استفاده میکند.بررسی کارایی روشهای ذکر شده نشان میدهد که روش ارائه شده در - Srinivasan et al, 2006 - که از مدل درخت تاشونده برای دستهبندی بستهها استفاده میکند کارایی بهتری نسبت به روشهای دیگر دارد.
نکته قابل توجه در مورد این روش آن است که ساختار داده مورد استفاده انعطاف پذیر است و میتوان در آن از سابقه ترافیک در بازههای زمانی برای انجام تغییرات خاص در جهت کاهش تعداد دسترسی به قوانین پرکاربرد استفاده نمود. نقطه ضعف اساسی پیادهسازی این روش در - Srinivasan et al, 2006 - آن است که هرگاه گرهای با بسته ای منطبق میشود بلافاصله با انجام عملیات چرخش به ریشه درخت منتقل میشود. انجام عملیات چرخش به ازای هر گره مورد دسترسی واقع شده، باعث افزایش تعداد دسترسیها به حافظه، تغییرات ساختار درخت و در نتیجه افزایش سربار ناشی از بروزرسانی درخت میشود. در این مقاله روشی برای دسته
