مقاله جایگذاری ماشین های مجازی در رایانش ابری با استفاده از خوشه بندی نزدیکترین همسایه

بخشی از مقاله

چکیده

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

کلید واژه : خوشه بندي، رایانش ابري، ماشین مجازي، هسته.

.1مقدمه

در سال هاي اخیر، رایانش ابري به علت استفاده موثر از منابع و دسترسی راحت به سرویس ها، محبوبیت بسیاري پیدا کرده است.[1,2] این قدرت رقابتی ناشی از معرفی تکنولوژي مجازي سازي و ویژ گی توزیع شده ابري می باشد. در مراکز داده اي که از مجازي سازي استفاده می شود، سرویس دهنده ها، میزبان ماشین هاي کامل نرم افزاري هستند که به آن ها ماشین هاي مجازي می گویند. با ایجادیک ماشین مجازي می توان یک بار کاري را پردازش کرده و پس از اتمام کار، آن را از بین برد تا میزبان بتواند ماشین مجازي دیگري را در خود جاي دهد.براین اساس، هسته هاي ماشین هاي فیزیکی، تبدیل به پردازنده هاي مجازي[3]خواهند شد که ماشین هاي مجازي بر روي آن ها قرار می گیرند.کاربران ابري به ویژه براي اجراي کاربردهاي ﺑﺎ نیاز پردازشی بالا، معمولا به جاي یک ماشین مجازي، مجموعه اي ازآن ها را درخواست می کنند.

این ماشین هاي مجازي قادرند به صورت مشترك، بارکاري درخواست شده را پردازش کنند. این امر باعث ایجاد جریان داده بین آن ماشین ها خواهد شد. جریان داده ها، بخش عظیمی از پهناي باند بین مراکز داده اي را مصرف می کند.همچنین براساس ویژگی توزیع شده ابر می توان انتظار داشت که ماشین هاي مجازي براساس موقعیت جغرافیایی هر کاربر، در نزدیکی آن ها مستقر شوند. ابر توزیع شده، از تعداد زیادي مرکز داده1 تشکیل شده و همه این مراکز، به وسیله اینترنت پر سرعت به یکدیگر متصل شده اند.[4] برخلاف ابر متمرکز، مراکز داده اي توزیع شده به دلیل پراکندگی جغرافیایی، از توانایی هاي نسبتا کمتري برخوردار بوده و ترافیک کمتري را تحمل می کنند.

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

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

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

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

شبیه سازي هاي انجام شده نشان می دهند که الگوریتم پیشنهادي با جلوگیري از ایجاد تنگناها در شبکه ابري و با مصرف کمتر انرژي، در مقایسه با روش هاي موجود، تقاضاهاي بیشتري را برآورده می سازد.ادامه این مقاله به صورت زیر سازماندهی شده است. در بخش 2، کارهاي مرتبط بحث می شود . در بخش 3، مسئله انتخاب مرکز داده به وسیله روش خوشه بندي نزدیک ترین همسایه ارائه می گردد. در بخش 4، محیط آزمایشی موردنظر معرفی شده و کارایی الگوریتم پیشنهادي ارزیابی خواهد شد. سرانجام در بخش 5 ، به ارائه نتیجه راهکار پیشنهادي پرداخته و کارهاي آینده را ارائه می دهیم.

-2 کارهاي مرتبط

استفاده موثر از منابع، اساس تضمین سطح سرویس بوده و باعث می شود فراهم کنندگان سرویس ابري از نظر اقتصادي موفق بوده و سوداوریحداکثریداشته باشند. بر این اساس مسئله تخصیص منبع، به عنوان موضوعی کلیدي در رایانش ابري در نظر گرفته می شود.[7,8] جنبه هاي متفاوتی از تخصیص منبع مانند ادغام سرویس دهنده ها[9]، توازن بار[10] و انرژي [11] بررسی شده اند. اما همه این مقالات، بر دو منبع حافظه و پردازنده تمرکز کرده اند. انتخاب مرکز داده و ص  رفه جویی در پهناي باند به ندرت در سال هاي اخیر مورد مطالعه قرار گرفته است. جایگذاري ماشین هاي مجازي در یک مرکز داده براساس ماتریس ترافیک مورد بررسی قرار گرفته [12,13] و هدف آن مقیاس پذیري مراکز داده بوده است.

مدل هاي مختلفی براي حل این مشکل پیشنهاد شده است. بسته بندي سبد[14,15]3 و نظریه گراف [12,16,17] دو مدلی هستند که بسیار استفاده شده و انتخاب آن ها براساس میزان اندازه منبع بوده است. الگوریتم بسته بندي سبد، به جهت برآورده کردن نیازهاي متنوع ماشین هاي مجازي،فرض می کند که می تواند منابع را بهاندازه هاي مخت لفی تقسیم کرده و به کار گیرد. از تسهیم سازي آماري4براي قرار دادن هر چه بیشتر ماشین هاي مجازي به صورت فشرده در یک ماشین فیزیکی استفاده می شود. اما این روش، مناسب تکنیک هاي مجازي سازي فعلی نیست. از این روش فقط می توان هنگامی استفاده کرد که اندازه هاي متفاوتی از پردازنده هاي مجازي وجود داشته باشد.[18]

