Manuscript ID : 1401120841386 Visit : 4370 Page: 200 - 223

Article Type: Original Research

A review of the application of meta-heuristic algorithms in load balancing in cloud computing

Subject Areas : ICT

Mehdi Morsali ^{1
*} , Abolfazl Toroghi Haghighat ² , Sasan Hosseinali-Zade ³

1 - Faculty of Electrical, Computer and IT Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran
2 - Faculty of Electrical, Computer and IT Engineering, Islamic Azad University, Qazvin Branch, Qazvin, Iran
3 -

Received: 2021-10-18 Accepted : 2022-05-26 Published : 2023-03-01

Keywords: Cloud computing, load babancing, Metaheuristic methods, overloading, underloading,

Abstract :

By widespread use of cloud computing, the need to improve performance and reduce latency in the cloud increases. One of the problems of distributed environments, especially clouds, is unbalanced load which results in reducing speed and efficiency and increasing delay in data storage and retrieval time. Various methods for load balancing in the cloud environment have been proposed, each of which has addressed the issue from its own perspective and has its advantages and disadvantages. In this research, we first provide some criteria for measuring load balance in the cloud and then examine the use of Metaheuristic methods in load balancing in the cloud environment. After introducing Metaheuristic load balancing methods, we have compared them based on the aforementioned criteria and discussed the advantages and disadvantages of each. Ant Colony Algorithms, Artificial Ant Colony, Bee Colony, Artificial Bee Colony, Bee Foraging Algorithm, Particle Swarm, Cat Swarm, Simulated Annealing, Genetic Algorithm, Tabu Search, Fish Swarm and Hybrid Algorithms and etc. examined in this research.

References:

