مقاله مطالعه ای بر روشهای نظریه بازی برای بهبود تخصیص منابع در رایانش ابری

بخشی از مقاله

مطالعه ای بر روشهای نظریه بازی برای بهبود تخصیص منابع در رایانش ابری

چکیده

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

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

واژههای کلیدی: رایانش ابری، تخصیص منبع، نظریه بازی ها، تعادل نش.

-1 مقدمه:

محاسبه یا رایانش ابری، یک نوع محاسباتی جدیدی را برای پروژه ها، کلاینت ها و مشاغل آنلاین فراهم کرده به گونه ای که در آن، منابع بر اساس تقاضا تخصیص داده میشود.[1] مفهوم تخصیص منبع در رایانش ابری، عبارت است از تخصیص CPU ها و سایر منابع در میان مصرف کنندگان مختلف. کاربران و منابع جهانی، استراتژی های عرضه و تقاضای مختص به خود را دارند؛ بنابراین به نظر می رسد که مکانیسم بازار می تواند برای مدیریت منابع در این محیط توزیع شده پیچیده، مناسب باشدPopcorn .[2] از مفهوم پول مجازی [3] برای کاربرانی که وظایفی را در یک سرور متمرکز ثبت می نمایند؛ استفاده می کند. Walras، یک پیاده سازی توزیع شده و همگرا [4] از نظریه تعادل را ارائه می نماید که در آن، مشتریان سرویس بر مینای توابع قیمتی خود، پیشنهاداتی را مطرح می سازند تا اینکه فرآیند عرضه و تقاضا با یکدیگر مطابق شوند. به علاوه، Cloudbus یک ساختار سرویس دلالی و یک میان افزار مرکزی[5] را برای گسترش اپلیکیشن ها در دیتا سنتر ارائه می نماید و به این وسیله قصد دارد تا مفهوم بازار جهانی رایانش ابری را محقق سازد.

.ComConf.ir

کنفرانسالمللیبین یافته های نوین پژوهشی در

مهندسی برق و علوم کامپیوتر

The International Conference in New Research of Electrical Engineering and Computer Science

اهداف کلیدی تأمین کنندگان سرویس ابری و مصرف کنندگان، تخصیص منابع ابری قدرتمند و رسیدن به بالاترین سطح سود مالی میباشد. تخصیص منبع ، یکی از مباحث ضروری در محاسبه ی ابری به شمار میرود، چرا که منابع کمی باید توزیع گردد. از دید یک مصرف کننده، تخصیص منبع، مرتبط با این است که سرویس ها و تجهیزات چطور در بین کاربران توزیع میشود. تخصیص منبع به صورت درست، در نهایت منجر به یک اقتصاد کوشا خواهد شد. یک مشتری با گسترش مهارت به عنوان یک سرویس، نیاز کمتری را به منابع مورد نیاز خود برای یک وظیفه ی حساس ایجاد میکند. اینکار از پرداخت هزینه های بی مورد برای منابع بلااستفاده اجتناب میکند. تخصیص منبع، میتواند چیزی بیشتر از سرمایه گذاری پولی باشد، بدین صورت که به کلاینت ها اجازه داده تا از بروز ترین نرم افزار ها و توزیع محیط برای ترفیع پروسه ی شغلی خود استفاده کنند.[6]

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

در تخصیص منابع ، فاکتورهای مختلفی مثل کیفیت سرویس، قیمت، عدالت، میزان سود، تعادل بار و... تاثیرگذار هسـتند و از آنجایی که هم مصرف کننده وهم سرویس دهنده ابر، به دنبال بدست آوردن بیشترین سود میباشـند، فراینـد تخصـیص منابع، یک فرایند بسیار پیچیده می باشد.[9-7]

از طرفی دیگر، روش نظریه بازی ها که به طور کامل توضیح داده خواهد شد، به خوبی می تواند با مفاد رایانش ابری تطبیق یابد به طوری که می توان آنرا به عنوان مجموعـه ای از کنشـگرهایی کـه دارای اهـداف متضـاد مـی باشـند، مـدنظر قـرار داد.[10]

ما دراین مقاله به دنبال بررسی راهکارهایی هستیم که برای حل مشکلات مـدیریت و تخصـیص منبـع بـا اسـتفاده از روش نظریه بازیها وجود دارند.

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

www.ComConf.ir

کنفرانسالمللیبین یافته های نوین پژوهشی در

مهندسی برق و علوم کامپیوتر

The International Conference in New Research of Electrical Engineering and Computer Science

-2 نظریه بازیها1

نظریه بازی تلاش میکند تا رفتار ریاضی حاکم بر یک موقعیت استراتژیک (تضاد منافع) را مدلسازی کند. این موقعیت زمانی پدید میآید که موفقیت یک فرد وابسته به استراتژیهایی است که دیگران انتخاب میکنند و تصمیمگیری وی بر تصمیمات بقیه نیز تاثیر میگذارد. این فرایند تصمیمگیری بوسیلهی یک بازی مدل میشود که فرض میکند تصمیمگیرندهها به صورت عقلانی تصمیماتی را اتخاذ میکنند که بیشترین سود را داشته باشند. در واقع نظریهبازیها علمی است که رفتار تعدادی تصمیمگیرندهی مستقل با تمایلات متناقض را در کنار یکدیگر بررسی میکند و هدف نهایی این دانش، یافتن استراتژی بهینه برای بازیکنان میباشد.[11]

یک بازی شامل مجموعهای از بازیکنان، مجموعهای از حرکتها یا راهبردها2 و نتیجه مشخصی برای هر ترکیب از استراتژیها میباشد. پیروزی در هر بازی تنها تابع یاری شانس نیست، بلکه اصول و قوانین ویژه خود را دارد و هر بازیکن در طی بازی سعی میکند با به کارگیری آن اصول، خود را به برد نزدیک کند. رقابت دو کشور برای دستیابی به انرژی هستهای، سازوکار حاکم بر روابط بین دو کشور در حل یک مناقشه بینالمللی، رقابت دو شرکت تجاری در بازار بورس کالا نمونههایی از بازیها هستند.[12]

-1-2 اجزای تشکیل دهنده یک بازی

برای اینکه بتوانیم فرایندی را به کمک یک بازی مدل کنیم، ابتدا لازم است تک تک عناصر بازی را مشـخص نمـاییم. یـک بازی نرمال که به صورت G(N,A,U) نشان داده میشود، از سه المان اصلی زیر تشکیل میگردد.[12]

 امجموعهی بازیکنان

بازیکنها در اصل همان تصمیم گیرندگان بازی میباشند که رقیب یکدیگر بوده و در بازی به صورت Q 1'2'….'L'…'1 نشان داده میشود.

 امجموعه استراتژیها

این مجموعه که برای بازیکن iام با Ai نشان داده میشـود، فضـای حرکـت و کلیـه عملکردهـای ممکنـی را مشـخص میکند که این کاربر خاص میتواند بسته به شرایط موجود از بین آنها گزینهای را انتخاب نماید.

در واقع توصیف کاملی است از تصمیماتی که بازیکنان تحت هر رخداد میگیرند. فضـای حرکـت کـل بـازی از ضـرب کارتزین A=A1*A2*…..*$N بدست میآید.