۲-۳-۲-۱زیرساخت به عنوان سرویس(IAAS)

سرویس‌هایی که IaaS ارائه می دهد، منابع محاسباتی مانند پردازنده‌ها و فضاهای ذخیره سازی هستند. مثالهایی از ارائه این سرویس‌ها که در شکل ۴-۷ آمده اند را می توان به صورت زیر لیست کرد[Stanoevska10]:
سرویس‌های وب آمازون^[۸۲]، که شامل دو بخش زیر می باشد:
^[۸۳]EC2: برای ارائه خدمات پردازشی.

^[۸۴]S3: برای ارائه خدمات ذخیره سازی.
سرویس ابر شرکت سان (Joyent) که شامل دو زیر بخش می باشد:
سرویس ذخیره سازی ابر شرکت سان برای بارگذاری وب سایت‌ها.
سریس پردازش ابر شرکت سان برای اجرای برنامه‌های تحت وب.

۲-۳-۲-۲ بستر به عنوان سرویس (PAAS)

بستر، لایه‌ای است که بین برنامه‌های نرم افزاری و زیرساخت قرار می گیرد و خدماتی که ارئه می کند، مربوط به توسعه دهندگان نرم افزار می باشد. توسعه دهنگان می توانند بدون نگرانی در خصوص زیرساخت، برنامه‌های کاربردی خود را بر اساس مختصاتی که یک بستر خاص ارائه می‌‌کند، بنویسند. مثالهایی از PaaSعبارتند از موتور برنامه‌های کاربردی گوگل^[۸۵]و بستری که توسط سایت Force.com ارائه می شود.

۲-۳-۲-۳ نرم افزار به عنوان سرویس(SAAS)

