Dynamic Service Placement for Mobile Micro-Clouds with Predicted Future Costs

By Shiqiang Wang, Rahul Urgaonkar, Kevin Sean Chan, Ting He, Murtaza Zafer, Kin Kwong Leung. 2015

258 citations recorded by the source corpus.

Mobile micro-clouds are promising for enabling performance-critical cloud applications. However, one challenge therein is the dynamics at the network edge. In this paper, we study how to place service instances to cope with these dynamics, where multiple users and service instances coexist in the system. Our goal is to find the optimal placement (configuration) of instances to minimize the average cost over time, leveraging the ability of predicting future cost parameters with known accuracy. We first propose an offline algorithm that solves for the optimal configuration in a specific look-ahead time-window. Then, we propose an online approximation algorithm with polynomial time-complexity to find the placement in real-time whenever an instance arrives. We analytically show that the online algorithm is <inline-formula><tex-math notation="LaTeX">$O(1)$</tex-math><alternatives> <inline-graphic xlink:href="wang-ieq1-2604814.gif"/></alternatives></inline-formula>-competitive for a broad family of cost functions. Afterwards, the impact of prediction errors is considered and a method for finding the optimal look-ahead window size is proposed, which minimizes an upper bound of the average actual cost. The effectiveness of the proposed approach is evaluated by simulations with both synthetic and real-world (San Francisco taxi) user-mobility traces. The theoretical methodology used in this paper can potentially be applied to a larger class of dynamic resource allocation problems.

Subfields: Computer Networks and Communications, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

Citations in the corpus

Adaptive Federated Learning in Resource Constrained Edge Computing Systems (2018, background): “Existing work on MEC focuses on generic applications, where solutions have been proposed for application offloading [11], [12], workload scheduling [13], [14], and service migration triggered by user mobility [15], [16].”
Online Resource Allocation for Arbitrary User Mobility in Distributed Edge Clouds (2017, background): “Most of them often assume statistical knowledge about user mobility [12]–[14], or rely on prediction of future costs [15].”
Resource Management in Fog/Edge Computing (2018, methodology): “es in fog/edge computing under static network conditions and predetermined resource demands and were not dynamic condition-aware (do not consider users’ mobility and changes in resource availability) [177]. This shortcoming was addressed by considering an additional set of parameters including the l”
Toward Edge Intelligence: Multiaccess Edge Computing for 5G and Internet of Things (2020, background): “It is shown that compared to never and always migrate options, up to 32%–50% of the average cost can be reduced [172].”
Joint Service Caching and Task Offloading for Mobile Edge Computing in Dense Networks (2018, unknown): “We also note that the term “service placement” was used by some other literature [19], [20] in a different context.”
A Survey of Multi-Access Edge Computing in 5G and Beyond: Fundamentals, Technology Integration, and State-of-the-Art (2019, unknown): “DP in [332], which was later extended in [330] to derive a threshold policy-based mechanism, in [333] to consider general cost models, 2-D mobility model, and application to real-world traces, and in [334] to remove the Markovian assumption and deal with dynamic service arrivals and departures. In [”
Delay-Aware Microservice Coordination in Mobile Edge Computing: A Reinforcement Learning Approach (2019, background): “To address this issue, service migration is proposed, which deals with whether, how, and where the service should be migrated when users change their locations [17], [18], [19], [20].”
Mobile Edge Computing: A Survey on Architecture and Computation Offloading (2017, background): “and up to 50% reduction of average cost is achieved compared to never and always migrate options, respectively [117]).”
Follow Me at the Edge: Mobility-Aware Dynamic Service Placement for Mobile Edge Computing (2018, background): “For example, in [15], by finding an optimal look-ahead window size, the long-term optimization problem can be approximately discretized into a series of equivalent short-path problems.”