حتی VMware به عنوان یک شرکت برجسته در تکنولوژي مجازي سازي، ادعا کرده است که در آخرین محصول تولیدي خود - Wmware vSphere 5.x - ، در یک ماشین مجازي، تعداد پردازنده هاي مجازي نمی تواند بیشتر از هسته هاي منطقی یک میزبان باشد. تعداد هسته هاي منطقی در صورتیکه چندنخی غیرفعال باشد، برابر تعداد هسته هاي فیزیکی خواهد بود درحالی که با فعال بودن چندنخی، می توان حداکثر دوبرابر هسته هاي  فیزیکی ماشین میزبان، هسته منطقی ایجادکرد.[3] تعداد هسته هايمنطقی، درست برابر حداکثر تعداد ماشین هاي مجازي موجود در ماشین میزبان است. در انواع مختلف نمونه هاي ماشین مجازي فراهم   شده توسط شرکت آمازون، پردازنده مجازي به عنوان معیاري از منابع محاسباتی در نظر گرفته شده است که تعداد آن از 1 تا 32 عدد، می  تواند تغییر کند.[19]

از طرف دیگر، الگوریتم هاي مبتنی بر بسته بندي سبد، فرض می کنند که عناصر انتخابی، هیچگونه ارتباطی بایکدیگر نداشته و در نتیجه در حل مسائلی که ماشین هاي مجازي با یکدیگر داراي ارتباط هستند، با ﺷﮑﺴﺖ مواجه می شوند.[21] از این رودر مواردي که ماشین هاي مجازي با هم در ارتباط هستند، براي حل مسائل از ﻣﺪل مبتنی بر نظریه گراف استفاده میشود.[12,16,17] مسئله انتخاب مرکز داده براي اولین بار در [6] بررسی شد. پس ازفرموله کردن این مسئله به صورت حداقل سازي قطر یک گراف کامل وزن دار، ثابت شدکه این موضوع در گروه مسائلNP-hard قرار میگیرد. الگوریتمی به نام FindMinStarبراي یافتن یک خوشه مرکزداده در اطراف مرکز داده اي خاص پیشنهاد شدکه قطر مربوط به خوشه را محاسبه می کرد.

سپس در یک الگوریتم با تقریب 2، دو الگوریتم MinDiameterGraph ، FindMinStar براي هر مرکزداده، فراخوانی می شدند. همه قطرهاي مربوطه، محاسبه شده و بایکدیگر مقایسه می شدند. در بین آن ها، خوشه اي از مراکز داده که داراي قطر کوچکتري بود، به عنوان راه حل انتخاب می شد. پیچیدگی زمانی MinDiameterGraphبرابر O - n3 - بودکه الگوریتم FindMinStar توانست با پیچیدگی O - n2 - برآن غلبه کند.همچنین یک الگوریتم اکتشافی نیز براي مسئله تقسیم سازي ماشین هاي مجازي با پیچیدگی زمانی O - n2 logn - در[6] ارائه شده است. نتایج شبیه سازي نشان می دهند که این روش می تواند نتایج بهتري نسبت به الگوریتم هاي تصادفی و حریصانه تولید نماید.

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

براي حل این مسئله از بسته بندي سبد و پیاده سازي گونه اي از الگوریتم بهترین مناسب کاهشی5استفاده شده است. نتایج حاصل از شبیه سازي این الگوریتم نشان می دهد که مصرف انرژي  کاهش یافته است. اما این الگوریتم علاوه بر مشکلی که الگوریتم هاي مبتنی بر بسته بندي سبد با در نظر نگرفتن ارتباط بین ماشین هاي  مجازي دارند، تاثیر ترافیک شبکه در ادغام ماشین هاي مجازي  نیزلحاظ نشده است. روش خوشه بندي مبتنی بر تراکم نیز به طور گسترده در تحلیل خوشه استفاده شده است.[23-25] ایده اصلی به این صورت است که،با یک شعاع مشخص ε، خوشه از دو نوع شی تشکیل شده است.اولین نوع از اشیا عبارت است از "شی هسته".6 براي هر شی هسته i، -ε همسایگی آن را با    Nε - i -  نشان می دهند که شامل حداقل،MinPts نقطه می باشد، به این معنی که تعداد نقاط موجود   در همسایگی i از حد تعیین شده بیشتر است.

براي اشیا دیگر درخوشه ، -εهمسایگی آن ها شامل نقاط کمتري از MinPts می باشد. نام این اشیا، "اشیاءمرزي"7است. اگر -εهمسایگی یک شی       شامل نقاط کمتري از MinPts بوده و در هیچ خوشه اي قرار نگیرد، به آن شی ،" مزاحم"8 می گوییم. بدیهی است که اشیا مزاحم، پراکنده اند. کل مجموعه نقاط را می توان به صورت خوشه اي از نقاط در نظر گرفت که اشیاي مزاحم در اطراف آن ها پراکنده شده اند. با  توجه به مفاهیم مزبور، الگوریتم DBSCAN ارائه شده در [26] قادراست خوشه هاي مرتبط را براساس شعاع ورودي و MinPts پیدا کند. براي فهم آسانتر الگوریتم، می توان به شکل 1 مراجعه نمود.