مقاله روشی نوین برای جایگزینی در جدول جریان سوییچ OpenFlow

بخشی از مقاله

چکیده

شبکههای مبتنی بر نرمافزار1 با این هدف که کل شبکه به صورت یک موجودیت قابل برنامهریزی مدیریت شود، ارائه شده و در حال توسعه است. پروتکل OpenFlow بعنوان پروتکلی مطرح در این زمینه، به منظور پیادهسازی سیاستهای مدیریتی موردنظر، قوانین جدید هدایت ب ستهها را در مورد جریانهای متمایز ب ستهها تحت عنوان درایههای جریان2، در جدولهای جریان سوییچهای شبکه نصب میکند. جدولهای جریان با وجود سرعت بالا ظرفیت محدودی دارند. بنابراین، مدت زمان نگهداری و نحوه جایگزینی درایههای مفیدتر، به چالشی مهم در این پروتکل تبدیل شده است. در نتیجه ناکارآمدی سیاست جایگزینی درایههای جدول جریان، به دلیل عدم ح ضور درایههای جریان متناظر با ب ستههای ورودی در جدول جریان سوییچ، میزان مراجعات به کنترلر جهت هدایت این ب ستهها و در نتیجه تاخیر هدایت ب ستهها افزایش مییابد. از همینرو، تمرکز این پژوهش، بر ارائه رو شی پویا جهت جایگزینی درایههای جدول جریان ا ست که بتواند سربار کنترلر را تا حد امکان کاهش دهد. ایده کلیدی در روش پی شنهادی آن ا ست که از محبوبیت جریانهای ترافیکی موجود در جدول جهت انتخاب جریان موردنظر برای جایگزینی ا ستفاده شود. پیاده سازی الگوریتم پیشنهادی به کمک ابزار MiniNet و مقایسه نتایج آن با الگوریتمهای جایگزینی موجود، چون FIFO و Random نشاندهنده افزایش قابل توجه در نرخ برخورد در جدول جریان سوییچ Openflow بوده و برتری آن را در کاهش سربار کنترلر تایید مینماید.

کلمات کلیدی:شبکه مبتنی بر نرمافزار، جدول جریان، سوییچ OpenFlow، الگوریتم جایگزینی.

-1 مقدمه

اخیراً شبکههای مبتنی بر نرمافزار در میان پژوهشگران و صنعت محبوبیت زیادی پیدا کرده است. شکل - 1 - ، ساختار کلی از این شبکهها را نشان میدهد. مزیت اصلی این شبکهها انعطافپذیری آن به دلیل جدا بودن سطح کنترل3 از سطح داده 4 است. با استفاده از شبکههای مبتنی بر نرمافزار کل شبکه و عناصر آن بصورت یک شبکه مجازی دیده میشود. این شبکهها با استفاده از نرمافزارها و رابطهای برنامهنویسی کاربردی طراحی شده، کنترل میگردد. بنابراین، در شب که های مبتنی بر نرمافزار ن یازم ند یک پروت کل ارت باطی بین نرمافزارها و سختافزارها هستیم که بتواند کدهای نرمافزاری کنترلی را به تمامی ابزارهای گوناگون از تولیدکنندگان متفاوت اعمال کند.[1]

OpenFlow نام پروتکلی است که این کار را انجام میدهد. در معماری این پروتکل، که در شکل - - 2، نمایش داده شده است، هر سوئیچ OpenFlow که عملیات هدایت بستههای شبکه را انجام میدهد، شامل یک یا چند جدول و یک لایه انتزاعی میباشد. این لایه انتزاعی، برای ارتباط ایمن سوییچ با کنترلر از پروتکل OpenFlow استفاده میکند.[3]مهمترین مولفههای هر سوییچ OpenFlow جدولهای جریان آن است. جدولهای جریان شامل درایههای جریان هستند، که هرکدام از این درایهها تعیین میکند که چطور بستههای متعلق به یک جریان باید پردازش و ار سال شوند. درایههای جریان تو سط کنترلر در جدول های جریان تعریف میشوند.[4] این جدولها ظرفیت محدودی دارند. ب نابراین، ت عداد درا یه های جر یانی که در آن ها میتوان ذخیره نمود م شخص و محدود ا ست.

جدولهای جریان از حافظههای تداعیگر سه و ضعیتی5 ساخته شدهاند. حافظههای تداعیگر سهو ضعیتی علاوه بر قیمت زیاد، مصرف انرژی بالایی دارد. بنابراین، افزایش اندازه جدولهای جریان هزینهبر بوده و همچنین مصرف انرژی را افزایش میدهد.[5] نحوه عملکرد جدولهای جریان به این صورت است که اطلاعات هریک از بستههای جریانهای ورودی با درایههای موجود در جدولهای جریان مقایسه میشود. در صورت تطبیق بسته با یکی از درایههای جدول، سیاست مشخصشده در آن درایه جریان بر بسته مذکور اعمال میگردد. چنانچه بسته ورودی با هیچیک از درایههای جریان مطابقت نداشته باشد؛ پیامی به نام Packet_in جهت پردازش آن به کنترلر ارسال میگردد.

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

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

