بخشی از مقاله
چالش ها و الگوریتم های تعادل باردر رایانش ابری با تکیه بر الگوریتم کلونی مورچگان (ACO)
چکیده
رایانش ابری به سرعت درحال رشد است. دررایانش ابری، منابع، اطلاعات، نرم افزارودیگر دستگاه های به اشتراک
گذاشته شده بسته به نیازمشتری درزمان خاص ارائه می شوند.رایانش ابری شامل مجازی سازی، رایانش توزیع
شده، پلت فرم، زیرساخت ها، نرم افزار و خدمات مبتنی بر وب می باشد. تعادل باریک مسئله چالش برانگیزدرمحیط ابری است. تعادل بار یک فرایند توزیع شده است که در آن بار در میان گره های مختلف سیستم توزیع شده تا باعث استفاده بهترازمنابع شده وازوضعیتی که در آن برخی از گره ها با بار زیاد وبرخی بیکار و یا کم بارگذاری شده باشد اجتناب شود. دراین مقاله الگوریتم های مختلف بر اساس الگوریتم کلونی مورچگان (ACO)
برای حفظ تعادل بار گره بررسی شده و نمای کلی از آخرین الگوریتمها در محیط پردازش ابری مورد بحث و
بررسی و مقایسه قرارخواهد گرفت.
کلمات کلیدی: رایانش ابری،تعادل بار،کلونی مورچگان
.1 مقدمه
با توسعه سریع فن آوری های پردازش و ذخیره سازی و موفقیت اینترنت ،منابع کامپیوتری ارزانتر ،قوی تر و در دسترس تر از قبل شدند. این روند تکنولوژیکی تحقق جدیدی از مدل رایانش به نام رایانش ابری را فعال کرده است که در آن منابع (به عنوان
مثال، CPU و و دستگاه های ذخیره سازی) به عنوان خدماتی ارائه شده است که می تواند توسط کاربران از طریق اینترنت در مد
مبتنی بر تقاضا اجاره داده شده و منتشر شود. در یک محیط رایانش ابری، نقش سنتی ارائه دهنده خدمات به دو بخش تقسیم بندی
می شود:.1 ارائه دهندگان زیرساخت ها که سیستم عامل ابر را مدیریت کرده و منابع رابر اساس مدل قیمت گذاری مبتنی بر
استفاده اجاره می دهند و.2 ارائه دهندگان خدمات، که منابع را از یک یا بسیاری از ارائه دهندگان زیرساخت برای خدمت به
کاربران نهایی اجاره می کنند. [8] به طور کلی رایانش ابری عبارتند از تعدادی سرور توزیع شده ارائه خدمات به مشتری مبتنی بر
درخواست در یک شبکه با مقیاس پذیری و قابلیت اطمینان.محققان از رفتار اجتماعی حشرات الهام گرفتند.در عمل مورچه ها به تعدادی از تکنیک های شناخته شده بهینه سازی معروف به کلونی مورچه( 2(ACO الهام بخشیدند.ACO از رفتار جستجوگر مورچه های واقعی الهام می گیرد .[11] الگوریتم ACO الگوریتم
1
جستجوی تصادفی است. این الگوریتم کلنی رفتار مورچه در طبیعت در جستجوی غذا و ارتباط با دیگر مورچه ها از طریق
فرومون به جای گذاشته در مسیر را در بر می گیرد. بسیاری از محققان برای حل مشکل بهینه سازی ازACO استفاده می کنند .[7]تعادل باردر ابر مکانیزمی است که بار کاری را به صورت پویا در میان تمام گره توزیع می کند.با رسیدن به بالا بودن نسبت رضایت کاربر و بهره برداری از منابع مطمئن شوید که هیچ گره ای حاوی بار زیاد نیست. در این مقاله "بهینه سازی کلونی مورچه ها برای تعادل بار موثر در رایانش ابری را پیشنهاد می شود". بقیه این مقاله به شرح زیر است: بخش 2 طبقه بندی رایانش ابری
را توصیف می کند. بخش 3 تعادل بار را توصیف می کند. در بخش چهارم بهینه سازی کلونی مورچه توصیف می شود. بخش 5
تجزیه و تحلیل مقایسه ای از الگوریتم های مختلف ACO را توصیف می کند. در نهایت بخش ششم نتیجه گیری مقاله است.
.2 طبقه بندی ازرایانش ابری
1,2معماری ابر - شکل 1 معماری ابررا نشان می دهد . معماری ابر نرم افزار های کاربردی را با استفاده سرویس های مبتنی بر تقاضا قابل دسترس از طریق اینترنت طراحی می کند.
شکل:1معماری ابر
بر اساس تعریف NIST از محاسبات ابری دو نوع ابر وجود دارد .
2,2مدل استقرار-3که اشاره به مکان و مدیریت زیر ساختهای ابر می کند.این مدل چهار نوع می باشد:ابر عمومی4،ابر
خصوصی5،ابر گروهی6،ابر آمیخته7
3,2 مدل سرویس-8 اشاره به انواع خاصی ازسرویس هایی می کند که شما می توانید از طریق آن به پلت فرم ها(بستر های نرم
افزاری)رایانش ابری دسترسی داشته باشید.این مدل شامل سه نوع زیرمی باشد:
1,3,2زیر ساخت به عنوان سرویس. 9IaaS به تامین تقاضا از منابع زیرساختی معمولا از لحاظ VMS اشاره می کند. صاحب ابر کسی که IaaS راارائه می دهد به نام ارائه دهنده IaaSخوانده می شود. نمونه هایی از ارائه دهندگان IaaS شامل
2
[13] Amazon EC2،.[16] Flexiscale [14] ,GoGridسرویسهای زیرساخت ابری یا زیرساخت به عنوان سرویس
(IaaS)زیرساخت رایانه را که عموماً یک بستر مجازی است را به صورت سرویس ارائه میدهند. کاربران به جای خرید سختافزار و نرمافزار و فضای مرکز داده (دیتا سنتر) ویا تجهیزات شبکه، همه این زیر ساختها را به صورت یک سرویس کاملاً برونسپاری 10شده میخرند. صورتحساب سرویسمعمولاً بر اساس مدل رایانش همگانی (Utility Computing) ومیزان منابع مصرف شده صادر میشود و بنابر این هزینه منعکس کننده میزان فعالیت است. این شیوه در واقع تکامل یافته مدل عرضه سرورهای خصوصی مجازی است.
.2,3,2بستر به عنوان سرویس.11 PaaS اشاره به ارائه منابع لایه پلت فرم، از جمله پشتیبانی از سیستم عامل و چارچوب توسعه
نرم افزار دارد. نمونه هایی از ارائه دهندگان PaaS شامل [17] Google App Engine ،Microsoft Windows Azure [20] ،[18] Force.com می باشد.
.3,3,2نرم افزار به عنوان سرویس. سرویسهای برنامه کاربردی ابری یا نرمافزار به عنوان سرویس(12(SaaS ، نرمافزار را به صورت سرویس روی اینترنت تحویل میدهند و بدین وسیله نیاز به نصب نرمافزار روی رایانههای مشتریان را ازبین میبرند و نگهداری و پشتیبانی را ساده تر میسازد .نمونه هایی از ارائه دهندگان SaaS شامل [18] Salesforce.com ،Rack space [15] ،[19] SAP Business By Design می باشد.
به طور خاص، پنج ویژگی اساسی ازرایانش ابری عبارتند از :[5]
4,2 خود خدمتی مبتنی بر تقاضا.13مصرف کنندگان با نیاز فوری در یک زمان خاص می توانداز منابع کامپیوتری مانند زمان CPU، CPU، ذخیره سازی شبکه، استفاده از نرم افزار، و غیره به یک مد خودکار(یعنی به راحتی و خودخدمتی)سودبرده بدون آن که
نیازبه متوسل شدن به ارائه دهنده این منابع باشد.به عبارت بهتر مشتری میتواند امکانات رایانشی همچون فضای ذخیرهسازی در شبکه را به هنگام نیاز از هر سرویس دهندهای به طور خودکار بهدست آورد.
5,2 دسترسی گسترده شبکه14 امکانات روی شبکه در دسترس هستند و میتوان با سازوکارهای استاندارد به آنها دست یافت. این
سازوکارها از بسترهای ناهمگون و متفاوت (گوشیهای موبایل، لپتاپها وPDA ها) پشتیبانی میکنند .هنگامی که ما به
دسترسی به شبکه گسترده رایانش ابری اشاره می کنیم، منظور ما منابعی به میزبانی ابر است که باید در دسترس هر دستگاه محاسباتی بدون در نظر گرفتن نوع و مکان اتصال به اینترنت، قرار بگیرد. از 5 ویژگی اساسی رایانش ابری، بیشتر دسترسی به
شبکه گسترده مورد بحث قرار دارد. دلیل آن هم این است که زمانی که شما در مورد ابر خصوصی فکر می کنید، اولین مورد برای
3
استقرار ابر خصوصی، حفاظت از اطلاعات با ارزش خود به دور از دسترسی بسیاری از مردم در اینترنت است. به نظر می رسد در
دیدگاه بسیاری از افراد، broad network accessدر ابر عمومی نسبت به ابر خصوصی کاربردی تر باشد. با این حال، شما می توانید دیدگاه متفاوت تری نسبت به broad network access داشته باشید.
.6,2 جمع کردن منابع.15منابع رایانشی فراهمکننده جمعآوری شدهاند تا با به کارگیری مدل »چند مشتری« به چندین کاربر خدمترسانی کنند. این کار به وسیله منابع فیزیکی یا مجازی مختلف که به شکلی پویا و بنابر درخواست مشتری واگذار و پس
گرفته میشوند صورت میگیرد. در اینجا حالتی از عدم وابستگی به مکان وجود دارد که در آن مشتری معمولا کنترل یا دانشی
درباره محل دقیق منابع فراهم شده ندارد ولی ممکن است در سطوح بالاتر انتزاعی بتواند محل را تعیین کند، مثل: کشور، استان یا
مرکز داده. برای نمونه منابع شامل فضای ذخیرهسازی، توان پردازشی، حافظه، پهنای باند شبکه و ماشینهای مجازی میشود. [5] 7,2 انعطافپذیری بالقوه.16میتوان امکانات را به سرعت و با انعطاف، در بعضی موارد به صورت خودکار، به دست آورد تا به سرعت گسترش داده شده(از دید مقیاس) یا در جا آزاد شوند و خیلی سریع به مقیاس کوچکتری دست یابند. از دید مشتری امکاناتی که برای به دست آمدن در دسترس هستند اغلب نامحدود به نظر میآیند و میتوانند به هر مقدار و در هر زمان خریداری شوند.[5]
8,2 پرداخت در قبال استفاده.17هر چند منابع کامپیوتری توسط مصرف کنندگان متعدد (یعنی با دسترسی چندگانه)با هم مخلوط و به اشتراک گذاشته شده اند ،اما زیرساخت های ابر قادراست ازمکانیسم های مناسب استفاده کند.[ 5]سیستمهای ابری منابع را خودکار کنترل و بهینه میکنند. این کار با بهکارگیری توانایی اندازهگیری در سطحی که مناسب نوع سرویس یا منبع مورد استفاده
است (مانند: فضای ذخیرهسازی، توان پردازشی، پهنای باند و شمار کاربران فعال) انجام میشود. میزان استفاده از منابع میتواند به شکلی شفاف هم برای مشتری و هم برای فراهمکننده تحت نظر گرفته شود، کنترل شده و گزارش داده شود.
.3تعادل بار18
مسئله تعادل بار در رایانش ابری یک چالش جدید است. همیشه یک راه حل توزیع شده مورد نیاز است. از آنجا که همیشه در
عمل امکان پذیر ومقرون به صرف نیست ک یک تا تعداد بیشتری سرویس دهنده برای پاسخ به در خواستهای مورد نیاز بیکار نگه
داریم . کارها نمی توانند به سرور مناسب اختصاص داده شده، و تعادل بار موثربه صورت جداگانه برای مشتریان در ساختار ابر بسیار پیچیده است و اجزاء در سراسر یک منطقه گسترده حضور دارند.تعادل بار، روند تخصیص دوباره کل بار به گره های
منحصر به فرد یک سیستم جمعی به منظور بهره برداری موثر از منابع، بهبود بخشیدن به زمان پاسخ یک کار و به طور همزمان
حذف وضعیتی است که در آن تعدادی از گره ها به شدت بار شده اند در حالی که تعدادی دیگر بار کمی دارند، می باشد.
4
الگوریتم های تعادل بار به دو دسته ایستا و پویا تقسیم بندی می شوند. الگوریتم های استاتیک بیشتر برای محیط های همگن و
پایدار مناسب می باشد و می تواند نتایج بسیار خوبی در این محیط ها تولید نماید. با این حال، آنها معمولا انعطاف پذیرنبوده و نمی توانند خود را با تغییرات پویای ویژگی ها در زمان اجرا تطبیق دهند . الگوریتم پویا انعطاف پذیر تر بوده و انواع مختلف
ویژگی ها در سیستم را در هر دو حالت یعنی در قبل و در طول زمان اجرا در نظر می گیرند.[1] تعادل بار فرایندی است که عملکرد سیستم را از طریق توزیع مجدد بار در میان پردازنده ها بهبود می دهد.[2]
.1,3معیارهای تعادل بار در ابر
تکنیکهای تعادل بار موجود در ابر، پارامترهای مختلف را در نظر می گیرد.[6]
· سربار مرتبط-هنگامی که یک الگوریتم تعادل بار اجرا می شود مقدار سربار درگیر را تعیین می کند. این شامل سربار
مقرر برای بهبود وظایف، ارتباطات میان پردازنده ها و پردازشها می شود. این مقدار باید به حداقل برسد تا تکنیک تعادل
بار به طور کارآمد عمل نماید.
شکل .2انواع تعادل بار
· توان عملیاتی: برای محاسبه وظایفی که اجرای آنها به پایان رسیده، استفاده می شود. این مقدار باید برای بهبود کارایی
سیستم بالا باشد.
· کارایی: برای کنترل بهره وری سیستم استفاده می شود. این معیار باید هزینه های معقول را بهبود بخشد. به عنوان مثال،
زمان پاسخ وظایف را کاهش دهد در حالی که تأخیرها را قابل قبول نگه دارد.
· بهره برداری از منابع: برای کنترل بهره برداری از منابع استفاده می شود. این مقدار باید برای تعادل بار کارآمد بهینه شود.
· مقیاس پذیری: توانایی یک الگوریتم برای اجرای تعادل بار برای یک سیستم با تعداد متناهی گره است. این معیار باید بهبود داده شود.
5
· زمان پاسخ: مقدار زمان گرفته شده برای پاسخ دادن، توسط یک الگوریتم تعادل بار خاص در یک سیستم توزیع شده
است. این پارامتر باید به حداقل رسانده شود.
· تحمل خطا: توانایی یک الگوریتم برای اجرای یکنواخت تعادل بار در موارد خرابی اتصال است. تعادل بار باید یک
تکنیک تحمل خطای خوب باشد.
· زمان مهاجرت: زمانی برای مهاجرت کارها یا منابع از یک گره به دیگری است. این زمان برای افزایش کارایی سیستم
باید به حداقل رسانده شود.[6]
.4الگوریتم کلونی مورچگان
Dorigo M. الگوریتم مورچه ها را بر اساس رفتار مورچه ها در سال 1996 پیشنهاد داده است. [7] [11]، این الگوریتم یک
الگوریتم فراابتکاری جدید برای حل مسائل بهینه سازی ترکیبی است.این الگوریتم در ابتدا به عنوان یک راه حل چند عامله (Multi Agent)برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد. الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه ها
حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء
از آن. یکی از مهمترین و جالبترین رفتار مورچه ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. در طبیعت ، کلونی مورچه ها بدون اینکه اطلاع سراسری از مسیرها داشته باشند ، معمولا کوتا هترین مسیر لانـه تـا محـل غـذا را پیـدا مـی کند. زمانیکه مورچه راه می رود، از خود فرمون ترشح می کند وردپایی به جای می گذارد
. مورچهها برای انتخاب مسیر ، مسیری را بـر میگزینندکه دارای فرومون بیشتری است.
شکل.3چگونگی یافتن کوتاهترین مسیر توسط مورچه ها
در شکل A.1، مورچهها به نقطهای میرسند که بایستی تصمیم بگیرند که آیا به راست بروند یا به چپ. از آنجایی که هیچ سرنخی
وجود ندارد که کدام بهتر است، مورچهها یکی را بصورت تصادفی بر می گزینند. در شکل B.1 و C.1 با فرض اینکه مورچهها
6
دارای سرعت یکسانی هستند، مسیری که دارای طول کمتری می باشد پس از مدتی توسط مورچههای بیشتری طی می شود و
بنابراین میزان فرومون بیشتری روی آن مسیر بجای گذاشته میشود.در D.1، مورچه در نقطه تصمیم گیری مسیری را که دارای فرومون بیشتری است را با احتمال بالاتر انتخاب می کند. بدین گونه کلونی مورچهها پس از مدتی کوتاهترین مسیر را پیدا می کند.
علاوه بر این فرومون بجای گذاشته شده با نرخ معینی بخار میشود و به همین دلیل مسیری که کمتر مورد تردد مورچهها واقع می شود پس از مدتی فرومونش را از دست می دهد. لذا اگر در محیط تغییری حاصل شود(مثلا مسیری مسدود شود)، مورچهها می
توانند مسیر بهینه دیگری را بیابند.ACO [11]از کلنی مورچه هایی الهام گرفته شده که با هم به رفتار جستجوگری کار می کنند.
در واقع مورچه ها الهام بخش بسیاری از محققان برای کارهایشان می باشد و روش مورچه ها توسط بسیاری محققان برای حل
مشکلات در زمینه های مختلف به کار رفته است.این رو ش معروف به روش ACO می باشد.[9]
.5تجزیه و تحلیل مقایسه ای از انواع :ACO
در این بخش در مورد مقایسه الگوریتم های مختلف کلونی مورچگان بحث می کنیم. روش های مختلفی برای تعادل بار وجود
داردکه با توجه به برخی شرایط مناسب بوده اما همه آنها نتایج خود رادارند، که در بین آنها بعضی از الگوریتم ها مناسب برای
ماهیت استاتیک و برخی مناسب برای ماهیت پویا می باشند. این الگوریتم ها به شیوه ای غیر متمرکز کار می کنند.جدول 1 مزایا ومعایب الگوریتم ها و شرح مختصری از آنها را نشان می دهد.به عنوان نمونه حالات اولین الگوریتم برای سه سطح رایانش ابری[10]،به طورموثر کار می کند و باعث استفاده بهتر از منابع شده اما،سربار بیشتری را در طول زمان اجرا می دهد.در یک زمانبندی کار در ابر بر اساس تعادل بار 19LBACO [7] ACO (بهینه سازی تعادل بار مورچگان) پیشنهاد می شودو برای پیدا کردن تخصیص منابع به صورت مطلوب برای هر وظیفه به صورت پویا مورد استفاده قرار می گیرد.در این الگوریتم مقایسه با الگوریتم های عمومی ACO و الگوریتم FCFS انجام می شود.در نتیجه گره ها به صورت پویا متعادل می شوند. علاوه بر
این،وظایف دو به دومستقل است یعنی هیچ محدودیت اولویت بین کار وجود نداشته ومتمرکز است و این برای سیستم ابر واقع
گرایانه نیست. اشکال اصلی این روش ناهمگنی های سیستم است.مشکل ناهمگنی سیستم در تکنیکی که از مکانیزم تعادل بار بر اسا س کلونی مورچه و تئوری شبکه های پیچیده استفاده می کنند حذف شده است.[12]این روش یک مقیاس پذیری خوب از گره ها را فراهم کرده و تحمل خطای سیستم را بهتر می کند.عملا سربار را در طول زمان اجرا افزایش داده و زمان پاسخ نامناسب
می باشد.یک مورچه به یک حالت بن بست به علت عدم هماهنگی با مورچه ها برخورد می کند.در رایانش ابری طرح ابتکاری
استفاده ازتغییر یا اصلاح در چارچوب الگوریتم ACO است[4] و این محدوده را به حداقل می رساند (توان عملیاتی از سیستم
محاسبات ناهمگن).این تغییر الگوریتم درگیر در فرمول بروزرسانی فرمون عمومی است.این تغییر استفاده از منابع را بهتر کرده اما
تحمل سیستم در برابر خطا را بهبود نمی دهد.هدف اولیه در هر تعادل بار بهترشدن استفاده از منابع است. تعادل بار در گره ها ازبهینه سازی ACO استفاده می کند.[9]این بهترین حالت برای تعادل بار موثر می باشد. زیرا در کار قبلی مورچه می تواند تنها در
یک جهت حرکت کند .[12] اما در این الگوریتم یک مورچه می تواند حرکت در هر دو جهت رو به جلو و درجهت عقب داشته باشد. از جمله یک مورچه مواد غذایی رابا حرکت رو به جلو و بازگشت به لانه را با حرکت رو به عقب می یابد.این برای تعادل
7
سرعت گره مفید است. این الگوریتم سریع کار می کند به دلیل این که یک مورچه می تواند به صورت همزمان در هر دو جهت
برای تعادل گره حرکت کند. این الگوریتم باعث استفاده بهتر از منابع می شود. اما این الگوریتم [9] بر روی پارامتر محدودی مانند
سرعت، سربار شبکه و تحمل خطا کار می کند.این الگوریتم از قدرت بیشتری برخوردار است و مسائل مرتبط با انرژی را در نظر نمی گیرد.هزینه های عملیاتی متعدد در نظر گرفته نمی شود زیرا ممکن است باعث عملکرد ضعیف نتیجه شود.
جدول.1مقایسه الگوریتم های تعادل بار
معیارهای در نظر
تکنیک توصیف مزایا معایب گرفته شده توسط
تعادل بار
به سوی یک تعادل .1گره ها در ساختار سه سطحی .1استفاده موثر از منابع .1 وظیفه هرسطح گره وابسته کارایی،بهره برداری
بار در سه سطح توزیع شده اند که در آن کار در .2 هر گره در هر حالت به گره سطح بالاتر خواهد بود از منابع
شبکه رایانش ابری میان گره ها توزیع شده است . مشغول به کاراست (به عنوان مثال گره
[10] .2 این روش OLB (توازن بار خدمات(سرویس) به گره مدیر
فرصت طلب) برای حفظ هر یک خدمات وابسته است و گره
از گره های شلوغ و LBMM مدیر خدمات بستگی به گره
(تعادل بار حداقل حداقل) برای مدیر درخواست دارد.)
رسیدن به حداقل زمان اجرای هر .2هر زمان مقدار آرایه تغییر می
وظیفه را ترکیب می کند. کند.
زمانبندی ابر وظیفه (LBACO) .1 الگوریتم بهینه .1گره ها به صورت پویا .1 کار دو به دو مستقل است به کارایی،بهره برداری
مبتنی بر تعادل بار تعادل بار کلونی مورچه برای پیدا متعادل می باشند. طوری که محدودیت اولویت ازمنابع،توان
[7] ACO کردن تخصیص منابع مطلوب LBMM.2 کل سیستم را به بین کارها وجود ندارد. عملیاتی،
برای هر کار در سیستم ابر هر حالتی که وظایف هستند .2 وظیفه متمرکز است به طوری مقیاس پذیری
پویاپیشنهاد می شود. متعادل می کندLBMM همه که برای سیستم ابر واقع گرایانه
.2این الگوریتم برای به حداقل نوع وضعیتی را اداره می کند نیست.