1. Adhianto, L. et al. 2010. “HPCTOOLKIT: Tools for Performance Analysis of Optimized Parallel Programs.” Concurrency Computation Practice and Experience 22(6): 685–701.
2. Afzal, Shahbaz, and G. Kavitha. 2019. “Load Balancing in Cloud Computing – A Hierarchical Taxonomical Classification.” Journal of Cloud Computing 8(1).
3. Agarwal, Tusha, and Abhishek Saxena. 2018. “A Review On Load Balancing Algorithm in Cloud Computing Using Restful Web Services.” International Journal of Computer Sciences and Engineering 6(7): 704–7.
4. Ahmad, Mohammad Oqail, and Rafiqul Zaman Khan. 2018. “Load Balancing Tools and Techniques in Cloud Computing: A Systematic Review.” Advances in Intelligent Systems and Computing 554(November 2017): 181–95.
5. Alam, Mahfooz, and Zaki Ahmad Khan. 2017. “Issues and Challenges of Load Balancing Algorithm in Cloud Computing Environment.” Indian Journal of Science and Technology 10(25): 1–12.
6. Alankar, Bhavya et al. 2020. “Experimental Setup for Investigating the Efficient Load Balancing Algorithms on Virtual Cloud.” Sensors (Switzerland) 20(24): 1–26.
7. Anna Victoria Oikawa, C. R., Vinicius Freitas, Marcio Castro, and Laercio L. Pilla. 2020. “Adaptive Load Balancing Based on Machine Learning for Iterative Parallel Applications.” Proceedings - 2020 28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2020: 94–101.
8. Aruna, M., D. Bhanu, and S. Karthik. 2019. “An Improved Load Balanced Metaheuristic Scheduling in Cloud.” Cluster Computing 22(March): 10873–81.
9. Ashouraei, Mehran, Seyed Nima Khezr, Rachid Benlamri, and Nima Jafari Navimipour. 2018. “A New SLA-Aware Load Balancing Method in the Cloud Using an Improved Parallel Task Scheduling Algorithm.” Proceedings - 2018 IEEE 6th International Conference on Future Internet of Things and Cloud, FiCloud 2018: 71–76.
10. Attiya, Ibrahim, Mohamed Abd Elaziz, and Shengwu Xiong. 2020. “Job Scheduling in Cloud Computing Using a Modified Harris Hawks Optimization and Simulated Annealing Algorithm.” Computational Intelligence and Neuroscience 2020.
11. Balaji, K., P. Sai Kiran, and M. Sunil Kumar. 2021. “An Energy Efficient Load Balancing on Cloud Computing Using Adaptive Cat Swarm Optimization.” Materials Today: Proceedings.
12. Basu, Sayantani, G. Kannayaram, Somula Ramasubbareddy, and C. Venkatasubbaiah. 2019. “Improved Genetic Algorithm for Monitoring of Virtual Machines in Cloud Environment.” Smart Innovation, Systems and Technologies 105: 319–26. http://dx.doi.org/10.1007/978-981-13-1927-3_34.
13. Bhargavi, K., B. Sathish Babu, and Jeremy Pitt. 2020. “Performance Modeling of Load Balancing Techniques in Cloud: Some of the Recent Competitive Swarm Artificial Intelligence-Based.” Journal of Intelligent Systems 30(1): 40–58.
14. Černý, V. 1985. “Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm.” Journal of Optimization Theory and Applications 45(1): 41–51.
15. Chauhan, Prof Samir, and Jinal Patel. 2019. “Load Balancing in Cloud Computing Using Machine Learning Techniques.” JASC: Journal of Applied Science and Computations VI(Iv): 3533–41. 16. Dasgupta, Kousik et al. 2013. “A Genetic Algorithm (GA) Based Load Balancing Strategy for Cloud Computing.” Procedia Technology 10: 340–47. http://dx.doi.org/10.1016/j.protcy.2013.12.369.
17. Davidović, Tatjana, Dušan Teodorović, and Milica Šelmić. 2015. “Bee Colony Optimization Part I: The Algorithm Overview.” Yugoslav Journal of Operations Research 25(1): 33–56.
18. Dhiman, Gaurav, and Amandeep Kaur. 2018. “Optimizing the Design of Airfoil and Optical Buffer Problems Using Spotted Hyena Optimizer.” Designs 2(3): 1–16.
19. Djennane, Nabila, Rachida Aoudjit, and Samia Bouzefrane. 2018. “Energy-Efficient Algorithm for Load Balancing and VMs Reassignment in Data Centers.” Proceedings - 2018 IEEE 6th International Conference on Future Internet of Things and Cloud Workshops, W-FiCloud 2018: 225–30.
20. Fahim, Youssef et al. 2018. “Load Balancing in Cloud Computing Using Meta-Heuristic Algorithm.” Journal of Information Processing Systems 14(3): 569–89.
21. Gavvala, Siva Kumar, Chandrashekar Jatoth, G. R. Gangadharan, and Rajkumar Buyya. 2019. “QoS-Aware Cloud Service Composition Using Eagle Strategy.” Future Generation Computer Systems 90: 273–90.
22. Geethu, Gopinath P.P., and Shriram K. Vasudevan. 2015. “An In-Depth Analysis and Study of Load Balancing Techniques in the Cloud Computing Environment.” Procedia Computer Science 50: 427–32. http://dx.doi.org/10.1016/j.procs.2015.04.009.
23. Gulbaz, Rohail et al. 2021. “Balancer Genetic Algorithm-a Novel Task Scheduling Optimization Approach in Cloud Computing.” Applied Sciences (Switzerland) 11(14).
24. Kaur, Amanpreet, and Bikrampal Kaur. 2019. “Load Balancing Optimization Based on Hybrid Heuristic-Metaheuristic Techniques in Cloud Environment.” Journal of King Saud University - Computer and Information Sciences (xxxx). https://doi.org/10.1016/j.jksuci.2019.02.010.
25. Krishnaveni, H., and V. Sinthu Janita. 2019. “Modified Artificial Fish Swarm Algorithm for Efficient Task Scheduling in Cloud Environment.” International Journal of Computer Sciences and Engineering 7(5): 1363–71.
26. Kruekaew, Boonhatai, and Warangkhana Kimpan. 2020. “Enhancing of Artificial Bee Colony Algorithm for Virtual Machine Scheduling and Load Balancing Problem in Cloud Computing.” International Journal of Computational Intelligence Systems 13(1): 496–510.
27. Kumar, Arun Rana, Ayodeji Olalekan Salau, Swati Gupta, and Sandeep Arora. 2018. “A Survey of Machine Learning Methods for IoT and Their Future Applications.” Amity Journal of Computational Sciences 2(2): 1–5. www.amity.edu.in/ajcs.
28. Kumar, Jitendra, Ashutosh Kumar Singh, and Anand Mohan. 2020. “Resource-Efficient Load-Balancing Framework for Cloud Data Center Networks.” ETRI Journal 43(June 2019): 53–63.
29. Kumar, Kethavath Prem, Thirumalaisamy Ragunathan, Devara Vasumathi, and Pamulapati Krishna Prasad. 2020. “An Efficient Load Balancing Technique Based on Cuckoo Search and Firefly Algorithm in Cloud.” International Journal of Intelligent Engineering and Systems 13(3): 422–32.
30. Kumar Mishra, Sambit, Bibhudatta Sahoo, and Paramita Parida. 2018. “Load Balancing in Cloud Computing: A Big Picture Q.” https://doi.org/10.1016/j.jksuci.2018.01.003 (August 21, 2021).
31. Kumar, Pawan, and Rakesh Kumar. 2019. “Issues and Challenges of Load Balancing Techniques in Cloud Computing: A Survey.” ACM Computing Surveys 51(6).
32. Li, Kun et al. 2011. “Cloud Task Scheduling Based on Load Balancing Ant Colony Optimization.” Proceedings - 2011 6th Annual ChinaGrid Conference, ChinaGrid 2011: 3–9.
33. Lim, Jongbeom, and Daewon Lee. 2020. “A Load Balancing Algorithm for Mobile Devices in Edge Cloud Computing Environments.” Electronics (Switzerland) 9(4): 1–13.
34. Mallikarjuna, B., and P. Venkata Krishna. 2015. “OLB: A Nature Inspired Approach for Load Balancing in Cloud Computing.” Cybernetics and Information Technologies 15(4): 138–48.
35. Manasrah, Ahmad M., and Hanan Ba Ali. 2018. “Workflow Scheduling Using Hybrid GA-PSO Algorithm in Cloud Computing.” Wireless Communications and Mobile Computing 2018.
36. Milani, Alireza Sadeghi, and Nima Jafari Navimipour. 2016. “Load Balancing Mechanisms and Techniques in the Cloud Environments: Systematic Literature Review and Future Trends.” Journal of Network and Computer Applications 71: 86–98.
37. Mishra, Kaushik, Jharashree Pati, and Santosh Kumar Majhi. 2020. “A Dynamic Load Scheduling in IaaS Cloud Using Binary JAYA Algorithm.” Journal of King Saud University - Computer and Information Sciences. https://doi.org/10.1016/j.jksuci.2020.12.001.
38. Mohammad Oqail Ahmad and Rafiqul Zaman Khan. 2018. 554 Advances in Computer and Computational Sciences.
39. de Monts, Robert et al. 2016. “Defined Categories of Security as a Service.” Cloud Security Alliance –. https://downloads.cloudsecurityalliance.org/assets/research/security-as-a-service/csa-categories-securities-prep.pdf.
40. Patel, Karan D., and Tosal M. Bhalodia. 2019. “An Efficient Dynamic Load Balancing Algorithm for Virtual Machine in Cloud Computing.” In 2019 International Conference on Intelligent Computing and Control Systems, ICCS 2019, , 145–50.
41. Pattnaik, Saumendra, Jyoti Prakash Mishra, Bidush Kumar Sahoo, and Binod Kumar Pattanayak. 2021. “Load Balancing in Cloud Computing Environment Using CloudSim.” Smart Innovation, Systems and Technologies 194(01): 197–205.
42. Prassanna, J., and Neelanarayanan Venkataraman. 2019. “Threshold Based Multi-Objective Memetic Optimized Round Robin Scheduling for Resource Efficient Load Balancing in Cloud.” Mobile Networks and Applications 24(4): 1214–25.
43. Ramadhan, Gema, Tito Waluyo Purboyo, Roswan Latuconsina, and A Round Robin. 2018. “Experimental Model for Load Balancing in Cloud Computing Using Throttled Algorithm.” International Journal of Applied Engineering Research 13(2): 1139–43. https://www.ripublication.com/ijaer18/ijaerv13n2_42.pdf.
44. Ramasubbareddy, Somula et al. 2019. “Analysis of Load Balancing Algorithms Using Cloud Analyst.” International Journal of Recent Technology and Engineering 7(6): 684–87.
45. Rani, Mercy Gnana et al. 2014. “Artificial Fish Swarm Load Balancing and Job Migration Task with Overloading Detection in Cloud Computing Environments.” International Review on Computers and Software (IRECOS) 9(4): 727–34. https://www.praiseworthyprize.org/jsm/index.php?journal=irecos&page=article&op=view&path[]=15345 (August 29, 2021).
46. Shahid, Muhammad Asim et al. 2020. “A Comprehensive Study of Load Balancing Approaches in the Cloud Computing Environment and a Novel Fault Tolerance Approach.” IEEE Access 8(c): 130500–526.
47. Sui, Xin et al. 2019. “Virtual Machine Scheduling Strategy Based on Machine Learning Algorithms for Load Balancing.” Eurasip Journal on Wireless Communications and Networking 2019(1).
48. Talaat, Fatma M. et al. 2020. “A Load Balancing and Optimization Strategy (LBOS) Using Reinforcement Learning in Fog Computing Environment.” Journal of Ambient Intelligence and Humanized Computing 11(11): 4951–66. https://doi.org/10.1007/s12652-020-01768-8.
49. Talbi, El-Ghazali. 2009. “Frontmatter Enhanced Reader.Pdf.” : 25.
50. ———. 2020. “Machine Learning into Metaheuristics: A Survey and Taxonomy of Data-Driven Meta-Heuristics.” : 1–30. https://hal.inria.fr/hal-02745295.
51. Téllez, Nadim, Miguel Jimeno, Augusto Salazar, and Elias D. Nino-Ruiz. 2018. “A Tabu Search Method for Load Balancing in Fog Computing.” International Journal of Artificial Intelligence 16(2): 106–35.
52. Thanka, M. Roshni, P. Uma Maheswari, and E. Bijolin Edwin. 2019. “An Improved Efficient: Artificial Bee Colony Algorithm for Security and QoS Aware Scheduling in Cloud Computing Environment.” Cluster Computing 22: 10905–13.
53. UMA, Mrs. R., M . BALA SARASWATHY. 2019. “OPTIMIZATION ALGORITHMS IN LOAD BALANCING: A STUDY.” XII(Iv): 1–22.
54. Venkata Rao, R. 2016. “Jaya: A Simple and New Optimization Algorithm for Solving Constrained and Unconstrained Optimization Problems.” International Journal of Industrial Engineering Computations 7(1): 19–34.
55. Viana, Monique Simplicio, Orides Morandin Junior, and Rodrigo Colnago Contreras. 2020. “A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem.” Sensors (Switzerland) 20(18): 1–32.
56. Wang, Chuan’An et al. 2017. “A Switch Migration-Based Decision-Making Scheme for Balancing Load in SDN.” IEEE Access 5(c): 4537–44.
57. Wang, Chunpu, Chen Feng, and Julian Cheng. 2018. “Distributed Join-the-Idle-Queue for Low Latency Cloud Services.” IEEE/ACM Transactions on Networking 26(5): 2309–19.
58. Wang, Lijuan, and Jun Shen. 2016. “Multi-Phase Ant Colony System for Multi-Party Data-Intensive Service Provision.” IEEE Transactions on Services Computing 9(2): 264–78.
59. Xu, Peng, Guimin He, Zhenhao Li, and Zhongbao Zhang. 2018. “An Efficient Load Balancing Algorithm for Virtual Machine Allocation Based on Ant Colony Optimization.” International Journal of Distributed Sensor Networks 14(12).
60. Yaashuwanth, C et al. 2012. “Performance Comparison of Priority Rule Scheduling Algorithms Using Different Inter Arrival Time Jobs in Grid Environment.” International Journal of Grid and Distributed Computing 6(4): 157–68.

