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

Shiqiang Wang; Rahul Urgaonkar; Ting He; Kevin Chan; Murtaza Zafer; Kin K. Leung

Source-linked AI summary

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

Shiqiang Wang, Rahul Urgaonkar, Ting He, Kevin Chan, Murtaza Zafer, Kin K. Leung

arXiv:1503.02735v2Mar 9, 2015cs.DCcs.NImath.OC

TL;DR

Dynamic service placement in mobile micro-clouds must handle mobility, changing network conditions, and uncertain future costs. The paper combines offline dynamic programming, an online polynomial-time approximation, and look-ahead-window selection; analysis and simulations support the approach, including on San Francisco taxi traces.

Problem
The paper studies how to place multiple service instances in mobile micro-clouds as users, network conditions, and future costs change.
Method
It models placement over predicted-cost look-ahead windows, solves offline configurations by dynamic programming, and uses an online approximation algorithm when instances arrive.
Results
The online algorithm is O(1)-competitive for certain cost functions, and simulations use synthetic arrivals and San Francisco taxi mobility traces.
Takeaways & Limitations
The framework can potentially extend to broader online resource-allocation problems with convex objective functions.
Takeaways & Limitations
The look-ahead-window bound depends on Γ and σ, whose exact values may be difficult to determine and may require tuning in practice.

Abstract

from arXiv · show

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 $O(1)$-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.

1 INTRODUCTION

The paper addresses dynamic service placement in mobile micro-clouds, where user mobility, changing network conditions, arrivals, departures, and migration costs complicate choosing instance locations. It develops offline and online approaches that use bounded-accuracy predictions to optimize average cost over time.

Motivation: Mobile micro-clouds place computation near users, but user mobility and changing edge conditions make service-instance location decisions dynamic.The paper positions MMCs as edge-connected clouds supporting applications requiring high reliability or processing capability.
Problem: Placement must choose where each service instance runs and whether to migrate it as users or network conditions change.Both running an instance and moving it between clouds incur costs that the placement decision must account for.
Research gap: Existing placement work largely assumes static network conditions, while mobility-driven migration studies often rely on Markovian mobility models.The paper identifies insufficient treatment of dynamically changing resource availability linked to user mobility in MMC environments.
Evaluation: Simulations evaluate the approach using synthetic arrivals and real-world San Francisco taxi mobility traces, including comparisons with alternative placement and migration policies.The proposed approach performs close to online placement with precise future knowledge and outperforms the listed alternatives in the reported real-world-trace results.
Approach: The paper assumes future cost parameters can be predicted with known accuracy and formulates placement as minimizing average cost over time.Predictions may incorporate user locations and preferences, system load, and database locations.
Contributions: The offline problem becomes a shortest-path problem solved by dynamic programming, while the online algorithm places arriving instances in polynomial time and is O(1)-competitive for certain cost functions.The online method calls the offline dynamic-programming algorithm as a subroutine for each arriving instance.

2 PROBLEM FORMULATION

The paper formulates dynamic service placement for mobile micro-clouds as minimizing long-run average cost under changing user, network, and instance conditions. It represents placements across time with configuration matrices, separates local and migration costs, and uses predicted future costs within look-ahead windows.

2 PROBLEM FORMULATION: The system comprises mobile micro-clouds and a backend cloud that host service instances arriving and departing over time.
2 PROBLEM FORMULATION: A service instance may serve one or more users, while users can move across geographical areas and trigger placement or migration decisions.
2 PROBLEM FORMULATION: Every T slots, the controller predicts costs and computes a configuration for the next T-slot look-ahead window.
2.1.2 Service Configurations: A Q-by-M configuration matrix records each instance's cloud location in each slot, using 0 for instances that are not running.
2.1.3 Costs: The cost framework includes local transmission and processing costs, initial placement costs, and migration costs between consecutive slots.
2.2 Actual and Predicted Costs: Actual costs A_π(t) are distinguished from predicted costs D^t0_π(t), with prediction error bounded by a non-decreasing function ϵ(τ) for future horizons.
2.3 Our Goal: The objective is to find a configuration π* minimizing actual average cost over a sufficiently long time.
2.3 Our Goal: Because future costs and instance arrivals or departures are not precisely known, the paper seeks an approximate solution using predicted cost values collected every T slots.

