Provisioning Delay-Aware Services in Mobile Edge Cloud-Networks via Efficient Resource Allocation and Optimization

Abstract

Thanks to advances in wireless communication and mobile computing, the last decade has seen an explosion of new innovative services on smartphone devices in areas as diverse as transportation, mobile payment and social media. The ubiquity of mobile smart devices and their constant presence in every day life has generated unprecedented data traffic between end users and the remote cloud. To prepare for the increasing data traffic in the coming years and the demand for low-latency computation resources near the user, network service providers are increasingly turning to Mobile Edge Computing to bring cloud computing capabilities to the edge of the network. Mobile Edge Computing (MEC) is a recent network paradigm and is conceived as consisting of three layers: (1) a layer of users, (2) a layer of small-scale data centers called cloudlets situated at the network edge that inter-connect to form the edge-cloud, and (3) and geographically distributed data-centers that form the remote cloud with vast resources in remote locations. Users at the edge of the network offload computation tasks to the edge-cloud instead of remote clouds, thereby decreasing the response time for offloaded tasks and reducing congestion in the back-haul network. In this thesis, we will focus on the provisioning of Delay-Aware Services in MEC networks by efficiently utilizing various MEC resources to reduce the latency of user offloaded tasks in different application scenarios, while meeting ever-growing user demands. We firstly address how to balance the workload among cloudlets in the edge-cloud with the aim to minimize the maximum response time of all offloaded tasks. We propose two algorithms for the problem: one is a fast heuristic, and another is a distributed genetic algorithm that is capable of delivering a more accurate solution compared to the heuristic, but at the expense of a longer running time. We then study policy-aware unicast request admissions with and without end-to-end delay constraints in a Software Defined Network (SDN). We develop efficient algorithms for the admission of a single request with and without the end-to-end delay constraint, and online algorithms with a guaranteed performance for the dynamic admission of requests without the knowledge of future arrivals. In particular, we provide the very first online algorithm with a provable competitive ratio for the problem without the end-to-end delay requirement. We thirdly investigate the deployment of virtualized network functions among cloudlets to serve end-users, while meeting the resource demands of mobile users and their Quality-of-Service (QoS) requirements. We devise an efficient algorithm for the problem by utilizing VNF instance sharing and cost-effective creation of new VNF instances, and develop an effective prediction mechanism to predict idle VNF instance releases and new VNF instance creations for further cost savings over time. We fourthly envision a scenario in the near future where players wearing AR heads-up display devices engage with other players over a large area with densely deployed cloudlets. We propose a novel system model and formulate the Decentralized Multiplayer Coordination (DMC) Problem with the aim of minimizing the game frame duration of all players. We then devise an efficient algorithm for the problem. Finally we conduct extensive experiments to evaluate the effectiveness of each proposed algorithm, and investigate the impact of various algorithm parameters and environmental settings. Experimental results show that the proposed algorithms are promising. Show more