پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری

چکیده                            

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

مسئله تخصیص منابع در رایانش ابری و زمانبندی هر یک از کارهای کاربر بر روی ماشین های مجازی موجود، یک مسئلهNP-Completeمی باشد که تاکنون الگوریتم‌های بسیاری جهت حل آن ارائه گردیده است. ولی هیچ یک از این الگوریتم ها قادر به برآورده ساختن نیازمندیهای مرتبط با سرعت و دقت در محیطهای رایایش ابری نیستند. در این پژوهش، روشی ترکیبی از الگوریتم رقابت استعماری و جستجوی محلی، برای حل این مسئله پیشنهاد گردیده است. این الگوریتم با ایجاد یک امپراتوری اولیه سعی در بهبود سازی پاسخ های ممکن، از طریق اعمال مراحل الگوریتم رقابت استعماری دارد. جهت جلوگیری از همگرایی زودرس، الگوریتم رقابت استعماری با یک الگوریتم جستجوی محلی ترکیب شده است. الگوریتم ترکیبی پیشنهادی از یک مکانیسم تشخیص همگرایی مبتنی بر ضریب شباهت استفاده کرده و در زمانهایی که روش رقابت استعماری دچار همگرایی زودرس می شود، روش جستجوی محلی را اجرا می کند.

کیفیت جواب­ها وکارایی الگوریتم پیشنهادی با کارایی الگوریتمهای دور رابین، کلونی مورچگان و ژنتیک، مقایسه گردید.

 نتایج : نتایج بدست آمده، نشان میدهد که الگوریتم پیشنهادی از نظر کیفیت زمان اجرا از دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک سریعتر عمل می کند. علاوه بر این، الگوریتم پیشنهادی از نظر کیفیت جواب‌ها، از بقیه الگوریتم‌ های مقایسه شده بهتر عمل می کند.

مقدمه:

در سال های اخیر توجهات فزاینده ای به محاسبات ابری شده است. بیشترین استقبالی که از این تکنولوژی صورت گرفته در صنعت چندرسانه ای  و سیستم‌ های آنالیز می‌باشد. در محاسبات ابری برخی از تصمیمات تحت عنوان تصمیمات برنامه‌ریزی شناخته می‌شوند. فرآیند برنامه‌ریزی منابع لازم جهت تولید مجموعه فعالیت‌های مورد نیاز جهت زمانبندی را تعیین می‌کند[Baker00]. زمانبندی  عبارت است از تخصیص منابع محدود به فعالیت‌ها در طول زمان، جهت بهینه سازی یک یا چند تابع هدف [Baker00]. مسئله زمانبندی منابع رایانش ابری ، جزء مهمترین مسائل زمانبندی می‌باشد که توجه بسیاری از محققان را به خود جلب کرده است. مسئله زمانبندی منابع، یک مسئله بسیار سخت در میان مسائل NP-hard محسوب می‌شود [Yu12، Garey76].

مسئله زمانبندی و تخصیص منابع در یک ابر و یک تور، یک مسئله بسیار سخت می باشد و در نتیجه فضای جستجو ی این مسئله به اندازه ای بزرگ است که اگر یک الگوریتم بخواهد این فضا را به صورت ترتیبی مورد بررسی قرار داده و بهترین جواب را بیابد، نیاز به زمان نمایی خواهد داشت. از جمله الگوریتم های ابتکاری که در حوزه زمانبندی و تخصیص منابع مورد استفاده قرار گرفته اند، می توان به الگوریتم کلونی مورچگان [Zhu12, Chen09]  و الگوریتم ژنتیک [Javier07] اشاره کرد.

