Source-linked AI summary
Joint Service Placement and Request Routing in Multi-cell Mobile Edge Computing Networks
Konstantinos Poularakis, Jaime Llorca, Antonia M. Tulino, Ian Taylor, Leandros Tassiulas
TL;DR
The paper addresses joint service placement and request routing in multi-cell MEC networks with storage, computation, and communication constraints, including asymmetric bandwidth needs. It develops a randomized-rounding algorithm and reports close-to-optimal performance, with gains over Greedy and small gaps from LR in evaluated settings.
Problem
Prior MEC studies largely omit service storage and asymmetric bandwidth while addressing execution and request routing, leaving the joint constrained optimization problem insufficiently addressed.
Method
The paper formulates JSPRR and develops a randomized-rounding algorithm for joint placement and routing under multidimensional resource constraints.
Results
Randomized Rounding performs close to LR, gains up to 25% over Greedy as storage reaches Rn = 1250GBs, and improves computation utilization for 8 of 9 BSs.
Takeaways & Limitations
The approach can utilize edge resources to maximize requests served by low-latency BSs while reducing reliance on the centralized cloud.
Abstract
from arXiv · showhide
The proliferation of innovative mobile services such as augmented reality, networked gaming, and autonomous driving has spurred a growing need for low-latency access to computing resources that cannot be met solely by existing centralized cloud systems. Mobile Edge Computing (MEC) is expected to be an effective solution to meet the demand for low-latency services by enabling the execution of computing tasks at the network-periphery, in proximity to end-users. While a number of recent studies have addressed the problem of determining the execution of service tasks and the routing of user requests to corresponding edge servers, the focus has primarily been on the efficient utilization of computing resources, neglecting the fact that non-trivial amounts of data need to be stored to enable service execution, and that many emerging services exhibit asymmetric bandwidth requirements. To fill this gap, we study the joint optimization of service placement and request routing in MEC-enabled multi-cell networks with multidimensional (storage-computation-communication) constraints. We show that this problem generalizes several problems in literature and propose an algorithm that achieves close-to-optimal performance using randomized rounding. Evaluation results demonstrate that our approach can effectively utilize the available resources to maximize the number of requests served by low-latency edge cloud servers.
I. INTRODUCTION
The paper formulates joint service placement and request routing for multi-cell MEC networks, addressing storage, computation, and asymmetric communication constraints to reduce centralized-cloud load.
- MEC places services near users to support latency-sensitive requests, but BS computation capacity may not satisfy all demand.
- Existing approaches largely overlook service data that must be pre-stored at BSs before computation can execute.AR services may require object databases and visual-recognition models at the edge.
- Many services require asymmetric uplink and downlink bandwidth for user inputs and service outputs.
- Overlapping BS coverage creates multiple placement and routing alternatives, requiring joint optimization under storage, computation, and communication constraints.
- JSPRR minimizes centralized-cloud load while routing each request to one nearby BS or the cloud and enforcing placement, storage, computation, and bandwidth constraints.The model uses binary service-placement and request-routing variables; cloud access is a last resort because it may cause high delay.
- The proposed randomized-rounding algorithm provides bounded resource-constraint violations, extends to changing demand profiles, and performs close to optimal in evaluations.The paper also identifies related placement and routing problems as special cases of JSPRR.
III. COMPLEXITY ANALYSIS
JSPRR is computationally difficult because it generalizes knapsack through multiple packing constraints, even under homogeneous service requirements.
- JSPRR is NP-Hard because it generalizes knapsack with multiple packing constraints.
- With unit-sized storage, computation, and bandwidth requirements, the problem still contains several established placement and routing problems as special cases.This supports the model’s broad applicability across related problem classes.
A. Special case 1: Non-overlapping BS coverage regions
With non-overlapping BS coverage, JSPRR decomposes into independent per-BS problems; under additional uncongested-resource assumptions, routing becomes straightforward data placement.
- Special case 1: Non-overlapping BS coverage regions: When BS coverage regions do not overlap, JSPRR decomposes into N independent subproblems, each maximizing requests served by one BS.
- Special case 1: Non-overlapping BS coverage regions: Each BS can optimally place its Rn most locally popular services, then admit requests subject to computation and bandwidth capacities.
- Special case 2: Data placement/caching problem: If computation and bandwidth are non-congestible, the corresponding constraints can be removed without changing the optimum.
- Special case 2: Data placement/caching problem: Under those assumptions, requests route to a nearby BS storing the requested service, or to the cloud otherwise, yielding the data placement or caching problem.
- Special case 2: Data placement/caching problem: Although data placement is NP-Hard, submodularity enables approximation methods including greedy, local search, and pipage rounding.Greedy is described as the simplest and fastest of these methods.
C. Special case 3: Middlebox placement problem
With overlapping coverage, congestible computation and bandwidth, and unit storage per BS, JSPRR reduces to a middlebox placement problem.
- The special case assumes overlapping BS coverage, congestible computation and bandwidth, and unit storage capacity, so each BS stores only one service.
- Each user flow can use a node whose BS covers that user and whose service matches the request, subject to per-middlebox flow limits.
- The reduction creates one network node for each BS-service pair and one flow for each user.It sets m = NS and f = U.
- Selecting N of the NS nodes deploys middleboxes, with at most one selected node for each BS determining its stored service.
- Because the middlebox maximum-flow objective is submodular, approximation algorithms used for data placement can also solve this special case.
D. General case: Non-submodular
In the general JSPRR case, the request-service function is not submodular, because computation or bandwidth congestion can increase the marginal benefit of a placement.
- D. General case: Non-submodular: JSPRR is not generally submodular when coverage overlaps, computation and bandwidth are congestible, and storage capacities are large.The paper constructs counterexamples to the tempting general-form submodularity conjecture.
- D. General case: Non-submodular: The service-placement ground set contains one element for each possible service-base-station placement, and f(E) is the maximum requests satisfiable under placement set E.Every placement policy is represented by a subset E of the ground set.
- D. General case: Non-submodular: For two base stations and two users requesting different services, adding a placement yields a larger marginal performance gain after another placement is already present.With one placement set, the added service still serves one request; with the larger set, it enables both base stations to serve one request each.
- D. General case: Non-submodular: The counterexample uses one-request computation capacities, abundant storage and bandwidth, and users located in overlapping coverage regions.The placement sets are A = {e11} and B = {e11, e21}, with f(A) = f(B) = 1, f(A ∪ {e12}) = 1, and f(B ∪ {e12}) = 2.
- D. General case: Non-submodular: A similar non-submodularity counterexample arises with congestible bandwidth when storage capacity exceeds 1.Thus, the failure is not limited to computation congestion.
E. General case: Approximately-submodular
Although JSPRR is not submodular, the paper places it in the broader approximately submodular class and applies a greedy method with an approximation guarantee that degrades under congestion and larger storage capacities.
- E. General case: Approximately-submodular: JSPRR belongs to the approximately submodular class even though it is not submodular.The paper uses this broader classification to analyze the general and special cases.
- E. General case: Approximately-submodular: A δ-approximately submodular function is bounded relative to a submodular function F(E) by (1 − δ)F(E) ≤ f(E) ≤ (1 + δ)F(E).Here, F(E) is the maximum requests satisfied when bandwidth and computation resources are non-congestible.
- E. General case: Approximately-submodular: For a base station whose demand exceeds capacity, the congestion factors are bounded by Φn/Cn for computation and Φn/B↑n for bandwidth.The construction also uses a max term whose value 1 ensures F(E) is never below f(E).
- E. General case: Approximately-submodular: A greedy algorithm is used to maximize the δ-approximately submodular objective and obtain the proposition’s approximation ratio.The method is based on prior results for maximizing approximately submodular functions.
- E. General case: Approximately-submodular: When demand exceeds available resources by up to 50%, δ = 1/3.The corresponding approximation factor is stated immediately afterward in the paper.
- E. General case: Approximately-submodular: The greedy approximation ratio worsens as network congestion and storage capacities increase, motivating a different method with tighter guarantees.The paper introduces that alternative method in the next section.
IV. APPROXIMATION ALGORITHM
The paper presents a randomized-rounding approximation algorithm for JSPRR, beginning with a fractional linear relaxation and producing integer placement and routing decisions. Its expected solution preserves the fractional objective and satisfies resource constraints in expectation, while high-probability bounds quantify possible violations.
- Randomized Rounding: The algorithm solves the linear relaxation of JSPRR, then independently rounds fractional placement and routing variables into an integer solution.Placement variables are rounded first; routing uses nearby base stations storing the requested service or the cloud.
- Routing guarantee: The Randomized Rounding algorithm routes all user requests with high probability, with the routing probability gap converging to zero as nearby base-station coverage increases.Requests are routed to eligible base stations or the cloud, and the approximation becomes closer as the number of covering base stations grows.
- Expected feasibility: The rounded solution satisfies storage, computation, and bandwidth capacity constraints in expectation.The guarantee covers storage together with computation and uplink/downlink bandwidth constraints.
- Expected objective: The objective value returned by Randomized Rounding is in expectation equal to that of the optimal fractional solution.The expected number of cloud-routed requests matches the objective value of the optimal linear-relaxation solution.
- Bi-criteria interpretation: The expected guarantees do not ensure practical feasibility, so capacity violations must be bounded separately.The paper explicitly distinguishes expected satisfaction from possible violations in an actual rounded solution.
- High-probability guarantees: 3 ln(S)/Rn + 4 bounds the storage-capacity violation for any base station with high probability.The bound follows from applying Chernoff and Union Bound arguments to independently rounded placement variables.
- Bi-criteria interpretation: The approximation factors jointly bound objective and capacity deviations, and are constant in many practical scenarios.The paper illustrates this bi-criteria interpretation using a system with S = 1,000 services and base stations processing up to 1,000 requests.
V. EXTENSION AND PRACTICAL CASES
The extension addresses changing demand by repeatedly updating service placement and request routing for each new predicted demand period.
- Extension and practical cases: The proposed solution is designed for a fixed, predicted demand during each time period.Demand may change after a few hours or at a faster scenario-dependent timescale.
- Extension and practical cases: The service placement and request routing decisions must be repeatedly adapted when user demand changes.The extension is intended to make the algorithm more practical under changing demand.
A. Handling user demand changes
The demand-change extension accounts for the operational cost of updating service placements as popularity shifts. It adds a bound on replacement data and retains the earlier guarantees while bounding adaptation-cost violations.
- Handling user demand changes: The MEC operator must repeatedly predict demand and adapt placement and routing as service popularity changes.Services that lose popularity may be replaced by services whose popularity has increased.
- Handling user demand changes: Replacing services requires downloading non-trivial data from the cloud over backhaul links, creating potentially significant overhead.The overhead depends on the timescale of demand changes and should therefore be avoided when possible.
- Handling user demand changes: The extended formulation adds a constraint that upper-bounds the total data associated with replaced services by D.A newly placed service contributes its storage size to adaptation cost when it was absent from the previous placement.
- Handling user demand changes: The earlier lemmas and theorems remain valid after adding the adaptation constraint.The remaining issue is the probability that randomized rounding violates the new constraint.
- Handling user demand changes: 2 ln(S)/D + 3 bounds the adaptation data above D with high probability.The theorem applies the same concentration-based style of analysis used for the earlier capacity guarantees.
B. Constructing a feasible solution
The paper converts the randomized-rounding output into a feasible solution because its bi-criteria guarantees can violate storage, adaptation, computation, and bandwidth limits. Iterative service removal and request redirection restore feasibility, although solution quality may deteriorate.
- Constructing a feasible solution: Randomized Rounding may violate storage, adaptation, computation, and bandwidth constraints, requiring conversion of its bi-criteria output into a feasible solution.These violations can prevent the operator from storing required services or maintaining the stated performance guarantee.
- Constructing a feasible solution: The repair procedure removes a service from a base station when this yields the minimum cloud-load increment.Requests affected by removal are redirected to nearby base stations with available resources or to the cloud.
- Constructing a feasible solution: Overloaded-base-station requests are iteratively redirected until no base station remains overloaded.Redirection uses another base station with available computation and bandwidth when possible, otherwise the cloud.
- Constructing a feasible solution: The feasibility-restoration process may deteriorate solution quality, but numerical evaluation reports operation close to optimal in realistic settings.The quality impact is acknowledged as a trade-off of enforcing feasibility.
VI. EVALUATION RESULTS
Evaluations compare Randomized Rounding with Linear-Relaxation and Greedy across varied storage, computation, and bandwidth capacities. Randomized Rounding reduces centralized-cloud load, approaches the relaxation benchmark, and uses computation resources more effectively than Greedy.
- Experimental setup: The evaluation uses 9 grid-deployed BSs, 500 uniformly distributed users, and 100 services, with storage, computation, and bandwidth parameters varied.Each BS is configured with 500 GB storage, 10 GHz computation, and 250 Mbps uplink and downlink bandwidth before capacity variations.
- Storage capacity: Randomized Rounding reduces cloud load as storage capacity increases, outperforming Greedy by up to 25% at Rn = 1250GBs.Its gap from the Linear-Relaxation benchmark is below 10% for Rn ≥1000GBs.
- Computation capacity: With computation capacity varied, Randomized Rounding consistently outperforms Greedy and remains within 3% of Linear-Relaxation when Cn ≤ 3GHz.Cloud load decreases with computation capacity for all evaluated algorithms.
- Bandwidth capacity: Cloud load decreases as uplink and downlink bandwidth capacities increase across the evaluated combinations.The evaluation separately varies the two directional bandwidth capacities, reflecting asymmetric communication requirements.
- Overall comparison: Randomized Rounding achieves gains between 9% and 24% over Greedy in the evaluated comparisons.The gains are reported in the bar labels.
VII. CONCLUSION
The paper studies joint service placement and request routing in multi-cell MEC networks under storage, computation, and communication constraints. It proposes randomized rounding with provably close-to-optimal performance and identifies coordination and chained services as future directions.
- The study jointly optimizes service placement and request routing in multi-cell MEC networks with storage, computation, and communication constraints.
- Randomized rounding yields a provably close-to-optimal algorithm and, to the authors’ knowledge, the first approximation for this problem.
- Future work includes coordinating BSs through backhaul links and generalizing the model to services with multiple chained functions.