A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> This paper introduces an analytical model for the Follow-Me Cloud (FMC) concept whereby service mobility is enabled across data centers following the mobility of a mobile user. Given a network and cloud setup and a mobility pattern of a mobile user, the proposed analytical model provides the performance of the FMC concept related to: (i) the user experience with the service (such as: UE average distance from the optimal DC, average end-to-end delay, service disruption duration); and (ii) to the cloud/mobile operator (such as the service migration cost). Obtained results are encouraging. They confirm the advantage of the FMC concept, but stress the need for careful consideration when triggering the service migration. <s> BIB001 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> The Follow-Me Cloud (FMC) concept enables service mobility across federated data centers (DCs). Following the mobility of a mobile user, the service located in a given DC is migrated each time an optimal DC is detected. The detailed criterion for optimality is defined by operator policy, but it may be typically derived from geographical proximity or load. Service migration may be an expensive operation given the incurred cost in terms of signaling messages and data transferred between DCs. Decision on service migration defines therefore a tradeoff between cost and user perceived quality. In this paper, we address this tradeoff by modeling the service migration procedure using a Markov Decision Process (MDP). The aim is to formulate a decision policy that determines whether to migrate a service or not when the concerned User Equipment (UE) is at a certain distance from the source DC. We numerically formulate the decision policies and compare the proposed approach against the baseline counterpart. <s> BIB002 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> Mobile micro-cloud is an emerging technology in distributed computing, which is aimed at providing seamless computing/data access to the edge of the network when a centralized service may suffer from poor connectivity and long latency. Different from the traditional cloud, a mobile micro-cloud is smaller and deployed closer to users, typically attached to a cellular base station or wireless network access point. Due to the relatively small coverage area of each base station or access point, when a user moves across areas covered by different base stations or access points which are attached to different micro-clouds, issues of service performance and service migration become important. In this paper, we consider such migration issues. We model the general problem as a Markov decision process (MDP), and show that, in the special case where the mobile user follows a one-dimensional asymmetric random walk mobility model, the optimal policy for service migration is a threshold policy. We obtain the analytical solution for the cost resulting from arbitrary thresholds, and then propose an algorithm for finding the optimal thresholds. The proposed algorithm is more efficient than standard mechanisms for solving MDPs. <s> BIB003 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> We study the dynamic service migration problem in mobile edge-clouds that host cloud-based services at the network edge. This offers the benefits of reduction in network overhead and latency but requires service migrations as user locations change over time. It is challenging to make these decisions in an optimal manner because of the uncertainty in node mobility as well as possible non-linearity of the migration and transmission costs. In this paper, we formulate a sequential decision making problem for service migration using the framework of Markov Decision Process (MDP). Our formulation captures general cost models and provides a mathematical framework to design optimal service migration policies. In order to overcome the complexity associated with computing the optimal policy, we approximate the underlying state space by the distance between the user and service locations. We show that the resulting MDP is exact for uniform one-dimensional mobility while it provides a close approximation for uniform two-dimensional mobility with a constant additive error term. We also propose a new algorithm and a numerical technique for computing the optimal solution which is significantly faster in computation than traditional methods based on value or policy iteration. We illustrate the effectiveness of our approach by simulation using real-world mobility traces of taxis in San Francisco. <s> BIB004 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> Mobile micro-clouds (MMCs), which are small cloud-like infrastructures that can host services for mobile users, provide a promising approach to deliver data and computation to users in low bandwidth/high latency networks. In this work, we take a step towards security-aware service migration for multiple servers for MMC in tactical environments. As a fundamental model, we consider two users sharing a cluster of MMCs and moving between coverage areas of different MMCs according to random walk. We formulate the problem using a finite horizon Markov Decision Process (MDP). Due to the coupling between users due to security (and possibly interference) costs, we observe that the problem is significantly more complex compared with the non-security-aware single user service migration problem studied in the literature, even in the simplest case of two users. Accordingly, we consider efficient control algorithms which aim to minimize time average costs. Particularly, we propose a modified myopic policy which aims to reduce time average costs by steering operation towards settings which would reduce the likelihood of future security cost increases, by proactively keeping the services distant. Our numerical results demonstrate that our modified myopic policy outperforms other policies in terms of average cost for various settings. <s> BIB005 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> Edge-clouds provide a promising new approach to significantly reduce network operational costs by moving computation closer to the edge. A key challenge in such systems is to decide where and when services should be migrated in response to user mobility and demand variation. The objective is to optimize operational costs while providing rigorous performance guarantees. In this paper, we model this as a sequential decision making Markov Decision Problem (MDP). However, departing from traditional solution methods (such as dynamic programming) that require extensive statistical knowledge and are computationally prohibitive, we develop a novel alternate methodology. First, we establish an interesting decoupling property of the MDP that reduces it to two independent MDPs on disjoint state spaces. Then, using the technique of Lyapunov optimization over renewals, we design an online control algorithm for the decoupled problem that is provably cost-optimal. This algorithm does not require any statistical knowledge of the system parameters and can be implemented efficiently. We validate the performance of our algorithm using extensive trace-driven simulations. Our overall approach is general and can be applied to other MDPs that possess a similar decoupling property. <s> BIB006 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> Edge cloud computing moves cloud services to the edge of the network, thereby allowing clients to access services with a significantly reduced network delay. This service migration is intended to enable a range of latency sensitive mobile applications. In this paper, we propose to manage user QoS by actively migrating services to different edge clouds in response to degraded server or network performance. Previous studies have proposed a distance-based Markov Decision Process (MDP) for optimizing migration decisions. These models provide the feasibility of applying MDP to edge cloud service migration decisions. However, these models fail to consider dynamic network and server states in migration decisions. In this work, we address these limitations by designing a comprehensive edge cloud migration decision system, which we call SEGUE. SEGUE achieves optimal migration decisions by providing a long-term optimal QoS to mobile users in the presence of link quality and server load variation. The basis of SEGUE is in its QoS-aware service migration and its state based MDP model which effectively incorporates the two dominant factors in making migration decisions: 1) network state, and 2) server state. An evaluation of SEGUE performance is given through an augmented reality application. Our results demonstrate that SEGUE reduces the response time of this application by 27.21% and 53.70% compared to the lowest load migration model and the least hop migration model, respectively. <s> BIB007 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> With the popularity of Massively Multiplayer Online Games (MMOGs) and Virtual Reality (VR) technologies, VR-MMOGs are developing quickly, demanding ever faster gaming interactions and image rendering. In this paper, we identify three main challenges of VR-MMOGs: (1)a stringent latency requirement for frequent local view change responses, (2) a high bandwidth requirement for constant refreshing, and (3)a large scale requirement for a large number of simultaneous players. Understanding that a cloud-centric gaming architecture may struggle to deliver the latency/bandwidth requirements, the game development community is attempting to leverage edge cloud computing. However, one problem remains unsolved: how to distribute the work among the user device, the edge clouds, and the center cloud to meet all three requirements especially when users are mobile. In this paper, we propose a hybrid gaming architecture that achieves clever work distribution. It places local view change updates on edge clouds for immediate responses, frame rendering on edge clouds for high bandwidth, and global game state updates on the center cloud for user scalability. In addition, we propose an efficient service placement algorithm based on a Markov decision process. This algorithm dynamically places a user's gaming service on edge clouds while the user moves through different access points. It also co-places multiple users to facilitate game world sharing and reduce the overall migration overhead. We derive optimal solutions and devise efficient heuristic approaches. We also study different algorithm implementations to speed up the runtime. Through detailed simulation studies, we validate our placement algorithms and also show that our architecture has the potential to meet all three requirements of VR-MMOGs. <s> BIB008 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> Envisioned low-latency services in 5G, like automated driving, will rely mainly on Multi-access Edge Computing (MEC) to reduce the distance, and hence latency, between users and the remote applications. MEC hosts will be deployed close to mobile base stations, constituting a highly distributed computing platform. However, user mobility may raise the need to migrate a MEC application among MEC hosts to ensure always connecting users to the optimal server, in terms of geographical proximity, Quality of Service (QoS), etc. However, service migration may introduce: (i) latency for users due to the downtime duration; (ii) cost for the network operator as it consumes bandwidth to migrate services. One solution could be the use of service replication, which pro-actively replicates the service to avoid service migration and ensure low latency access. Service replication induces cost in terms of storage, though, requiring a careful study on the number of service to replicate and distribute in MEC. In this paper, we propose to compare service migration and service replication via an analytical model. The proposed model captures the relation between user mobility and service duration on service replication as well as service migration costs. The obtained results allow to propose recommendations between using service migration or service replication according to user mobility and the number of replicates to use for two types of service. <s> BIB009 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> The trend towards the cloudification of the 3GPP LTE mobile network architecture and the emergence of federated cloud infrastructures call for alternative service delivery strategies for improved user experience and efficient resource utilization. We propose Follow-Me Cloud (FMC), a design tailored to this environment, but with a broader applicability, which allows mobile users to always be connected via the optimal data anchor and mobility gateways, while cloud-based services follow them and are delivered via the optimal service point inside the cloud infrastructure. Follow-Me Cloud applies a Markov-decision-process-based algorithm for cost-effective performance-optimized service migration decisions, while two alternative schemes to ensure service continuity and disruption-free operation are proposed, based on either software defined networking technologies or the locator/identifier separation protocol. Numerical results from our analytic model for follow-me cloud, as well as testbed experiments with the two alternative follow-me cloud implementations we have developed, demonstrate quantitatively and qualitatively the advantages it can bring about. <s> BIB010 </s> A Survey on Mobility-Induced Service Migration in the Fog, Edge, and Related Computing Paradigms <s> Cost-Related Tradeoffs. <s> Fog Computing (FC) is a flexible architecture to support distributed domain-specific applications with cloud-like quality of service. However, current FC still lacks the mobility support mechanism when facing many mobile users with diversified application quality requirements. Such mobility support mechanism can be critical such as in the industrial internet where human, products, and devices are moveable. To fill in such gaps, in this paper we propose novel container migration algorithms and architecture to support mobility tasks with various application requirements. Our algorithms are realized from three aspects: 1) We consider mobile application tasks can be hosted in a container of a corresponding fog node that can be migrated, taking the communication delay and computational power consumption into consideration; 2) We further model such container migration strategy as multiple dimensional Markov Decision Process (MDP) spaces. To effectively reduce the large MDP spaces, efficient deep reinforcement learning algorithms are devised to achieve fast decision-making and 3) We implement the model and algorithms as a container migration prototype system and test its feasibility and performance. Extensive experiments show that our strategy outperforms the existing baseline approaches 2.9, 48.5 and 58.4 percent on average in terms of delay, power consumption, and migration cost, respectively. <s> BIB011
Whenever a migration decision has to be taken, a tradeoff has to be made between the potential benefit that would result from migrating a service (e.g., QoS improvement) and the cost that may be incurred from doing so. Alternatively, the tradeoff may deal with the assessment of the impact of different types of costs on the performance. To address and model these tradeoffs, different approaches have been taken, including the use of Markov MDP. Markov Decision Processes constitute one of the most used approaches to model the migration tradeoff. In this model, a decision maker in a given state is presented with a set of possible actions it can take (e.g., to migrate or not to migrate), each leading to an immediate reward (alternatively, penalty/cost). Consequently, it has to decide which action to take in order to maximize its reward (alternatively, minimize the penalty/cost) on the long term. Value iteration and policy iteration are the most used approaches to solve the MDP. However, more recently, efforts are instead shifting toward solving the MDP problem using (deep) Q-learning approaches, which do not require prior knowledge about the MDP environment dynamics. Initial contributions where MDPs have been used for service migration can be found in the context of the Follow-me Cloud in its non-edge-centric version BIB002 BIB001 . However, the authors' subsequent work BIB010 extends this to the case where micro data centers are deployed at the edge and propose an MDP-based algorithm that is able to capture the tradeoff between the migration cost and the user experience. As shown in the simulation results, the algorithm performs fewer service migrations when the migration cost is non-negligible compared to the expected quality. Similarly, the authors in BIB003 model the problem of service migration in mobile micro-clouds (MMCs) as an MDP and derive a modified version of the policy iteration algorithm to obtain the optimal actions to take depending on the distance between the user and its serving MMC. Simulation results show that the proposed algorithm has a low complexity and that it is able to perform migrations when the transmission cost from the previous micro-cloud is high and avoid them otherwise. In BIB004 , the authors go beyond the contributions in BIB003 by additionally considering general cost models and 2D user mobility, as well as using real-world mobility traces for evaluation purposes. Instead of considering only the usual transmission and migration costs, an additional security (i.e., inter-user interference) cost is introduced in BIB005 . This cost models the risks related to keeping services belonging to different users running in the same/nearby MMCs. Therefore, with an overall objective of reducing the time average costs, the proposed migration policy proactively keeps the services from different users in distant MMCs to reduce future security cost increases. Numerical results show that this policy achieves the lowest-sum costs compared to "always migrate," "never migrate," and a "myopic" policy. In contrast, in BIB008 , the authors propose to co-place multiple users of a Virtual RealityMassively Multiplayer Online Game (VR-MMOG) at the same edge cloud to facilitate sharing their "game worlds" and therefore reduce the migration overhead. Given the complexity inherent to making joint migration decisions rather than per-player decisions, a "Highest Migrate Probability First" heuristic is proposed, where players are ordered according to their migration probabilities. Migration decisions are therefore performed following the obtained players' order. It is shown that the proposed heuristic performs close to the optimal cost. Instead of solving the MDP problem using complex dynamic programming solutions that require statistical knowledge, the authors in BIB006 leverage Lyapunov optimization to design online algorithms, where prior knowledge about the MDP states is not required. Trace-based simulations prove that the proposed Lyapunov-based algorithm achieves a good tradeoff between the average delay and the cost. Observing that in previous MDP-based studies, migration decisions do not take into account network and server states, the authors in BIB007 propose an MDP-based QoS-aware service migration where such states are considered. The MDP model's reward function assesses the difference between the incurred downtime and the potential QoS improvement for the user. The implementation of an AR application on the "Open-Access Research Testbed for Next-Generation Wireless Networks (ORBIT)" along with the use of real-world mobility traces shows a reduction in the response time of this scheme compared to the "lowest load" and the "least hop" migration schemes. Finally, in BIB011 , the problem of container migration in fog computing is modeled as a large-scale MDP. Deep reinforcement learning algorithms are designed to reduce the large MDP spaces and achieve faster decision making. The authors conduct trace-based experiments that confirm the algorithms' ability to obtain reduced delays, power consumption, and migration costs. Markov Chains. The authors in BIB009 consider proactive service replication as an alternative to avoid migration-incurred costs (in terms of both downtime and bandwidth consumption). Since service replication also comes with a storage cost, the authors analytically compare the cost incurred by both approaches, taking users' mobility and service duration into account. Results show that for a short-duration service, replication is preferred. On the other hand, migration would be preferred for longer services, since, given their size, they are likely to cause a higher service replication cost.