Service Placement and Request Scheduling for Data-Intensive Applications in Edge Clouds

Mobile edge computing provides the opportunity for wireless users to exploit the power of cloud computing without a large communication delay. To serve data-intensive applications (e.g., video analytics, machine learning tasks) from the edge, we need, in addition to computation resources, storage resources for storing server code and data as well as network bandwidth for receiving user-provided data. Moreover, due to time-varying demands, the code and data placement needs to be adjusted over time, which raises concerns of system stability and operation cost. In this paper, we address these issues by proposing a two-time-scale framework that jointly optimizes service (code and data) placement and request scheduling, while considering storage, communication, computation, and budget constraints. First, by analyzing the hardness of various cases, we completely characterize the complexity of our problem. Next, we develop a polynomial-time service placement algorithm by formulating our problem as a set function optimization, which attains a constant-factor approximation under certain conditions. Furthermore, we develop a polynomial-time request scheduling algorithm by computing the maximum flow in a carefully constructed auxiliary graph, which satisfies hard resource constraints and is provably optimal in the special case where requests have homogeneous resource demands. Extensive synthetic and trace-driven simulations show that the proposed algorithms achieve 90% of the optimal performance.

I. Introduction

The emerging technology of mobile edge computing [3] enables wireless users to run resource-intensive and delay-sensitive applications from the edge of mobile networks, at small server clusters referred to as edge clouds [4], cloudlets [5], fog [6], follow me cloud [7], or micro clouds [8]. Mobile applications are increasingly resource-demanding as they address use cases based on big data and machine learning problems. As users access these resource-hungry applications via bandwidth-limited wireless links, how to optimally allocate the limited resources at edge clouds to competing demands poses a difficult but intriguing research question, which has attracted tremendous interest in the research community.