Full-Text:

الگوي تهيه مقالات

دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال چهاردهم، شماره‌هاي 53 و 54، پاییز و زمستان 1401

صفحات: 201تا 224

$E:\E Drive\logo\iicta Logo0.JPG$

Review: Application of Meta-Heuristic Algorithms in Cloud Load Balancing

Mehdi Morsali،* Abolfazl Taroghi Haqiqat، * Sasan Hossein Alizadeh**

* Faculty of Computer Engineering and Information Technology, Qazvin Branch, Islamic Azad University, Qazvin, Iran

** Information Technology Research Institute, Communication and Information Technology Research Institute, Tehran, Iran

Abstract:

Ant Colony Algorithms, Artificial Ant Colony, Bee Colony, Artificial Bee Colony, Bee Foraging Algorithm, Particle Swarm, Cat Swarm, Simulated Annealing, Genetic Algorithm, Tabu Search, Fish Swarm and Hybrid Algorithms and etc. examined in this research.

Keywords: Cloud Computing, Load Balancing, Meta-heuristic Methods, Overloading, Underloading

مروری بر کاربرد الگوریتم‌های فراابتکاری در توازن بار در رایانش ابری

مهدی مرسلی* ، ابوالفضل طرقی حقیقت* ، ساسان حسینعلی زاده**

* دانشکده مهندسی کامپیوتر و فناوری اطلاعات، دکترا ،واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران

** پژوهشکده فناوری اطلاعات، دکترا ،پژوهشگاه ارتباطات و فناوری اطلاعات، تهران، ایران

تاریخ دریافت:26/07/1400 تاریخ پذیرش: 05/03/1401

نوع مقاله: مروری

چکیده

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

الگوریتم‌های کلونی مورچه، کلونی مورچه مصنوعی، کلونی زنبور، کلونی زنبور مصنوعی، جست‌وجوی غذای زنبور عسل، ازدحام ذرات، ازدحام گربه‌ها، تبرید شبیه‌سازی شده، الگوریتم ژنتیک، جست‌وجوی ممنوعه، الگوریتم دسته ماهی‌ها و الگوریتم‌های ترکیبی در این کار بررسی شده‌اند.

واژگان کلیدی: رایانش ابری، توازن بار، روش‌های فراابتکاری، بیش‌باری ، کم‌باری

1. مقدمه

با رشد سریع فناوری اطلاعات، رایانش ابری به عنوان جایگزین فناوری‌های رایانش سنتی ظهور کرد تا کاربران بتوانند با پرداخت هزینه، در هر مکان و هر زمانی از خدمات رایانشی استفاده کنند. این فناوری به کاربران امکان دسترسی به مجموعه‌ای از منابع رایانش (سرویس‌دهنده‌ها، حافظه‌ها، شبکه‌ها و برنامه‌ها) را می‌دهد. شرکت‌های زیادی مانند سرویس وب آمازون¹ (AWS)، مایکروسافت آژور²، گوگل، ابر آی.بی.ام³ و آمازون جزء ارائه دهندگان بزرگ خدمات ابر به شمار می‌آیند [1]. هدف اولیه ابر استفاده موثر از منابع توزیع شده با هدف رسیدن به بازدهی و کارایی بالا می‌باشد. این امر به ابر توانایی حل مسائلی را می‌دهد که نیاز به توان رایانشی بالایی دارند. همچنین امکان توزیع منابع در تمام جهان و اجرای وظایف بر روی مراکز داده مختلف را فراهم می‌آورد[2].

رایانش ابری را می‌توان به دو صورت دسته‌بندی کرد: براساس مکان یا براساس خدمات ارائه شده. براساس مکان، یک ابر می‌تواند عمومی، خصوصی، ترکیبی یا انجمنی باشد. خدمات ابر عمومی با اجازه شرکت ارائه دهنده خدمات، در هر زمان و هر مکان و بر روی هر زیرساختی و برای هر کسی در دسترس هستند. ابرهای عمومی در برابر حمله‌های مختلف بسیار آسیب‌پذیر هستند، اما از نظر هزینه به صرفه‌اند. ابرهای خصوصی به طور انحصاری برای کاربران یا سازمان‌های خاصی در دسترس هستند. بالاترین سطح امنیت و کنترل دسترسی را دارند، البته هزینه‌هایشان نیز بالاتر است. ابرهای ترکیبی همانطور که از نامشان پیداست ترکیبی از ابرهای عمومی و خصوصی هستند و براساس نیازهای سازمان برای اهداف مختلفی مورد استفاده قرار می‌گیرند. ابرهای انجمنی از یک زیرساخت عمومی تشکیل شده‌اند که به وسیله سازمان‌هایی مورد استفاده قرار می‌گیرند که مدیریت و داده مشترک دارند. ابرها براساس خدماتی که ارائه می‌دهند، به دسته‌های زیرساخت به عنوان سرویس⁴ (IaaS)، پلتفرم به عنوان سرویس⁵ (PaaS) یا نرم‌افزار به عنوان سرویس⁶ (SaaS) تقسیم می‌شوند. در IaaS ابر منابع اولیه فناوری اطلاعات مانند ویژگی‌های شبکه، کامپیوترها، انعطاف‌پذیریِ کنترل بر روی منابع رایانشی ارائه می‌کند. PaaS معمولا سازمان را از زیرساخت پایه بی‌نیاز می‌کند و اجازه می‌دهد تا سازمان روی گسترش برنامه‌ها تمرکز کند. SaaS به کاربران اجازه می‌دهد تا به جای فکر به زیرساخت و سرویس‌ها بر روی یک نرم‌افزار خاص تمرکز کند. رایانش ابری در کنار این سرویس‌ها، سرویس‌هایی مانند پایگاه داده به عنوان سرویس⁷ (DaaS)، سیستم خبره به عنوان سرویس⁸ (EaaS)، محل ذخیره‌سازی به عنوان سرویس⁹ (SaaS)، شبکه به عنوان سرویس¹⁰ (NaaS)، امنیت به عنوان سرویس¹¹SECaaS) ارائه می‌کند [3].

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

1-1- انگیزه پژوهش

مقاله‌های مروری نسبتا زیادی در ارتباط با توازن بار و زمان‌بندی در ابر و کاربرد روش‌های مبتنی بر یادگیری ماشین و همچنین کاربرد الگوریتم‌های فراابتکاری در رایانش ابری منتشر شده‌اند.

