Dynamic service placement in mobile micro-clouds

Abstract

Cloud computing is an important enabling technique for running complicated applications on resource-limited handheld devices, personal computers, or small enterprise servers, by offloading part of the computation and storage to the cloud. However, traditional centralized cloud architectures are incapable of coping with many emerging applications that are delay-sensitive and require large amount of data exchange between the front-end and back-end components of the application. To tackle these issues, the concept of mobile micro-cloud (MMC) has recently emerged. An MMC is typically connected directly to a network component, such as a wireless basestation, at the edge of the network and provides services to a small group of users. In this way, the communication distances between users and the cloud(s) hosting their services are reduced, and thus users can have more instantaneous access to cloud services.

Several new challenges arise in the MMC context, which are mainly caused by the limited coverage area of basestations and the dynamic nature of mobile users, network background traffic, etc. Among these challenges, one important problem is where (on which cloud) to place the services (or, equivalently, to execute the service applications) to cope with the user demands and network dynamics. We focus on this problem in this thesis, and consider both the initial placement and subsequent migration of services, where migration may occur when the user location or network conditions change.

The problem is investigated from a theoretical angle with practical considerations. We first abstract the service application and the physical cloud system as graphs, and propose online approximation algorithms for finding the placement of an incoming stream of application graphs onto the physical graph. Then, we consider the dynamic service migration problem, which we model as a Markov decision process (MDP). The state space of the MDP is large, making it difficult to solve in real-time. Therefore, we propose simplified solution approaches as well as approximation methods to make the problem tractable. Afterwards, we consider more general non-Markovian scenarios but assume that we can predict the future costs with a known accuracy. We propose a method of dynamically placing each service instance upon its arrival and a way of finding the optimal look-ahead window size for cost prediction. The results are verified using simulations driven by both synthetic and real-world data traces. Finally, a framework for emulating MMCs in a more practical setting is proposed. In our view, the proposed solutions can enrich the fundamental understanding of the service placement problem. It can also path the way for practical deployment of MMCs. Furthermore, various solution approaches proposed in this thesis can be applicable or generalized for solving a larger set of problems beyond the context of MMC.