بخشی از مقاله
چکیده
طبقهبندی بستهها یکی از مهمترین عملکردها در سوئیچها میباشد. با ظهور شبکههای نرم افزار محور به دلیل ساده شدن تعیین سیاست و ارسال آنها به سوئیچها از طریق کنترلرها و لزوم طبقه بندی بستهها برای برخی سرویسهای جدید - مثلاً سرویسهای چندرسانهایی - و روند افزایش تعداد فیلدها در جدول جریان، اهمیت طبقه بندی بستهها در این حیطه نمود بیشتری میکند. یکی از روشهای ارتقاء کیفیت طبقهبندی بستهها، تغییر در نحوه جستجوی فیلدها و تمرکز بر روی تعداد فیلد بیشتر از شبکههای سنتی - 5 فیلد - میباشد.
یکی از محبوبترین متدهای دسترسی، ساختار داده درخت مستطیلی میباشدکه به دلیل وِیژگیهای بارزی همچون تسهیل بروزسانی پویا، زمان و حافظه مصرفی کارآمد و غیره برای طبقهبندی 15 بعدی بستهها از این ساختار استفاده کردیم. با استفاده از مجموعه قوانین و سرآیند بستههایی 15 فیلدی - توسعه یافته - ClassBench که تولید کردیم، طبقهبندی بستهها را در شرایط یکسان انجام دادیم. برای ارزیابی این ساختار داده از درخت HyperCuts استفاده کردیم. نتایج نشان دادند که هر دو ساختار با افزایش تعداد قانون کارایی آنها کاهش مییابد، اما درخت مستطیلی در بیشتر موارد نسبتاً خیلی بهتر از HyperCuts عمل میکند.
-1 مقدمه
عصر جدید که میتوان آن را "عصر جامعه دیجیتالی" نامید به وسیله تکنولوژیهای مبتنی بر شبکهبندی محقق میشود؛ همواره این عرصه در حال پیشرفت روزافزون است. دستگاههای شبکهبندی مثل روترها، سوئیچها، پلها و دیگر دستگاههای ارسال اطلاعات نیز از این پیشرفت مستثنی نبوده اند. گرچه در سالهای اخیر، شبکهها با پیشرفت قابل توجهی مواجه بودهاند، اما همچنان با مشکلات و چالشهای مهمی روبرو هستند.
از جمله این مشکلات و چالشها میتوان به عدم مقیاسپذیری، خودمختاری دستگاههای قدیمی و پیاده سازی سخت سیاستهای شبکه برای مدیران شبکه و نبود یک کنترل و دید یکپارچه نسبت به کل شبکه، اشاره کرد. در معماری نوظهور شبکه نرمافزار محور، بخش کنترلِ شبکه از بخش انتقال ترافیک مجزا بوده و بطور مستقیم برنامهریزی میشود که این رویه چالشهای مذکور را مرتفع میسازد و مزایایی همچون انعطافپذیرییشترِب شبکه، عدم وابستگی به سخت افزار، کاهش هزینه و غیره را برای شبکه به ارمغان میآورد
بخش عمدهایی از قابلیتها و مزایای شبکه نرمافزار محور مرهون روش مدیریت ترافیک آن است. وظیفه انتقال ترافیک یا ارسال بستهها بر عهده دستگاههایی مثل روتر و سوئیچ میباشد؛ در این دستگاهها حافظهایی منحصر به فرد به نام CAM وجود دارد که عمل جستجو را در جدولی به نام جدول جریان که در سوئیچها قرار دارد، انجام میدهد. جدول جریان را میتوان قلب تجهیزات ترافیک داده دانست. سیاستهای کنترلی از طرف کنترلر به صورت یکسری جریان - به صورت یک قانون - در جدول جریان سوئیچ ذخیره میشود. این جدول شامل تعدادی مدخل است که هر مدخل شامل تعدادی فیلد سرآیند، شمارندهها و دستورالعمل است.
وقتی بستهایی از پورت ورودی - مثلاً از کنترلر شبکه - وارد سوئیچ میشود؛ برای اینکه بفهمد که با این بسته چه کار کند؛ فیلدهای سرآیند بسته استخراج میشود و با فیلدهای قانونهایی که درون جدول جریان وجود دارد مقایسه میشود. در صورت مطابقت با یک قانون خاص، دستورالعمل مربوطه اجرا میشود و در صورت عدم مطابقت با مدخل بعدی مقایسه میشود و این روند تا پیدا کردن مدخل مربوطه و اجرای دستورالعمل مربوط به آن، تا آخرین مدخل دنبال میشود.
درصورتیکه هیچ مدخلی با آن مطابقت داده نشود، بسته مربوطه مطابق با سیاستی که کنترلر برای آن در نظر گرفته است، آن بسته را حذف کرده و یا اینکه آن را برای کنترلر ارسال میکند6]،4،.[3 به عبارت دیگر، جدول جریان یک جدول Look up است که هدایت و طبقه بندی بستهها از طریق این جدول انجام میشود. طبقهبندی بستهها به این دلیل صورت میگیرد که لایه انتقال سیستم نیاز دارد تشخیص دهد که بسته متعلق به کدام اتصال خاص است.[5] به طورکلی طبقهبندی بستهها، برای اعمال مانیتورینگ، مدیریت، امنیت شبکه - کاربرد در برخی نرم افزارهای امنیتی - ، Qos اهمیت بسزایی دارد؛ سرعت و کارایی الگوریتم طبقه بندی بستهها در زمان تأخیر شبکه تأثیر زیادی خواهد داشت.
مطابقت بستهها به صورت مختلفی همچون مطابقت کامل، مطابقت دامنهایی، مطابقت پیشوندی انجام میشود. در شبکههای سنتی فیلدهای 5 فیلد: آدرس مبدأ و مقصد، پورت مبدأ و مقصد، پروتکل، برای مطابقت بسته با قوانین پیش تعریف در نظر گرفته شده بود. با پیشرفت شبکه و معماری جدید اینترنت، نوع کاربرد و برنامههای کاربردی، فرمت جدید رسانه، نیاز به فیلدهای بیشتری برای مطابقت استاندارد احساس شد که این در روند نیز در نسخههای مختلف پروتکل OpenFlow مشاهده میشود. برای مثالOpenFlow-V.1.0، 12 فیلد و در نسخه OpenFlow 1.3، 15فیلد را برای مطابقت بستهها در نظر میگیرد. از جمله این فیلدها میتوان به آدرس مبدأ و مقصد، پورت مبدأ و مقصد، شناسه و اولویت شبکه محلی مجازی، نوع پروتکل، نوع سرویس و غیره اشاره کرد4]،.[6 در نتیجه با افزایش فیلدهای قوانین - فیلترها - ، حجم هر جریان نیز افزایش پیدا میکند و مسائلی همچون سرعت طبقه بندی بستهها، پشتیبانی از مجموعه قوانین بزرگ، تسهیل بروزرسانی پویا از اهمیت بالاتری برخوردار خواهد شد.
در این مقاله ما برای طبقهبندی بستهها در سوئیچهای شبکهنرم-افزار محور از ساختار داده درخت مستطیلی که یک ساختار مبتنی بر درخت تصمیمگیری است استفاده میکنیم. درختهای مستطیلی یکی از محبوبترین روشهای دسترسی مبتنی بر درخت است که توسط گوتمن در سال 1984 برای دادههای فاصلهایی- فضایی تعریف شد. این دادهها کاربردهایی زیادی در سیستمهای اطلاعاتی جغرافیایی، CAD/CAM، علمی و پزشکی و چندرسانهایی دارد. این ساختار میتواند دادههای هندسی مثل؛ نقاط، خطوط، سطوح،حجمها و غیره را به صورتاَشکالی بابُعد زیاد مدیریت کند.
درخت مستطیلی مطابقت طولانیترین پیشوند آدرسها را به خوبی انجام میدهد و استفاده از درخت مستطیلی به عنوان متد دسترسی، مزایایی چون پویایی در بروز رسانیهای افزایشی، عمق مناسب آن و مناسب برای ترکیب چندین تاپل، سرعت مناسب - لگاریتمی - خواهد داشت[8] میتواند گزینه خوبی برای این کار باشد. در بخش بعدی مروری بر کارهای پیشین خواهیم داشت و در بخشهای بعدی روش پیشنهادی خود را تشریح کرده و در نهایت به ارزیابی و بررسی نتایج خواهیم پرداخت.
-2 کارهای پیشین
در صورتی که طبقهبندی بستهها بر اساس یک فیلد انجام شود، طبقه بندی یکبُعدی نامیده میشود و در صورتی که از چندین فیلد به این منظور استفاده شود، طبقه بندی بر اساس "مطابقت چند فیلدی" نامیده میشود. بنابر اهمیت موضوع کارهای زیادی در زمینه جستجو و طبقه بندی بسته انجام شده است که ما نگاهی اجمالی بر آنها خوهیم داشت.
الگوریتمهای مختلفی برای طبقه بندی بستهها ارائه شده است؛ روشهای نرم افزاری و روشهای سخت افزاری . طبقه بندی بستهها در سوئیچها به صورت پیش فرض سخت افزاری و در یک سیکل ساعت و با دسترسی مستقیم O - 1 - انجام میشود. عمل دسترسی به فیلدهای موجود درجدول جریان میتواند به صورت چند فیلدی و به روش موازی - در یک مرحله - انجام گیرد.
اما به دلیل افزایش حجم فیلترها گران قیمت بودن حافظه CAM موجود در سوئیچ و مصرف انرژی بالا و عدم مقیاس پذیری برای مجموعه قوانین با اندازه متفاوت گزینه مطلوبی نمیباشند. میبایست برای تقلیل موارد مذکور از روشهای دیگری برای بالا بردن کارایی استفاده کردTCAMهای توسعهیافته نیز که %5 مصرف انرژی کمتری نسبت به TCAM دارند، همچنان مطلوب نیستتند روشهای سختافزاری علیرغم سرعت بالا، انعطاف-پذیری کمتری نسبت به روشهای نرمافزاری دارند
ساده ترین روش طبقهبندی نرمافزاری بستهها روش خطی می-باشد. در این روش قوانین به ترتیب کاهش اولویت در یک لیست پیوندی قرار میگیرند و بسته ورودی به ترتیب با کلیه بستههای لیست پیوندی مقایسه می شود. این الگوریتم از نظر میزان حافظه مناسب مناسبترین روش است زیرا هر قانون یک بار در حافظه ذخیره می شود ولی قابلیت مقیاس پذیری پایینی دارد. چون با افزایش تعداد قوانین، زمان انجام طبقه بندی نیز افزایش پیدا میکند و برای مجموعه قوانین بزرگ این روش کارا نیست 10]،.[9 برای کاهش پیچیدگی زمانی میتوان مجموعه قوانین را به چند زیرمجموعه تبدیل کرد و برای هر جستجو از یک مرحله پاپلاین استفاده کرد تا پیچیدگی زمانی جستجو از O - N - به O - N/P - کاهش یابد.
دستهبندیهای مختلفی برای طبقهبندی بستهها مطرح شده است11]،.[10 اما به طور ساده میتوان طبقه بندی بستهها را به دو دسته تقسیم کرد: الگوریتمهای مبتنی بر توابع درهم ساز - مثل جستجو در فضای تاپلی - که از یک ساختار داده فشرده به نام بلوم-فیلتر استفاده میکنند و روشهای مبتنی بر درخت - مثل درختهای سلسله مراتبی ،HiCuts ، شبکه ایی از درختها و درختهای مستطیلی و... - اشاره کرد. هر کدام از آنها مزایا و معایب و کاربرد خاص خودشان را دارند. به طور مثال استفاده از الگوریتم "جستجو در فضای تاپلی" زمانی میتواند کارآمد و مفیدباشد که تعداد بُعدها برای طبقهبندی بستهها کم باشد.
یکی از مشکلات روشهای مبتنی بر توابع درهم ساز، غیر قابل پیش بینی بودن رفتار این الگوریتم است که ممکن است باعث ایجاد تصادم در فیلترها شود، در مقابل روشهای مبتنی بر درخت به دلیل سادگی و صریح بودن پیادهسازی رایجتر است.
بلوم فلیترها ساختاری مبتنی بر توابع درهم ساز دارند. این ساختار برای نمایش داده به صورت فشرده بسیار مناسب میباشد؛ به عبارت دیگر بلوم فیلترها را میتوان یک آرایه بیتی که از تابعهای درهمساز انتخاب شده به صورت تصادفی استفاده میکنند، دانست. بلومفیلتر از معیار false positive - احتمال اینکه عنصری در مجموعه وجود نداشته باشد ولی به اشتباه موجود تشخیص داده شود - استفاده میکند. در بیشتر موارد این احتمال میتواند کوچک باشد که میتواند در صرفهجویی حافظه خیلی مؤثر باشد.
از جمله تحقیقاتی که در آن از تکنیک بلوم فیلتر برای طبقهبندی بستهها استفاده شده است میتوان به مطالعه و بررسی میثم غلامی و همکارانش اشاره کرد، این تحقیق بر روی روتر نرمافزاری متنباز، ماژولار و قابل توسعه "کلیک" انجام شد. یکی از اجزای ماژولار این روتر عمل طبقه بندی بستهها را انجام میداد و در زمان اجرا برای دستکاری و تست بستهها از این ماژول استفاده میشد. بنابراین تغییر این روتر نرم افزاری به منظور تسریع در طبقه بندی بستهها انجام گرفت و به منظور تسریع بیشتر این عملیات از پردازنده گرافیکی استفاده شد.
ماژول طبقه بندی بستهها، برای طبقه بندی بستهها از یک الگوریتم هرس تاپل به نام بلوم فیلتر استفاده میکرد. نتایج این تحقیق نشان داد که روتر ارتقاء داده شده نسبت به روتر استاندارد کلیک، عمل طبقه بندی را 5 برابر سریعتر انجام میداد و حدود 6 مگابایت مصرف حافظه آن نسبت به روتر استاندارد کاهش یافته بود. لازم به ذکر است که مجموعه فیلترهای مورد استفاده در آن فقط شامل آدرس مبدأ و مقصد بود.[13] یک کار مشابه به کار قبلی، بر روی روتر نرم افزاری Bird انجام گردید.
در این تحقیق برای بالا بردن سرعت و کارایی روترهای Bird، توابع استاندارد از جمله تطبیق طولانیترین پیشوند آن را تغییر و به ازای هر فیلد به آن فیلترهای بلوم اضافه کردند. هدف اصلی آن تسریع عملیات IP-Lookup بود .[14] به دلیل اینکه اکثر روترهای قدیمی طبقه بندی بستهها را بر اساس آدرس مقصد انجام میدادند، بیشتر روشها بر طبقهبندی بستهها بر اساس جستجوی آدرس تمرکز داشتند.
"درک پائو" در مقاله [15] بایک روش شبه یک بُعدی به نام "تجزیه فیلتر"، طبقه بندی دوبعدی را بر اساس پیشوندهای آدرس مبدأ و مقصد انجام داد. این پیشوندها را به دامنهایی مرتب از نقاط تبدیل کرد و در داخت درخت جستجوی متوازن قرار داد.