برای نمونه آرونرانی و همکاران¹² مروری بر استراتژی‌های زمان‌بندی ارائه کرده‌اند و به برخی مزایا و معایب پرداخته‌اند. تمرکز این کار بر روی الگوریتم‌های جست‌وجوی فراابتکاری نیست ولی با این وجود به دلیل تعدد کاربرد الگوریتم‌های فراابتکاری، بخش عمده‌ای از کار به الگوریتم‌های ژنتیک، ازدحام ذرات و کلونی مورچه‌ها اختصاص داده شده است [4]. در این کار معیارهای مقایسه مدونی برای مقایسه استراتژی‌های زمان‌بندی ارائه نشده است و فقط به مرور ادبیات پرداخته شده است. کومار و همکاران¹³ یک مرور سیستماتیک روی الگوریتم‌های زمان‌بندی در رایانش ابری انجام داده‌اند و معیارهایی برای مقایسه الگوریتم‌های زمان‌بندی معرفی کرده‌اند و مروری کوتاه بر ابزارهای شبیه‌سازی ابر ارائه نموده‌اند. [5]. نقطه قوت این کار ارائه فلوچارت‌های ساده و گویای الگوریتم‌های فراابتکاری پرکاربرد می‌باشد. یانگ¹⁴ و رحمانی مروری بر سازوکارهای زمان‌بندی در رایانش مه ارائه کرده‌اند. در این مقاله مروری روش‌های زمان‌بندی به دسته ابتکاری و فراابتکاری دسته‌بندی و معرفی شده‌اند، اما به جزئیات و چگونگی کارکرد روش‌ها پرداخته نشده است [6]. موهان سینگ و همکاران¹⁵، در کاری ارزشمند، یک رده‌بندی نسبتا کامل از روش‌های جست‌وجوی فراابتکاری و کاربرد آنها در زمان‌بندی ابر و مه، ارائه کرده‌اند [7]. کونجانگ و لینا¹⁶ یک مرور سیستماتیک بر کاربرد رویکردهای فراابتکاری در زمان‌بندی ابرهای زیرساخت به عنوان سرویس ارائه کرده‌اند که به مزایای الگوریتم‌های فراابتکاری، چالش‌های این الگوریتم‌ها پرداخته‌اند. این کار از نظر بیان نظری مزایا و معایب و دسته‌بندی الگوریتم‌های فراابتکاری بسیار جامع است، اما به خود الگوریتم‌ها و نحوه عملکرد آنها اشاره‌ای نکرده است [8].

1-2- نوآوری‌ها

· مطالعه تحلیلی روش‌های توازن بار مبتنی بر الگوریتم‌های فراابتکاری در طول بازه تحقیق

· بررسی مزایا و معایب روش‌های فراابتکاری ارائه شده در منابع

· شناسایی معیارهای سنجش توازن بار و مقایسه روش‌های موجود بر اساس معیارهای شناسایی شده

· ارائه پیشنهادهایی برای مطالعه در زمینه کاربرد روش‌های فراابتکاری در توازن بار در رایانش ابری

1-3- روش انجام پژوهش

مسئله توازن بار با استفاده از متدلوژی چارچوب سازنده عمومی¹⁷ (CGF) مورد بررسی قرار گرفت. با مطالعه منابع مرتبط با موضوع روش‌های فراابتکاری در توازن بار در محیط ابر، از یک ساختار درختی برای رده‌بندی روش‌های فراابتکاری و کاربرد آنها در توازن بار در منابع استفاده شد. علاوه بر این مطالعه منابع مرتبط، براساس مرور سیستماتیک منابع و تمرکز بر روی کاربرد الگوریتم‌های فراابتکاری در توازن بار ابر انجام شد. حوزه کاری محدود به بهینه‌سازی توازن بار بوده و به موضوع‌های دیگری مانند بهینگی مصرف انرژی و چیزهایی از این دست پرداخته نشده است. منابع مطالعه شده محدود به بازه زمانی 2010 تا فوریه 2022 می‌باشد. برای اینکه سرعت پژوهش بیشتر باشد و نتایج مطالعه به روزتر باشند، تمرکز کار بیشتر بر روی منابع منتشر شده پس از سال 2016 می‌باشد.

برای یافتن منابع پایگاه داده‌های IEEE Xplore، ACM Digital Library، Springer Link،Web of Science ، Google Scholar و منابع دیگر با کلیدواژه‌هایی همچون Cloud load balancing، Task Scheduling، Workflow Scheduling، Resource Allocation، Single and Multi-objective scheduling techniques به همراه واژگان Meta-heuristics، Meta-heuristic optimization مورد جست‌وجو قرار گرفتند و کلیدواژه‌های به دست آمده جدید دوباره جست‌وجو شدند. منابع به دست آمده براساس عنوان، چکیده مقاله‌ها و در انتها براساس مطالعه متن پالایش شدند. مراحل روش جست‌وجو در تصویر 1 نمایش داده شده است.

1-4- شناسایی پرسش‌های اصلی

پرسش 1: چرا متوازن سازی بار در ابر اهمیت دارد؟

پرسش 2: معیار سنجش توازن بار چیست؟ آیا توازن بار یک مسئله با تک هدف است یا چندین هدف دارد؟

پرسش 3: روش‌های پرکاربرد برای متوازن سازی بار کدامند؟

پرسش 4: استفاده از الگوریتم‌های فراابتکاری چه مزایا و معایبی نسبت به روش‌های معمول دارد؟

2. روش‌های توازن بار در منابع مطالعه شده

برای پاسخ به پرسش سوم، در این بخش به مرور استراتژی‌های توازن بار در حالت کلی پرداخته‌ایم. البته تکنیک‌های زیادی در این گروه وجود دارد، مانند راند روبین¹⁸، الگوریتم تصادفی‌سازی شده¹⁹، الگوریتم حد آستانه²⁰، OLB، OLB+LBMM، Min-Min، Max-Min، الگوریتم اجرای جریان پخش برابر²¹، توازن بار متوقف کننده²²، الگوریتم تپه نوردی تصادفی²³، پیوستن به صف خالی که مزایا و معایب آنها در جدول 1 نمایش داده شده است.

1.2. Round Robin (RR)

یک الگوریتم توازن بار ثابت است که وضعیت بار پیشین گره را در تخصیص بار کنونی در نظر نمی‌گیرد و از زمان‌بندی RR برای تخصیص کارها استفاده می‌کند. این الگوریتم گره نخست را به طور تصادفی انتخاب می‌کند و سپس کارها را به ترتیب RR به گره‌ها تخصیص می‌دهد. این الگوریتم برای رایانش ابری مناسب نیست، زیرا ممکن است بار برخی گره‌ها بسیار سنگین شود و برخی بیکار بمانند. دلیل این امر آن است که زمان اجرای هیچکدام از فرایندها پیش از اجرا معلوم نیست [9].

بنابراین الگوریتم RR وزن‌دار برای حل این مشکل ارائه شد. در این الگوریتم به هر گره یک وزن خاص، اختصاص داده می‌شود. هر گره براساس وزن اختصاص داده شده به آن تعداد مناسبی درخواست دریافت می‌کند. اگر وزن اختصاص داده شده به تمام گره‌ها یکسان باشد، آنگاه تمام گره‌ها ترافیک یکسان دریافت می‌کنند. در رایانش ابری تعیین دقیق زمان اجرا امکان‌پذیر نیست، بنابراین این الگوریتم توصیه نمی‌شود [10].

[1] نویسنده مسئول: مهدی مرسلی mehdi_morsali@qiau.ac.ir

Amazon Web Service

[2] Microsoft Azure

[3] IBM Cloud

[4] Infrastructure as a Service

[5] Platform as a Service

[6] Software as a Service

[7] Database as a Service

[8] Expert system as a Service

[9] Storage as a Service

