A Multi-Objective Differential Evolutionary Algorithm-based Approach for Resource Allocation in Cloud Computing Environment
Subject Areas :
Saeed Bakhtiari
1
(پلیس فتا)
Mahan Khosroshahi
2
()
Keywords: Cloud computing, Scheduling, Allocation, Multi-objective differential evolution algorithm (DEA), Migration.,
Abstract :
In recent years, the cloud computing model has received a lot of attention due to its high scalability, reliability, information sharing and low cost compared to separate machines. In the cloud environment, scheduling and optimal allocation of tasks affects the effective use of system resources. Currently, common methods for scheduling in the cloud computing environment are performed using traditional methods such as Min-Min and meta-heuristic methods such as ant colony optimization algorithm (ACO). The above methods focused on optimizing one goal and do not estimate multiple goals at the same time. The main purpose of this research is to consider several objectives (total execution time, service level agreement and energy consumption) in cloud data centers with scheduling and optimal allocation of tasks. In this research, multi-objective differential evolution algorithm (DEA) is used due to its simple structure features and less adjustable parameters. In the proposed method, a new approach based on DEA to solve the problem of allocation in cloud space is presented which we try to be effective in improving resource efficiency and considering goals such as time, migration and energy by defining a multi-objective function and considering mutation and crossover vectors. The proposed method has been evaluated through a CloudSim simulator by testing the workload of more than a thousand virtual machines on Planet Lab. The results of simulation show that the proposed method in comparison with IqrMc, LrMmt and FA algorithms, in energy consumption by an average of 23%, number of migrations by an average of 29%, total execution time by an average of 29% and service level agreement violation (SLAV) by an average of 1% has been improved. In this case, use of the proposed approach in cloud centers will lead to better and appropriate services to customers of these centers in various fields such as education, engineering, manufacturing, services, etc.
[1] H. Yuan, J. Bi, and M. Zhou, "Spatial task scheduling for cost minimization in distributed green cloud data centers," IEEE Transactions on Automation Science and Engineering, vol. 16, no. 2, pp. 729-740, 2018.
[2] A. Arunarani, D. Manjula, and V. Sugumaran, "Task scheduling techniques in cloud computing: A literature survey," Future Generation Computer Systems, vol. 91, pp. 407-415, 2019.
[3] Y. Li, S. Wang, X. Hong, and Y. Li, "Multi-objective task scheduling optimization in cloud computing based on genetic algorithm and differential evolution algorithm," in 2018 37th Chinese Control Conference (CCC), 2018: IEEE, pp. 4489-4494.
[4] E. H. Houssein, A. G. Gad, Y. M. Wazery, and P. N. Suganthan, "Task scheduling in cloud computing based on meta-heuristics: Review, taxonomy, open challenges, and future trends," Swarm and Evolutionary Computation, vol. 62, p. 100841, 2021.
[5] E. Arianyan, H. Taheri, and V. Khoshdel, "Novel fuzzy multi objective DVFS-aware consolidation heuristics for energy and SLA efficient resource management in cloud data centers," Journal of Network and Computer Applications, vol. 78, pp. 43-61, 2017.
[6] D. Maharana, B. Sahoo, and S. Sethi, "Energy-efficient real-time tasks scheduling in cloud data centers," International Journal of Science Engineering and Advance Technology, IJSEAT, vol. 4, no. 12, pp. 768-773, 2017.
[7] H. Wang and H. Tianfield, "Energy-aware dynamic virtual machine consolidation for cloud datacenters," IEEE Access, vol. 6, pp. 15259-15273, 2018.
[8] Y. Li, S. Wang, X. Hong, and Y. Li, "Multi-objective task scheduling optimization in cloud computing based on genetic algorithm and differential evolution algorithm." pp. 4489-4494.
[9] S. Srichandan, T. A. Kumar, and S. Bibhudatta, "Task scheduling for cloud computing using multi-objective hybrid bacteria foraging algorithm," Future Computing and Informatics Journal, vol. 3, no. 2, pp. 210-230, 2018.
[10] J. Li, J. Liu, and J. Wang, "An improved differential evolution task scheduling algorithm based on cloud computing," in 2018 17th International Symposium on Distributed Computing and Applications for Business Engineering and Science (DCABES), 2018: IEEE, pp. 30-35.
[11] X. Zhang et al., "Energy-aware virtual machine allocation for cloud with resource reservation," Journal of Systems and Software, vol. 147, pp. 147-161, 2019.
[12] A. Rehman, S. S. Hussain, Z. ur Rehman, S. Zia, and S. Shamshirband, "Multi‐objective approach of energy efficient workflow scheduling in cloud environments," Concurrency and Computation: Practice and Experience, vol. 31, no. 8, p. e4949, 2019.
[13] K. Naik, G. Meera Gandhi, and S. Patil, "Multiobjective virtual machine selection for task scheduling in cloud computing," in Computational Intelligence: theories, applications and future directions-volume I: Springer, 2019, pp. 319-331.
[14] E. Aloboud and H. Kurdi, "Cuckoo-inspired job scheduling algorithm for cloud computing," Procedia Computer Science, vol. 151, pp. 1078-1083, 2019.
[15] M. Aruna, D. Bhanu, and S. Karthik, "An improved load balanced metaheuristic scheduling in cloud," Cluster Computing, vol. 22, no. 5, pp. 10873-10881, 2019.
[16] N. Mc Donnell, E. Howley, and J. Duggan, "Dynamic virtual machine consolidation using a multi-agent system to optimise energy efficiency in cloud computing," Future Generation Computer Systems, vol. 108, pp. 288-301, 2020.
[17] N. Khattar, J. Singh, and J. Sidhu, "An energy efficient and adaptive threshold VM consolidation framework for cloud environment," Wireless Personal Communications, vol. 113, no. 1, pp. 349-367, 2020.
[18] R. Shaw, E. Howley, and E. Barrett, "Applying reinforcement learning towards automating energy efficient virtual machine consolidation in cloud data centers," Information Systems, vol. 107, p. 101722, 2022.
[19] S. Mustafa, K. Bilal, S. U. R. Malik, and S. A. Madani, "SLA-aware energy efficient resource management for cloud environments," IEEE Access, vol. 6, pp. 15004-15020, 2018.
[20] A. Beloglazov and R. Buyya, "Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers," Concurrency and Computation: Practice and Experience, vol. 24, no. 13, pp. 1397-1420, 2012.
[21] R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. De Rose, and R. Buyya, "CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms," Software: Practice and experience, vol. 41, no. 1, pp. 23-50, 2011.
[22] Standard Performance Evaluation Corporation. https://www.spec.org/power_ssj2008/results/
[23] Amazon EC2 Instance Types. https://aws.amazon.com/ec2/instance-types/
[24] K. Park and V. S. Pai, "CoMon: a mostly-scalable monitoring system for PlanetLab," ACM SIGOPS Operating Systems Review, vol. 40, no. 1, pp. 65-74, 2006.
|
دو فصلنامه علمی فناوری اطلاعات و ارتباطات ایران | سال چهاردهم، شمارههای 51 و 52 ، بهار و تابستان 1401 |
|
ارائه رویکرد مبتنی بر الگوریتم تکاملی تفاضلی چندهدفه برای مسئله تخصیص منبع در محیط رایانش ابری
سعید بختیاری * ماهان خسروشاهی **
* استادیار گروه فتا، دانشگاه علوم انتظامی امین، تهران
** دانشجو کارشناسی ارشد مهندسی فناوری اطلاعات و ارتباطات، دانشگاه آزاد اسلامی واحد تهران مرکزی، تهران
تاریخ دریافت: ۲۴/۰۳/۱۴۰۰ تاریخ پذیرش: ۰۷/۱۲/۱۴۰۰
نوع مقاله: پژوهشی
چکیده
در سالهای اخیر، الگوی رایانش ابری به دلیل مقیاسپذیری بالا، قابلیت اطمینان، اشتراک اطلاعات و هزینه پایین نسبت به ماشینهای مجزا، بسیار مورد توجه قرارگرفته است. در محیط ابر، زمانبندی و تخصیص بهینه وظایف بر استفاده مؤثر از منابع سیستم اثر میگذارد. در حال حاضر روشهای متداول برای زمانبندی در محیط رایانش ابری با استفاده از روشهای سنتی مانند حداقل-حداقل و روشهای فرا ابتکاری مانند الگوریتم کلونی مورچهها انجام میشود. روشهای فوق بر بهینه سازی یک هدف متمرکز هستند و به طور همزمان چندین هدف را برآورد نمیکنند. هدف اصلی این تحقیق در نظر گرفتن چندین هدف (زمان اجرای کل، توافقنامه سطح سرویس، مهاجرت و انرژی مصرف شده) در مراکز داده ابری با زمانبندی و تخصیص بهینه وظایف میباشد. در این پژوهش الگوریتم تکاملی تفاضلی چندهدفه به دلیل ویژگیهای ساختار ساده و پارامترهای قابل تنظیم کمتر، مورد استفاده قرار میگیرد. در روش پیشنهادی، رویکردی جدید مبتنی بر الگوریتم تکاملی تفاضلی برای حل مسأله تخصیص در فضای ابری ارائه میشود که در رویکرد ارائه شده سعی میشود که بر اساس تابع سودمندی چندهدفه تعریف شده و در نظر گرفتن بردارهای جهش و تقاطع بتوانیم در بهبود بهرهوری از منابع و در نظر گرفتن اهدافی چون زمان، مهاجرت و انرژی تأثیرگذار باشیم. روش پیشنهادی از طریق شبیهساز کلودسیم با آزمایش بر روی حجم کار بیش از هزار ماشین مجازی بر روی دادههای Planet Lab ارزیابی شده است. نتایج حاصل از شبیهسازی نشان میدهد که روش پیشنهادی توانسته است معیار مصرف انرژی را نسبت به الگوریتمهای IqrMc، LrMmt و FA مقایسه شده به طور میانگین به میزان ۲۳ درصد، تعداد مهاجرتها را به طور میانگین به میزان ۲۹ درصد، زمان اجرای کل را به طور میانگین به میزان ۲۹ درصد و نقص توافقنامه سطح سرویس را به طور میانگین به میزان ۱ درصد بهبود دهد. در این صورت استفاده از رویکرد پیشنهادی در مراکز ابری منجر به سرویسهای بهتر و مناسب به مشتریان این مراکز در حوزههای مختلفی از جمله آموزش، مهندسی، صنایع تولیدی، خدماتی و... خواهد شد.
واژگان کلیدی: رایانش ابری، زمانبندی، تخصیص، الگوریتم تکاملی تفاضلی چندهدفه، مهاجرت.
نویسنده مسئول: سعید بختیاری s.b.fata@police.ir
۱. مقدمه
رایانش ابری مدلی است برای فراهم کردن دسترسی آسان بر اساس تقاضای کاربر از طریق شبکه به مجموعهای از منابع رایانشی قابل تغییر و پیکربندی (مثل: شبکهها، سرورها، فضای ذخیرهسازی، برنامههای کاربردی و سرویسها) که این دسترسی بتواند بدون کمترین نیاز به مدیریت منابع و یا دخالت مستقیم فراهمکننده سرویس، به سرعت فراهم شده یا آزاد گردد [1]. رایانش ابری را میتوان از جمله بزرگترین راهحلهای مشکلات صنعت فناوری اطلاعات برشمرد. در واقع با استفاده از آن میتوان با صرف هزینههای کم و بدون نگرانی از ارتقای سخت افزار و یا بهروزرسانی نرمافزار مورد استفاده، از امکاناتی نظیر قدرت پردازشی و یا فضای ذخیرهسازی سرویس دهندههای ابری، تنها به واسطه اتصال به اینترنت، استفاده نمود. با توجه به گسترش روزافزون استفاده از رایانش ابری، سرویس دهندگان این تکنولوژی با چالشهای جدیدی مواجه گردیدهاند [2]. مسأله تخصیص منابع و زمانبندی یکی از چالشهای مهم در رایانش ابری میباشد. زمانبندی به معنای واگذاری کارآمد و مناسب منابع به کارهاست. هدف اصلی آن کوتاه کردن زمان تکمیل کار، بالا بردن توان عملیاتی سیستم و ایجاد تعادل بار بر روی منابع میباشد. این مسئله در ابر به دلیل مقیاس بزرگ منابع، پیچیدهتر است؛ بنابراین شناخت بهتر الگوریتمها میتواند در انتخاب الگوریتم مناسب جهت زمانبندی و تخصیص بهینه منابع کمک زیادی کند [1] و [2]. تخصیص منبع و زمانبندی برای پردازش توسط منابع مناسب موجود در شبکه ابر، به عنوان یک مساله اساسی در رسیدن به کارایی بالا در سیستم رایانش ابری مطرح شده است. بر این اساس اگر به مسئله زمانبندی توجه نشود کارایی منابع ابری کاهش یافته و زمان اجرای کل افزایش مییابد. در حال حاضر روشهای متداول برای زمانبندی و تخصیص منابع در محیط رایانش ابری با استفاده از روشهای سنتی مانند روش حداقل-حداقل1، روش حداکثر-حداقل2 و روشهای فرا ابتکاری مانند الگوریتم کلونی مورچهها3 و الگوریتم ژنتیک4 انجام میشود. روشهای فوق غالباً بر بهینه سازی یک هدف متمرکز هستند و به طور همزمان چندین هدف را برآورد نمیکنند. در این میان برخی از الگوریتمهای فرا ابتکاری نیاز به پارامترهای زیادی جهت تنظیم دارند و سرعت همگرایی آنها پایین است [3]. روشهای مختلفی مبتنی بر الگوریتمهای فرا ابتکاری برای حل مسئله تخصیص و زمانبندی وجود دارند که هر کدام از آنها کاراییهای مختلفی و پیچیدگیهای متفاوتی دارند که در این مقاله الگوریتم تکاملی تفاضلی مورد مطالعه و بررسی قرار داده میشود.
رویکرد مبتنی بر تفاضلی دارای ویژگیهای ساختار ساده و پارامترهای قابل تنظیم کمتر میباشد که برای حل انواع مسائل بهینه سازی پیچیده عددی و مهندسی منجر به نتایج رضایت بخشی شده است [1]. از آنجایی که مسئله تخصیص منابع و زمانبندی در محیط رایانش ابری یک مسئله انپی-سخت5 است، بدین جهت بهکارگیری الگوریتم تکاملی تفاضلی چندهدفه در محیط رایانش ابری میتواند کارایی آن را به طور گسترده بهبود دهد. این الگوریتم برای غلبه بر عیب اصلی الگوریتم ژنتیک یعنی فقدان جستجوی محلی، ارائه شده است و تفاوت اصلی آن با الگوریتم ژنتیک در عملگر انتخاب میباشد. در رویکرد ارائه شده ابتدا سعی میشود که بر اساس تابع سودمندی چندهدفه تعریف شده و در نظر گرفتن بردارهای جهش و تقاطع بر اساس بهرهوری از منابع و انرژی مصرفی قصد داریم با استفاده بهینه از منابع و بهبود بهرهوری در کاهش زمان اجرای کل6 کارها، نقص توافقنامه سطح سرویس7، تعداد مهاجرتها و مصرف انرژی تأثیرگذار باشیم تا خدمات ابری مورد توجه مشتریان قرار گیرد.
۲. کارهای پیشین
رایانش ابری به عنوان یکی از انواع سیستمهای توزیع شده که دسترسی به منابع گوناگون را از طریق سرویسها بر روی بستر اینترنت فراهم میکند روز به روز در حال گسترش میباشد. از آنجایی که وظیفه ابر پاسخگویی به حجم بالای وظایف دریافتی است زمانبندی وظایف در رایانش ابری، مسأله بسیار مهمی میباشد که سعی دارد یک زمانبندی بهینه برای اجرای وظایف مشخص نماید. روشهای بسیاری به ویژه روشهای اکتشافی و تکاملی برای این مسأله ارائه گردیده است [4]. که در ادامه به بررسی برخی از این پژوهشهای اخیر میپردازیم.
در مقاله [5] از مزایای روش مقیاس گذاری فرکانس و ولتاژ پویا8 همراه با رویکرد تجمیع9 برای ارائه دادن یک روش جدید چند معیاره فازی و راه حل مدیریت منبع واقعی استفاده شده است. ارزیابی گسترده الگوریتمهای پیشنهادی با استفاده از شبیهساز کلودسیم، کاهشهای قابل توجهی در انرژی مصرفی، نقص توافقنامه سطح سرویس و تعداد مهاجرتها در مقایسه با بهترین فناوری روز موجود نشان میدهد. این مقاله به بهبود زمان اجرای کل در محیط ابر توجه نکرده است.
مقاله [6] روشی بر پایه الگوریتم زمانبندی انرژی آگاه10 برای تخصیص ماشینهای مجازی ارائه نموده است. هدف اصلی این پژوهش کاهش مصرف انرژی و کاهش زمان پاسخ ماشینهای مجازی میباشد. این مقاله همچنین وظایفی که بر روی ماشینهای مجازی اجرا میشوند را به گونهای برای اجرا، اولویت بندی میکند تا این وظایف در کمترین زمان ممکن اجرا گردند. این مقاله به بهبود زمان اجرای وظیفه و زمان واقعی در محیط ابر توجه نکرده است.
تجمیع پویای ماشین مجازی معیار مهمی در بهبود بهرهوری منابع میباشد. در مقاله [7] یک سیاست تخصیص ماشین مجازی جدید بهنام11SABFD و یک سیاست مهاجرت جدید برای انتخاب ماشین مجازی بهنام انتخاب ماشین مجازی برای مهاجرت مبتنی بر بهره پردازنده پیشنهاد شده است. نتایج تجربی آزمایشات، بهبود انرژی مصرفی و کارایی را در استفاده از این دو سیاست نسبت به برنامههای تجمیع پویای ماشین مجازی موجود نشان میدهد. از معایب این مقاله میتوان به عدم توجه به زمانبندی و تخصیص منابع نام برد.
در مقاله [8] یک الگوریتم بهینه سازی ترکیبی مبتنی بر الگوریتم ژنتیک و تکاملی تفاضلی ارائه شده است. با توجه به اینکه فرایند زمانبندی وظایف در محیط ابر یک ویژگی طبیعت پویا دارد بر این اساس محدودیت تابع هدف تنها از این جهت نمیتواند خواستههای کاربران را برآورده نماید. با توجه به همین مشکل یک الگوریتم چندهدفه مبتنی بر الگوریتم ژنتیک و الگوریتم تکاملی تفاضلی در این مقاله ارائه میشود که در الگوریتم پیشنهادی زمان کل، هزینه و تعادل بار به طور همزمان بررسی میگردد. در فاز جمعیت اولیه و ترکیب مجدد تنوع جمعیت اولیه با معرفی فاکتورهای مختلف فرد افزایش مییابد که میتواند مانع عبور افراد مشابه و رعایت قوانین درونی نسلهای طبیعی شود. معرفی الگوریتم تکاملی تفاضلی در مرحله جهش الگوریتم ژنتیک میتواند نه تنها به مزایای قابلیت جستجوی سراسری الگوریتم ژنتیک منجر شود بلکه باعث سرعت بخشیدن به الگوریتم برای بهینه سازی راه حل با استفاده از قابلیتهای جستجوی محلی و سرعت همگرایی سریع الگوریتم تکاملی تفاضلی میشود. نتایج شبیهسازی در کلودسیم نشان میدهد که این الگوریتم میتواند دو الگوریتم ژنتیک و تفاضلی را با توجه به کیفیت خدمات و تعادل بار ماشین مجازی در شرایط مشابه بهینه سازد و یک الگوریتم کارآمد برای زمانبندی وظایف در محیط ابر باشد. روش پیشنهادی را میتوان تنها در محیط محاسبات پایدار استفاده کرد. درحالیکه در دنیای واقعی، استفاده از منابع محاسباتی بهصورت تمام وقت مفید نیستند. بنابراین بهتر است اهداف دیگری مانند استحکام، قابلیت اطمینان و امنیت علاوه بر اهداف مطالعه شده برای کارهای بعدی مورد توجه قرار گیرد.
مقاله [9] یک رویکرد ترکیبی از الگوریتم زمانبندی وظایف را که ترکیبی از ویژگیهای مطلوب دو الگوریتم ابتکاری الهام گرفته از زیست شناسی میباشد، ارائه کرده است. این رویکرد ترکیبی از الگوریتمهای ژنتیک و الگوریتمهای جستجوی باکتری12 در رایانش ابری است. هدف اصلی این مقاله حداقلسازی زمان پاسخ و کاهش مصرف انرژی است. در این رویکرد به مساله سربار محاسباتی توجهی نشده است. در این مقاله به معیارهای بهبود کیفیت سرویس و کاهش تعداد مهاجرتها به منظور بهبود مناسبتر کاهش مصرف انرژی توجهی نکرده است.
در مقاله [10] به معرفی مکانیسم داوری در استراتژی انتخاب که میتواند زمان اجرای الگوریتم تکاملی تفاضلی را کاهش دهد، پرداخته شده است. در این مقاله به طور مؤثر کاستیهای الگوریتم تکامل دیفرانسیل استاندارد را با سرعت همگرایی آهسته بهبود بخشیده است. در این مقاله بر بهبود الگوریتم تکاملی چندهدفه با هدف کاهش زمان متمرکز شده است. در این مقاله به معیارهای بهبود انرژی و کیفیت سرویس توجهی نشده است.
در مقاله [11] یک رویکرد تکاملی جدید و مؤثر، برای تخصیص ماشینهای مجازی که میتواند بهرهوری انرژی در مرکز داده ابری را با در نظر گرفتن ماشینهای مجازی رزرو شده بیشتر به حداکثر رساند معرفی شده است. این رویکرد میتواند دسترسی سریع به یک راه حل تخصیص بهینه برای یک دسته از ماشینهای مجازی رزرو شده را فراهم کند و در عین حال ماشینهای مجازی بیشتری را با ماشینهای فیزیکی کمتری تجمیع نماید تا بهینهسازی انرژی بهتری را در مقایسه با روشهای موجود ایجاد نماید. در این مقاله به کاهش زمان اجرا و تعداد مهاجرتها توجهی نشده است.
در مقاله [12] یک رویکرد چندهدفه برای زمانبندی جریان کاری در محیطهای ابری پیشنهاد شده است. در این تحقیق نویسنده یک الگوریتم ژنتیکی چند منظوره جدید برای زمانبندی جریان کار در محیط ابر ارائه داده است. نتایج شبیه سازی نشان میدهد که الگوریتم پیشنهادی نه تنها از نظر بودجه، مهلت و انرژی بهبود یافته بلکه در استفاده از منابع ابر نیز در مقایسه با الگوریتمهای رقابتی بهبود یافته است. این مقاله به اهداف دیگری مانند سطح امنیتی، اعتماد و رضایت کاربر هنگام زمانبندی توجه نکرده است. همچنین باید تحمل خطا در هنگام ترسیم وظایف گردش کار به منابع ابری مورد توجه قرار گیرد.
مقاله [13] یک الگوریتم اکتشافی چندوجهی هیبریدی جدید مبتنی بر الگوریتم ژنتیکی13 (NSGA-II) و الگوریتم جستجوی گرانش14 (GSA) برای تسهیل انتخاب ماشینهای مجازی برای زمانبندی وظایف ارائه کرده است. نتایج شبیه سازی نشان میدهد که الگوریتم پیشنهادی در مقایسه با سایر الگوریتمهای زمانبندی چندهدفه عملکرد بهتری داشته و اهداف تعیین شده را برآورده میکند. در مسئله زمانبندی پویا عوامل دیگری مانند دما تأثیر دارند و سربار انرژی باید با جزئیات مورد بررسی قرار گیرد.
در مقاله [14] یک الگوریتم زمانبندی را که از رفتار انگلی پرنده فاخته تقلید مینماید، پیشنهاد شده است. فاختهها با بهرهگیری از لانههای دیگر پرندگان، تخمهای مشابه با خود را تکثیر میکنند. الگوریتم زمانبندی فاخته پیشنهاد شده را تحت تعداد مختلفی از گرهها و درصد کارها با اولویت بالا ارزیابی میکند. نتایج تجربی نشان میدهد که الگوریتم پیشنهادی از نظر معیارهایی چون میانگین استفاده از پردازنده و متوسط زمان چرخش برای هر نوع کار برتری داشته است.
تخصیص، زمانبندی و کارایی انرژی موضوعات مهمی در سیستمهای ابری میباشند. مقاله [15] به تخصیص و زمانبندی جهت حداقل کردن تعداد سرورهای فعال پرداخته است. در این مقاله از الگوریتم کرم شب تاب جهت فرآیند تخصیص استفاده شده است. این الگوریتم متعلق به الگوریتمهای تصادفی میباشد بدین معنا که یک نوع جستجوی تصادفی برای رسیدن به مجموعهای از راه حلها به کار برده میشود. مشخصه اصلی کرمهای شب تاب نور چشمک زن آنها است. کرمهای شب تاب به سمت کرمی میروند که پرنورتر است. نتایج شبیهسازی نشان دهنده این است که روش ارائه شده در زمان اجرا بهبود داشته است. از معایب این مقاله میتوان به عدم توجه به معیارهای انرژی و بهبود بهرهوری از منابع نام برد.
رایانش ابری در دهه اخیر رشد سریعی داشته است، از این روی نگرانی فزایندهای در مورد انرژی مورد نیاز مراکز داده ابر وجود دارد. یک روش برای حل این مساله، تجمیع پویای ماشین مجازی15 (DVMC) است که در آن ماشینهای مجازی (میزهای مجازی) در تعداد کمتری میزبان قرار میگیرند، در حالی که میزبانانی که ماشین مجازی ندارند در حالت خواب قرار داده میشوند. DVMC به طور سنتی با استراتژیهایی که بر اساس توپولوژی متمرکز ساخته میشوند، حل میشود. یکی از معایب این راهحلها این است که آنها در مراکز داده بسیار بزرگ مقیاس خوبی ندارند زیرا گره مدیر به یک تنگنا و یک نقطه خرابی تبدیل میشود. بر این اساس در مقاله [16] قراردادهای شایعه پراکنی16 (GC) را که یک چارچوب جدید چند عاملی برای تهیه استراتژیهای همکارانه غیر متمرکز است پیشنهاد شده است. GC از پروتکل شایعه17 و پروتکل قرارداد خالص18 الهام گرفته است. با استفاده ازGC، یک استراتژی GC مبتنی بر DVMC توسعه داده شده است و آن با دو استراتژی محبوب Sercon که متمرکز است و ecoCloud که استراتژی توزیع شده میباشد، مقایسه شده است. در این روش کاهش مصرف انرژی در نظر گرفته شده اما به مساله سربار محاسباتی توجهی نشده است.
محاسبات مبتنی بر ابر، علیرغم مزایای بسیار زیاد آن، تأثیرات نامناسبی بر محیط زیست نیز دارد. انتشار گازهای گلخانهای و انرژی مصرفی توسط مراکز داده ابر، مهمترین مسألهای است که نیاز به توجه جدی دارد. تجمیع ماشین مجازی یک روش اساسی برای صرفهجویی در مصرف انرژی و استفاده بهینه از منابع میباشد. با این حال، رویکردهای تجمیع ماشین مجازی موجود بدون در نظر گرفتن عوامل کیفیت سرویس19 به طور تهاجمی باعث کاهش مصرف انرژی میشوند. برخلاف راهحلهای موجود، راه حل ارائه شده در مقاله [17]، یک چارچوب عمومی است زیرا، هم برای پردازنده و هم برای کارهای فشرده ورودی / خروجی کار میکند. اثربخشی چارچوب پیشنهادی با استفاده از مجموعه داده واقعی پلتفرم Planet Lab و CloudSim نشان داده شدهاست. راهحل پیشنهادی را میتوان در مراکز داده ابری استفاده کرد تا محاسبات کارآمد انرژی را فعال نماید. این مقاله به معیارهای کیفیت سرویس و کاهش مهاجرت توجهی نکرده است.
آگاهی از انرژی، چالش بزرگی برای زیرساختهای رایانش ابری و توسعه مراکز داده نسل بعدی است. تجمیع ماشینهای مجازی یکی از تکنیکهایی است که میتواند برای کاهش هزینههای مربوط به انرژی و مسائل پایداری زیست محیطی مراکز داده استفاده گردد. در زمانهای اخیر ثابت شده است که رویکردهای یادگیری هوشمند برای مدیریت منابع در مراکز داده ابری مؤثر میباشند. در مقاله [18] به بررسی کاربرد الگوریتمهای یادگیری تقویتی20 (RL) برای مساله تجمیع ماشین مجازی، که ظرفیت آنها را برای بهینهسازی توزیع ماشینهای مجازی در مرکز داده برای بهبود منابع نشان میدهد، پرداخته شده است. تعیین سیاستهای کارآمد در محیطهای پویا میتواند کار دشواری باشد، با این حال، روش پیشنهادی RL به دلیل توانایی ذاتی استدلال در عدم اطمینان در صورت عدم دانش کامل، رفتار بهینه را میآموزد. با استفاده از دادههای بار کاری واقعی، یک تحلیل مقایسهای از الگوریتمهای محبوب RL از جمله SARSA و Q-learning ارائه داده شده است. نتایج تجربی نشان میدهند چگونه این رویکرد 25٪ بهرهوری انرژی را بهبود میبخشد در حالی که 63٪ نقض خدمات را نسبت به الگوریتم اکتشافی محبوب انرژی آگاه کاهش میدهد. در این مقاله به معیارهای زمان و مهاجرت توجهی نشده است.
۳. روش پیشنهادی
۳. 1 کلیت روش پیشنهادی
الگوریتم تکاملی تفاضلی یک الگوریتم جدید اکتشافی است که دارای ویژگیهای ساده و پارامترهای قابل تنظیم کمتر میباشد که برای حل انواع مسائل بهینه سازی پیچیده عددی و مهندسی منجر به نتایج رضایت بخشی شده است. از آنجائیکه مسئله زمانبندی و تخصیص در محیط ابری یک مسئله پیچیده سخت است، بدین جهت کاربرد الگوریتم تکاملی تفاضلی در تخصیص منابع در محیط ابری میتواند کارایی را به طور قابل توجهی بهبود دهد. همچنین مسئله مصرف انرژی در سیستمهای ابری مسئله مهمی است و باید منابع به شیوهای مناسب مدیریت شوند و به گونهای ماشینهای مجازی به منابع محاسباتی تخصیص داده شوند که منابع دچار پرباری نشوند.
با توجه به ماهیت الگوریتم تکاملی تفاضلی که بهدنبال جواب بهینه هستند برای انتخاب میزبان مناسب برای تخصیص و جایدهی مناسب با هدف بهبود فرایند زمانبندی و کاهش مصرف انرژی از الگوریتم تکاملی تفاضلی استفاده میگردد. با توجه به این تعاریف روند کلی الگوریتم تکاملی تفاضلی در شکل ۱ نمایش داده شده است. این الگوریتم از چهار مرحله تشکیل شده است که در شکل زیر نمایش داده شده است.
در ادامه جزئیات روش پیشنهادی بیان شده است.
۳. 1. ۱ گام اول: ورودیهای الگوریتم پیشنهادی
با توجه به شکل بالا، این الگوریتم دارای چهار مرحله اصلی شامل ورودی، جهش، تقاطع و انتخاب میباشد. برای حل مسئله پیشنهادی ابتدا به گام اول، ورودیها در روش پیشنهادی میپردازیم. در گام اول ماشینهای مجازی و میزبانهای فیزیکی به عنوان مؤلفههای ورودی مسئله در نظر گرفته میشوند. بعد
از اینکه ورودیهای مسئله مشخص شد، بردارهایی از آنها تشکیل میگردد. بردارهای مسئله به تعداد ماشینهای مجازی و میزبانهای فیزیکی به عنوان جمعیت اولیه در نظر گرفته میشوند.
۳. 1. ۲ گام دوم: جهش در الگوریتم پیشنهادی
با توجه به بردارهای ایجاد شده در مرحله قبل، مشخصات ماشینهای مجازی و مشخصات میزبانهای فیزیکی به عنوان جمعیت اولیه برای ورودی الگوریتم تکاملی تفاضلی تعیین میگردد. با توجه به ورودیهای ایجاد شده در مرحله قبل، بهدنبال میزبان فیزیکی میگردیم که بتواند بهترین تخصیص برای ماشینهای مجازی و درخواستها به لحاظ منابع آزاد داشته باشد. هر چه پردازنده و حافظه آزاد بیشتر باشد، احتمال پربار شدن سرور و مهاجرت اضافی که در افزایش زمان و مصرف انرژی تأثیرگذار است، کاهش پیدا میکند. در نتیجه برای در نظر گرفتن عملگر جهش از آنجا که این بردار در ابتدا بدترین حالت در نظر گرفته میشود، در نتیجه بردار جهش با مقدار موقت تابع هدف بیشتر مقداردهی میشود.
۳. 1. ۳ گام سوم: تقاطع در الگوریتم پیشنهادی
در هر مرحله از الگوریتم تکاملی تفاضلی بردار تقاطع محاسبه میشود. بردار تقاطع بر اساس تابع هدف سنجیده میشود و اگر مقدار تابع هدف کمتر از مقدار قبلی باشد، آنگاه در مرحله انتخاب، این مقدار جایگزین مقدار قبلی میگردد. این عملیات بر اساس تعداد منابع محاسباتی که در نظر گرفته شده است تکرار میشود تا به بهترین جواب برای به دست آوردن بهترین منبع محاسباتی دستیابد.
۳. 1. ۴ گام چهارم: انتخاب در الگوریتم پیشنهادی
در گام سوم، چنانچه مقدار تابع هدف محاسبه شده توسط بردار تقاطع کمتر از مقدار آن در بردار جهش باشد، آنگاه بردار تقاطع جایگزین بردار جهش از نسل قبل میگردد. این مرحله انتخاب نام دارد و توسط تابع هدف مشخص میگردد. تمامی مراحل جهش، تقاطع و انتخاب تکرار میگردد و در پایان بهترین جواب جایگزین بردار قبلی میشود. برای این منظور فرمولهای زیر جهت تقاطع، توسط تابع هدف برای انتخاب بهترین منبع محاسباتی جهت تخصیص در نظر گرفته شده است.
در نتیجه رابطه (1) برای تابع هدف در نظر گرفته شده است.
(1) |
i =1,2..., N, j =1,2…, M |
(2) |
|
(3) |
|
(4) |
|
(5) |
|
(6) |
|
(7) |
|
(8) |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(9) |
|
(10) | SLAV = SLATAH |
Pseudo-code Alghorithm |
Input: hostList, vmList Output: allocation of VMs 1) For each VM in VMlist do 2) allocatedHost NULL; 3) MinFitness MAX; 4) For each host in HostList do 5) if host has enough resource for vm then 6) fitness (RequestedCPU(VM)/AllocatedMipsForVm(PM)) +(RequestedRAM(VM)/ AllocatedRAMForVm(PM))+ host.getMaxUtilization(); 7) if fitness < MinFitness then 8) MinFitness fitness; 9) AllocatedHost host; 10) end if 11) end if 12) if allocatedHost ≠ NULL then 13) allocate vm to allocatedHost 14) end if 15) end for 16) return allocation; 17) end for |
شکل ۳. شبه کد الگوریتم پیشنهادی
۴. تجزیه و تحلیل
۴. 1 معماری سیستم
در این مقاله، معماری سیستم هدف یک محیط زیرساخت بهعنوان سرویس میباشد که توسط یک دیتاسنتر در مقیاس بزرگ که شامل N نود فیزیکی ناهمگن میباشد ارائه شده است. مشخصات هر نود شامل پردازنده، حافظه و پهنای باند میباشد. سرورها دیسکهای داخلی ندارند. حافظه ذخیرهسازی بهصورت ذخیرهساز تحت شبکه3 ارائه شده است که برای مهاجرت ماشینهای مجازی بهصورت آنلاین استفاده میشود. کاربران مستقل از هم درخواستهایی را ارسال میکنند که برای اجرای این درخواستها نیاز به M ماشین مجازی ناهمگن با مشخصات مورد نیاز از پردازنده، حافظه و پهنای باند میباشد. کاربران به صورت مستقل از هم جریانهای کاری متنوعی ایجاد میکنند. این جریان کاری شامل انواع مختلفی از برنامهها مانند رایانش سریع4 و وب اپلیکیشنها که از منابع بهطور همزمان استفاده میکنند میباشد [20].
شکل ۴: معماری سیستم [20]
لایه نرم افزاری سیستم شامل مدیران محلی و جهانی میباشد همانطور که در شکل ۴ نشان داده شده است. مدیران محلی درون هر نود بهعنوان یک ماژول VMM قرار داده شدهاند. هدف آنها مانیتور کردن مداوم استفاده از پردازنده توسط هر نود، تغییر اندازه ماشینهای مجازی بر اساس نیاز منابع از آنها و تصمیمگیری در مورد اینکه چه زمانی و کدام ماشینمجازی باید از نود مهاجرت داده شود (4). مدیر جهانی داخل نود اصلی قرار دارد و اطلاعات را از مدیران محلی برای برقرار نگهداشتن استفاده از منابع جمعآوری میکند (2). مدیر محلی دستوراتی را برای بهینهسازی فرآیند تخصیص صادر میکند (3). ماژولهای VMM تغییر اندازه نهایی و مهاجرت ماشینهای مجازی و همچنین تغییرات در میزان مصرف انرژی در هر نود را انجام میدهند (5) [20].
۴. 2 معماری پردازنده
در این مقاله، معماری پردازندههای سرورهای فیزیکی چند هستهای میباشند. در این معماری یک پردازنده چند هستهای با تعداد n هسته که هر کدام m میلیون دستورالعمل را در ثانیه میتوانند اجرا کنند بهعنوان یک پردازنده تک هستهای با ظرفیت کل اجرای nm میلیون دستورالعمل در ثانیه میباشد. این کار بهصورت نرم افزاری انجام میشود و همچنین ماشینهای مجازی به هستههای پردازشی وابسته نیستند و میتوانند با استفاده از الگوریتم زمانبندی اشتراک زمانی با استفاده از یک هسته دلخواه اجرا شوند. تنها محدودیت این روش این است که ظرفیت پردازنده مورد نیاز برای یک ماشین مجازی باید کمتر و یا برابر با ظرفیت یک هسته باشد. زمانی که ظرفیت پردازنده مورد نیاز برای یک ماشین مجازی بیشتر از ظرفیت یک هسته باشد نیاز به موازی اجرا شدن آن میباشد. به دلیل اینکه اطلاعاتی از قبل در مورد برنامههای در حال اجرا روی ماشینهای مجازی نداریم و همچنین موازی سازی خودکار یک مشکل پیچیده تحقیقاتی میباشد ما موازی اجرا شدن ماشینهای مجازی را در نظر نمیگیریم [20].
۴. 3 شبیهسازی
ارزیابی الگوریتم پیشنهادی در زیرساخت مراکز داده ابری در مقیاس بزرگ و بر روی یک زیرساخت واقعی بسیار دشوار میباشد. در نتیجه برای اطمینان از تکرار آزمایشها، شبیهسازها به عنوان راهی برای ارزیابی عملکرد پیشنهادی انتخاب شدهاند. ابزار کلودسیم5 بهعنوان یک بستر شبیهسازی انتخاب شده است [21]. زیرا یک چارچوب شبیهسازی مدرن میباشد که برای محاسبات ابری طراحی شده است. این ابزار برخلاف سایر ابزارهای شبیهسازی، امکان مدل سازی محیطهای مجازی، پشتیبانی از تأمین منابع درخواستی و مدیریت آنها را فراهم میکند. این شبیهساز برای برنامههای آگاه از انرژی6 نیز توسعه یافته است. جدا از مدل سازی مصرف انرژی، قابلیت شبیهسازی برنامههای کاربردی با حجم کاری پویا نیز گنجانده شده است. برای ارزیابی روش پیشنهادی از حجم کاری دنیای واقعی برای ارزیابی بهتر، استفاده کردهایم. حجم کاری استفاده شده، حجم کاری واقعی میباشد که توسط دادههایPlanet Lab ایجاد شده است. در نتیجه در ابزار کلودسیم، ما یک مرکز داده شبیه به ۸۰۰ گره فیزیکی ناهمگن را شبیهسازی کردهایم که نیمی از آنها سرورهای HP ProLiant ML110 G4 میباشند و نیمی دیگر سرورهایHP ProLiant ML110 G5 میباشند. مشخصات این سرورها بر اساس [22] در جدول ۱ آورده شده است. هر دسته از سرورها دارای سرعت پردازش، میزان حافظه، تعداد هسته و پهنای باند متفاوتی میباشند.
جدول ۱. مشخصات میزبانهای فیزیکی در شبیهسازی
ماشین مجازی | Extra-large instance | Small instance | Micro instance |
سرعت پردازش (MIPS) | 2000 | 1000 | 500 |
حافظه (MB) | 3750 | 1700 | 613 |
پهنای باند (Gbit / s) | 1 | 1 | 1 |
سایز (GB) | 2.5 | 2.5 | 2.5 |
مشخصات انواع ماشینهای مجازی استفاده شده بر اساس نمونههای واقعی آمازون EC2 میباشد [23]. با این تفاوت که همه ماشینهای مجازی تک هستهای هستند زیرا دادههای حجم کاری مورد استفاده برای شبیهسازی از ماشینهای مجازی تک هستهای استفاده میکنند. در ابتدا، ماشینهای مجازی با توجه به منابع مورد نیاز تخصیص داده میشوند. با این حال، در طول عمر شبیهسازی ماشینهای مجازی با توجه به حجم کار از منابع کمتری استفاده میکنند و فرصتهایی برای تجمیع ماشینهای مجازی ایجاد میشود. مشخصات انواع ماشینهای مجازی استفاده شده در جدول ۲ آورده شده است. ماشینهای مجازی از نظر سرعت پردازش و میزان حافظه متفاوت میباشند. همانطور که در جدول ۲ نشان داده شده است.
جدول ۲. مشخصات ماشینهای مجازی در شبیهسازی
میزبان فیزیکی | سرعت پردازش (MIPS) | حافظه (MB) | تعداد هسته | پهنای باند (Gbit / s) | سایز (GB) |
HP ProLiant ML110 G4 | 1860 | 4096 | 2 | 1 | 1 |
HP ProLiant ML110 G5 | 2660 | 4096 | 2 | 1 | 1 |
حجم کاری استفاده شده، حجم کاری واقعی میباشد که توسط دادههای Planet Lab در ده روز مختلف دریافت شده است [24]. این دادهها از دادههای استفاده از پردازنده توسط بیش از ۱۰۰۰ ماشین مجازی در یک زمان از سرورهای واقع در بیش از ۵۰۰ مکان آورده شده است. برای این منظور، به طور تصادفی ۱۰ روز از بین جریان کار جمعآوری شده در ماههای مارس و آوریل ۲۰۱۱ انتخاب شده است. مشخصات دادهها در جدول ۳ نمایش داده شده است.
جدول ۳. مشخصات دادههای جریان کار
تاریخ | تعداد ماشینهای مجازی | Median | St. Dev |
03/03/2011 | 1052 | ٪6 | 09/٪17 |
06/03/2011 | 898 | 5٪ | 83/16٪ |
09/03/2011 | 1061 | 4٪ | 57/15٪ |
22/03/2011 | 1516 | 5٪ | 78/12٪ |
25/03/2011 | 1078 | 6٪ | 14/14٪ |
03/04/2011 | 1463 | 6٪ | 55/16٪ |
09/04/2011 | 1358 | 6٪ | 09/15٪ |
11/04/2011 | 1233 | 6٪ | 07/15٪ |
12/04/2011 | 1054 | 6٪ | 15/15٪ |
20/04/2011 | 1033 | 4٪ | 21/15٪ |
الگوریتم پیشنهادی و روش مورد مقایسه با استفاده از محیط توسعه نتبینز در نرمافزار کلودسیم ورژن ۳ کد نویسی شدهاند و در سیستم عامل ویندوز ۶۴ بیتی و با حافظه 8G اجرا گردیده است.
۴. 4 نتایج شبیهسازی
معیارها و پارامترهای کیفیت سرویسی که در روش پیشنهادی در نظر گرفته شده است، انرژی مصرفی، تعداد مهاجرتها، نقض توافقنامه سطح سرویس و زمان اجرای کل کارها میباشند. کارهایی که جهت مقایسه در نظر گرفته شده است روش IqrMc و روش LrMmt در مقاله [20] و روش FA در مقاله [14] میباشد. علت انتخاب این روشها سازگاری بیشتر روشهای مورد مقایسه با محیط شبیهسازی و استفاده از الگوریتمهای فرا اکتشافی و غیر فرا اکتشافی میباشد. ایده و روش پیشنهاد شده در این مقاله، رویکردی جدید مبتنی بر الگوریتم تکاملی تفاضلی برای حل مساله تخصیص در فضای ابری میباشد که در رویکرد ارائه شده سعی میشود بر اساس تابع سودمندی چندهدفه تعریف شده و در نظر گرفتن بردارهای جهش و تقاطع بر اساس بهرهوری از منابع و انرژی مصرفی، قصد داریم با استفاده بهینه از منابع و بهبود بهرهوری در کاهش زمان اجرای کل کارها، انرژی مصرفی، تعداد مهاجرتها و نقض کیفیت سرویس تأثیرگذار باشیم. برای بررسی روش پیشنهادی و روشهای مورد مقایسه از شبیهساز کلودسیم استفاده شده است.
در ادامه نمودارهای حاصل از شبیهسازی بر روی دادههای Planet Lab برای پارامترهای کیفیت سرویس مورد نظر آورده شده است.
معیار انرژی مصرفی میزان اتلاف انرژی کل مراکز داده که شامل مجموع انرژی میزبانهای فیزیکی میباشد را نمایش میدهد. این اتلاف انرژی، ناشی از اجرای وظایف مورد نظر بر روی هستههای پردازشی مختلف است. شکل ۵، انرژی مصرفی روش پیشنهادی DEO و روشهای مورد مقایسه را بر روی دادههای Planet Lab نمایش میدهد
[1] SLA violation Time per Active Host
[2] Performance Degradation due to Migrations
[3] Network Attached Storage (NAS)
[4] High Performance Computing (HPC)
[5] CloudSim
[6] Energy-Aware
شکل ۵. انرژی مصرفی
با توجه به شکل ۵، روش پیشنهادی کمترین میزان مصرف انرژی در بین سایر الگوریتمها در تمام ده روز را دارا میباشد. دادهها در زمانهای متفاوتی بر روی محور افقی و انرژی مصرفی برحسب کیلو وات بر روی محور عمودی نشان داده شده است. با توجه به نمودار فوق مشخص است که، عملکرد روش پیشنهادی DEO در کاهش انرژی مصرفی در مقایسه با روشهای مورد مقایسه IqrMc، LrMmt، FA بهتر میباشد. همانطور که در نمودار بالا نمایش داده میشود در روش پیشنهادی سعی شده است با استفاده از الگوریتم تکاملی تفاضلی تخصیص مؤثر و مناسبی از منابع محاسباتی انجام شود. از آنجایی که پردازنده بیشترین تأثیر را در مصرف انرژی دارد در رویکرد ارائه شده که بر اساس تابع سودمندی چندهدفه تعریف شده است با در نظر گرفتن پردازنده در تابع هدف پیشنهادی باعث میشود میزبانی که پردازنده آزاد بیشتری دارد جهت تخصیص انتخاب شود در واقع این میزبان احتمال پربار شدن آن کمتر است و از مهاجرت اضافی که در افزایش انرژی مصرفی تأثیرگذار است جلوگیری میکند و همچنین از تعداد سرورهای فعال کمتری استفاده خواهد شد. در نتیجه ما توانستهایم مصرف انرژی را در مقایسه با مقالات مورد مطالعه کاهش دهیم. انرژی مصرفی در روش پیشنهادی DEO به میزان 17٪ نسبت به روش IqrMc، 46٪ نسبت به روش LrMmt و 8٪ نسبت به روش FA بهبود داشته است.
۴. ۵. ۲ بررسی تعداد مهاجرتها
یکی از مهمترین عواملی که بر مصرف انرژی و نقض توافقنامه سطح سرویس تأثیر میگذارد تعداد مهاجرتها میباشد. شکل ۶ مقایسه بین روش DEO با IqrMc، LrMmt و FA از نظر تعداد مهاجرتها را نمایش میدهد.
شکل ۶. تعداد مهاجرتها
در نمودار بالا مشاهده میشود که روش DEO حداقل تعداد مهاجرت را در تمام ده روز دارد. از آنجایی که میزان حافظه بر روی مهاجرت تأثیر دارد در رویکرد ارائه شده که بر اساس تابع سودمندی چندهدفه تعریف شده است با در نظر گرفتن حافظه در تابع هدف پیشنهادی باعث میشود میزبانی که حافظه آزاد بیشتری دارد جهت تخصیص انتخاب شود در واقع این میزبان احتمال پر بار شدن آن کمتر است و از مهاجرتهای اضافی جلوگیری میکند و در انتخاب مقصد مناسب برای تجمیع با استفاده از تابع هدف چند معیاره در الگوریتم پیشنهادی از مهاجرتهای اضافی جلوگیری میکند. در نتیجه در روش پیشنهادی ما توانستهایم تعداد مهاجرتها را در مقایسه با مقالات مورد مقایسه کاهش دهیم. شکل ۶ تعداد مهاجرتها را در این ده روز نمایش میدهد. رویکرد ارائه شده بر اساس تابع سودمندی چندهدفه تعریف شده توانسته است در کاهش تعداد مهاجرتها در مقایسه با مقالات مورد مطالعه نسبت به روش IqrMc به میزان 23٪، نسبت به روش LrMmt به میزان 51٪ و نسبت به روش FA به میزان 13٪ بهبود داشته باشد.
۴. 5. ۳ بررسی زمان اجرای کل
یکی دیگر از اهداف الگوریتم پیشنهادی، به حداقل رساندن زمان اجرای کل میباشد. شکل ۷، زمان اجرای کل روش پیشنهادی و روش مقالات مورد مقایسه را بر روی دادههای Planet Lab نمایش میدهد.
شکل ۷. زمان اجرای کل
با توجه به شکل ۷، روش پیشنهادی کمترین میزان زمان اجرای کل در بین سایر الگوریتمها در بین روزهای مختلف را دارا میباشد. دادهها در روزهای متفاوت بر روی محور افقی و زمان اجرا برحسب ثانیه بر روی محور عمودی نشان داده شده است. با توجه به نمودار فوق مشخص میباشد که، عملکرد روش پیشنهادی DEO در کاهش زمان اجرای کل در مقایسه با روشهای مورد مقایسه IqrMc، LrMmt و FA بهتر میباشد. در رویکرد ارائه شده که بر اساس تابع سودمندی چندهدفه تعریف شده است با در نظر گرفتن پردازنده و حافظه در تابع هدف پیشنهادی باعث میشود میزبانی که پردازنده آزاد و حافظه بیشتری دارد جهت تخصیص انتخاب شود در واقع این میزبان احتمال پربار شدن آن کمتر است و از مهاجرت اضافی که در افزایش زمان اجرای کل تأثیرگذار است جلوگیری میکند و از تعداد سرورهای فعال کمتری استفاده خواهد شد که باعث بهینهسازی فرآیند تخصیص میشود. در نتیجه زمان اجرای کل در روش پیشنهادی DEO نسبت به روش IqrMc به میزان 23%، نسبت به روش LrMmt به میزان 46% و نسبت به روش FA به میزان 18% بهبود داشته است.
۴. ۵. ۴ بررسی نقض توافقنامه سطح سرویس
یکی دیگر از معیارهای مهم که در بهبود بهرهوری سیستمهای ابری نقش حیاتی دارد، معیار کیفیت سرویس میباشد که در شرکتهای ارائه دهنده ابر نقش بسیار مهمی دارد. هر چه بتوانیم در شناسایی سرور پر بار در تجمیع روش مناسبتری را ارائه دهیم بهتر میتوانیم در کاهش نقض توافقنامه سطح سرویس که به معیارهای تعداد مهاجرتها و پربار بودن سرورها بستگی دارد، تأثیرگذار باشیم. شکل ۸ نتایج ارزیابی میانگین نقص توافقنامه سطح سرویس روش پیشنهادی و سایر روشها را در روزهای مختلف بر روی دادههای Planet Lab نمایش میدهد.
شکل ۸. میانگین نقص توافقنامه سطح سرویس
با توجه به شکل ۸، روش پیشنهادی DEO در تاریخهای ۲۰۱۱/۹/۳ و ۲۰۱۱/۲۰/۴ نتوانسته عملکرد بهتری را نسبت به سایر الگوریتمها نشان دهد. میزان درصد میانگین نقض توافقنامه سطح سرویس بر روی محور عمودی نمایش داده شده است. با توجه به نمودار فوق مشخص میباشد که عملکرد روش DEO در کاهش نقص توافقنامه سطح سرویس در اکثر روزها در مقایسه با روشهای مورد مقایسه بهتر میباشد. دلیل این کاهش تخصیص مناسب و جلوگیری از پرباری و کاهش مهاجرتهای اضافی با تعریف تابع هدف چند معیاره پیشنهادی میباشد. در نتیجه در روش پیشنهادی ما توانستهایم نسبت به روش IqrMc به میزان 1%، نسبت به روش LrMmt به میزان 2% و نسبت به روش FA به میزان 1% در کاهش نقص توافقنامه سطح سرویس تأثیرگذار باشیم.
5. نتیجهگیری و پیشنهادات
برای به حداکثر رساندن مزایای ارائه دهندگان خدمات ابری، لازم است مصرف انرژی بدون هیچ گونه عارضه جانبی یا تضعیف توافقنامه سطح سرویس در مراکز ابری کاهش پیدا کند. الگوریتمهای متنوعی برای تخصیص وظایف به منابع در محیط ابر پیشنهاد شده است که اغلب آنها معیارهایی همچون توزیع بار متعادل، تخصیص بهینهی منابع، کاهش زمان اجرا و کاهش انرژی مصرفی را در نظر نمیگیرند. برای بهبود انرژی مصرفی علاوه بر فرایند تخصیص، مدیریت منابع با استفاده از تجمیع ماشینهای مجازی نقش مؤثری را در محاسبات ابری ایفا میکند. به همین دلیل به منظور زمانبندی و تخصیص بهینه وظایف به منابع در محیط ابر یک رویکرد مبتنی بر الگوریتم تکاملی تفاضلی چندهدفه برای مساله زمانبندی کارها، حل مساله تخصیص و بهبود بهرهوری از منابع در محیط رایانش ابری ارائه میشود. در روش پیشنهادی سعی میشود که بر اساس تابع سودمندی چندهدفه تعریف شده و در نظر گرفتن بردارهای جهش و تقاطع بر اساس بهرهوری از منابع و انرژی مصرفی قصد داریم در کاهش اهدافی چون زمان اجرای کل و مصرف انرژی تأثیرگذار باشیم. ما الگوریتم پیشنهادی را از طریق شبیهسازیهای گسترده در شبیهساز کلودسیم با آزمایش بر روی حجم کار بیش از هزار ماشین مجازی بر روی دادههای Planet Lab ارزیابی کردهایم. نتایج شبیهسازی نشان دهنده این میباشد که الگوریتم پیشنهادی توانسته است معیارهای مصرف انرژی را نسبت به سه الگوریتم مورد مقایسه به طور میانگین به میزان ۲۳ درصد، تعداد مهاجرتها را به طور میانگین به میزان ۲۹ درصد، زمان اجرای کل را به طور میانگین به میزان ۲۹ درصد، نقص توافقنامه سطح سرویس را به طور میانگین به میزان ۱ درصد نسبت به روشهای مورد مقایسه بهبود دهد. در این صورت استفاده از رویکرد پیشنهادی در مراکز ابری منجر به سرویسهای بهتر و مناسب به مشتریان این مراکز خواهد شد. لذا برای کارهای آینده در راستای این پژوهش در نظر داریم موارد زیر را مورد مطالعه قرار دهیم:
· استفاده از چند الگوریتم فرا ابتکاری به صورت ترکیبی با استفاده از تابع هدف ارائه شده در روش پیشنهادی.
· ترکیب پردازش ابری با پردازش مه به منظور جلوگیری از تأخیر و استفاده از تابع هدف ارائه شده در روش پیشنهادی به منظور تخصیص کارآمدتر.
· در نظر گرفتن معیارهای نقض کیفیت سرویس و چارچوبهای امنیتی در روش پیشنهادی.
· بررسی روش پیشنهادی در شبکههای خودرویی به منظور بهبود انرژی و کاهش هزینه.
· ترکیب روش پیشنهادی با شبکههای مه و اینترنت اشیا به منظور بهبود بهرهوری و کاهش هزینهها در این شبکهها.
مراجع
[1] H. Yuan, J. Bi, and M. Zhou, "Spatial task scheduling for cost minimization in distributed green cloud data centers," IEEE Transactions on Automation Science and Engineering, vol. 16, no. 2, pp. 729-740, 2018.
[2] A. Arunarani, D. Manjula, and V. Sugumaran, "Task scheduling techniques in cloud computing: A literature survey," Future Generation Computer Systems, vol. 91, pp. 407-415, 2019.
[3] Y. Li, S. Wang, X. Hong, and Y. Li, "Multi-objective task scheduling optimization in cloud computing based on genetic algorithm and differential evolution algorithm," in 2018 37th Chinese Control Conference (CCC), 2018: IEEE, pp. 4489-4494.
[4] E. H. Houssein, A. G. Gad, Y. M. Wazery, and P. N. Suganthan, "Task scheduling in cloud computing based on meta-heuristics: Review, taxonomy, open challenges, and future trends," Swarm and Evolutionary Computation, vol. 62, p. 100841, 2021.
[5] E. Arianyan, H. Taheri, and V. Khoshdel, "Novel fuzzy multi objective DVFS-aware consolidation heuristics for energy and SLA efficient resource management in cloud data centers," Journal of Network and Computer Applications, vol. 78, pp. 43-61, 2017.
[6] D. Maharana, B. Sahoo, and S. Sethi, "Energy-efficient real-time tasks scheduling in cloud data centers," International Journal of Science Engineering and Advance Technology, IJSEAT, vol. 4, no. 12, pp. 768-773, 2017.
[7] H. Wang and H. Tianfield, "Energy-aware dynamic virtual machine consolidation for cloud datacenters," IEEE Access, vol. 6, pp. 15259-15273, 2018.
[8] Y. Li, S. Wang, X. Hong, and Y. Li, "Multi-objective task scheduling optimization in cloud computing based on genetic algorithm and differential evolution algorithm." pp. 4489-4494.
[9] S. Srichandan, T. A. Kumar, and S. Bibhudatta, "Task scheduling for cloud computing using multi-objective hybrid bacteria foraging algorithm," Future Computing and Informatics Journal, vol. 3, no. 2, pp. 210-230, 2018.
[10] J. Li, J. Liu, and J. Wang, "An improved differential evolution task scheduling algorithm based on cloud computing," in 2018 17th International Symposium on Distributed Computing and Applications for Business Engineering and Science (DCABES), 2018: IEEE, pp. 30-35.
[11] X. Zhang et al., "Energy-aware virtual machine allocation for cloud with resource reservation," Journal of Systems and Software, vol. 147, pp. 147-161, 2019.
[12] A. Rehman, S. S. Hussain, Z. ur Rehman, S. Zia, and S. Shamshirband, "Multi‐objective approach of energy efficient workflow scheduling in cloud environments," Concurrency and Computation: Practice and Experience, vol. 31, no. 8, p. e4949, 2019.
[13] K. Naik, G. Meera Gandhi, and S. Patil, "Multiobjective virtual machine selection for task scheduling in cloud computing," in Computational Intelligence: theories, applications and future directions-volume I: Springer, 2019, pp. 319-331.
[14] E. Aloboud and H. Kurdi, "Cuckoo-inspired job scheduling algorithm for cloud computing," Procedia Computer Science, vol. 151, pp. 1078-1083, 2019.
[15] M. Aruna, D. Bhanu, and S. Karthik, "An improved load balanced metaheuristic scheduling in cloud," Cluster Computing, vol. 22, no. 5, pp. 10873-10881, 2019.
[16] N. Mc Donnell, E. Howley, and J. Duggan, "Dynamic virtual machine consolidation using a multi-agent system to optimise energy efficiency in cloud computing," Future Generation Computer Systems, vol. 108, pp. 288-301, 2020.
[17] N. Khattar, J. Singh, and J. Sidhu, "An energy efficient and adaptive threshold VM consolidation framework for cloud environment," Wireless Personal Communications, vol. 113, no. 1, pp. 349-367, 2020.
[18] R. Shaw, E. Howley, and E. Barrett, "Applying reinforcement learning towards automating energy efficient virtual machine consolidation in cloud data centers," Information Systems, vol. 107, p. 101722, 2022.
[19] S. Mustafa, K. Bilal, S. U. R. Malik, and S. A. Madani, "SLA-aware energy efficient resource management for cloud environments," IEEE Access, vol. 6, pp. 15004-15020, 2018.
[20] A. Beloglazov and R. Buyya, "Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers," Concurrency and Computation: Practice and Experience, vol. 24, no. 13, pp. 1397-1420, 2012.
[21] R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. De Rose, and R. Buyya, "CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms," Software: Practice and experience, vol. 41, no. 1, pp. 23-50, 2011.
[22] Standard Performance Evaluation Corporation. https://www.spec.org/power_ssj2008/results/
[23] Amazon EC2 Instance Types. https://aws.amazon.com/ec2/instance-types/
[24] K. Park and V. S. Pai, "CoMon: a mostly-scalable monitoring system for PlanetLab," ACM SIGOPS Operating Systems Review, vol. 40, no. 1, pp. 65-74, 2006.
A Multi-Objective Differential Evolutionary Algorithm-based Approach for Resource Allocation in Cloud Computing Environment
Abstract:
In recent years, the cloud computing model has received a lot of attention due to its high scalability, reliability, information sharing and low cost compared to separate machines. In the cloud environment, scheduling and optimal allocation of tasks affects the effective use of system resources. Currently, common methods for scheduling in the cloud computing environment are performed using traditional methods such as Min-Min and meta-heuristic methods such as ant colony optimization algorithm (ACO). The above methods focused on optimizing one goal and do not estimate multiple goals at the same time. The main purpose of this research is to consider several objectives (total execution time, service level agreement and energy consumption) in cloud data centers with scheduling and optimal allocation of tasks. In this research, multi-objective differential evolution algorithm (DEA) is used due to its simple structure features and less adjustable parameters. In the proposed method, a new approach based on DEA to solve the problem of allocation in cloud space is presented which we try to be effective in improving resource efficiency and considering goals such as time, migration and energy by defining a multi-objective function and considering mutation and crossover vectors. The proposed method has been evaluated through a CloudSim simulator by testing the workload of more than a thousand virtual machines on Planet Lab. The results of simulation show that the proposed method in comparison with IqrMc, LrMmt and FA algorithms, in energy consumption by an average of 23%, number of migrations by an average of 29%, total execution time by an average of 29% and service level agreement violation (SLAV) by an average of 1% has been improved. In this case, use of the proposed approach in cloud centers will lead to better and appropriate services to customers of these centers in various fields such as education, engineering, manufacturing, services, etc.
Keywords: Cloud computing, Scheduling, Allocation, Multi-objective differential evolution algorithm (DEA), Migration.
Rimag
Links
Related Centers
Technical Support
Official pages
The rights to this website are owned by the Raimag Press Management System.
Copyright © 2017-2024