بخشی از مقاله
بررسی موردی الگوریتم های ایستا و پویای تعادل بار در رایانش ابری
چکیده - امروزه گسترش فناوری اطلاعات وارتباطات باعث افزایش سرعت، کارایی و کاهش هزینه های موجود در شبکه های کامپیوتری شده است. مبحث رایانش ابری تحولی جدید ایجاد کرده است. رایانش ابری یک مخزن از منابع فیزیکی و مجازی است که در واقع کلیه کار های رایانش ابری می بایست به صورت سرویس ارائه شوند و تعادل بار در این شبکه ها مهم است که خود باعث افزایش کارایی در رایانش ابری می شود. انتخاب گره مناسب برای انجام یک وظیفه خاص می تواند تا حد زیادی کارایی را بهبود بخشد و خدمات رسانی را بصورت متعادل انجام دهد. مسئله تعادل بار با استفاده از روش های الگوریتم ژنتیک، الگوریتم ژنتیک موازی، مسئله کلونی مورچگان، الگوریتم رفتار زنبور عسل، الگوریتم PSO و توسط بسیاری از الگوریتم هایی که مربوط به حل مسائل زمانبندی مربوط می شوند نیز حل شده است . دراین مقاله به مقایسه مهمترین الگوریتم های زمانبندی تعادل بارمی پردازیم.
واژگان کلیدی: الگوریتم های تعادل بار، تعادل بار، رایانش ابری ، ماشین مجازی
-1 مقدمه
یکی از مهمترین مولفه های یک معماری محاسبات ابری مولفه ی توازن بار است . مهمترین وظیفه ای این مولفه دریافت کارهای کاربران و توزیع آنها بر روی سرورهای متفاوت می باشد ، به گونه ای که دسترسی به داد ه ها تا حد امکان محلی شده و محاسبات بصورت نیز بصورت متوازن بر روی هر سرور قرار گیرد. یعنی آنکه درصد بکارگیری منابع سرورها تقریبا یکسان گردد . فرایند توازن بار در واقع یک فرایند جا به جای و بارگذاری کلی است تا گره های منحصر به فرد در یک سیستم اشتراکی ، استفاده موثر از منابع را داشته باشند و زمان پاسخ به کارها را بهبود بخشند و بطور همزمان تقسیم کار را بین گره ها انجام دهد .[9]
الگوریتم متفاوت و زیادی در بحث تعادل بار وجود دارند که می توان آنها را به دو دسته اصلی تقسیم بندی نمود که تقسیم بندی آنها به شرح زیر می باشد : [1 ]
-1-1 الگوریتم تعادل بار ایستا
این نوع از الگوریتم ها ترافیک را به چندین سرور به صورت متعادل تقسیم میکنند. با این روش ترافیک روی سرور ها به آسانی قابل تفکیک است و در نتیجه ترافیک به صورت موثرتری قابل تعمیم است این الگوریتم ها با استفاده از الگوریتم نوبت چرخشی به صورت مساوی ترافیک را تقسیم میکند. بنابراین الگوریتم نوبت چرخشی وزن دار برای بهبود چالش های موجود در الگوریتم نوبت چرخشی تعریف شده است. در این الگوریتم هر سروری به آن یک وزن اختصاص داده می شود و طبق بیشترین وزن برای هر سرور تعداد ارتباطات بیشتری آن سرور قبول می کند. و در این حالت همه سرور ها دارای یک وزن میباشند. و بدین صورت ترافیک را به صورت متعادل دریافت می کنند .[2]
-2-1 الگوریتم تعادل بار پویا
در این نوع الگوریتم ها وزن های مناسب روی هم سرور ها طراحی میشوند که این کار توسط جستجوی کلی شبکه انجام میشود و سبک ترین سرور برای انجام عمل متعادل بار توزیع داده میشود انتخاب سرور مناسب نیاز به زمان واقعی جهت ارتباط با شبکه دارد. که باعث هدایت ترافیک بیشتر برای سیستم می شود. الگوریتم پویا از یک پرس و جوی پیش بینی شده روی هم سرور ها بصورت مرتب استفاده میکند. ولی در بعضی مواقع ترافیک غالب شده و از پاسخ پرس و جو ها جلوگیری میکند و باعث ایجاد ترافیک در شبکه میشود . [2 ]
-2 بررسی الگوریتم های تعادل بار
در قسمت قبل الگوریتم های ایستا و پویا را تعریف نموده و حال به دسته بندی و کارایی هر کدام از الگوریتم ها پرداخته می شود.
-1-2 الگوریتم ژنتیک
الگوریتم ژنتیک از مجموعه تکنیکهای تکاملی بر گرفته از طبیعت است که کاربرد فراوانی در مسائل بهینه سازی دارد.
برحسب جمعیت بالقوه عمل می کند و اصول تنازع بقا را در تولید تقریبهای بهترو بهتر جواب مسئله به کار می رود.الگوریتم ژنتیک روشی بهینه برای حل مسائل بهینه سازی میباشد و همچنین روشی ساده و سریع است و میتواندجایگزین روش های دیگر شود. این الگوریتم میتواند ما را به حل بهینه ای برساند که با روشهای دیگر امکان پذیر نیست .[6]
-2-2 الگوریتم ژنتیک ترکیبی
الگوریتم ژنتیک ترکیبی یک نوع الگوریتم ژنتیک بهبود شده است. الگوریتم ژنتیک و الگوریتم ژنتیک ترکیبی((MAGA در صورت لزوم کروموزم ها را تغییر می دهند. هر کروموزم در الگوریتم ژنتیک ترکیبی یک عامل در نظر گرفته می شود. همه عوامل در محیط عامل شبکه هستند.در الگوریتم ژنتیک ترکیبی کروموزم ها می توانند یکنواخت نباشند و همچنین چهار نوع عملگر در آن تعریف شده است .[7]
-3-2 الگوریتم کلونی مورچگان
با بهینه سازی الگوریتم جامعه مورچگان، یک روش بهینه سازی نشات گرفته از رفتار مورچه ها در یافتن غذا می باشد. در سال های اخیر محققان دریافته اند که مورچه ها گرچه تقریباً به طور کامل نابینا هستند ولی می توانند به طور موفقیت آمیزی خود را بین لانه و منابع غذایی هدایت کنند و طی همین فرآیند کوتاهترین راه را کشف کنند. مورچه ها مسیر بین غذا و لانه خود را، در ابتدا به صورت کاملاً تصادفی انتخاب می کنند و کم کم پس از طی چندین دوره رفت و برگشت بین غذا و لانه و افزایش اثر برجای مانده در مسیر کوتاهتر، در نهایت همگی در کوتاهترین مسیر حرکت می کنند. وقتی مورچه ای به دنبال غذا می گردد، در طول مسیر حرکت ماده بوداری به نام فرمون1 از خود بر جای می گذارند که سایر مورچه ها می توانند فرمون موجود را استشمام کرده و سپس مسیری که غلظت فرمون بیشتری دارد را انتخاب کنند 4]و.[5
-4-2 الگوریتم متعادل کننده فرصـت طلـب : (2OLB )
این الگوریتم در نظر دارد که گره ها را مشـغول نگـه دارد .صـرف نظر از حجم کاری که آن گره در حال حاضر دارد و وظایف را بـه صورت تصادفی به گره های قابل دسترس اختصاص میدهد .[3]
-5-2 الگوریتم حداقل زمان اتمام : (3MCT)
در این الگوریتم به گره وظیفه ای را می داد که انتظار می رود حداقل زمان جهت اتمام این وظیفه را نسبت به گره های دیگر داشته باشد . [ 3 ]
-6-2 الگوریتم زمان بندی حداقل حداقل : 4MM
همان روش برنامه ریزی حداقل زمان اتمام الگوریتم MCT را برای واگذاری وظیفه به گرهی که می تواند این کار را با حداقل زمان اتمام نسبت به بقیه گره ها دیگر انجام دهد پذیرفت .[3]
-7-2 الگوریتم حداقل حداقل تعادل بار :(5LBMM)
در این روش زمان بندی MM و استراتژی حفظ تعادل بار را پذیرفت. این می تواند از انتساب تکرار غیر ضروری اجتناب کنند.
روش زمانبندی MM و استراتژی حفظ تعادل بار را باهم ترکیب کرد .[3]
-8-2 الگوریتم : 6LB3M
این الگوریتم می تواند تعادل بار بهتر و عملکرد بهتر نسبت به الگوریتم های دیگر، مانند الگوریتم MM و LBMM را داشته باشد .[3]
-9-2 الگوریتم :7SHC
این الگوریتم برای بهینه سازی حداکثر از منابع موجود استفاده می کند. الگوریتم SHC یک تعادل بار غیر متمرکز می باشد که مبتنی بر محاسبات نرم می باشد .[8]
-3 ابزار های مورد استفاده شبیه سازی رایانش ابر
- :Cloud Sim
در ابتدا توسط دانشگاه ملبورن روانه بازار شد. ایـن شـبیه سـاز بـا Java طراحی شده است ویک نرم افزار نسخه باز می باشد ،کـه در محیط های ویندوز ،یونیکس و لینوکس نیز قابـل اجـرا و اسـتفاده می باشد و این نرم افزار دارای کاربردهـای ماننـد مـدل سـازی و شــبیه ســازی مراکــز داده، مــدل ســازی ابرهــای فــدرال، نمــایش چگونگی ساخت یک فضای ابری و غیره می باشد.
- :Cloud Analyst