[10] Network as a service

[11] Security as a Service

[12] Arunarani et al.

[13] Kumar et al.

[14] Yang.Z

[15] Singh et al.

[16] J. Kok Konjaang and Lina. Xu

[17] Constructive Generic Framework

[18] Round Robin

[19] Randomize Algorithm

[20] Threshold Algorithm

[21] Equally Spread Current Execution Algorithm

[22] Throttled Load Balancing

[23] Stochastic Hill Climbing

تصویر 1- نمودار روش جستجو، شناسایی و دسته‌بندی منابع مربوط به کاربرد روش‌های فراابتکاری در رایانش ابری و تعداد منابع در هر گام از پژوهش

2.2. Min-Min

یک الگوریتم توازن بار ایستاست، بنابراین تمام اطلاعات مربوط به کار (job) از پیش مشخص است. برخی اصطلاحات مربوط به توازن بار در ادامه آمده است:

¹ETC: زمان مورد انتظار برای اجرای کار روی تمام گره‌ها در ماتریس ETC ذخیره می‌شود. اگر کار بر روی یک گره خاص قابل اجرا نباشد، مقدار مربوطه در ماتریس ETC بی‌نهایت در نظر گرفته می‌شود.

OLB²: یک روش توازن بار فرصت طلبانه است که در آن هر کار با ترتیبی بدون تبعیض به ETC مربوطه روی گره‌ها تخصیص داده می‌شود. OLB زمان‌بندی توازن بار را فراهم می‌کند ولی دامنه پوشش ضعیفی دارد.

MET³: الگوریتم با زمان اجرای کمینه. در این الگوریتم هر کار به گرهی که کمترین زمان اجرا را مطابق جدول ETC دارد تخصیص داده می‌شود، بدون اینکه به بار کنونی پردازنده توجه شود. MET تلاش می‌کند تا بهترين زوج کار-پردازنده را بيابد ولي چندان موفق نيست و موجب عدم توازن بار سرويس دهنده می‌شود.

MCT⁴: الگوريتم با پايين‌ترين زمان کامل شدن. در اين الگوريتم کارها براساس کوتاه‌ترین زمان براي کامل شدن به گره‌ها تخصیص داده می‌شوند. زمان کامل شدن با افزودن زمان مورد انتظار برای انجام آن کار با توجه به زمان آماده به کار گره محاسبه می‌شود. گره با کوتاه‌ترین زمان کامل شده برای انجام آن کار خاص انتخاب می‌شود. این الگوریتم در هر زمان تنها یک کار را در نظر می‌گیرد.

الگوریتم Min_Min با مجموعه‌ای از کارهای اختصاص داده نشده آغاز می‌شود. نخست کوتاه‌ترین زمان برای کامل شدن تمام کارها محاسبه می‌شود. کار با کوتاه‌ترین زمان انتخاب شده و سپس گرهی که کوتاه‌ترین زمان کامل شدن را برای تمام کارها دارد، انتخاب می‌شود. در پایان گره انتخاب شده و کار انتخاب شده تایید می‌شوند و زمان آماده به کار گره به‌هنگام‌سازی می‌شود. این فرایند تا هنگامی که تمام کارهای تخصیص داده نشده، تخصیص داده شوند، تکرار می‌شود. مزیت این الگوریتم این است که کار با کوتاه‌ترین زمان اجرا، انجام می‌شود. عیب این الگوریتم هم این است که برخی کارها ممکن است با گرسنگی مواجه شوند [11].

2.3. Max_Min

الگوریتم Max_Min مانند الگوریتم Min_Min است به جز اینکه تفاوت‌های زیر را دارد: پس از یافتن کوتاه‌ترین زمان کامل شدن برای کارها، بیشترین مقدار انتخاب می‌شود و ماشینی که کوتاه‌ترین زمان کامل شدن برای تمام کارها را دارد، انتخاب می‌شود. در پایان گره انتخاب شده و کار انتخاب شده تایید می‌شوند. سپس زمان آماده به کار گره با افزودن زمان اجرای وظیفه تخصیص داده شده به‌هنگام‌سازی می‌شود [11].

[1] Expected Time of Compute

[2] Opportunistic Load Balancing

[3] Minimum Execution Time

[4] Minimum Complete Time

جدول 1- روش‌های توازن بار و مزایا و معایب آنها

شماره منبع	سال چاپ	نوع روش استفاده شده	مزایا	معایب
[12]	2018	Central manager Algorithm [12]	· برای میزبان‌های متفاوت از کارهای پیچیده ایده‌آل است.	· دارای گلوگاه است، زیرا نیاز به هماهنگی عملیاتی بالایی دارد.
[13]	2019	Round Robin Algorithm [13]	· پرکاربرد است و راه‌اندازی آن آسان است. · با تعداد عملیات بیشتر از تعداد پردازنده‌ها به خوبی عمل می‌کند.	· در سرویس‌دهنده‌های با ورودی چندگانه بلااستفاده است و ممکن با بیش‌باری و خرابی روبرو شود. · امیدی به نتایج خوب نیست.
[9]	2020	Randomize Algorithm [14]	· ارائه گزینه‌ها سریع است. · پذیرش و سرعت بالایی دارد.	· در حالت‌های تحت فشار ممکن است بسیار کند باشد. · احتمال کمی وجود دارد که پاسخ‌های اشتباه دهد.
[13]	2019	Threshold Algorithm [13]	· مقدار آستانه‌ای ارتباط کمی با فرایندها دارد. · تخصیص‌های متنوعی به یک فرایند محلی داده می‌شود.	· اگر تمام فرایندها بیش از حد اجرا شوند، تمام رویه‌ها باید به صورت دستی تخصیص داده شوند.
[15]	2020	Opportunistic LB Algorithm [15]	· به سادگی از عهده کارهای اجباری همزمان برای گره برمی‌آید.	· وظایف به کندی برنامه‌ریزی می‌شوند، زیرا نمی‌تواند دوره زمانی اجرای کنونی گره‌ها را تعیین کند.
[16]	2015	OLB+LBMM[16]	· منابع با بازدهی بالایی مورد استفاده قرار می‌گیرند و رقابت کاری بهبود می‌یابد.	· کامل شدن و زمان اجرای وظایف گره‌ها در OLB در نظر گرفته نشده است. به Main دلیل زمان زیادی برای کامل شدن وظایف صرف می‌شود.
[17]	2019	Min-Min LB Algorithm [17]	· ساده و سریع است. · زمان انجام کلی را بهبود می‌بخشد.	· منجر به گرسنگی می‌شود.
[13], [18]	2019, 2019	Max-Min LB Algorithm[18], [13]	· کارایی بهتر از Min-Min · تعداد وظایف کوچ نسبت به وظایف طولانی بیشتر است.	· از گرسنگی رنج می‌برد.
[19]	2020	Equally Spread Current Execution Algorithm [19]	· تقویت زمان بارگذاری مرکز داده و زمان‌های پاسخ	· باید زمان پردازش را بهتر کند. · افزایش هزینه‌ها
[20]	2018	Central LB for VMs [20]	· افزایش کارایی کل فرایند	· سیستم‌های مقاوم در برابر خطا را در نظر نگرفته است.
[21]	2018	Throttled LB [21]	· بیشینه کردن استفاده از منابع · کاهش قابل توجه میانگین زمان اجرا	· در موقعیت بار کاری خاصی شبیه‌سازی نشده است. · محدودیت‌های زمانی را نمی‌یابد.
[22]	2013	Stochastic Hill Climbing [22]	· حمله به مسئله گلوگاه · توزیع بار کاری موثر سیستم	· راه حل نامناسب برای حل مسائل بهینه‌سازی
[23]	2018	Join Idle Queue [23]	· هزینه سربار اتصال پایین · مقیاس پذیری بالا · زمان پاسخ کوتاه	· پیچیدگی بالا · منابع همگون
[24]	2020	Least Connections [24]	با بررسی تعداد ارتباط‌های سرویس‌دهنده از بار بیش از حد روی یک سرویس‌دهنده پیشگیری می‌کند.	هنگام محاسبه تعداد ارتباط‌های موجود، نمی‌توان ظرفیت سرویس‌دهنده را در نظر گرفت.
[10]	2019	Weighted Round Robin [10]	می‌توان برای سرویس‌دهنده‌های با بار بالایی که ظرفیت بیشتری دارند، درخواست‌های بیشتری فرستاد.	تمام برآوردها نیاز به پیاده‌سازی این الگوریتم دارند و این اشکال بزرگی است. همچنین نیاز به برآورد شبکه‌های IP با اندازه‌های بسته مختلف دارد که انجام آن دشوار است.
[16]	2015	Source Hash [16]	کاربران پس قطع اتصال و اتصال مجدد به نشستی وصل می‌شوند که هنوز فعال است که باعث افزایش کارایی می‌شود.	· ISPها آدرس‌های IP پویا تولید می‌کنند، بنابراین نگهداری آنها دشوار است.
[25]	2020	Least Response Time [25]	ظرفیت سرویس‌دهنده، زمان پاسخ و تعداد اتصال‌های کنونی را در نظر می‌گیرد تا از بیش‌باری و شکست پیشگیری کند.	· از ماشین‌های مجازی با عملکرد ساده استفاده شده و ممکن است باعث ترافیک نابرابر شود. · برای برنامه‌های با نشست‌های مبتنی بر کوکی توصیه نمی‌شود.
[26]	2012	Least Bandwidth [26]	می‌توان برای سرویس‌دهنده‌های با بار بالایی که ظرفیت بیشتری دارند، درخواست‌های بیشتری فرستاد.	· نیاز به پهنای باند تقریبی درباره شبکه دارد که در شبکه‌های با اندازه بسته متغیر دشوار است. · ممکن است پهنای باند شبکه فرسوده شود.
[27]	2020	Adaptive LB [27]	تعصبی روی روش خاصی ندارد و بسته به شرایط بهترین روش توازن بار را انتخاب می‌کند.	· روی سیستم‌های موازی پیاده‌سازی نشده است. · سوئیچ کردن میان الگوریتم‌ها سربار دارد.

