TL;DR
This paper introduces PRIMAL, a novel strategy for optimizing the placement of "Avatars" (software clones of users) in mobile edge computing (MEC) networks. PRIMAL aims to maximize profit by intelligently balancing the benefits of reduced latency from Avatar migration against the costs incurred by the migration process itself, outperforming existing strategies.
What Problem Does This Paper Address?
Modern mobile applications, like augmented reality and real-time data analysis, are computationally intensive and can quickly drain user device batteries. Mobile Cloud Computing (MCC) offers a solution by offloading these tasks to the cloud. However, the significant latency introduced by communicating with distant data centers can make this approach impractical for many time-sensitive applications.
Cloudlets, which are small, localized data centers, have emerged as a solution to bring computing resources closer to users, thereby reducing end-to-end (E2E) delay. In this context, each user (UE) is represented by an "Avatar" – a virtual machine running in a cloudlet. The challenge arises because users are mobile. If an Avatar remains static in a cloudlet, the user might move away, leading to increased E2E delay, negating the benefits of the cloudlet. Live Avatar migration allows Avatars to move to more suitable cloudlets to maintain low latency. However, this migration process is resource-intensive and incurs costs that can degrade application performance. Therefore, the core problem is to find an optimal strategy for placing and migrating Avatars that maximizes the overall "profit," defined as the gain from reduced latency minus the cost of migration.
Methods
The paper proposes the PRofIt Maximization Avatar pLacement (PRIMAL) strategy. PRIMAL models the problem as an optimization task to maximize the total profit from Avatar migrations.
Key methodological components include:
- Live Avatar Migration Gain Model: This model quantizes the benefit of migrating an Avatar. The gain is primarily defined as the reduction in the "core delay" (delay between a UE's base station and its cloudlet), as changes in access delay and intra-cloudlet delay are considered less significant.
- Live Avatar Migration Cost Model: This model quantifies the expense of migration. The cost is proportional to the total migration time, which is calculated based on the Avatar's memory size, bandwidth provisioning, and the rate at which memory pages are "dirtied" during the migration process. The paper details the pre-copy live migration procedure and derives formulas for total migration time.
- Cost Coefficient ($k_i$): The cost coefficient is made Avatar-specific, reflecting that migration can have a differential impact on applications with varying resource utilization (e.g., I/O-intensive applications are more affected). This coefficient is modeled as proportional to the weighted sum of resource utilization (bandwidth, memory, disk I/O, CPU).
- PRIMAL Formulation: The problem is formulated as a Mixed-Integer Quadratic Programming (MIQP) problem. The objective is to maximize the sum of individual Avatar profits ($f_i = r_i - c_i$, where $r_i$ is gain and $c_i$ is cost). Constraints include ensuring each Avatar is in exactly one cloudlet and respecting the capacity limits of each cloudlet. The paper proves that the PRIMAL problem is NP-hard.
Datasets
The paper uses a simulated network environment. For emulating resource utilization of Avatars, they apply the Google cluster data trace [21]. Specifically, they use machines with 0.5 normalized CPU and memory capacity from this trace. Bandwidth demand is emulated as a stochastic process following a normal distribution.
Key Insights and Ideas
- Profit Maximization as a Tradeoff: The central idea is that simply minimizing latency (like the "Follow Me Avatar" strategy) or minimizing migration cost (like the "Static" strategy) is suboptimal. True optimization lies in finding the sweet spot between migration gain and migration cost.
- Avatar-Specific Migration Costs: Recognizing that migration impacts different applications differently is crucial. Modeling the cost coefficient ($k_i$) based on an Avatar's resource utilization allows for more nuanced decision-making.
- The Role of $\alpha$: The penalty coefficient $\alpha$ acts as a critical knob to tune the system's behavior. A low $\alpha$ prioritizes RTT reduction, leading to more migrations, while a high $\alpha$ discourages migrations to avoid costs, effectively favoring static placements. This allows for dynamic adjustment of the RTT vs. migration cost tradeoff.
- PRIMAL's Selectivity: PRIMAL doesn't just migrate; it selectively migrates Avatars that offer significant RTT improvement with manageable migration time, avoiding "worthless" migrations.
Key Results
- Highest Profit: PRIMAL consistently achieves the highest profit compared to the "Follow Me Avatar" (FAR) and "Static" strategies across simulations.
- Reduced Migration Cost: PRIMAL incurs significantly less migration cost than the FAR strategy, contributing to its higher profit.
- Similar RTT to FAR: PRIMAL achieves comparable average Round Trip Time (RTT) to the FAR strategy, which solely focuses on minimizing RTT. This indicates PRIMAL effectively reduces latency without the excessive migration overhead of FAR.
- Reduced Migrations and Time: PRIMAL leads to a lower average number of migrations and a shorter average migration time compared to FAR.
- Impact of $\alpha$: As $\alpha$ increases, PRIMAL's profit gap with FAR widens (as PRIMAL becomes more cost-aware), while the gap with Static narrows (as PRIMAL favors static placements more). The study shows clear tradeoffs between average RTT, number of migrations, and migration time, all adjustable via $\alpha$.
Limitations and Future Work
- NP-Hardness: The PRIMAL problem is proven to be NP-hard, meaning finding an optimal solution for large-scale networks can be computationally intractable. The paper uses a Mixed-Integer Quadratic Programming (MIQP) solver for heuristic solutions.
- Homogeneous Avatars Assumption: The formulation assumes Avatars are homogeneous in terms of hardware configuration.
- Limited Cloudlet Capacity: The formulation considers limited cloudlet capacity, but the proof of NP-hardness simplifies this to a capacity of one for demonstration.
- Future Work: The paper suggests that the parameter $\alpha$ can be chosen via experiments by testing users' Quality of Experience (QoE). Further research could explore more sophisticated optimization techniques for the NP-hard problem and investigate dynamic adjustments of $\alpha$ based on network conditions or user demands.
Summary updated