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 incloud computing, to be developed by the student Matheus Ataíde at theDepartment of Computer Science (DIKU) of the University of Copenhagenunder the supervision of Professor Marcos Salles.Cloud computing has flourished in recent years. By sharing resourcesand adopting a pay-as-you-go pricing model, cloud computing promise abetter use of the computational infrastructure and to reduce costs.However, to achieve a high level of resource use, it is inevitablethat the components of a given application are assigned tonon-contiguously virtual machines. In this way, those components canend up in physically distant machines in the cloud. These differencesin distance can cause big average latency variations between thecomponents. For many applications this discrepancy in latency has ahuge impact in performance, which depends fundamentally on the way thatthe application components are mapped to the cloudmachines. Optimization problems related to this mapping were discussedin recent scientific articles by Zou etal. (2012,2015). Besides showing that those problemsare NP-hard, the authors also proposed and tested some greedyheuristics to solve them, comparing the results with solutionsgenerated in a purely random way. Analyzing these results, we noticedthe potential of using heuristics that combined those twocharacteristics to achieve better solutions. One heuristic thatappears as a natural candidate in this situation is GRASP (GreedyRandomized Adaptive Search Procedure).In this way, the goal of this proposal is to investigate the use ofGRASP in the solution of the problems treated in Zou etal. (2012, 2015). During his visit to DIKU the studentis expected mainly to run computational experiments and to writereports analyzing the results obtained with a view to publishing themin a scientific conference and/or journal.