2.4. توازن بار Min_Min

LBMM یک الگوریتم توازن بار ثابت است. این الگوریتم توازن بار میان گره‌ها را با در نظر گرفتن این کار به عنوان یک مسئله زمان‌بندی پیاده‌سازی می‌کند. هدف اصلی این الگوریتم کاهش زمان صرف شده (زمان کل) است که به صورت بیشینه زمان کامل شدن تمام کارهای زمان‌بندی شده به منابع است. این الگوریتم گامهای زیر را برای زمان‌بندی کارها روی گره‌ها انجام می‌دهد.

· الگوریتم زمان‌بندی Min-Min را اجرا کن و زمان صرف شده را محاسبه می‌کند.

· گره با بیشترین زمان انجام را محاسبه می‌کند.

· کوتاه‌ترین زمان اجرای مربوط به گره را محاسبه می‌کند.

· زمان کامل شدن کار مربوطه برای تمام منابع محاسبه می‌شود.

· بیشینه زمان کامل شدن کار انتخاب شده و گامها تکرار می‌شوند.

· فرایند هنگامی متوقف می‌شود که تمام کارها و تمام گره‌ها تخصیص داده شوند.

· در سناریوهایی که در meta-task تعداد کارهای کوتاه بیشتر از کارهای بلند است، این الگوریتم کارایی بهتری دارد. این الگوریتم ناهمگونی پایین و بالای ماشین‌ها و ناهمگونی وظایف را در نظر نمی‌گیرد [11].

2.5. توازن بار Max-Min-Max

سی. وانگ و همکاران¹ [28] یک الگوریتم زمان‌بندی دو مرحله‌ای پیشنهاد کرده‌اند که OLB را LBMM ترکیب می‌کند. الگوریتم زمان‌بندی OLB تمام گره‌ها را در وضعیت در حال کار نگه می‌دارد تا به هدف توازن بار برسد و از الگوریتم زمان‌بندی LBMM برای کمینه کردن زمان اجرای هر کدام از وظایف روی گره استفاده می‌شود و بنابراین زمان کامل شدن کلی کمینه می‌شود. این رویکرد ترکیبی شامل مراحل زیر است:

1. میانگین زمان اجرای هر وظیفه فرعی (زیروظیفه) محاسبه می‌شود.

2. اگر زمان مورد نیاز برای اجرای وظیفه فرعی کمتر یا مساوی میانگین زمان اجرا بود، آنگاه وظیفه فرعی را انجام می‌دهد تا به طور معمول به پایان برسد.

3. اگر زمان مورد نیاز برای انجام وظیفه فرعی بیشتر از میانگین زمان اجرا بود، زمان اجرا برابر بینهایت در نظر گرفته می‌شود (زمان اجرا بسیار طولانی است و نمی‌تواند در نظر گرفته شود). دیگر گره‌هایی که اجرا می‌شوند، دوباره وارد سیستم خواهند شد تا در انجام وظایف فرعی مشارکت کنند.

4. گامهای 1 تا 3 را تکرار می‌کند تا تمام کارهای فرعی کامل شوند.

2.6. درهم سازی² منابع

در این الگوریتم آدرس IP منبع (کاربر) دقیقا مشخص می‌کند که کدام سرویس‌دهنده به درخواست او پاسخ می‌دهد. تصویر 2 این الگوریتم را نمایش می‌دهد. این الگوریتم هنگامی مورد استفاده قرار می‌گیرد که فراهم کننده برنامه می‌خواهد کاربر را به همان سرویس‌دهنده‌ای هدایت کند که آخرین درخواستش را انجام داده است. انجام این کار دشوار است زیرا ISPها از آدرس IP پویا استفاده می‌کنند [24] .

تصویر 2- الگوریتم درهم ساز IP [24]

2.7. کمترین اتصال‌

همانطور که از نامش پیداست درخواست‌های کاربران را به سرویس‌دهنده‌ای منتقل می‌کند که کمترین تعداد اتصال‌های فعال را داشته باشد. در تصویر 3 نمایش داده است که این الگوریتم چگونه درخواست‌های کاربران را میان سرویس‌دهنده‌های موجود توزیع می‌کند. این الگوریتم هنگامی که نشست‌های طولانی داشته باشیم، کاربرد بیشتری دارد. این الگوریتم برای کاربردهای با نشست‌های کوتاه مانند HTTP توصیه نمی‌شود اما در نشست‌های طولانی مانند LDAP، SQL و چیزهایی از این دست مفید است [24].

تصویر 3- الگوریتم با کمترین خطوط ارتباطی [24]

2.8.کوتاه‌ترین زمان پاسخ

الگوریتم کوتاه‌ترین زمان پاسخ مطابق تصویر 4 بازدید کنندگان را به سرویس‌دهنده‌ای هدایت می‌کند که کمترین مقدار اتصال‌های فعال و کوتاه‌ترین زمان پاسخ را دارد. اتصال‌هایی استفاده می‌شوند که دو پارامتر (کمترین اتصال‌های فعال و زمان پاسخ کوتاه) کمتری برای هر ماشین مجازی داشته باشند. این الگوریتم نیاز به ماشین مجازی دارد. در صورتی که از ماشین‌های مجازی با عملکرد ساده استفاده شود، ممکن است ترافیک مسیر نامساوی مشاهده شود. این الگوریتم برای نشست‌های کاربردی مبتنی بر کوکی مناسب نیست.

