بخشی از مقاله
چکیده
امروزه رایانش ابری عبارت معروف و مهمی در جامعه فناوری اطلاعات است. در واقع رایانش ابری مدلی برای دسترسی آسان براساس درخواست کاربر از طریق شبکه به مجموعهای از منابع رایانشی قابل تغییر است که این دسترسی باید بتواند با کمترین نیاز به مدیریت منابع و دخالت مستقیم فراهم کننده سرویس، به سرعت ارتباط را فراهم کند. چالشهای موجود در رایانش ابری آسیبپذیری در برابر رکورد اقتصادی، هزینههای پهنای باند، شفافیت دسترسی، قابلیت اطمینان، امنیت، توازن بار و... هستند. در واقع توازن بار روشی برای توزیع حجم کار در میان گرههای متنوع در محیط به طوریکه هیچ گرهی در سیستم برای یک لحظه از زمان اضافه بار نداشته باشد و یا بیکار نماند، است. الگوریتمها و روشهای مختلفی برای حفظ توازن بار در محیطهای رایانش ابری پیشنهاد شده است که تمرکز اصلی آنها برای کاهش زمان دریافت پاسخ و توزیع کارامد بار بین هر گره در سیستم میباشد. دراین پایان نامه یک روش توازن بار غیرانحصاری مبتنی بر تعیین حد آستانه با در نظر گرفتن کاهش زمان دریافت پاسخ و توزیع کارامد بار بین هر گره در سیستم معرفی شده است. نتایج شبیهسازی نشان میدهد که این روش نتایج بهتری نسبت به سایر روشهای هیوریستیک به دست آورده است.
واژگان کلیدی : رایانش ابری، توزیع بار، غیرانحصاری، حدآستانه، کاهش زمان دریافت پاسخ
-1 مقدمه
تعریف رایانش ابری ارائه شده توسط انجمن ملی استاندارد و فناوری اینگونه است : [1] رایانش ابری مدلی برای دسترسی فوری شبکه به منابع محاسباتی قابل تغییر است - شبکه ها، سرورها، ذخیره و... - که بتوان با سرعت و با کمترین نیاز به مدیریت منابع این دسترسی را فراهم نمود. [2] از مزایای رایانش ابری میتوان به سرعت، هزینه، نابستگی به دستگاه و مکان، چند مستاجری، قابلیت اطمینان، سنجشپذیری و امنیت اشاره کرد. برای ایجاد بهبود عملکرد کلی سیستم، حفظ پایداری و قابلیت دسترسی نیازمند مکانیسمی بهنام توازن بار هستیم. توازن بار در واقع یکی از انواع چالشهای ابری است. با توازن بار[3] ، میتوان بار را با انتقال پویای حجم کاری محلی از یک ماشین به ماشینی در گره راه دور و ماشینی که کمتر مورد استفاده قرار میگیرد، موازنه کرد. این عمل رضایت کاربر را حداکثر، زمان پاسخ را حداقل، بهره برداری از منابع را افزایش، تعداد رد کارها را کاهش و کارایی سیستم را بالا میبرد.
الگوریتمهای توازن بار را میتوان به دو دسته ایستا و پویا تقسیمبندی کرد. [4] الگوریتم توازن بار پویا به دلیل انعطاف پذیر بودن، عملکرد بهتری دارد. در این پایان نامه نیز، روش ما به صورت الگوریتم پویا ارایه میشود. مشکلات توازن بار، سربار زیاد در بعضی منابع و بیکاری برخی منابع دیگر است. برای حل این چالشها، روشهایی قبلا ارایه شده است. همه این روشها تا حدودی توازن بار را برآورده میکنند، اما زمانی که یک منبع کاری انجام میدهد و کار جدید با ویژگی منبع مشغول وارد میشود، در نظر گرفته نشده است. بنابراین، ایراد روشهای قبلی این است که این روشها به صورت انحصاری کار میکنند.
به این مفهوم که، اگر کاری به منبعی تخصیص داده میشد، دیگر از آن پس نمیگرفتیم. دراین مقاله، از یک روش غیرانحصاری با تعیین حدآستانه برای انجام کاری توسط منبعی، به منظور بیکار یا سربار نداشتن هیچ گرهی، توزیع بار را انجام میدهیم. بدین منظور که اگر کاری به منبعی با ویژگی مشترک اختصاص داده نشد، با در نظر گرفتن حد آستانهای بتوان در صورت بیکار شدن منبعی با ویژگی مد نظر، کار را از منبع قبلی پس گرفت. این مقاله در پنج فصل تنظیم شده است. در فصل اول، رایانش ابری و توزیع بار معرفی شدهاند. در فصل دوم، الگوریتمها و روشهای موجود پیشین مورد مطالعه و بررسی قرار گرفته شدهاند. در فصل سوم، روش پیشنهادی مطرح شده که یک روش توزیع بار غیرانحصاری با تعیین حدآستانه در رایانش ابری است. روش مورد نظر باذکر مثال به صورت کامل شرح داده شده است. در فصل چهارم، نتایج حاصل از شبیهسازی روش پیشنهادی بیان شده، پارامترهای شبیهسازی به طور کامل ذکر گردیده و نتایج، مورد تحلیل قرار گرفته است.
-2 کارهای مرتبط
در این قسمت میخواهیم روشها و الگوریتمهای قبلا ارایه شده درباره توازن بار که یکی از چالشهای رایانش ابری است، بررسی کنیم. الگوریتم Min-Min یک الگوریتم ساده و سریع که قادر به ارائه عملکرد بهبود یافته است، میباشد. بنابراین در این الگوریتم ابتدا کارهای کوچک اجرا خواهد شد. [5] الگوریتم Max-Min، این الگوریتم بسیار مشابه الگوریتم Min-Min است. به جز اینکه بعد از یافتن زمانهای اجرای حداقل، بیشترین مقدار انتخاب میشود. سپس مطابق با زمان حداکثر، وظیفه روی ماشین مربوطه زمانبندی میشود. [5] توازن بار DEMS، یک روش ترکیبی از زمانبندی کار و توازن میباشد که شامل: زمانبندی مبتنی بر درخواست، پرس و جو و مهاجرت کار - - QMT، مهاجرت کار اجرا شده - . - STM در همین حال، QMT و STM به ترتیب برای زمان-بندی مستقل از کار و وابسته به کار موثر هستند. [6] در الگوریتم توازن بار مدیریت اعتماد، بحث کلیدی که نیاز به اهمیت ویژه دارد، امنیت ابرها است و مدیریت اعتماد، مولفه مهم امنیت ابر میباشد. ایده اصلی این تکنیک برای مدیریت ارزش اعتماد، پیشنهاد پارامترهای Iaas ابر میباشد. [7]
الگوریتم توازن بار دوفازی، اترکیب الگوریتم های زمانبندی OLB و LBMM برای بهرهبرداری بهتر از بازده اجرایی میباشد. هدف اصلی این کار، حفظ توازن بار سیستم، به حداقل رسانی زمان اجرا و بهرهبرداری از بازده اجرایی بهتر است. [8] الگوریتم توازن بار تپه نوردی تصادفی، یک روش بهینهسازی برای تخصیص منابع به سرور و یا ماشین مجازی میباشد که هدف اصلی از این کار، توزیع بار در رایانش ابری است. این الگوریتم در مقایسه با الگوریتم نوبت گردشی و FCFS دارای عملکرد بهتری است. [9] الگوریتم مدیریت بار دوبعدی مبتنی بر VM، از روشهای پیشبینی و تخمین برای مدل خود جهت تصمیمگیری درباره مهاجرت VM یا مهاجرت کاری استفاده میکند. هدف از این کار توازن بار در سطح VM، انتخاب بهترین VM از بین تمامی VM ها و تصمیمگیری درباره انتخاب مهاجرت کاری مبتنی بر بار سیستم است. [10] روش الگوریتم DAIRS، توازن بار را مبتنی بر پارامترهای : پهنای باند شبکه ، CPU و حافظه برای VM، نمایش میدهد. هدف این روش ایجاد توازن بار از طریق الگوریتم زمانبندی یکپارچه در مراکز دادهای ابر است. [11]
-3 روش پیشنهادی
در روش پیشنهادی با فرض این که n ویژگی داریم، تعداد 2n لیست ایجاد میشود. یک لیست برای منابع درجه اول هر ویژگی و یک لیست برای منابع درجه دوم هر لیست ایجاد میشود. منابعی که ویژگی اولشان مشترک است در یک لیست و منابعی که ویژگی دومشان مشترک است در لیست دیگری وارد میشود. به عبارت دیگر اگر ویژگیهای ما عبارت باشند از . . . P:{p1, p2, p3, , pn} ، آنگاه منابع درجه یک ویژگی p1 - که ویژگی اولشان p1 است - در یک لیست قرار میگیرند. منابع درجه دو p1 در یک لیست دیگر قرار میگیرند، به همین ترتیب تا منابع درجه یک pn است و منابع درجه دو pn در لیستهای جداگانه قرار میگیرند. وقتی زیرکارها وارد میشود، هر زیرکار با توجه به ویژگی خود به یکی از منابع اختصاص داده میشود. مثلا اگر اولین زیرکار با ویژگی p4 باشد، به لیست منابع درجه یک ویژگیp4 مراجعه کرده و زیرکار مورد نظر را به اولین منبع موجود در لیست اختصاص میدهیم. هر موقع زیرکار دیگری با ویژگی p4 پیدا شود، به منبع بعدی در لیست ذکر شده اختصاص داده میشود. به همین ترتیب منابع موجود در هر لیست، به نوبت یک زیرکار دریافت میکنند و وقتی تمام منابع یک لیست، در حال انجام یک زیر کار بودند، زیرکار بعدی به منبع اول اختصاص داده میشود. در واقع به صف انتظار منبع اول اضافه میشود.
زیرکار بعدی به صف انتظار منبع دوم و بدین ترتیب تا اتمام زیرکارها ادامه پیدا میکند. زمان اتمام آخرین زیرکار - یا به عبارتی، زمان اتمام همه کارها - از رابطه 1 محاسبه میشود. در رابطه 1 متغیر tend زمان اتمام آخرین زیرکار را نشان داده و tinit زمان شروع را نشان میدهد. - 1 - روش پیشنهادی شامل یک الگوی توازن بار است که در سه مرحله عمل میکند. در مرحله اول که همزمان با زمانبندی عمل میکند، زیرکارها بصورت مساوی به منابع مورد نظر تخصیص داده میشوند، به گونهای که در هر لیست، تعداد زیرکارهای - در حال اجرا و در صف انتظار - هر منبع با منابع دیگر در آن لیست برابر بوده یا فقط یک اختلاف خواهد داشت. در مرحله دوم از توازن بار، به لیستهای درجه دوم مراجعه میکنیم. این لیستها، همان لیستهایی هستند که منابع بر اساس ویژگیهای دومشان در یک لیست قرار گرفتهاند. برای مثال لیست منابعی که ویژگی دومشان p1 باشد.
در این لیستها، هر منبعی که خالی و بیکار باشد، یک زیرکار از منبعی که ویژگی اول آن با ویژگی دوم منبع بیکار برابر است میگیرد. برای مثال اگر در لیست منابعی که ویژگی دومشان p3 است یک منبع بیکار باشد و از طرف دیگر در لیست منابعی که ویژگی اولشان p3 است تعداد زیر کار در صف انتظار منابع باشند، یک زیرکار از منابع مشغول به منبع بیکار مهاجرت میکند. با این تفاوت که زیرکار مورد نظر در منبع اول - که ویژگی اولش با ویژگی زیرکار برابر است - در زمان مورد نظر تمام میشود اما در منبع دوم - که ویژگی دومش با ویژگی زیرکار برابر است - دو برابر زمان مورد نظر طول میکشد. در مرحله سوم از توازن بار که برعکس مرحله دوم است، اگر یک زیرکار در منبعی درجه دوم در حال اجرا باشد، و اگر یک منبع درجه یک برای آن زیرکار بیکار شود، زیرکار مورد نظر اگر بیش از نصف اجرایش باقیمانده باشد، به منبع درجه یک مهاجرت میکند، در غیر اینصورت به اجرای خود در منبع درجه دو ادامه میدهد.
سیستمی را فرض میکنیم که دارای 30 منبع است. در این سیستم کلا 5 ویژگی وجود دارد. تعداد 100 زیرکار وارد سیستم میشود. منابع این سیستم را به نماد S به صورت 6 >61 ' 62' 63' … ' 630@ نشان میدهیم. لیست منابع و ویژگیهای هر منبع در جدول 1 قابل مشاهده است. ویژگیهای موجود در سیستم نیز با نماد P به صورت P=[P1, P2, P3, P4, P5] نشان داده میشود. زیرکارها نیز با نماد W به صورت : >: 1' :2' :3' …' :100@ نمایش داده میشود. در مرحله اول، به ازای هر ویژگی، دو لیست تشکیل داده میشود که یک لیست شامل منابع درجه یک آن ویژگی و لیست دیگر شامل منابع درجه دو آن ویژگی خواهد بود. منابع، براساس ویژگیهای اول و دوم خود در یک لیست درجه یک و یک لیست درجه دو قرار میگیرند. در این مثال، 5 ویژگی در سیستم وجود دارد، بنابراین 10 لیست تشکیل خواهد شد. لیستهای مورد نظر تشکیل شده و هر منبع در دو لیست عضو میشود. در جدول 2 لیستهای ایجاد شده و منابع موجود در هر لیست مشاهده میشود. در بین منابع ممکن است دو یا چند منابع دارای ویژگیهای اول و دوم مشترک باشند.
