GRASP heuristics for assignment problems in cloud computing

• Grant number: 15/23270-9
• Support Opportunities: Scholarships abroad - Research Internship - Scientific Initiation
• Start date: January 16, 2016
• End date: March 15, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cid Carvalho de Souza
• Grantee: Matheus de Souza Ataide
• Supervisor: Marcos Antonio Vaz Salles
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: University of Copenhagen, Copenhagen, Denmark
• Associated to the scholarship: 15/08438-0 - Optimization problems on virtual machines allocation for cloud computing, BP.IC

Abstract

This document presents a research project for assignment problems in cloud computing, to be developed by the student Matheus Ataíde at the Department of Computer Science (DIKU) of the University of Copenhagen under the supervision of Professor Marcos Salles. Cloud computing has flourished in recent years. By sharing resources and adopting a pay-as-you-go pricing model, cloud computing promise a better use of the computational infrastructure and to reduce costs. However, to achieve a high level of resource use, it is inevitable that the components of a given application are assigned to non-contiguously virtual machines. In this way, those components can end up in physically distant machines in the cloud. These differences in distance can cause big average latency variations between the components. For many applications, this discrepancy in latency has a huge impact in performance, which depends fundamentally on the way that the application components are mapped to the cloud machines. Optimization problems related to this mapping were discussed in recent scientific articles by Zou etal. (2012,2015). Besides showing that those problems are NP-hard, the authors also proposed and tested some greedy heuristics to solve them, comparing the results with solutions generated in a purely random way. Analyzing these results, we noticed the potential of using heuristics that combined those two characteristics to achieve better solutions. One heuristic that appears as a natural candidate in this situation is GRASP (Greedy Randomized Adaptive Search Procedure). In this way, the goal of this proposal is to investigate the use of GRASP in the solution of the problems treated in Zou et al. (2012, 2015). During his visit to DIKU the student is expected mainly to run computational experiments and to write reports analyzing the results obtained with a view to publishing the min a scientific conference and/or journal. (AU)