این لایه، با کاربران نهائی در ارتباط بوده و در برگیرنده برنامه‌های کاربردی است که توسط توسعه دهندگان دیگر (از راه دور) مدیریت شده و به صورت پرداخت به ازای استفاده در اختیار کاربران قرارمی گیرند.
۲-۴ الگوریتم رقابت استعماری^[۸۶] (ICA)
۲-۴-۱ نگاهی به تاریخچه استعمار
استعمار یا امپریالیسم، به معنای سیاست توسعه و گسترش قدرت یک حکومت در خارج از مرزهای کشور می باشد. یک کشور می تواند به طرق مختلفی بر کشورهای دیگر تسلط داشته باشد. این تسلط می تواند از طریق حکمرانی مستقیم بر آن کشور باشد یا از طریق کنترل بر مواد خام و مورد نیاز کشورهای مستعمره صورت گیرد. در شکل ساده تر، استعمار به معنای کنترل سیاسی بر کشورهای دیگر، تنها به منظور استفاده از منابع آنها بوده و گاهی اوقات این استعمار جهت جلوگیری از گسترش سایر استعمارگرها بر آن کشور رخ می داد. صرف نظر از دلیل استعمار، کشورهای استعمارگر به شدت جهت افزایش تعداد مستعمره های خود و گسترش استعمار خود بر جهان، با یکدیگر رقابت داشتند. این رقابت باعث رشد و توسعه برخی از استعمارگرها و نابودی و ضعیف شدن برخی دیگر از استعمارگرهای دیگر شد.
استعمار در طول قرنهای ۱۹ و ۲۰ به دلیل مدرنیته تغییر ماهیت داد. داروینیست های اجتماعی بر این عقیده بودند که فرهنگ غرب برتر از فرهنگ شرق می باشد. این تغییر ماهیت باعث شد تا کشورهای استعمارگر شروع به توسعه مستعمره های خود کنند (فرهنگ خود را گسترش دهند). به عنوان مثال، در میانه های قرن ۱۸، دو کشور استعمارگر فرانسه و بریتانیا جهت سلطه بر هند با یکدیگر رقابت شدیدی داشتند. در نهایت بریتانیا در این رقابت پیروز شد و توانست کنترل هند را به دست بگیرد. بعد از این تصرف، بریتانیا شروع به ساخت مدارس انگلیسی زبان، جاده ها، راه آهن و خطوط تلفن کرد. علاوه بر این بریتانیا سعی در تغییر باورهای اجتماعی که از منظر فرهنگ غربی نادرست شمرده می شد، کرد. از جمله این اصلاحات، تغییر فرهنگ خود سوزی زنان بیوه هندی پس از مرگ شوهرانشان بود. علاوه بر این، آنها حداقل سن ازدواج دختران را نیز افزایش دادند. این سیاست، سیاست جذب نامیده می شود. بریتانیا تغییرات مشابهی را در کشور مالزی انجام داد و قانون برده داری را لغو کرد. مثال دیگری از این دست اصلاحات در کشور هندوچین توسط کشور فرانسه صورت گرفت. این کشور از نظر منابع طبیعی برای فرانسه اهمیت بسیاری داشت و علاوه بر این فرانسه نمی خواست این کشور در اختیار بریتانیا قرار گیرد. اگرچه استعمارگرها نتوانستند با این سیاست ها سلطه خود بر جهان را افزایش دهند، ولی این سیاست ها رشد سریع اجتماعی و سیاسی را برای کشورهای مستعمره به همراه داشت.
۲-۴-۲ بهینه سازی بر اساس رقابت استعماری
شکل ۲-۸ فلوچارت الگوریتم رقابت استعماری را نشان می‌دهد [Atashpaz07]. همانند دیگر الگوریتم‌های تکاملی، این الگوریتم، نیز با تعدادی جمعیت اولیه تصادفی که هر کدام از آنها یک “کشور” نامیده می‌شوند؛ شروع می‌شود. تعدادی از بهترین عناصر جمعیت (معادل نخبه‌ها در الگوریتم ژنتیک) به عنوان امپریالیست^[۸۷] انتخاب می‌شوند. باقیمانده جمعیت نیز به عنوان مستعمره^[۸۸]، در نظر گرفته می‌شوند. استعمارگران بسته به قدرتشان، این مستعمرات را با یک روند خاص که در ادامه می‌آید؛ به سمت خود می‌کشند. قدرت کل هر امپراطوری، به هر دو بخش تشکیل دهنده آن یعنی کشور امپریالیست (به عنوان هسته مرکزی) و مستعمرات آن، بستگی دارد. در حالت ریاضی، این وابستگی با تعریف قدرت امپراطوری به صورت مجموع قدرت کشور امپریالیست، به اضافه در صدی از میانگین قدرت مستعمرات آن، مدل شده است.
با شکل‌گیری امپراطوری‌های اولیه، رقابت امپریالیستی میان آن‌ها شروع می‌شود. هر امپراطوری‌ای که نتواند در رقابت استعماری، موفق عمل کرده و بر قدرت خود بیفزاید (و یا حداقل از کاهش نفوذش جلوگیری کند)، از صحنه رقابت استعماری، حذف خواهد شد. بنابراین بقای یک امپراطوری، وابسته به قدرت آن در جذب مستعمرات امپراطوری‌های رقیب، و به سیطره در آوردن آنها خواهد بود. در نتیجه، در جریان رقابت‌های امپریالیستی، به تدریج بر قدرت امپراطوری‌های بزرگتر افزوده شده و امپراطوری‌های ضعیف‌تر، حذف خواهند شد. امپراطوری‌ها برای افزایش قدرت خود، مجبور خواهند شد تا مستعمرات خود را نیز پیشرفت دهند.با گذشت زمان، مستعمرات، از لحاظ قدرت به امپراطوری‌ها نزدیک‌تر خواهند شد و شاهد یک نوع همگرایی خواهیم بود. حد نهایی رقابت استعماری، زمانی است که یک امپراطوری واحد در دنیا داشته باشیم، با مستمراتی که از لحاظ موقعیت، به خود کشور امپریالیست، خیلی نزدیک هستند.
شکل ۲-۸: فلوچارت الگوریتم رقابت استعماری[Atashpaz07]
فصل سوم:
پیشینه تحقیق
۳-۱ مقدمه
برای رسیدن به یک استراتژی مناسب تخصیص منابع و زمانبندی در یک ابر، مفاهیم از رایانش توری به ارث برده شده است. اهداف این استراتژی ها، تخصیص منابع به گونه ای است که بتواند تعادل بار^[۸۹]در منابع را حفظ کرده و معیارهای کیفیت سرویس^[۹۰] (QoS) را تامین کند. تعادل بار بدین معنی است که کارها به صورت عادلانه به منابع موجود تخصیص داده شوند و از تخصیص بیش از حد کارها به یک منبع، در حالی که سایر منابع آزاد هستند، جلوگیری شود.
کیفیت سرویس به معنی میزان رضایت مشتری بوده و این معیار مهمترین عامل در موفقیت تجاری سیستم های “استفاده به ازای پرداخت"، مانند رایانش ابری، می باشد. پارامترهای کیفیت سرویس در رایانش ابری را می توان به صورت زیر بیان کرد:
پهنای باند شبکه: زمانی پهنای باند شبکه مشتری بالا است، مانند کاربردهای مربوط به مولتی مدیا، ابر باید نیازهای مربوط به این پهنای باند را پاسخ گو باشد.
زمان اتمام سرویس^[۹۱]: برای کاربرانی که دارای درخواست های آنی^[۹۲] هستند، زمانبندی و تخصیص منابع در ابر باید به گونه ای صورت گیرد که سرویس مورد نظر این کاربران در حداقل زمان ممکن اجرا گردد.
قابلیت اعتماد سیستم: برای اجرای تعدادی درخواست پیچیده کاربران، نیاز به مرکز رایانش ابری داریم تا بتواند کارایی قابل اعتمادی را چه از نظر محاسباتی و چه از نظر سرویس های ذخیره سازی فراهم سازد.
هزینه: یکی از معیارهای مورد توجه کاربران، میزان هزینه ای است که جهت دریافت سرویس ابر پرداخت می کنند. اگر زمانبندی و تخصیص منابع در این ابر به شکل کارآمدی انجام نگیرد، هزینه های ابر (شامل هزینه های مرتبط با انرژی و هزینه های مرتبط با نگهداری منابع)، افزایش یافته و این افزایش هزینه باعث افزایش هزینه استفاده کاربر شده و در نتیجه میزان رضایت کاربر کاهش پیدا خواهد کرد.
مطالعات بسیاری در حوزه تخصیص منابع و زمانبندی منابع چه در بستر رایانش ابر و چه در بستر رایانش توری صورت گرفته است. این مطالعات و روش ها را می توان به صورت کلی زیر دسته بندی کرد:
الگوریتم های زمانبندی و تخصیص منابع سنتی: این الگوریتم ها شامل الگوریتم های دور رابین، دور رابین وزن دار، زمانبندی با حداقل ارتباط، زمانبندی با حداقل ارتباط بهبود یافته، زمانبندی هش مقصد، زمانبندی هش مبدا و غیره.
الگوریتم های ابتکاری هوشمند^[۹۳]: همان طور که گفته شد، مسئله زمانبندی و تخصیص منابع در یک ابر و یک تور، یک مسئله NP-کامل می باشد و در نتیجه فضای جستجوی این مسئله به اندازه ای بزرگ است که اگر یک الگوریتم بخواهد این فضا را به صورت ترتیبی مورد بررسی قرار داده و بهترین جواب را بیابد، نیاز به زمان نمایی خواهد داشت. الگوریتم های ابتکاریهوشمند ، با تکیه بر مکانیسم های سیستم های موفق، سعی در شبیه سازی این مکانیسم ها، جهت حل مسائل مشکل، می نمایند. از جمله الگوریتم های ابتکاری که در حوزه زمانبندی و تخصیص منابع مورد استفاده قرار گرفته اند، می توان به الگوریتم کلونی مورچگان [Zhu12,Chen09] و الگوریتم ژنتیک [Javier07] اشاره کرد.
با توجه به این که الگوریتم رقابت استعماری در گروه الگوریتم های ابتکاری هوشمند دسته بندی می شود، بیشتر تمرکز این فصل بر پیشینه زمانبندی و تخصیص منابع رایانش ابری در این حوزه تخصیص داده شده است. علاوه بر این جهت آشنایی با مکانیسم الگوریتم های سنتی، الگوریتم دور رابین مورد بررسی قرار گرفته است. بنابراین ادامه این فصل به صورت زیر سازماندهی شده است:
در بخش اول این فصل، الگوریتم دور رابین، به عنوان یک الگوریتم سنتی زمانبندی و تخصیص منابع معرفی شده است. این الگوریتم جزء الگوریتم های مهم در این حوزه بوده و در بخش ارزیابی الگوریتم پیشنهادی از این الگوریتم نیز استفاده خواهد شد. در بخش دوم، کلونی مورچگان که در [Zhu12] معرفی شده است پرداخته خواهد شد و بخش سوم این فصل به بررسی الگوریتم ژنتیک ارائه شده [Javier07] تخصیص داده شده است.
۳-۲ سیستم مدیریت منابع اکالیپتوس^[۹۴]
اکالیپتوس [EUCALYPTUS-WEB], [Nurmi09] یک سیستم نرم افزاری متن باز و رایگان کامپیوتری، جهت ایجاد محیط های رایانش ابری مبتنی بر سرویس وب آمازون^[۹۵] (AWS)، می باشد. این سیستم، از الگوریتم دور رابین^[۹۶]، که یک روش حریصانه محصوب می شود، جهت تخصیص درخواست ها به گره های محاسباتی (منابع) استفاده می کند. در الگوریتم دور رابین، یک چرخه از گره های محاسباتی ایجاد شده و هر درخواست به اولین گرهی که دارای منابع لازم جهت اجرای آن درخواست باشد، تخصیص داده می شود.
مثال ۱: یک ابر با تعداد ۳ گره محاسباتی را در نظر بگیرید. مشخصات کلی این گره ها از نظر محاسباتی، اندازه حافظه اصلی و اندازه حافظه سخت به صورت جدول ۱ می باشد. فرض می کنیم که گره ها دارای سیستم عامل اشتراک زمانی^[۹۷] می باشند، بدین معنی که امکان اجرای چندین درخواست بر روی یک گره به صورت همزمان وجود دارد.
جدول۳-۱: مثالیازمشخصاتگرههایمحاسباتییکابربا ۳ گره