توازن‌بار در محیط رایانش ابری با در نظر گرفتن وابستگی میان وظایف و استفاده از الگوریتم ژنتیک تطبیقی
محورهای موضوعی : مهندسی الکترونیکیلدا درخشانیان 1 , سید جواد میرعابدینی 2 , علی هارون آبادی 3
1 - گروه مهندسی کامپیوتر – نرم‌افزار، واحد بوشهر، دانشگاه آزاد اسلامی، بوشهر، ایران
2 - گروه کامپیوتر، واحد تهران مرکز، دانشگاه آزاد اسلامی، تهران، ایران
3 - گروه مهندسی کامپیوتر، واحد تهران مرکز، دانشگاه آزاد اسلامی، تهران، ایران
کلید واژه: cloud computing, Load balancing, Tasks dependency, Adaptive Genetic, رایانش ابری, توازن‌بار, وابستگی وظایف, ژنتیک تطبیقی,
چکیده مقاله :
گسترش روز افزون نیازهای محاسباتی، اهمیت استفاده از رایانش ابری را روز به روز بیشتر می‌کند. رایانش ابری، یک مدل رایانشی بر مبنای شبکه‌های رایانه‌ای است که الگویی تازه برای عرضه‌ی منابع را ارائه می‌دهد، بگونه‌ای که کاربران بر اساس نیاز خود، منابع را درخواست نموده یا آنها را آزاد می‌سازند. هنگامیکه تقاضاها برای استفاده از منابع رایانشی افزایش می‌یابند، توزیع مناسب آنها از اهمیت بالایی برخوردار می‌شود، چراکه اگر یک واحد پردازشی دارای حجم زیادی از وظایف، و واحدی دیگر تقریباً بیکار باشد، از منابع بخوبی استفاده نمی‌شود و همچنین زمان اتمام کل وظایف می‌تواند بسیار افزایش بیابد. لذا برای غلبه بر این مشکل، از تکنیک توازن بار استفاده می‌شود. بطورکلی از دید محاسباتی، به فرایند توزیع متعادل بار بر روی واحدهای پردازشی، توازن‌بار گفته می‌شود. در اکثر پژوهش‌های انجام‌شده در رابطه با توازن‌بار، تعاملات میان وظایف در حال اجرا، در نظر گرفته نشده، لذا در صورتیکه وظایف در تعامل با یکدیگر، در واحدهای پردازشی مجزا، در یک شبکه توزیع‌شده قرار گرفته باشند، تعاملات میان آنها می‌تواند در زمان اتمام کل وظایف، تاثیرگذار باشد. هدف از این پژوهش، ارائه روشی است که بتواند با در نظر گرفتن تعاملات میان وظایف، به یک توازن‌بار مطلوب در شبکه دست یابد، بطوریکه زمان اتمام کل و زمان بیکاری ماشین‌ها به حداقل برسند. برای این منظور، از الگوریتم ژنتیک استفاده می‌شود. نتایج آزمایشی بدست‌آمده نشان می‌دهند که محلی‌کردن تعاملات، تاثیر قابل توجهی در کاهش زمان اتمام کل خواهد داشت.
The increasing computing needs leads to an increase in the importance of using cloud computing day by day. Cloud computing is a computing model based on computer networks that presents a new pattern to supply resources, so that users request or release resources based on their needs. When the requests for computing resources increase, proper distribution of resources becomes very important, because if a computational unit has a large number of tasks and the other one is almost idle, resources are not used well and also makespan would be very high. Therefore, in order to overcome this problem, load balancing technique is used. In general, from the computing point of view, the process of distributing the loads on the processing units in a balanced way is called load balancing. In most researches, interactions between running tasks are not considered, so if the tasks in interaction with each other are located in separate processing units in a distributed network, the interactions between them would be effective on makespan. The aim of this research is to present an approach which can achieve a desirable load balancing in the network, such that the makespan and idle time of machines minimized, taking into account the interactions between the tasks. For this purpose, the genetic algorithm is used. The obtained experimental results show that localizing the interactions will have a significant impact in reducing the makespan.
]1[ حاتمیان، آناهیتا؛ بزرگی راد، سیدیاسر و نعمتی، سمیرا، "ارائه یک روش جدید مبتنی بر ترکیب الگوریتم‌های ژنتیک و کلونی مورچه‌ها جهت توازن بار در رایانش ابری"، دومین کنفرانس ملی توسعه علوم مهندسی، دوره 2، 1394.
]2[ سعادتی، فاطمه و میرعابدینی، سیدجواد، "بهبود روند توازن بار در پردازش ابری به کمک متغیرهای وزنی با رویکرد فازی"، کنفرانس بین المللی سیستمهای غیر خطی و بهینه سازی مهندسی برق و کامپیوتر، دوره 1، 1394.
]3[ میر، سجاد و فاضلی، مهدی، "ارائه یک الگوریتم زمانبندی وظایف کارا در محیط‌های رایانش ابری بر مبنای الگوریتم ژنتیک بهینه‌سازی شده"، اولین کنفرانس بین المللی وب پژوهی، دوره 1، 1394.
[4] A.Agarwal, G.Manisha, R. N.Milind, & S. S.Shylaja,“ A Survey of Cloud Based Load Balancing Techniques”, In proc. Proceedings of Int. Conf. on Electrical, Electronics, Computer Science & Mechanical Engg, 2014.
[5] L.Bononi, M.Bracuto, G. D'Angelo, & L.Donatiello, “A new adaptive middleware for parallel and distributed simulation of dynamically interacting systems”, In proc. Distributed Simulation and Real-Time Applications, Eighth IEEE International Symposium on, pp. 178-187, 2004.
[6] L.Bononi, G.D'Angelo, & L.Donatiello, “ HLA-based adaptive distributed simulation of wireless mobile systems”, In proc. Proceedings of the seventeenth workshop on Parallel and distributed simulation, 2003, pp. 40-49.
[7] J.Cao, K.Li, & I.Stojmenovic, “Optimal power allocation and load distribution for multiple heterogeneous multicore server processors across clouds and data centers”, IEEE Transactions on Computers, Vol. 63, No.1, pp. 45-58, 2014.
[8] N. K.Chien, N. H.Son, & H. D.Loc,“Load balancing algorithm based on estimating finish time of services in cloud computing”, In proc. 2016 18th International Conference on Advanced Communication Technology (ICACT), January 2016, pp. 228-233.
[9] D.C.Chou,“ Cloud computing: A value creation model”, Computer Standards & Interfaces, Vol.38, pp. 72-77, 2015.
[10] G. D’Angelo, & M.Marzolla, “New trends in parallel and distributed simulation: From many-cores to Cloud Computing”, Simulation Modelling Practice and Theory, Vol.49, pp. 320-335, 2014.
[11] K.Dasgupta, B.Mandal, P.Dutta, J. K.Mandal, & S. Dam, “A genetic algorithm (ga) based load balancing strategy for cloud computing”, Procedia Technology, Vol. 10, pp. 340-347, 2013.
[12] I.D. Falco, E.Laskowski, R.Olejnik, U.Scafuri, E. Tarantino, & M.Tudruj, “Extremal Optimization applied to load balancing in execution of distributed programs”, Applied Soft Computing, Vol. 30, pp. 501-513, 2015.
[13] T.Desai, & J.Prajapati, “A survey of various load balancing techniques and challenges in cloud computing”, International Journal of Scientific & Technology Research, Vol. 2, No. 11, pp. 158-161, 2013.
[14] F.Ghazipour, S. J. Mirabedini, & A. Harounabadi, “ Proposing a new Job Scheduling Algorithm in Grid Environment Using a Combination of Ant Colony Optimization Algorithm (ACO) and Suffrage”, International Journal of Computer Applications Technology and Research, Vol. 5, No. 1, pp. 20-25, 2016.
[15] J.O. Gutierrez-Garcia, & A. Ramirez-Nafarrate, “Agent-based load balancing in Cloud data centers”, Cluster Computing, Vol. 18, No. 3, pp. 1041-1062, 2015.
[16] M.Katyal, & A.Mishra,“A comparative study of load balancing algorithms in cloud computing environment”, arXiv preprint arXiv, pp.1403.6918, 2014.
[17] A.Khiyaita, H.El Bakkali, M.Zbakh, & D.El Kettani, “ Load balancing cloud computing: state of art”, In proc. Network Security and Systems (JNS2), April 2012, pp. 106-109.
[18] Y.Lu, Q.Xie, G.Kliot, A.Geller, J. R. Larus, & A.Greenberg, “Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services”, Performance Evaluation, Vol. 68, No. 11, pp. 1056-1071, 2011.
[19] T.Mastelic, A.Oleksiak, H.Claussen, I.Brandic, J.M.Pierson, & A. V.Vasilakos, “Cloud computing: Survey on energy efficiency”, ACM Computing Surveys (CSUR), Vol. 47, No. 2, pp. 1-36, 2015.
[20] P.Mell, & T. Grance, “ The NIST definition of cloud computing”, 2011.
[21] R. K.Naha, & M.Othman,“ Optimized load balancing for efficient resource provisioning in the cloud”, In proc. Telecommunication Technologies (ISTT), 2014 IEEE 2nd International Symposium on, November 2014, pp. 442-445.
[22] Z.Pooranian, A.Harounabadi, M.Shojafar, & J.Mirabedini,“ Hybrid pso for independent task scheduling in grid computing to decrease makespan”, In Proc. of International Conference on Future Information Technology, IPCSIT'11, Vol. 13, 2011, pp. 435-439.
[23] Y.W.Qiu, & J. I. G.Hwang, “ A Two-Level Load Balancing Method with Dynamic Strategy for Cloud Computing”, In proc. Dependable, Autonomic and Secure Computing, 14th Intl Conf on Pervasive Intelligence and Computing, 2nd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress (DASC/PiCom/DataCom/CyberSciTech), 2016 IEEE 14th Intl C, August 2016 , pp. 565-571.
[24] B.Radojević, & M. Žagar,“ Analysis of issues with load balancing algorithms in hosted (cloud) environments”, In proc. MIPRO, 2011 Proceedings of the 34th International Convention, May 2011, pp. 416-420.
[25] B. L.Sahu, & R.Tiwari, “ A comprehensive study on Cloud computing”, International journal of Advanced Research in Computer science and Software engineering, Vol. 2, No.9, pp. 33-37, 2012.
_||_]1[ حاتمیان، آناهیتا؛ بزرگی راد، سیدیاسر و نعمتی، سمیرا، "ارائه یک روش جدید مبتنی بر ترکیب الگوریتم‌های ژنتیک و کلونی مورچه‌ها جهت توازن بار در رایانش ابری"، دومین کنفرانس ملی توسعه علوم مهندسی، دوره 2، 1394.
]2[ سعادتی، فاطمه و میرعابدینی، سیدجواد، "بهبود روند توازن بار در پردازش ابری به کمک متغیرهای وزنی با رویکرد فازی"، کنفرانس بین المللی سیستمهای غیر خطی و بهینه سازی مهندسی برق و کامپیوتر، دوره 1، 1394.
]3[ میر، سجاد و فاضلی، مهدی، "ارائه یک الگوریتم زمانبندی وظایف کارا در محیط‌های رایانش ابری بر مبنای الگوریتم ژنتیک بهینه‌سازی شده"، اولین کنفرانس بین المللی وب پژوهی، دوره 1، 1394.
[4] A.Agarwal, G.Manisha, R. N.Milind, & S. S.Shylaja,“ A Survey of Cloud Based Load Balancing Techniques”, In proc. Proceedings of Int. Conf. on Electrical, Electronics, Computer Science & Mechanical Engg, 2014.
[5] L.Bononi, M.Bracuto, G. D'Angelo, & L.Donatiello, “A new adaptive middleware for parallel and distributed simulation of dynamically interacting systems”, In proc. Distributed Simulation and Real-Time Applications, Eighth IEEE International Symposium on, pp. 178-187, 2004.
[6] L.Bononi, G.D'Angelo, & L.Donatiello, “ HLA-based adaptive distributed simulation of wireless mobile systems”, In proc. Proceedings of the seventeenth workshop on Parallel and distributed simulation, 2003, pp. 40-49.
[7] J.Cao, K.Li, & I.Stojmenovic, “Optimal power allocation and load distribution for multiple heterogeneous multicore server processors across clouds and data centers”, IEEE Transactions on Computers, Vol. 63, No.1, pp. 45-58, 2014.
[8] N. K.Chien, N. H.Son, & H. D.Loc,“Load balancing algorithm based on estimating finish time of services in cloud computing”, In proc. 2016 18th International Conference on Advanced Communication Technology (ICACT), January 2016, pp. 228-233.
[9] D.C.Chou,“ Cloud computing: A value creation model”, Computer Standards & Interfaces, Vol.38, pp. 72-77, 2015.
[10] G. D’Angelo, & M.Marzolla, “New trends in parallel and distributed simulation: From many-cores to Cloud Computing”, Simulation Modelling Practice and Theory, Vol.49, pp. 320-335, 2014.
[11] K.Dasgupta, B.Mandal, P.Dutta, J. K.Mandal, & S. Dam, “A genetic algorithm (ga) based load balancing strategy for cloud computing”, Procedia Technology, Vol. 10, pp. 340-347, 2013.
[12] I.D. Falco, E.Laskowski, R.Olejnik, U.Scafuri, E. Tarantino, & M.Tudruj, “Extremal Optimization applied to load balancing in execution of distributed programs”, Applied Soft Computing, Vol. 30, pp. 501-513, 2015.
[13] T.Desai, & J.Prajapati, “A survey of various load balancing techniques and challenges in cloud computing”, International Journal of Scientific & Technology Research, Vol. 2, No. 11, pp. 158-161, 2013.
[14] F.Ghazipour, S. J. Mirabedini, & A. Harounabadi, “ Proposing a new Job Scheduling Algorithm in Grid Environment Using a Combination of Ant Colony Optimization Algorithm (ACO) and Suffrage”, International Journal of Computer Applications Technology and Research, Vol. 5, No. 1, pp. 20-25, 2016.
[15] J.O. Gutierrez-Garcia, & A. Ramirez-Nafarrate, “Agent-based load balancing in Cloud data centers”, Cluster Computing, Vol. 18, No. 3, pp. 1041-1062, 2015.
[16] M.Katyal, & A.Mishra,“A comparative study of load balancing algorithms in cloud computing environment”, arXiv preprint arXiv, pp.1403.6918, 2014.
[17] A.Khiyaita, H.El Bakkali, M.Zbakh, & D.El Kettani, “ Load balancing cloud computing: state of art”, In proc. Network Security and Systems (JNS2), April 2012, pp. 106-109.
[18] Y.Lu, Q.Xie, G.Kliot, A.Geller, J. R. Larus, & A.Greenberg, “Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services”, Performance Evaluation, Vol. 68, No. 11, pp. 1056-1071, 2011.
[19] T.Mastelic, A.Oleksiak, H.Claussen, I.Brandic, J.M.Pierson, & A. V.Vasilakos, “Cloud computing: Survey on energy efficiency”, ACM Computing Surveys (CSUR), Vol. 47, No. 2, pp. 1-36, 2015.
[20] P.Mell, & T. Grance, “ The NIST definition of cloud computing”, 2011.
[21] R. K.Naha, & M.Othman,“ Optimized load balancing for efficient resource provisioning in the cloud”, In proc. Telecommunication Technologies (ISTT), 2014 IEEE 2nd International Symposium on, November 2014, pp. 442-445.
[22] Z.Pooranian, A.Harounabadi, M.Shojafar, & J.Mirabedini,“ Hybrid pso for independent task scheduling in grid computing to decrease makespan”, In Proc. of International Conference on Future Information Technology, IPCSIT'11, Vol. 13, 2011, pp. 435-439.
[23] Y.W.Qiu, & J. I. G.Hwang, “ A Two-Level Load Balancing Method with Dynamic Strategy for Cloud Computing”, In proc. Dependable, Autonomic and Secure Computing, 14th Intl Conf on Pervasive Intelligence and Computing, 2nd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress (DASC/PiCom/DataCom/CyberSciTech), 2016 IEEE 14th Intl C, August 2016 , pp. 565-571.
[24] B.Radojević, & M. Žagar,“ Analysis of issues with load balancing algorithms in hosted (cloud) environments”, In proc. MIPRO, 2011 Proceedings of the 34th International Convention, May 2011, pp. 416-420.
[25] B. L.Sahu, & R.Tiwari, “ A comprehensive study on Cloud computing”, International journal of Advanced Research in Computer science and Software engineering, Vol. 2, No.9, pp. 33-37, 2012.