Source-linked AI summary
Online Placement of Multi-Component Applications in Edge Computing Environments
Shiqiang Wang, Murtaza Zafer, Kin K. Leung
TL;DR
The paper addresses where to place application components across devices, MECs, and centralized clouds when resource and communication constraints make placement difficult. It models applications and infrastructure as annotated graphs, solves linear placement optimally, and builds online approximation algorithms for tree placement. The resulting algorithms provide polynomial-logarithmic competitive guarantees under stated tree and junction-node conditions.
Problem
Application placement across devices, MECs, and core clouds is difficult because MECs have lower capacity and existing heuristics may lack performance guarantees.
Method
The paper models applications and infrastructures as resource-annotated graphs, solves linear placement exactly, and generalizes the result to online tree placement.
Results
The proposed tree-placement algorithms achieve poly-log worst-case optimality bounds, with polynomial time and space complexity when unplaced junction nodes per root-to-leaf path are bounded by a constant.
Takeaways & Limitations
The method provides provable online performance for MEC application placement while jointly considering node and link resource utilization.
Takeaways & Limitations
The paper focuses on tree-to-tree placements and suggests extensions only when a limited number of cycle-free paths can be found between unplaced junction nodes.
Abstract
from arXiv · showhide
Mobile edge computing is a new cloud computing paradigm which makes use of small-sized edge-clouds to provide real-time services to users. These mobile edge-clouds (MECs) are located in close proximity to users, thus enabling users to seamlessly access applications running on MECs. Due to the co-existence of the core (centralized) cloud, users, and one or multiple layers of MECs, an important problem is to decide where (on which computational entity) to place different components of an application. This problem, known as the application or workload placement problem, is notoriously hard, and therefore, heuristic algorithms without performance guarantees are generally employed in common practice, which may unknowingly suffer from poor performance as compared to the optimal solution. In this paper, we address the application placement problem and focus on developing algorithms with provable performance bounds. We model the user application as an application graph and the physical computing system as a physical graph, with resource demands/availabilities annotated on these graphs. We first consider the placement of a linear application graph and propose an algorithm for finding its optimal solution. Using this result, we then generalize the formulation and obtain online approximation algorithms with polynomial-logarithmic (poly-log) competitive ratio for tree application graph placement. We jointly consider node and link assignment, and incorporate multiple types of computational resources at nodes.
I. INTRODUCTION
The paper frames online placement of multi-component applications across hierarchical cloud, MEC, and device resources as a difficult optimization problem. It motivates graph-based modeling because placement choices must balance processing, storage, communication, and changing resource conditions.
- Motivation: MECs reduce communication distance but have less processing and storage capacity than centralized clouds, so components must be distributed across devices, MECs, and core clouds.
- Motivating Example: Face recognition illustrates the trade-offs: placing detection near the device can reduce transferred data, whereas limited device capacity may favor MEC placement.
- Motivating Example: Database size and locality can shift the preferred placement of recognition and storage components between the core cloud and MEC.
- Motivation: The problem becomes more complex with multi-component applications, hierarchical MEC layers, and multiple applications arriving over time.
- Problem Abstraction: The paper models applications as graphs of components and communication demands mapped onto physical graphs of computing devices and links.
- Related Work: Prior work often uses heuristics without performance guarantees, while limited online work provides competitive-ratio analysis for both node and link placement.
C. Our Approach
The approach builds non-LP online approximation algorithms for tree-to-tree placement from an exact algorithm for linear application graphs. It uses cycle-free mappings and distinguishes cases with pre-specified and unplaced junction nodes.
- Approach: The authors use an optimal linear-graph placement algorithm as the baseline for more general tree-application placement.
- Approach: The proposed methodology avoids LP relaxation and decomposes placement into small building blocks that may support future distributed implementations.
- Mapping Constraint: Cycle-free mappings preserve application-node order along physical subpaths and avoid circular traffic that can congest communication links.
- Tree Structure: Junction nodes represent data splitting or joining processes and may have pre-specified locations in online deployments.
- Main Results: The paper provides an optimal offline algorithm for linear applications with O(V^3N^2) time and O(VN(V+N)) space complexity.
- Main Results: For tree applications with pre-specified junction placements, the online algorithm has competitive ratio O(log N).
A. Definitions
The formulation represents applications and computing infrastructures as graphs with resource and communication costs. Its load-balancing objective minimizes the maximum weighted utilization across physical nodes and links.
- Graph Definitions: An application graph represents computational modules as nodes and communication demands between modules as edges.
- Graph Definitions: A physical graph represents computing devices and communication links, with multiple resource types at nodes and communication resources on edges.
- Costs: Placement costs encode resource usage, communication bandwidth, and restrictions by assigning prohibited mappings infinite cost.
- Mapping: A mapping assigns application nodes to physical nodes, while the physical paths between assigned nodes determine edge placement.
- Objective: The objective minimizes the maximum weighted cost on any physical node or link to prevent overload concentration.
- Capacity: The formulation omits explicit physical capacity constraints, while resource demands still allow total consumption at each node and link to be calculated.
III. BASIC ASSIGNMENT UNIT: SINGLE LINEAR APPLICATION GRAPH PLACEMENT
For a single linear application graph mapped cycle-free onto a tree physical graph, the paper decomposes placement cost into pairwise transitions and solves the resulting problem by dynamic programming.
- Problem Setup: The linear-placement problem is the foundational assignment unit for the paper’s later tree-placement algorithms.
- Cost Decomposition: Pairwise costs combine edge costs with the cycle-free constraint, assigning infinity when a physical path violates the required ordering.
- Cost Decomposition: The objective decomposition separates costs for earlier application nodes, nodes co-located on one physical node, and their connecting pairwise costs.
- Dynamic Programming: Bellman’s equation enables iterative dynamic programming that computes optimal conditional costs and recovers the final optimal mapping.
- Algorithm: The algorithm maintains cost and mapping matrices while evaluating application and physical node combinations.
C. Optimal Algorithm
The paper presents an exact algorithm for optimal placement under the cycle-free constraint, using an auxiliary graph of possible application-to-physical-node assignments. Its time complexity is O(V^3N^2), while the stated space complexity is O(VN(V + N)).
- Complexity: The algorithm computes V · N values and minimizes over at most V · N candidates, yielding time complexity O(V^3N^2).The complexity treats K as a constant.
- Complexity: The stated space complexity is O(VN(V + N)) for storing matrices D, C, J, and Π.K is also regarded as a constant in this bound.
- Optimality condition: The result is optimal subject to the cycle-free constraint, with application-node order preserved during each iteration.
- Auxiliary-graph formulation: The exact algorithm represents each possible application-node placement as a node in an auxiliary graph with an associated cost.The algorithm computes costs from earlier placement states and selects the minimum among candidate values.
E. Extensions
The paper extends linear-graph placement to tree applications by combining an optimal linear-placement subroutine with online branch-placement procedures. It establishes NP-hardness for tree placement and derives performance guarantees for pre-placed junction nodes.
- Objective-function extensions: Alternative increasing objective functions preserve the linear-placement procedure and support goals beyond min-max optimization.These functions are later used for online placement.
- Complexity: Tree application placement is NP-hard even when junction-node placements are either pre-specified or unrestricted.The result follows by reduction from minimum makespan scheduling on unrelated parallel machines.
- Online decomposition: The online method splits each arriving tree into simple branches and separately places nodes with given placements before placing the branches.Each simple branch is treated as an independent application graph.
- Objective rationale: The alternative objective uses incremental exponential costs to discourage concentration on already expensive nodes and links while also encouraging low aggregate cost.The exponential function is convex and increasing, so high existing costs produce high incremental costs.
- Branch placement: For a simple branch, the method extends it to a linear graph with zero-resource-demand nodes and applies Algorithm 1 using the alternative objective.The procedure checks node and link costs against β ˆJ and returns FAIL when a bound is exceeded.
- Performance guarantee: If an offline mapping has cost at most ˆJ, Algorithm 2 never fails and achieves competitive ratio β when ˆJ equals the optimal offline cost.The resulting node and link costs are bounded by β ˆJ.
2) Complexity and Competitive Ratio:
The high-level online procedure repeatedly places arriving tree applications and doubles its reference cost after failures. For each application, it runs in O(V^3N^2) time and O(VN(V + N)) space, with competitive ratio O(log N).
- Complexity: For each arriving application graph, Algorithm 3 has time complexity O(V^3N^2).Its calls to Algorithms 2 and 1 together cover the application graph's branches and placed-node set.
- Complexity: For each arriving application graph, Algorithm 3 has space complexity O(VN(V + N)).This is the same order as Algorithm 1.
- Competitive ratio: The paper states Algorithm 3's competitive ratio as 4β, with β expressed through log_α in Proposition 4.The displayed proposition is partially truncated in the supplied passage.
- Termination: The doubling procedure has finitely many steps when the optimal offline cost is finite.The paper excludes cases where no placement with finite cost is realizable.
- High-level procedure: Algorithm 3 initializes a reference cost and repeatedly invokes Algorithm 2 for split applications, increasing the reference cost when placement fails.After a successful attempt, the application is mapped according to the resulting placement.
- Competitive ratio: With constant α, γ, and K and L = N − 1 for a tree physical graph, the competitive ratio is O(log N).
C. When at Least One Junction Node Placement Is Not Given
When junction placements are not fully specified, the paper generalizes branches to include unplaced junction nodes. General branches exclude pre-specified nodes while retaining their incident edges and contain simple branches as a special case.
- Problem setting: The method addresses application graphs in which some or all junction-node placements are not given.
- Examples: Figure 6 illustrates general branches with both junction nodes unplaced, one placed and one unplaced, or one placed and two unplaced.
- General branches: A general branch is the largest interconnected subset excluding nodes with pre-specified placements but including edges connected to those nodes.Every simple branch is a general branch, but a general branch need not be simple.
1) Algorithm Design:
The paper develops a recursive tree-to-tree placement algorithm for application graphs with unplaced junction nodes. It enumerates feasible placements when needed, embeds this procedure in an online algorithm, and achieves polynomial time with a poly-log competitive ratio under bounded junction-node depth.
- Algorithm Design:: The algorithm combines Algorithm 2 with enumeration of possible placements for unplaced junction nodes.This remains polynomial when every root-to-leaf path contains only a constant number of such nodes.
- Algorithm Design:: For the illustrative graph, the algorithm determines deeper unplaced nodes first, evaluating node 5 for each possible placement of node 2 before placing node 2.The placement decisions use the cost function in (12) with constraints in (13a) and (13b).
- Algorithm Design:: Independent unplaced nodes need not be enumerated in every combination, because their placements may impose no additional restrictions on one another.In the example, nodes 5 and 6 can be placed subsequently once node 2 is fixed.
- Algorithm Design:: The procedure recursively determines one previously unplaced junction node per Unplaced(v, h) call, starting from the top-most unplaced node with h set to H.H denotes the maximum number of unplaced junction nodes on any root-to-leaf path.
- Algorithm Design:: Algorithm 4 is embedded into Algorithm 3, which handles multiple arriving application graphs and selects Algorithm 2 or Algorithm 4 for each general branch.The modified procedure uses general branches that may contain unplaced junction nodes.
- Algorithm Design:: The combined procedure has per-arrival time complexity O(V^3N^(2+H)), while H is the maximum unplaced-node depth rather than generally the total number of unplaced nodes.The placement routine returns the minimum-cost mapping for the selected junction node.
2) Complexity and Competitive Ratio:
The extended algorithm handles unplaced junction nodes recursively, with complexity and competitive guarantees that grow with the maximum recursion depth H. Simulations compare the proposed method with greedy and Vineyard baselines under synthetic MEC topologies.
- Complexity: O(V 3N 2+H) time complexity results from recursion depth H over unplaced junction nodes.Parallel general branches do not increase recursion depth because they are processed sequentially.
- Complexity: O(V N 1+H(V +N)) space complexity is required per application arrival because recursion stores results for possible junction-node placements.
- Competitive Ratio: Algorithm 4 never fails when an offline mapping has cost at most ˆJ, and its resulting resource costs remain bounded by β1+H ˆJ.
- Competitive Ratio: 4β1+H = 4 log1+H gives Algorithm 4, combined with the extended Algorithm 3, a competitive ratio of O(log1+H N).
- Numerical Evaluation: Simulations compare the proposed algorithm against greedy maximum-utilization placement and the Vineyard load-balancing algorithm.
- Numerical Evaluation: The proposed method outperforms the comparison methods, with larger performance gaps when junction-node placements are not pre-specified.The simulations use synthetic tree application and physical graphs because large-scale real MEC topologies are unavailable.
VI. DISCUSSION
The discussion examines extensions and practical implications of the tree-placement framework, while identifying topology and competitive-ratio questions for future work. The paper concludes that bounded unplaced junction nodes yield polynomial complexity and poly-logarithmic worst-case guarantees, with reasonable average performance in simulation.
- Scope and extensions: The paper focuses on tree-to-tree placements for practical MEC relevance, although its algorithms can also apply to some non-tree graphs.For non-tree applications, junction nodes and cycle-free paths provide the stated route to extension.
- Practical implications: With pre-specified junction placements, placement is easier and the proposed algorithm improves time complexity, space complexity, and competitive ratio relative to.The discussion explicitly contrasts cases with and without unplaced junction nodes.
- Open questions: The tightness of the competitive-ratio bound remains unclear, leaving the best achievable performance guarantee as an open problem.The authors identify this as a difficult direction for future study.
- Theoretical guarantees: A constant maximum number of unplaced junction nodes on any root-to-leaf path gives polynomial time and space complexity with a poly-logarithmic competitive ratio.The conclusion frames this as a worst-case optimality bound for online placement.
- Evaluation: Simulations indicate that the method performs reasonably well on average and remains robust in extreme cases.The evaluation uses synthetic tree application and physical graphs because large-scale real MEC topologies were unavailable.
- Open questions: The framework is presented as an initial step because many formulation constraints can be relaxed for more general problems.The discussion specifically notes that the tree-topology restriction is not absolutely essential in some cases.
APPENDIX A APPROXIMATION RATIO FOR CYCLE-FREE MAPPING
This appendix analyzes the cycle-free restriction for linear application placement, separating link and node costs. Cycle-free mapping is optimal for edge cost, but node-cost approximation can be substantially worse, while allowing cycles is NP-hard.
- Complexity: Allowing cycles makes the line-to-line placement problem NP-hard for the load-balancing objective.The hardness result concerns the objective defined in (3).
- Combined costs: The joint node-and-link approximation ratio is the maximum of the separate node-cost and edge-cost ratios.The appendix establishes tightness when the separate ratios are tight.
- Edge cost: Cycle-free placement on tree physical graphs always has lower or equal maximum edge cost than placement allowing cycles.Thus the restriction is optimal when only edge cost is considered.
- Node cost: A cycle-free line-to-line placement has a tight approximation ratio of 2 when each application node has the same placement cost on every physical node.The bound is approached by ordered instances with arbitrarily large N and arbitrarily small ϵ.
- Node cost: For tree physical graphs, heterogeneous node costs yield an approximation ratio of 2V · max_v d%,v = O(V).The bound reflects the possible gap between minimum and maximum placement costs and the possibility of concentrating application nodes.
- Implications: The cycle-free restriction guarantees optimal link cost but can incur O(V) node-cost approximation in extreme cases.The authors regard the restriction as reasonable where workload splitting must account for total link-resource consumption.
APPENDIX B PROOF OF PROPOSITION 3
The proof establishes a competitive bound by normalizing node and link costs, aggregating resource usage, and comparing each online mapping with a reference offline mapping. A potential function is shown not to increase across requests, yielding the result.
- Normalization: The proof places node and link resources in one framework by treating each resource type as an element and defining aggregated normalized cost.Both aggregated cost and request cost are normalized by the reference cost ˆJ.
- Objective: The objective function is rewritten using the unified element notation, so node and link costs can be handled identically.The text states that the rewritten objective is equivalent to the original objective with its node and link terms.
- Online-offline comparison: The proof compares the online mapping produced by Algorithm 2 with a reference offline mapping for each arriving application.Superscript-o variables denote the offline reference quantities, while unsuperscripted variables come from Algorithm 2.
- Potential-function proof: A potential function is defined from the aggregated offline costs and is shown not to increase as applications arrive.The argument uses the per-request inequalities and chooses α = 1 + 1/γ to obtain the smallest β.
- Conclusion: Taking logarithms of the potential bound and rescaling by ˆJ completes the proof of the stated result.The final step uses z_r(i) = ˜z_r(i) · ˆJ.