الگوریتم کلونی مورچه ها، نوعی الگوریتم مبتنی بر هوش جمعی است که از مطالعات و مشاهدات روی کلونی مورچه ها الهام گرفته شده است [Diargo96]. در دنیای واقعی، ابتدا مورچه ها به صورت تصادفی به این سو و آن سو می روند تا غذا بیابند. سپس به لانه بر می گردند و ردی از فرومون[1] در مسیر به جای می گذارند. هنگامی که یک مورچه به طور تصادفی و تنها حرکت می کند، با مواجه شدن با مسیری که دارای اثر فرومون  بیشتری است، به احتمال زیاد مسیر فوق را انتخاب می کند و با فرومونی که از خود بر جای می گذارد، آن را در مسیر مذکور تقویت می کند. اگر چه الگوریتم های مبتنی بر کلونی مورچگان ارائه شده [Zhu12, Chen09]، قابلیت زمانبندی موازی مسئله تخصیص منابع در رایانش ابری را فراهم می کند، ولی جهت اجرای کارآمد این الگوریتم نیاز به سخت افزار موازی قدرتمندی می  باشد و اجرای آن بر روی یک سیستم زمانبند نیاز به زمان قابل ملاحظه ای خواهد داشت.

در [Javier07] الگوریتم زمانبندی و تخصیص منابع در رایانش ابری و توری به وسیله الگوریتم ژنتیک مورد بررسی قرار گرفته است. الگوریتم ژنتیک، نوعی الگوریتم ابتکاری است که از تئوری "زنده ماندن شایسته‌ترین"[2]داروین ایده گرفته است [Eiben07]. الگوریتم ژنتیک را می‌توان به عنوان نوعی الگوریتم تکاملی[3] دسته‌بندی کرد که جواب‌های بالقوه یک مسئله خاص را در قالب ساختارهای داده ای شبیه به کروموزوم[4]، کدگذاری کرده و عملگرهای ترکیب مجدد را بر روی این ساختارها اعمال می‌کند تا اطلاعات حیاتی را حفظ کند.

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

رقابت استعماری

شکل 2-8 فلوچارت الگوریتم  رقابت استعماری را نشان می‌دهد [Atashpaz07]. همانند دیگر الگوریتم‌های تکاملی، این الگوریتم، نیز با تعدادی جمعیت اولیه تصادفی که هر کدام از آنها یک "کشور" نامیده می‌شوند؛ شروع می‌شود. تعدادی از بهترین عناصر جمعیت (معادل نخبه‌ها در الگوریتم ژنتیک) به عنوان امپریالیست[5]انتخاب می‌شوند. باقیمانده جمعیت نیز به عنوان مستعمره[6]، در نظر گرفته می‌شوند. استعمارگران بسته به قدرتشان، این مستعمرات را با یک روند خاص که در ادامه می‌آید؛ به سمت خود می‌کشند. قدرت کل هر امپراطوری، به هر دو بخش تشکیل دهنده آن یعنی کشور امپریالیست (به عنوان هسته مرکزی) و مستعمرات آن، بستگی دارد. در حالت ریاضی، این وابستگی با تعریف قدرت امپراطوری به صورت مجموع قدرت کشور امپریالیست، به اضافه در صدی از میانگین قدرت مستعمرات آن، مدل شده است.

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

کلمات کلیدی:

 تخصیص منابع، رایانش ابری، الگوریتم رقابت استعماری، جستجوی محلی، NP-Complete.

فصل اول:

کلیات

مقدمه

سیر تکاملی محاسبات به گونه ای است که می‌توان آن را پس از آب، برق، گاز و تلفن به عنوان عنصر اساسی پنجم فرض نمود. در چنین حالتی کاربران سعی می‌کنند بر اساس نیازهایشان و بدون توجه به آن که یک سرویس در کجا قرار دارد و یا چگونه تحول داده می‌شود، به آن دسترسی یابند. نمونه‌های متنوعی از سیستم‌های محاسباتی ارائه شده است که سعی دارند چنین خدماتی را به کاربران ارائه دهند. برخی از این سیستم‌های محاسباتی عبارتند از: محاسبات خوشه ای[1]، محاسبات توری[2]و اخیراً رایانش ابری[3].

در سالهای اخیر توجهات فزاینده ای به محاسبات ابری شده است. بیشترین استقبالی که از این تکنولوژی صورت گرفته در صنعت چندرسانه ای[4] و سیستم‌های آنالیز می‌باشد سود استفاده از محاسبات ابری در سال 2008، برای کاربردهای تجاری را سه تا چهار برابر سیستم‌های غیر ابری تخمین زده  شده بود[Stanoevska10].فاستر و همکارانش[5][Foster08]محاسبات ابری را به صورت زیر تعریف می‌کند:

