The virtual machine (VM) allocation problem in cloud computing has been widely studied in recent years, and many algorithms have been proposed in the literature. Most of them have been successfully applied to batch processing models such as MapReduce; however, none of them can be applied to streaming workflow well because of the following weaknesses: 1) failure to capture the characteristics of tasks in streaming workflow for the short life cycle of data streams; 2) most algorithms are based on the assumptions that the price of VMs and traffic among data centers (DCs) are static and fixed. In this paper, we propose a streaming workflow allocation algorithm that takes into consideration the characteristics of streaming work and the price diversity among geo-distributed DCs, to further achieve the goal of cost minimization for streaming big data processing. First, we construct an extended streaming workflow graph (ESWG) based on the task semantics of streaming workflow and the price diversity of geo-distributed DCs, and the streaming workflow allocation problem is formulated into mixed integer linear programming based on the ESWG. Second, we propose two heuristic algorithms to reduce the computational space based on task combination and DC combination in order to meet the strict latency requirement. Finally, our experimental results demonstrate significant performance gains with lower total cost and execution time

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

اشکال در تطبیق خود با مشخصه‌های وظایفی که در جریان کاری استریمینگ و آن‌هم برای جریان‌های داده‌ای با طول عمر کوتاه وجود دارند.

اغلب الگوریتم‌ها بر مبنای این فرضیه بوده که قیمت ماشین‌های مجازی و ترافیک بین مراکز داده‌ای (dc) ایستا و ثابت می‌باشد.

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

 1- مقدمه