-2 مروری بر کارهای انجام شده

محق قان راه حل هایی برای م قاب له با م حدود یت جدول جر یان اندیشیدهاند که عبارتند از: تکنیکهای خروج6 برای حذف درایهها از جدول جریان قبل از نصب درایههای جدید، تکنیکهای مبتنی بر فشردهسازی7 که این روشها افزونگی اطلاعات بین درایههای جریان موجود در جدول های جر یان را تا جای ممکن کاهش میده ند و تکنیکهای شک ستن و توزیع8 ا ست که در این روشها سوییچها یک سی ستم توزیع شده کلی می سازند که به هم واب سته ه ستند به جای اینکه مستقل از هم باشند. روشهای پیشنهادی مبتنی بر خروج شامل الگوریتمهای جایگزینی و مکانیزمهای مبتنی بر زمان انقضا است.[6] الگوریتم های جایگزینی که تاکنون در م قالات مختلف ب کارگرف ته شدهاند و قابل پیاده سازی در شبکه مبتنی بر نرمافزار بودهاند FIFO و Random و LRU بودهاند.

Adam zarek از دانشگاه تورنتو در سال 2012 در مقالهای الگوریتمهای جایگزینی - LRU,FIFO,Random - را مقایسه کردهاند. به این صورت که جدول جریان به صورت یک Cache در نظر گرفته شده و درایهها فقط زمانی حذف میشوند که جدول جریان پر باشد و بر اساس سیاستهای جایگزینی نامبرده شده درایه مورد نظر انتخاب و حذف میشود. با بررسی این الگوریتمها دریافتهاند که FIFO و Random تفاوت نسبتا کمی با هم دارند ولی FIFO بهتر از Random است. با این وجود Random نیز نمیتواند خوب باشد چرا که ممکن است درایههایی از جدول که ارجاع زیادی را دارند جهت جایگزینی انتخاب کند.

اما LRU بهتر از دو الگوریتم دیگر است و اندازه نرخ برخورد برای آن بیشتر است. ولی LRU در آن زمان قابل پیاده سازی در شبکه-های مبتنی بر نرمافزار نبوده است. در پایان عملکرد ترکیب TimeOutهای مختلف با الگوریتم جایگزینیLRU نیز بررسی شده است. طبق نتایج، زمانی که طول جدول کوچکتر از تعداد درایههای فعال است اندازه TimeOut تاثیر چندانی ندارد و هر بهبود عملکردی وابسته به الگوریتم جایگزینی استEun-Do Kim .[7] و همکارانش نیز در سال 2014، در مقالهای به منظور کاهش سربار کنترلر شبکههای مبتنی بر نرمافزار که بر اثر عدم برخورد - - table miss در جدول جریان به هنگام ورود جریانها ایجاد میشود، راهکاری را ارائه دادهاند.

در این کار، برای مدیریت جدول جریان از الگوریتمLRU در هنگام جایگزینی درایههای جریان، استفاده شده است و نتایج نشان داده که این الگوریتم بهتر از روشهای FIFO و Random عمل میکند، از مفهوم Vacancy که در OpenFlow1.4 است استفاده کردهاند. [9 ,8] اما این روش در سوییچ OpenFlow پیادهسازی شده است در صورتی که در شبکه مبتنی بر نرمافزار کارهای کنترلی باید در قسمت کنترلر پیاده شود. پیادهسازی الگوریتم LRU در کنترلر نیازمند این است که کنترلر از آخرین درایهای که با جریانهای ورودی به سوییچ منطبق شده است مطلع باشد و این اطلاعرسانی به کنترلر خود بار زیادی بر کنترلر وارد میکند. از آنجا که در این مقاله الگوریتمهایی که در کنترلر قابل پیادهسازی و مبتنی بر شبکه مبتنی بر نرمافزار هستند ارزیابی شدهاند، لذا در این کار این الگوریتم مورد بررسی قرار نگرفته است.

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

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

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

تعداد ارجاعات به جریانها در دفعات قبلی که در جدول جریان نصب شدهاند در محاسبه این مقدار نقش دارند. i شماره جریان و x شماره دفعه - بار - ارجاع به کنترلر برای نصب این جریان است. درجه اهمیت جریان i در بار nام:در این رابطه t اندازه پنجره نمونه است . یعنی مثلا اگر 3 باشد اطلاعات سه بار نصب قبل این جریان در جدول جریان در محاسبه اندازه درجه اهمیت نقش دارند.و ماقبل آن در نظر گرفته نمیشوند.تابع وزنی یک تابع غیر افزایشی است و وزن بیشتری به جریانهایی میدهد که قبلا بی شتر مورد ارجاع قرار گرفتهاند. اگر مقدار j کمتر از k باشد مقدار fi - j-k - صفر میشود. این تابع همانندی