" محاسبات ابری مدلی توزیع شده با مقیاس بزرگ است که مجموعه مقیاس پذیر و مجازی شده از قدرت محاسباتی مدیریت شده،فضای ذخیره سازی و سرویس‌ها را از طریق اینترنت در اختیار مشتریان قرار می‌دهد."

در محاسبات ابری برخی از تصمیمات تحت عنوان تصمیمات برنامه‌ریزی[6]شناخته می‌شوند. فرآیند برنامه‌ریزی منابع لازم جهت تولید مجموعه فعالیت‌های مورد نیاز جهت زمانبندی را تعیین می‌کند[Baker00]. زمانبندی[7] عبارت است از تخصیص منابع محدود به فعالیت‌ها در طول زمان، جهت بهینه سازی یک یا چند تابع هدف [Baker00]. مسئله زمانبندی منابع رایانش ابری[8]، جزء مهمترین مسائل زمانبندی می‌باشد که توجه بسیاری از محققان را به خود جلب کرده است. مسئله زمانبندی منابع، یک مسئله بسیار سخت در میان مسائل NP-hardمحسوب می‌شود [Yu12، Garey76]. جواب‌های بهینه این مسئله، مطلوب بسیاری از کارخانه‌های تولیدی و نیز شرکت‌های خدماتی می‌باشند. در بخش دوم این فصل مسئله تخصیص و زمانبندی منابع رایانش ابری تعریف می شود. در بخش سوم، خلاصه ای از پیشنه تحقیق بیان شده و توصیفی از روش پیشنهادی آورده شده است. بخش چهارم به مروری بر فصل های مختلف این پایان نامه تخصیص داده شده است.

1-2 بیان مسئله

ساختار کلی منابع یک ابر در شکل 1-1 آورده شده است.

بر اساس این شکل، یک ابر از تعدادی سخت افزار (پردازنده، حافظه و ...) تشکیل شده است که این منابع لزوماً دارای ساختار همگنی نیستند. برای دسترسی و استفاده آسان کاربر، این عدم همگنی و پراکندگی منابع باید مخفی بماند. برای این منظور از ماشین های مجازی استفاده می شود. هر ماشین مجازی تعدادی از منابع را مدیریت کرده و آنها را در قالب یک واحد معرفی می کنند. به عنوان مثال ممکن است حافظه ای که یک ماشین مجازی معرفی می کند 1 گیگابایت باشد که 500 مگابایت آن مربوط به یک موبایل و بقیه مربوط به یک دستگاه پردازشی دیگر باشد. در خواست های مشتریان (که شامل طیف وسیعی از درخواست های پردازشی و ذخیره سازی و ... است) از طریق واسط کاربر به هسته ابر معرفی می شوند. هسته ابر برای انجام این کارها، درخواستی مبنی بر زمانبندی کارهای موجود بر روی ماشین های مجازی صادر می کند. وظیفه زمانبند، یافتن تخصیصی از ماشین های مجازی به کارهای ورودی است به گونه ای نیازهای محاسباتی و حافظه ای تمامی کارها، با کمترین هزینه برآورده شود. به عبارت دیگر، فرض کنید مجموعه درخواست ها (کارها) به صورت  از طریق واسط کاربر به هسته معرفی شده باشد. همچنین فرض کنید ماشین های مجازی آزاد به صورت وجود داشته باشند. حال وظیفه زمانبند تخصیص درخواست های ورودی به ماشین های مجازی آزاد است به گونه ای که تابع زیر را حداقل کند [Zhu12,Chen09,Javier07]  :

(1-1)

که در آن

(1-2)

و این مسئله قیود زیر را دارا می باشد:

(1-3)

( فرمول ها در فایل اصلی موجود است )

(1-4)

در فرمول (1-1)،  هزینه تخصیص درخواست (کار)  iام به ماشین jام را مشخص می کند. این هزینه میتواند به طرق مختلفی تعریف شود، ولی مهمترین هزینه ها عبارتند از

Makespan: زمان اتمام آخرین درخواست

Mean(flow_time): میانگین زمانهای اجرای درخواستها