تصویر 4- کوتاه‌ترین زمان پاسخ [24]

2.9. کمترین پهنای باند

این الگوریتم‌ کاربران را براساس مگابیت بر ثانیه (Mbps) پردازش کرده و مطابق تصویر 5 درخواست‌های کاربران را به سرویس‌دهنده‌های با کمترین نرخ بازدید کاربران ارسال می‌کند. این الگوریتم هنگامی که تمام ماشین‌های مجازی در زیرساخت ابر پهنای باند متفاوتی دارند، بسیار پرکاربرد است. این الگوریتم به پهنای باند تقریبی شبکه نیاز دارد که به دست آوردن آن در شبکه‌های با اندازه بسته‌های متنوع متفاوت است.

تصویر 5- الگوریتم کمترین پهنای باند [24]

3. معیارهای سنجش توازن بار

برای دستیابی به کارایی بهتر و مدیریت بهتر منابع، یک متوازن کننده بار باید دائما بار کاری را میان منابع موجود توزیع کند. روش‌های توزیع بار متفاوت و معیارهای سنجش کارایی مختلفی در منابع توسط پژوهشگران برای مقایسه روش‌های مختلف توزیع بار در ابر ارائه شده‌اند تا بتوانند کارایی کلی سیستم را بهینه کرده و رضایت کاربران را افزایش دهند[28]. در پاسخ به پرسش دوم برخی از معیارهای سنجش توازن بار مطرح شده در منابع، عبارت‌اند از:

· کارایی³: کارایی در محیط ابر، معیاری است که به صورت نسبت سرویس‌های مصرف شده در طول زمان به ظرفیت تقاضا تعریف می‌شود [29].

· میانگین زمان پاسخ: زمان کلی صرف شده برای انجام درخواست ثبت شده بر روی سیستم پس از پردازش درخواست [24].

· بازدهی: مقدار کلی وظایف ثبت شده یا فرایندهای کامل شده در واحد زمان روی یک سیستم. بازدهی بالاتر به معنای کارایی بالاتر سیستم می‌باشد [11].

· مقیاس پذیری (قابلیت گسترش): توانایی سیستم برای برآمدن از عهده توازن بار با افزایش تعداد گره‌ها [20].

· تحمل خطا: توانایی روش توازن بار برای ادامه یکنواخت کار در صورت از کار افتادن گره‌ها یا خطوط ارتباطی⁴[30].

· زمان مهاجرت: زمان مهاجرت⁵ به کل زمانی اطلاق می‌شود که طول می‌کشد تا یک درخواست یا وظیفه را از یک ماشین با بیش‌باری به یک ماشین با کم‌باری انتقال داده شود. هرچه زمان مهاجرت پایین‌تر باشد، کارایی سیستم ابر بالاتر است [30].

· استفاده از منابع: این ارزیابی برای اطمینان از استفاده درست از تمام منابع موجود در سیستم ابر انجام می‌شود. استفاده بیشتر از منابع منجر به کاهش هزینه‌های کلی و کاهش انرژی مصرفی سیستم ابر می‌شود [24].

· درجه نامتوازن بودن: میزان تغییرات میان ماشین‌های مجازی را توصیف می‌کند [31].

· زمان صرف شده (زمان کل)⁶: یکی از معمول‌ترین معیارها برای سنجش کارایی زمان‌بندی در ابر می‌باشد و به صورت زمان اتمام آخرین کار کامل شده تعریف می‌شود. زمان کل کوچکتر نشان می‌دهد که تخصیص کارها به ماشین‌های مجازی به صورت مناسبی انجام شده است [32].

4- توازن بار در ابر

پرسش نخست ما این است که چرا باید به توازن بار در ابر پرداخت؟ پاسخ کوتاه این است که هدف اصلی توازن بار پیشگیری از بیش‌باری یک سرویس‌دهنده و کم باری سرویس‌دهنده دیگر است، که بیش‌باری می‌تواند به افت کارایی و افزایش زمان پاسخ و در نهایت از کار افتادن سرویس‌دهنده منجر شود و کم باری هم باعث اتلاف منابع می‌شود [33]. ابر با ارائه مجموعه سرویس‌های متنوع نیاز دارد تا بتواند کیفیت این سرویس‌ها را با پایش سرویس‌های ارائه شده تضمین کند. ابر برای پاسخ به درخواست‌های کاربران با چالش‌های زیادی روبرو است که یکی از آنها توازن بار⁷ است [34]. زمان‌بندی یا تخصیص درخواست‌های کاربر – وظایف- یک مسئله بهینه‌سازی NP-hard است [35].

بنابراین برای ارائه سرویس‌های بهتر لازم است تا توازن بار در ابر (LBC) مورد مطالعه قرار گرفته و با بررسی چالش‌های آن از موقعیت‌هایی که باعث بار بیش از حد و بار کمتر از حد⁸ انتظار می‌شوند پیشگیری شود [2] و همچنین روش‌هایی برای توازن بار موثر ارائه گردد. برای توازن بار در ابر روش‌های گوناگونی ارائه شده‌اند که به دو دسته کلی روش‌های توازن بار ایستا و پویا تقسیم می‌شوند. روش‌های ایستا به دو دسته نیمه بهینه و بهینه تقسیم‌بندی می‌شوند. روش‌های پویا نیز به دو دسته توزیع شده و غیر توزیع شده تقسیم می‌شوند. در تصویر 6 دسته‌بندی روش‌های توازن بار از این منظر به نمایش گذاشته شده‌اند.

الف) الگوریتم‌های ایستا: الگوریتم‌های ایستای توازن بار، بار را به طور متوازن میان سرویس‌دهنده‌ها تقسیم می‌کنند. در این سناریوها، ابر نیاز به یک دانش اولیه درباره اندازه سرویس‌دهنده، توان پردازش، حافظه، کارایی و نیازمندی‌های کاربران ابر دارد. در طول زمان اجرا نیازهای کاربران تغییر می‌کنند و الگوریتم‌های ایستا توانایی تطبیق با نیازهای در حال تغییر کاربران را ندارند. به عنوان نمونه‌هایی از این نوع الگوریتم‌ها می‌توان به الگوریتم‌هایی مانند راند روبین، راند روبین وزن‌دار و الگوریتم نخست کوتاه ترین کار⁹ (SJF) اشاره کرد.

ب) الگوریتم‌های پویا: الگوریتم‌های پویای توازن بار شرایط کنونی سرویس‌دهنده‌های ابر را روی شبکه بررسی کرده و براساس رویکرد به کار رفته سرویس‌دهنده مناسب با کمترین بار کاری را برای ارائه سرویس انتخاب می‌کنند. با توجه به تغییر نیازهای کاربران در هنگام اجرا، توازن بار در هنگام اجرا تغییر کرده و الگوریتم توازن بار باید بتواند در هنگام اجرا با کاری روی سرویس‌دهنده‌ها را با توجه به شرایط موجود مدیریت کند [36].

تصویر 6- دسته‌بندی استراتژی‌های توازن بار در سیستم‌های مختلف

5. روش‌های فراابتکاری (الگوریتم‌های فراابتکاری)

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

برای حل چنین مسائلی روش‌های بهینه‌سازی فراابتکاری ارائه شده‌اند که قادر به حل این مسائل در تعداد دورهای محدود می‌باشند. الگوریتم‌های فراابتکاری از یک منظر به دو دسته کلی تقسیم می‌شوند:

· الگوریتم‌های مبتنی بر یک جواب

· الگوریتم‌های مبتنی بر جمعیت

در الگوریتم‌های مبتنی بر یک جواب، یک راه حل به طور تصادفی تولید شده و بهبود می‌یابد تا به جواب بهینه به دست آید ولی در الگوریتم‌های مبتنی بر جمعیت، به طور تصادفی مجموعه‌ای از جواب‌های تصادفی تولید می‌شوند و فضای جست‌وجوی داده شده و مقادیر راه حل، گام به گام به روز رسانی می‌شوند تا بهترین راه حل تولید شود. الگوریتم‌های مبتنی بر یک جواب ممکن است در دام جواب بهینه محلی بیفتند و نتوانند جواب بهینه کلی را بیابند، بنابراین امروزه بیشتر از الگوریتم‌های مبتنی بر جمعیت که توانایی ذاتی گریز از دام بهینگی محلی دارند، برای مسائل بهینه‌سازی استفاده می‌شود [38].

در این کار تعدادی از الگوریتم‌های مبتنی بر یک جواب و تعدادی از الگوریتم‌های مبتنی بر جمعیت پرکاربرد مطرح شده در منابع، مورد بررسی قرار گرفته‌اند:

· الگوریتم‌های فراابتکاری

o الگوریتم‌های مبتنی بر یک جواب

§ تبرید شبیه‌سازی شده

§ جست‌وجوی ممنوعه

o الگوریتم‌های مبتنی بر جمعیت

§ الگوریتم‌های تکاملی

· الگوریتم جست‌وجوی فاخته

· الگوریتم ژنتیک¹⁰

· الگوریتم استراتژی عقاب

§ الگوریتم‌های ازدحامی

· الگوریتم ازدحام ذرات

· الگوریتم کلونی مورچه‌ها

· الگوریتم جست‌وجوی زنبور عسل

· الگوریتم زنبور عسل مصنوعی

· الگوریتم عقاب

§ الگوریتم‌های مبتنی بر فیزیک

· الگوریتم توازن فشار اسمزی

o الگوریتم‌های ترکیبی

§ کلونی مورچه و زنبور عسل

§ ژنتیک و ازدحام ذرات

§ ...

در تصویر 7 رده‌بندی پیشنهادی الگوریتم‌های جست‌وجوی فراابتکاری به کار رفته در ابر نمایش داده شده‌اند.

5-1- الگوریتم‌های مبتنی بر یک جواب

5-1-1- تبرید شبیه‌سازی شده

تبرید شبیه‌سازی شده از تبرید مواد جامد مانند فلزات و شیشه الهام گرفته شده است که جامدات را گرم کرده و به آرامی سرد می‌کنند تا جنبش‌های درونی آن کمینه گردد. هدف این است که اندازه کریستال‌ها در حالت جامد به بزرگترین مقدار برسد. شبیه‌سازی تبرید رویکردی است که مسئله کمینه‌سازی یک تابع با تعداد بسیار زیادی متغیر را به یک مسئله مکانیک آماری کاهش می‌دهد. می‌توان تبرید تدریجی و آرام در این الگوریتم را به عنوان کاهش تدریجی احتمال انتخاب پاسخ‌های بدتر در هنگام جستجو در فضای پاسخ‌ها دانست [39]. در [32] از بهبود کارایی بهینه‌ساز شاهین هریس (HHO)¹¹ با استفاده از الگوریتم تبرید شبیه‌سازی شده به عنوان متدی جایگزین برای تخصیص کار در محیط ابر استفاده شده است.

5-1-2- جست‌وجوی ممنوعه

الگوریتم جست‌وجوی ممنوعه یک الگوریتم بهینه‌سازی سراسری با هدف شبیه‌سازی عقل انسانی است و توانایی بهینه‌سازی بالایی دارد. هدف این الگوریتم مدیریت رویکردهای دیگر است تا در تله بهینه‌سازی محلی نیفتند و برای تخصیص منابع و دیگر مسائل بهینه‌سازی کاربرد دارد [30]. در [40] از یک معماری ارتباطی میان گره‌های ابر و مه استفاده شده است. هدف این معماری استفاده از مزایای توانایی‌های رایانشی گره‌های مه در لحظه زمان‌بندی وظایف و انتخاب گره‌های مشارکت کننده در اجرا می‌باشد. این معماری دارای سه لایه زیرساخت، مه و ابر می‌باشد. در این کار، از یک روش جست‌وجوی ممنوعه ساده برای توازن بار بهینه میان گره‌های مه و ابر استفاده کرده است و مسئله بهینه‌سازی دو هدفه (بیشینه کردن استفاده از لایه رایانش مه و کمینه کردن لایه رایانش ابر) را به یک مسئله بهینه‌سازی تک هدفه تبدیل نموده است.

[1] Shu-Ching Wang et al.

[2] Hashing

[3] Efficiency

[4] Links

[5] Migration time

[6] Make span

[7] Load Balancing

[8] Overloading/underloading

[9] Shortest Job First

[10] Genetic

[11] Harris’s Hawks Optimizer

5-2- الگوریتم‌های مبتنی بر جمعیت

5-2-1- الگوریتم‌های تکاملی

5-2-1-1- الگوریتم جست‌وجوی فاخته (کوکو)

تکنیک جست‌وجوی فاخته یک الگوریتم فراابتکاری است که رفتار جنس فاخته را مدل‌سازی می‌کند. این الگوریتم با جابجایی متغیرها بهترین راه حل و کاراترین تعادل محلی را کشف می‌کند. مقادیر به دست آمده با این روش بهتر از بهینه‌سازی ازدحام ذرات می‌باشند. در [41] الگوریتم جست‌وجوی فاخته به همراه الگوریتم کرم شب‌تاب¹ (CS-FA) برای توازن بار در محیط ابر پیشنهاد شده است. نخست ظرفیت و بار هر کدام از ماشین‌ها محاسبه می‌شود. اگر بار ماشین مجازی بیشتر از یک مقدار آستانه‌ای بود، الگوریتم توازن بار برای تخصیص وظایف استفاده می‌شود. این الگوریتم بهترین ماشین مجازی را برای تخصیص وظایف انتخاب کرده و وظایف ماشین‌های مجازی با بیش‌باری را به ماشین‌های با بار کم مهاجرت می‌دهد. این الگوریتم بیشتر از نامتوازن شدن بار در محیط ابر پیشگیری می‌کند. کارایی الگوریتم CS-FA با الگوریتم‌های موجود مقایسه شده و مشاهده شده است که در این الگوریتم تعداد مهاجرت‌ها به میزان قابل توجهی کمتر از روش‌های توازن بار دیگر می‌باشد. در [42] یک الگوریتم آگاه از بار مبتنی بر جست‌وجوی کوکو، با هدف کاهش زمان انجام کل و هزینه رایانش با داشتن محدودیت زمانی ارائه شده است. مدنی² و همکاران، مسئله زمان‌بندی منابع را با در نظر گرفتن یک الگوریتم جست‌وجوی با چند هدف الهام گرفته از جست‌وجوی کوکو حل کرده‌اند [43].

5-2-1-2- الگوریتم ژنتیک

الگوریتم‌های ژنتیک دسته‌ای از الگوریتم‌های تکاملی هستند که روی سناریوهای با یک یا چند هدف اعمال می‌شوند. تصویر 8 شکل کلی یک الگوریتم ژنتیک را بازنمایی می‌کند.

Share To

Article Url

A review of the application of meta-heuristic algorithms in load balancing in cloud computing