بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارایه روشی بهینه جهت تامین منابع در مراکز داده رایانش ابری با استفاده از الگوریتم کرم شب تاب
خلاصه
هدف رایانش ابری1 افزایش ظرفیت و قابلیتهای پردازشی به صورت پویا، قابل اعتماد، با کیفیت تضمین شده، بدون توسعه زیرساخت های موجود، است. البته در مسیر توسعه آن چالشهایی مطرح است، یکی از این چالشها مدیریت منابع در مراکز داده رایانش ابری در لایه زیر ساخت است، در این لایه مسئله بهینه سازی استقرار ماشینهای مجازی 2 بروی ماشینهای فیزیکی بسیار حائز اهمیت است. در این تحقیق روشی جهت تأمین بهینه منابع برای ماشینهای مجازی در سرویس زیرساخت ابری، ارایه گردیده است، هدف نهایی در این پژوهش کاهش توان مصرفی در مراکز داده رایانش ابری میباشد. صرفه جویی در مصرف انرژی باعث کاهش تعداد سرورهای فیزیکی فعال و کاهش میزان هرزروی منابع در مراکز داده میگردد، در روش پیشنهادی از الگوریتم کرم شب تاب جهت جای دهی ماشینهای مجازی استفاده شده است، نتایج ارزیابی نشان میدهد که روش پیشنهادی بهتر از روشهای رایج کنونی در خصوص مسئله جایگذاری ماشینهای مجازی عمل میکند.
واژگان کلیدی: رایانش ابری، مجازی سازی، ماشین مجازی، الگوریتم کرم شب تاب3
1. مقدمه
رایانش ابریمفهوم کاملاً جدیدی نیست، ایده این موضوع در سال 2006 توسط اریک اشمیت مدیر بخش فناوری شرکت گوگل مورد توجه قرار گرفت و در حال حاضر آنچنان فراگیر شده است که تحلیلگران تخمین میزنند که در طی 5 سال بعدی بازار عمومی برای پردازش ابری تا حد %95 رشد خواهد داشت و %12 از بازار نرم افزار جهان به سمت پردازش ابری سوق داده خواهد شد .]1[ شرکت داده ای بینالمللی4، پیشرفت ابر را در آینده ای نزدیک، سه برابر پیش بینی کرده است و این رشد را تصاعدی دانسته است.
در مدل رایانشی ابر سرویسهای بسیاری عرضه میگردد، یکی از مدلهای خدمات ارایه شده، زیرساخت به عنوان سرویس5 است که در آن منابع پردازشی (شبکه، سرویس دهندهها، ذخیره سازها و ...) به صورت سرویس عرضه میگردند. پایه اصلی زیرساخت به عنوان سرویس را تکنولوژی مجازی سازی تشکیل میدهد و این سازوکار منافع زیادی را برای رایانش ابری به ارمغان آورده است ]2[ و امکان یکپارچه سازی منابع فیزیکی مستقل در قالب منابع مجازی را فراهم میآورد. در زیرساخت به عنوان سرویس کوچکترین جزء مشترک بین مشتری و ارایه دهنده سرویس، ماشین مجازی است. درخواست برای منابع مجازی به صورت پارامترهایی مانند سرعت پردازنده، ظرفیت حافظه و حجم دیسک مطرح میگردد و درخواستهای رسیده با نگاشت منابع مجازی (بیان شده در قالب پارامترهای ورودی) بر منابع فیزیکی تأمین میگردد .]3[
امروزه یکی از مهمترین چالشهای مطرح در زیرساخت به عنوان سرویس، مدیریت و تخصیص بهینه منابع به ماشین های مجازی میباشد. مسئله اصلی تخصیص منابع در زیرساخت به عنوان سرویس، پذیرش درخواست جدید (ماشین مجازی ) و جای دهی آن بروی ماشین فیزیکی مناسب است، با فرض وجود n ماشین مجازی و m ماشین فیزیکی، مسئله جای دهی n ماشین مجازی در بین m ماشین فیزیکی دارای mn حالت متفاوت است که فضای حالت بزرگی است و جستجو در این فضای حالت و یافتن گزینه مناسب بسیار زمانبر است .]4[ مسئله جای دهی بهینه سرویس دهنده های مجازی بروی ماشینهای فیزیکی مستقر در مراکز داده مشابه یک مسئله بسته بندی جعبهها1است. در مسئله بسته بندی جعبه ها، اشیاء2 با حجمهای مختلف باید درون تعداد مشخصی جعبه3 که هر یک ظرفیت مشخصی دارند، بسته بندی شوند، به گونه ای که تعداد جعبه های استفاده شده به حداقل رسانده شود. در نظریه پیچیدگی محاسباتی، این مسئله جزء مسایل بهینه سازی "ان پی سخت"4 است. ولی با این وجود، راه حل بهینه برای نمونه های بسیار زیادی از این مسئله با استفاده از الگوریتمهای پیچیده ارائه شده است.
هزینه های سرویس دهندگان زیرساخت به عنوان سرویس بیش از آنکه صرف ایجاد زیرساخت گردد مربوط به نگهداری آن است و بیشترین هزینه نگهداری مربوط به مصرف انرژی است .]5[ بنابراین بیشترین سود زمانی عاید سرویس دهنده میشود که بتواند انرژی مصرفی را به حداقل ممکن برساند و نحوه تخصیص منابع، رابطه مستقیم با میزان مصرف انرژی و سود سرویس دهنده پیدا کرده است، یک مرکز داده متوسط،معمولاًبه اندازه 2500 مشترک خانگی، برق مصرف میکند ]6[ و صورتحساب انرژی مصرفی برای یک مراکز داده متوسط در سال 2010 بیش از 11 میلیارد دلار بوده است و هزینه های انرژی در مراکز داده به طور معمول هر پنج سال دو برابر میگردد .]7[ نه تنها هزینه نگهداری مراکز داده بسیار گران است، بلکه وجود آنها برای محیط زیست نیز بسیار مضر است. به همین دلیل کاهش مصرف انرژی در مراکز داده یک موضوع چالش برانگیز و پیچیده است .]8[ از این رو لزوم تحقیقاتی جهت استفاده مفیدتر از زیرساختهای محاسباتی جهت حصول اطمینان از رشد و توسعه پایدار رایانش ابری در آینده لازم است و در همین راستا ارایه روش هایی جهت تلفیق بهینه سرویس دهنده ها و کاهش تعداد ماشینهای فیزیکی مورد نیاز در مراکز داده ضروری به نظر میرسد.
در این تحقیق از الگوریتم کرم شب تاب جهت دستیابی به روشی جهت استقرار بهینه ماشینهای مجازی بروی ماشینهای فیزیکی مستقر در مراکز داده با هدف کاهش مصرف توان و در نتیجه کاهش تعداد سرورهای فیزیکی فعال و کاهش میزان هرز روی منابع، استفاده شده است.
الگوریتم کرم شب تاب یک مدل تکاملی است که مبتنی بر الگوریتمهای هوش جمعی و الهام گرفته از طبیعت میباشد. کاربرد عمده این الگوریتم در حل مسایل بهینه سازی است.
سازماندهی این مقاله به شرحی که در ادامه آمده است: در بخش دوم به بررسی ادبیات و کارهای گذشته در خصوص استقرار ماشینهای مجازی در مراکز داده ابری پرداخته میشود، در بخش سوم روش پیشنهادی این مقاله به طور کامل شرح داده خواهد شد، در بخش چهارم نتایج حاصل از شبیه سازی روش پیشنهادی با سایر الگوریتمها و روشهای رایج در این خصوص مقایسه میگردد ونهایتاًدر بخش پنجم، نتیجه گیری از ا ین مقاله ارایه خواهد شد.
2. پیشینه تحقیق
استقرار ماشینهای مجازی در مراکز داده رایانش ابری در سالهای اخیر یک چالش تحقیقاتی عمده بوده است و نتایج حاصل از نگاشت منابع مجازی بروی منابع فیزیکی تأثیر مهمی بر استفاده بهینه و کارآمد از منابع و متعاقب آن کاهش هزینه های عملیاتی یک مرکز داده دارد. در خصوص این مسئله تا کنون روشهای بسیاری پیشنهاد شده است در برخی از آنها از روشهای مکاشفه ای و یا فرا مکاشفه ای استفاده شده است و در برخی دیگر نیز از روشهای ریاضی و احتمالاتی استفاده شده است، در تمام روشهای پیشنهادی تلاش بر این است که بهینهترین نحوه جای دهی ماشین های مجازی بروی ماشینهای فیزیکی بدست آید، در ادامه برخی از مهمترین روشهای ارایه شده در این حوزه بررسی میگردد.
بلگلازو و همکاران ]6[ چارچوبی برای مدیریت تخصیص منابع در مراکز داده رایانش ابری پیشنهاد کردهاند که شامل 4 بخش اصلی مشتری/ واسط، تخصیص دهنده سبز، ماشینهای مجازی، ماشینهای مجازی است و هدف نهایی کاهشانرژِی مصرفی، پایبندی بیشتر به توافق نامه سطح سرویس و کاهش تعداد مهاجرتها است. آنان با مسئله تخصیص منابع به صورت 2 مرحله ای رفتار کردهاند. نویسندگان اعتقاد دارند با توجه به
مشخصات خاص محیط رایانش ابری از جمله پویایی، مقیاس پذیری و توزیعشدگی، الگوریتمهایی که نیاز به محاسبات پیچیده و یادگیری ماشین دارند چندان مناسب نیستند و باید الگوریتمهای ارایه شده مقیاس پذیر و با تحمل پذیری خطای بالا باشند.
سیستمهای کنونی تخصیص منابع در لایه زیر ساختمعمولاً از الزامات برنامه ورودی بی اطلاع هستند و در نتیجه تخصیص منابع به طور مستقل از نیازهای برنامه صورت میگیرد، که به طور قابل توجهی میتواند عملکرد برنامه های کاربردی داده گرا و توزیع شده را متأثر بسازد. لی و همکاران[9] 1 چارچوبی به نامTARA2 ارایه کردهاند که در این معماری یک موتور پیش بینی و یک شبیه ساز سبک به منظور تخمین عملکرد تکنیک تخصیص منبع پیشنهادی بکار گرفته شده است. در این روش از الگوریتم ژنتیک برای پیدا کردن یک راه حل بهینه در فضای جستجوی بزرگ استفاده شده است.
چینگ چی3 و پنگ فنگ[10] 4 روشی به نام نوبت چرخشی پویا ارایه دادهاند، که 2 قانون اصلی را در مدیریت منابع اجرا میکند، اولین قانون از اضافه کردن ماشینهای مجازی بیشتر به یک ماشین فیزیکی بازنشسته اجتناب میکند برای اینکه بتواند در آینده آن را خاموش کند. دومین قانون سرعت فرایند تلفیق سرورها را افزایش می دهد و تعداد دستگاه های فیزیکی مورد نیاز برای اجرای تمام ماشین های مجازی را کاهش میدهد.
خوشدل و همکاران [11] مدلی ریاضی جهت مدیریت منابع در ابر پیشنهاد کردهاند، مبنای کار آنان تأمین منابع به صورت رزرو از پیش است و هدف آنان ارایه مدلی جهت تأمین بهینه منابع به منظور صرفه جویی در مصرف منابع و پذیرش بیشترین درخواست ماشین مجازی و صرفه جویی در مصرف انرژی و در نتیجه افزایش سود ارایه دهنده ابر است.
ژانگ و ژو [12] فریمورکی ارایه دادهاند که رویکرد اصلیشان بهینه سازی زمان پاسخ در ماشینهای مجازی است. نویسندگان اعتقاد دارند که مهاجرت بر عملکرد سیستم در طول مهاجرت تأثیر میگذارد و تکنیک های مجازی سازی کنونی ایزوله سازی عملکردی موثری بین ماشینهای مجازی برقرار نمیکنند، بنابراین برای انتخاب ماشینهای مجازی که باید انتقال یابند، هزینه مهاجرت را در نظر میگیرند و برای انتخاب ماشین فیزیکی مقصد نیز تداخل عملکردی را در نظر میگیرند.
اشکان فرهادی و همکاران در [13] مسئله تخصیص منبع به ماشین های مجازی را به صورت یک "مسئله بسته بندی جعبه ها" با حالت چند ظرفیته در نظر گرفتهاند و با استفاده از الگوریتم ژنتیک گروهی آن را حل کردهاند، آنان تخصیص ماشین مجازی به میزبانها را بر اساس بهترین کروموزومی که نتیجه اجرای الگوریتم ژنتیک گروهی است انجام دادهاند.
یانگ کیانک و هیبینگ [4] برای مسئله تخصیص منابع به سرورهای مجازی از الگوریتم کلونی مورچگان جند هدفه با 2 هدف کاهش مصرف انرژی و کاهش هرز روی منابع استفاده کردهاند، در این تحقیق از شکل تغییر یافته ای از الگوریتم کلونی مورچگان که مناسب مسائل چندهدفه است استفاده شده است
جیانگ جوانگ5 و کوانگ مونگ سیم[14] 6 روشی برای تخصیص منابع بر اساس آگاهی از محل منابع پیشنهاد کردهاند، ارائه دهنده ابر میتواند با تخصیص ماشین مجازی به یک ماشینهای فیزیکی مناسب باعث افزایش کارایی گردد.
به اعتقاد نیر7 و همکاران [15] مدیریت صحیح درخواست ها و پاسخ به آنها، با توجه به اینکه در رایانش ابری نرخ ورود درخواستها متفاوت و متغیر است حایز اهمیت فراوان است. ارائه دهنده خدمات باید روند های مختلف درخواستها را شناسایی کند. در این روش طبقه بندی خودکار درخواستها با استفاده از تعامل بین مشتریان و مدیر منابع انجام میشود و از تئوری تطبیقی رزونانس 2 برای حل مسائل برنامه ریزی درخواستها و پیدا کردن الگوی درخواستهای دریافتی در ابر استفاده میشود.
وانگ و همکاران[16] 8 مسئله جای دهی بهینه ماشینهای مجازی بروی سرورهای فیزیکی را با استفاده از الگوریتم ازدحام ذرات گسسته، با هدف کاهش مصرف انرژی حل کردهاند.
3. روش پیشنهادی
در این تحقیق از روشی جهت بهینه سازی تلفیق سرویس دهندهها در مراکز داده رایانش ابری با هدف کاهش مصرف توان، کاهش تعداد سرورهای فیزیکی فعال و کاهش میزان هرز روی منابع استفاده شده است. بدین منظور از الگوریتم کرم شب تاب برای پیدا کردن مناسبترین ماشینهای فیزیکی برای استقرار دسته ماشینهای مجازی ورودی استفاده شده است. در این فصل ابتدا به فرمول سازی مسئله تحقیق پرداخته میشود و در ادامه به شرح الگوریتم کرم شب تاب و استفاده از آن در مسئله تحت بررسی، اقدام میگردد.
1.3. فرموله سازی تحقیق
در مراکز داده مبتنی بر رایانش ابری، مجموعه ای از ماشینهای فیزیکی به صورت کلاسترهاییوجود دارد که تماماً به صورت مجازی سازی شده در آمدهاند. درخواستهای ماشین مجازی، به صورت مقدار پردازنده و حافظه مورد نیاز، وارد شده و در صورتی که امکان تأمین نیازمندیهایشان وجود داشته باشد مورد پذیرش قرار گرفته و بروی این سرورهای فیزیکی مستقر میشوند و در غیر این صورت رد میشوند، پس میتوان مسئله را به این صورت شرح داد که :
"مجموعه متشکل از ماشین مجازی و مجموعه متشکل از ماشین فیزیکی وجود دارد هدف ما استقرار این ماشینهای مجازی بروی ماشینهای فیزیکی موجود در مرکز داده است به نحوی که مجموع توان مصرفی و در نتیجه تعداد ماشینهای فیزیکی فعال و میزان هرزروی منابع حداقل گردد". مفروضات مسئله به این صورت است: فرض اول، تمام ماشین های فیزیکی و ماشین های مجازی با دو مشخصه پردازنده و حافظه نمایش داده میشوند. فرض دوم، از اندازه دیسک با فرض وجود انباره ذخیره سازی متصل به شبکه 1 صرف نظر میکنیم. فرض سوم، هیچ ماشین مجازی نیاز به منابعی بیشتر از آنچه در یک سرور فیزیکی ارائه شده، ندارد. فرض چهارم، ماشینهای مجازی بر اساس درخواست مشتری و مطابق سفارش وی ایجاد شده است. فرض پنجم، مشتریان نمیتوانند درخواستی با هر نسبت از منابع سفارش دهند. پارامترهای مسئله به شرح جدول 1 میباشد.
بخش اعظم مصرف انرژی در یک سرور مربوط به پردازنده است و توان مصرفی در یک ماشین فیزیکی رابطه مستقیم با سطح بهره برداری از پردازنده دارد. پس میتوان توان مصرفی را به عنوان تابعی از مقدار بهره برداری از پردازنده تعریف کرد و فرمول((1 را برای محاسبه توان مصرفی در ماشین فیزیکی j ام و فرمول (2) را برای محاسبه توان مصرفی در کل مرکز داده در نظر گرفت، در نتیجه تابع هدف مسئله مورد بررسی به صورت فرمول (3) میباشد.
البته با شرایطی که در فرمول (4)، (5) و (6) قید شده است. که فرمول (4) نشان میدهد ماشین مجازی ام فقط بروی یک ماشین فیزیکی باید مستقر گردد، فرمول (5) نشان دهنده محدودیت ظرفیت منبع پردازنده در ماشین فیزیکی ام است و فرمول (6) نشان دهنده محدودیت ظرفیت منبع
حافظه در ماشین فیزیکی ام است. دو فرمول اخیر نشان میدهد که مجموع منابع مورد نیاز برای ماشینهای مجازی باید کمتر از ظرفیت منابع ماشینهای فیزیکی باشد. فرمول (7) دامنه متغیرهای مسئله را نشان میدهد.
جدول - 1 پارامترهای مسئله
.3.2 الگوریتم کرم شب تاب
الگوریتمهای هوش ازدحامی1 یا هوش گروهی شاخه ای از هوش مصنوعی هستند که در دهه اخیر بسیار مورد توجه قرار گرفتهاند. این نوع الگوریتم ها از رفتار جمعی مورچه ها، موریانه، زنبورهای عسل، کرمها، گروه پرندگان و ماهیها الهام گرفتهاند. این موجودات خود مختار در یک محل مشترک با یکدیگر زندگی میکنند. به منظور هماهنگی میان اعضای گروه، نیاز به تعاملات و ارتباطاتی بین اعضاء گروه وجود دارد [17]، .[18]
الگوریتم کرم شب تاب یکی از الگوریتمهای هوش گروهی است که توسط یانگ2 در سال 2008 در دانشگاه کمبریج ارایه گردیده است، این الگوریتم یک الگوریتم فرا مکاشفه ای و الهام گرفته از طبیعت است که میتواند برای حل سختترین مسائل بهینه سازی (مسائل ان پی-سخت) به کار رود. الگوریتم پیشنهادی یانگ جز الگوریتمهای تصادفی است و با استفاده از نوعی جستجوی تصادفی به دنبال مجموعه ای از راه حلها میگردد. در این الگوریتم از رفتار نور دهی کرمهای شب تاب در طبیعت الگو گرفته شده است.[19]
کرمهای شب تاب یکی از خاصترین، فریبندهترین و جذابترین موجودات در طبیعت هستند. بسیاری از کرمهای شب تاب تولید نورهای کوتاه و منظم میکنند و الگوی نور دهی هر گونه، خاص همان گونه است و با بقیه گونهها متفاوت است .[20]
زندگی اجتماعی کرمهای شب تاب فقط اختصاص به جستجوی غذا ندارد و شامل تولید مثل نیز میگردد. این تصمیمات جمعی با رفتار نور دهی کرمهای شب تاب که به عنوان پایه و اساس بیولوژیکی برای توسعه الگوریتم کرم شب تاب بکار رفته است، مرتبط میباشد (ایزاک فیستر و همکاران،.(2013
سیستم نور دهی کرمهای شب تاب 2 کارکرد اصلی دارد: جذب سایر کرمهای شب تاب برای جفت گیری، جذب شکار الگوریتم کرم شب تاب بر اساس 3 فرض اصلی شکل گرفته است : [19]
1. تمام کرمهای شب تاب تک جنسیتی هستند، و یک کرم شب تاب صرف نظر از جنسیت کرم شب تاب دیگر، جذب آن خواهد شد.
2. در کرمهای شب تاب جذابیت متناسب با روشنایی است و کرم شب تاب با روشنایی کمتر به کرم شب تاب با روشنایی بیشتر جذب خواهد شد و در نتیجه به سمت آن حرکت میکند؛ روشنایی و در نتیجه جذابیت کرمهای شب تاب با افزایش فاصله آنها از هم، کاهش مییابد. اگر هیچ کرم شب تابی پرنورتر از یک کرم شب تاب خاص نباشد او به صورت تصادفی حرکت میکند و هیچ کرم شب تاب دیگری نمیتواند پرنورترین کرم شب تاب را جذب کند.
3. درخشندگی کرمهای شب تاب با استفاده از تابع هدف تعیین میشود. برای مسایل کمینه سازی و یا بیشینه سازی شدت نور میتواند توسط تابع هدف و یا متناسب با آن تعیین گردد.
· شدت نور و جذابیت
شدت نور و جذابیت دو مفهوم اساسی در الگوریتم کرم شب تاب هستند. جذابیت کرم شب تاب با روشنایی یا شدت نور آن تعریف میشود و شدت نور در یک مسئله بهینه سازی از تابع هدف به دست میآید. شدت نور با مجذور فاصله نسبت عکس دارد و فرمول (8) برای آن در نظر گرفته میشود، شدت نور در منبع است، فاصله است و ɤ ضریب جذب نور است.
(8)
(9)
جذابیت متناسب با شدت نور مشاهده شده توسط کرمهای شب تاب همسایه است که با β نشان داده میشود و با فاصله نسبت عکس دارد و
معمولاً به صورت فرمول (8) تعریف میشود، جذابیت در منبع است.
· فاصله
فاصله دو کرم شب تاب i و j که به ترتیب در موقعیت و هستند با فرمول فاصله اقلیدسی (10) نشان داده میشود، که موقعیت کرم شب تاب i در بعد مکانی k ام است.
· حرکت
حرکت کرم شب تاب i به سمت کرم شب تاب پرنورتر j با معادله حرکت (11) نشان داده میشود:
طبق این فرمول حرکت کرمهای شب تاب از سه جزء تشکیل شده است : جزء اول، موقعیت کنونی کرم شب تاب است. جزء دوم، میزان جذب به سمت کرم شب تاب پرنورتر است و جزء سوم، حرکت تصادفی است که میزان تصادفی سازی با پارامتر α مشخص میشود و تابع rand تولید اعداد تصادفی با توزیع یکنواخت در بازه است.