هزینه می تواند ترکیبی از این دو پارامتر نیز باشد.

1-3 پیشینه تحقیق

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

همان طور که گفته شد، مسئله زمانبندی و تخصیص منابع در یک ابر و یک تور، یک مسئله بسیار سخت می باشد و در نتیجه فضای جستجوی این مسئله به اندازه ای بزرگ است که اگر یک الگوریتم بخواهد این فضا را به صورت ترتیبی مورد بررسی قرار داده و بهترین جواب را بیابد، نیاز به زمان نمایی خواهد داشت. الگوریتم های ابتکاری هوشمند ، با تکیه بر مکانیسم های سیستم های موفق، سعی در شبیه سازی این مکانیسم ها، جهت حل مسائل مشکل،  می نمایند. از جمله الگوریتم های ابتکاری که در حوزه زمانبندی و تخصیص منابع مورد استفاده قرار گرفته اند، می توان به الگوریتم کلونی مورچگان [Zhu12, Chen09]  و الگوریتم ژنتیک [Javier07] اشاره کرد.

.  الگوریتم کلونی مورچه ها، نوعی الگوریتم مبتنی بر هوش جمعی است که از مطالعات و مشاهدات روی کلونی مورچه ها الهام گرفته شده است [Diargo96]. در دنیای واقعی، ابتدا مورچه ها به صورت تصادفی به این سو و آن سو می روند تا غذا بیابند. سپس به لانه بر می گردند و ردی از فرومون[9] در مسیر به جای می گذارند. هنگامی که یک مورچه به طور تصادفی و تنها حرکت می کند، با مواجه شدن با مسیری که دارای اثر فرومون  بیشتری است، به احتمال زیاد مسیر فوق را انتخاب می کند و با فرومونی که از خود بر جای می گذارد، آن را در مسیر مذکور تقویت می کند. اگر چه الگوریتم های مبتنی بر کلونی مورچگان ارائه شده [Zhu12, Chen09]، قابلیت زمانبندی موازی مسئله تخصیص منابع در رایانش ابری را فراهم می کند، ولی جهت اجرای کارآمد این الگوریتم نیاز به سخت افزار موازی قدرتمندی می  باشد و اجرای آن بر روی یک سیستم زمانبند نیاز به زمان قابل ملاحظه ای خواهد داشت. بخصوص اگر تعداد درخواست های مشتریان افزایش یابد، این الگوریتم عملاً کارایی خود را از دست داده و قادر به زمانبندی منابع نخواهد بود.

در [Javier07] الگوریتم زمانبندی و تخصیص منابع در رایانش ابری و توری به وسیله الگوریتم ژنتیک مورد بررسی قرار گرفته است. الگوریتم ژنتیک، نوعی الگوریتم ابتکاری است که از تئوری "زنده ماندن شایسته‌ترین"[10]داروین ایده گرفته است[Eiben07]. الگوریتم ژنتیک را می‌توان به عنوان نوعی الگوریتم تکاملی[11] دسته‌بندی کرد که جواب‌های بالقوه یک مسئله خاص را در قالب ساختارهای داده ای شبیه به کروموزوم[12]، کدگذاری کرده و عملگرهای ترکیب مجدد را بر روی این ساختارها اعمال می‌کند تا اطلاعات حیاتی را حفظ کند.اگر چه الگوریتم ژنتیک الگوریتمی قدرتمند در حل مسائل غیر خطی است، ولی اگر میزان غیر خطی بودن مسئله زیاد باشد، این الگوریتم کارایی خود را از دست می دهد و دچار همگرایی زودرس شده و در بهینه های محلی گرفتار می شود. مسئله زمانبندی از جمله مسائل با اندازه درجه غیرخطی بودن بسیار بالا است و در نتیجه احتمال گرفتار شدن این الگوریتم در بهینه های محلی بسیار بالا است و در نتیجه پاسخ های این الگوریتم قابل اعتماد نخواهند بود.

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

1-4 مروری بر فصل های پایان نامه

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

فصل دوم:

 ادبیات تحقیق

2-1 مقدمه