3 OFFLINE SERVICE PLACEMENT WITH GIVEN LOOK-AHEAD WINDOW SIZE

Given a look-ahead window and exact future instance arrivals and departures within it, the offline method minimizes predicted cost by solving a shortest-path problem over possible configurations. Dynamic programming implements the solution and returns the optimal window configuration.

3 OFFLINE SERVICE PLACEMENT WITH GIVEN LOOK-AHEAD WINDOW SIZE: The offline placement problem assumes exact knowledge of future instance arrival and departure times within the look-ahead window.
3.1 Procedure: For each window of T slots, the method solves an optimization problem using predicted costs and the preceding slot's configuration.
3.1 Procedure: The algorithm computes placements for the next T slots but needs only the current-slot placement for practical operation.
3.2 Shortest-Path Formulation: The optimization is equivalent to a shortest-path problem whose edges represent adjacent-slot configuration transitions weighted by predicted costs.
3.3 Algorithm: Dynamic programming solves the shortest-path problem by iteratively applying Bellman's equation to possible configurations and storing optimal predecessor paths.
3.3 Algorithm: The final minimum over last-level paths satisfies Bellman's principle of optimality and therefore yields the optimal solution.
3.4 Complexity: The algorithm's time complexity is determined by enumerating at most KM configurations per transition across at most KMT time-configuration combinations.

4 COMPLEXITY REDUCTION AND ONLINE SERVICE PLACEMENT

The offline placement problem is NP-hard, motivating a greedy online algorithm that places instances as they arrive while updating configurations for departures. The algorithm has polynomial complexity and is O(1)-competitive for broad cost functions, with optimality for linear costs.

Online placement: The online algorithm places instances one-by-one by greedily minimizing the placement objective while leaving prior configurations unchanged.
Online placement: For an arriving instance, the algorithm optimizes only its configuration over its assumed remaining lifetime, with complexity O(K^2T).
Online placement: When an instance departs unpredictably, its future configuration is set to zero, and the online configuration is updated upon arrivals and departures.
Complexity: Placing M instances within one window has complexity O(K^2TM), making the online procedure polynomial while the offline algorithm is exponential.
Complexity: The offline placement problem is NP-hard when the number of instances is non-constant.
Performance analysis: For linear cost functions, the greedy online placement is optimal because prior placements do not affect later placement costs.
Performance analysis: The online algorithm is O(1)-competitive, and its competitive ratio approaches a constant as the number of instances grows.

5 OPTIMAL LOOK-AHEAD WINDOW SIZE

The look-ahead window balances prediction error against the loss from truncating long-term effects. The paper minimizes an upper bound on actual cost and uses convexity-based discrete search, including binary search, to select the window size.

Window-size trade-off: Larger windows can improve long-term performance without prediction error but become less accurate as prediction errors accumulate farther into the future.
Window-size trade-off: Smaller windows reduce foresight and may neglect long-term migration effects, so the optimal window balances prediction error with look-ahead truncation.
Error analysis: The sum-error function F(T) is convex and non-decreasing when per-slot prediction error is nonnegative and non-decreasing over time.
Window optimization: Proposition 5 gives an upper bound on the cost difference between the predicted configuration and the optimal configuration while accounting for competitive ratio Γ.
Window optimization: The optimal window minimizes this upper bound under the assumption that Γ is independent of the window size.
Window optimization: For an analytical continuous extension G(T), the optimal discrete window is either floor(T0) or ceiling(T0) when a solution T0 exists.
Search procedure: Binary search compares θ(T) and θ(T+1) over a bounded discrete range and finds the optimal window in O(log Tm) time.

6 SIMULATION RESULTS

Simulations evaluate synthetic arrivals and departures, then real-world San Francisco taxi mobility, including heterogeneous costs, prediction errors, and alternative placement policies.

Simulation setup: The simulation models a backend cloud and multiple MMCs, with service instances placed on either cloud type.Local and migration costs incorporate resource consumption, user-to-instance distance, cloud distance, and migrated-instance counts.
6.1 Synthetic Arrivals and Departures: The synthetic-trace objective increases convexly for few instances and linearly at larger loads as MMCs approach overload and more instances use the backend cloud.The average performance ratio converges as the number of instances increases, supporting the analysis.
6.2 Real-World Traces: Real-world experiments use San Francisco taxi traces and evaluate prediction errors together with different look-ahead window sizes.The traces come from May 31, 2008, with MMCs arranged in a hexagonal cellular structure.
6.2 Real-World Traces: With β = 0.4, proposed method E performs close to precise-future online placement D and outperforms MMC-only, always-migrate, and backend-only policies.Daily cost fluctuations reflect changes in the number of users requiring the service and therefore system load.

7 CONCLUSIONS

The paper develops offline and online placement algorithms for mobile micro-clouds with predictable future costs and evaluates them analytically and through synthetic and real-world traces.

Contributions: The study addresses dynamic service placement for multiple service instances when future costs are predictable within known accuracy.The setting supports heterogeneous cost values, network structures, and mobility models.
Contributions: The proposed work includes offline and online placement algorithms plus a method for selecting the optimal look-ahead window size.The evaluation combines analytical results with synthetic arrivals and departures and San Francisco taxi mobility traces.
Scope: The algorithms are applicable whenever costs can be assigned to every possible configuration, while the online optimality-gap analysis covers a narrower but still general function class.The scope of the optimality analysis is therefore narrower than the scope of algorithm applicability.
Extensions: The theoretical framework can extend to multiple resource types and to a broad class of online resource-allocation problems with convex objective functions.The paper presents this extension as a potential application of its analytical framework.

APPENDIX A SUMMARY OF NOTATIONS

Appendix A points readers to Table 1 for the paper’s main notation.

Table 1 summarizes the main notations used throughout the paper.

APPENDIX B PROOF OF PROPOSITION 1

The appendix proves Proposition 1 by reducing a placement optimization problem from the partition problem through a two-bin packing construction.

Reduction: The partition problem asks whether positive integers can be divided into two subsets with equal sums.
Reduction: A bin-packing decision problem with M items and two unit-capacity bins is constructed as an equivalent formulation.
Construction: The reduction sets a single timeslot, two clouds, zero migration cost, and allows every item to be placed in either cloud.
Construction: The constructed cost function assigns a low cost when bin capacity is respected and a larger penalty when a bin exceeds capacity.
Conclusion: Because the placement problem distinguishes feasible from infeasible packing through its objective threshold, solving it would solve partition and therefore proves NP-hardness.

APPENDIX C PROOF OF PROPOSITION 2

The proof of Proposition 2 develops truncated placement vectors and lemmas to relate incremental placement costs to the convex cost function. These relationships establish the proposition’s stated bounds and identities.

Iterative proof setup: The proof uses lemmas concerning configuration sequences, departures, and the increase in sum cost when service instance j is placed.Departed instances contribute zero increments, while the placement increment is evaluated at arrival.
Iterative proof setup: The proof introduces x^j, y^j, and z^j to represent placements through instance j while ignoring later instances.The full vectors correspond to the latest arrived instance M.
Convexity and incremental bounds: Convexity and monotonicity of e_D(y,z), together with bounds on incremental vectors, support the key inequalities used in Proposition 2.The argument applies first-order conditions and the greedy assignment in Algorithm 3.
Convexity and incremental bounds: The proof relates ∇_x e_D(x) · x to ∇_{y,z} e_D(y,z) · (y,z) through the definitions of the vectors and Lemma 2.It also uses that e_D(x)=e_D(y,z) and x=x^M, y=y^M, z=z^M.
Conclusion: Applying the lemmas and convex first-order conditions yields equation (9), while linearity of y^{k,j}(t) and z^{kl,j}(t) in x_iλ yields equation (10).The proof explicitly identifies the final equality for equation (9) as following from Lemma 4.

PROOF OF PROPOSITION 4

The proof of Proposition 4 bounds the competitive ratio for polynomial cost functions using asymptotic growth, bounded instance departures, and derivative comparisons. It concludes that the ratio is constant in M.

Asymptotic polynomial bounds: Lemma 6 provides asymptotic bounds for polynomial cost functions under the forms specified in equations (15) and (16).The bounds hold for sufficiently large y, y_k, y_l, and z_kl, with arbitrary δ>0 and B≥0.
Asymptotic polynomial bounds: The proof introduces q and positive scaling constants ζ_1, ζ_2, and ζ_3 to represent arbitrary positive triples (y_k,y_l,z_kl).This transforms the multivariate analysis into a one-variable asymptotic argument.
Departure and derivative control: Combining the lemmas establishes bounds (51)–(54), while bounded unpredictable departures limit the gap between maximum and current vectors.With at most Bd departures per slot over T slots, a constant B bounds this gap.
Competitive-ratio conclusion: Γ=O(1) because Ω and δ′ are constants in M.The proof first establishes the bound for sufficiently large M, then invokes the definition of big-O notation.

APPENDIX E PROOF OF PROPOSITION 5

The proof of Proposition 5 compares predicted and actual costs over look-ahead windows. It first removes initial migration costs to relate windowwise solutions, then restores those costs and averages the resulting bounds.

Window decomposition: The proof partitions timeslots into full look-ahead windows of size T and a possibly shorter final window.The construction is considered through an arbitrarily large timeslot index T_max.
Prediction-error comparison: For the true optimal and prediction-based configurations, the difference between predicted and actual sum-costs is bounded using ε(τ) and F(T).The proof applies the same prediction-error relationship to both configurations.
Migration-cost adjustment: When migration costs at each window’s first slot are neglected, independently optimized predicted-cost windows form a Γ-approximation over all timeslots.The independence follows because there is no connection between different windows under this assumption.
Migration-cost adjustment: Restoring first-slot migration costs adds a bounded contribution because the migration cost in each window cannot exceed σ.The bound is based on the configuration in the preceding slot and the number of windows.
Conclusion: Summing the resulting inequalities, dividing by T_max, and taking the limit yields Proposition 5.The proof combines equations (79) and (81) after multiplying equation (78) by Γ.

APPENDIX F PROOF OF PROPOSITION 6 AND COROLLARY 1

The proof of Proposition 6 and Corollary 1 analyzes the bound’s dependence on the look-ahead window T through a monotone auxiliary function. It shows that the minimum is attained in the interval where that function crosses zero.

Optimal-window characterization: Convexity of G(T) implies that Φ(T) is non-decreasing, so equation (23) can hold on at most one consecutive interval [T−,T+].A selected solution T_0 lies within this interval.
Optimal-window characterization: For T<T−, the derivative of ln θ(T) is negative, while for T>T+, it is positive.The signs follow from the relationship between Φ(T) and the derivative in equations (22) and (23).
Optimal-window characterization: θ(T) therefore decreases until the optimal interval and increases afterward, placing its minimum at some T∈[T−,T+].Because T* is discrete, any T_0 in the interval completes the proof’s selection argument.
Corollary: The corollary follows without requiring convexity of θ(T).The proof explicitly notes that the preceding analysis does not assume this convexity.

APPENDIX G ADDITIONAL SIMULATION RESULTS

The appendix evaluates the computational overhead of approaches D and E for computing next-T-slot service configurations. The proposed approach E achieves short average runtime, with lower distributional statistics than D despite slightly higher aggregate work.

Computational-overhead evaluation: The evaluation measures computation time and FLOP count for each next-T-slot configuration computed by approaches D and E.Figure 7 presents cumulative distributions, while Table 2 reports sums, means, standard deviations, and maxima.
Runtime: Approach E finds a configuration in 1.84 s on average, which is short relative to the 60 s physical duration of each timeslot.Configurations covering multiple timeslots are usually obtained in one execution.
Implementation considerations: The reported MATLAB runtime is pessimistic because the implementation is not performance-optimized; the average FLOP count is 6.08 × 10^6.The authors expect faster execution with optimized code such as C.
Implementation considerations: Parallelization and GPU execution are identified as further ways to expedite configuration computation.The authors point to parallelizable “for all” loops in Algorithm 2.
Comparison with precise future knowledge: Approach E has lower mean, standard deviation, and maximum computation-time and FLOP-count values than approach D.Its optimal look-ahead window is usually much shorter than the instance’s full active duration, reducing optimization complexity.
Comparison with precise future knowledge: Approach E has similar but slightly larger total computation time and FLOP count than approach D.The aggregate comparison differs from the mean, standard deviation, and maximum statistics.