سیر تکاملی محاسبات به گونه ای است که می‌توان آن را پس از آب، برق، گاز و تلفن به عنوان عنصر اساسی پنجم فرض نمود. در چنین حالتی کاربران سعی می‌کنند بر اساس نیازهایشان و بدون توجه به آن که یک سرویس در کجا قرار دارد و یا چگونه تحول داده می‌شود، به آن دسترسی یابند. نمونه‌های متنوعی از سیستم‌های محاسباتی ارائه شده است که سعی دارند چنین خدماتی را به کاربران ارائه دهند. برخی از این سیستم‌های محاسباتی عبارتند از: محاسبات خوشه ای[13]، محاسبات توری[14]و اخیراً رایانش ابری[15].

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

2-2 محاسبات توری

واژه تور[16] یا محاسبات توری، معانی  مختلفی برای افراد مختلف دارد. معانی که به این واژه نسبت داده شده اند، طیف وسیعی از محاسبات خوشه ای، محاسبات با کارایی بالا[17]، محاسبات مبتنی بر کارکرد[18]، محاسبات نظیر به نظیر[19]گرفته تا نوع جدیدی از محاسبات تحت عنوان محاسبات بدن زیرساخت[20]را شامل می‌شود. ولی منظور ما از تور در این پایان نامه، همان محاسبات توری است که در ادامه به ترسیم ساختار و تعریف آن خواهیم پرداخت. بنابراین این بخش موارد زیر را پوشش می‌دهد:

تعریف محاسبات توری.

توصیف معماری محاسبات توری.

مختصری از مزایا و خطرات محاسبات توری.

انواع تورها.

 2-2-1 تعریف محاسبات توری

محاسبات توری پدیده ای پیچیده است که ریشه در دانش الکترونیکی[21] داشته واز توسعه مفاهیم محاسبات موازی[22] و توزیع شده[23] به دست آمده است. ظهور و بروز محاسبات توری مربوط به اوایل 1990 میباشد که کامپیوتر‌هایی با کارایی بالا به ارتباطات داده ای پرسرعت متصل شدند تا بتوانند محاسبات مربوط به کاربردهای علمی و مبتنی بر داده را پاسخ دهند. در آن زمان، محاسبات توری را با نامهایی مانند ابر محاسبات[24]یا فرا محاسبات[25]می‌شناختند و تاکید آن بر روی استفاده از منابع موجود برای کاربردهایی با کارایی بالا بود.

اولین و پرکاربردترین تعریف برای محاسبات توری تعریفی است که توسط فاستر و کسلمن[26][Foster08] ارائه شده است:

" یک تور محاسباتی، ساختاری سخت افزاری و نرم افزاری است که یک دسترسی قابل اعتماد[27]، سازگار[28]، فراگیر[29] و ارزان را به قابلیت‌های محاسباتی سطح بالا فراهم آورد. "

مشکل واقعی مربوط به تور عبارت است از اشتراک منابع و حل مسئله هماهنگ در سازمانهای مجازی که خود از چندین زیرسازمان تشکیل شده اند. اشتراکی که ما به دنبال آن هستم، فقط یک تبادل فایلی ساده نیست بلکه دسترسی مستقیم به کامپیوترها، نرم افزار، داده و منابع دیگر را نیز شامل می‌شود[Stanoevska10].

منابع اصلی که در یک تور می‌توانند به اشتراک گذاشته شوند، عبارتند از:

قدرت پردازنده (قدرت محاسباتی).

فضای ذخیره داده (سیستم فایل شبکه شده).

ارتباطات و پهنای باند.

نرم افزار کاربردی.

2-2-2 معماری محاسبات توری

یک معماری تور[30] نمایی کلی از اجزای تور را فراهم کرده اهداف و کارکردهای اجزای خود و نیز نحوه تعامل اجزا با یکدیگر را مشخص می‌کند. تمرکز اصلی معماری تور بر روی قابلیت همکاری و پروتکل‌های میان فراهم کنندگان منابع و استفاده کنندگان از این منابع می‌باشد. براساس کار فاستر و کسل‌من[31]، پروتکل‌های مورد نیاز برای تور به صورت شکل 2-1 سازماندهی می‌شوند: