PaperlayerView exact revision on arXiv

Source-linked AI summary

Cooperative Service Caching and Workload Scheduling in Mobile Edge Computing

Xiao Ma, Ao Zhou, Shan Zhang, Shangguang Wang

arXiv:2002.01358v1cs.NI

TL;DR

The paper addresses inefficient joint use of heterogeneous edge storage and computation when edge nodes do not cooperate. It formulates cooperative service caching and workload scheduling as a non-polynomial mixed integer nonlinear problem, then develops ICE using Gibbs sampling and water filling. Simulations show reduced service response time and outsourcing traffic compared with benchmark algorithms.

  • Problem

    Heterogeneous and inconsistent edge storage and computation capacities make it difficult to fully utilize resources jointly without cooperation among edge nodes.

  • Method

    ICE iteratively updates cooperative service caching with Gibbs sampling and schedules workloads using a water-filling-based algorithm with polynomial computation complexity.

  • Results

    The simulations demonstrate that ICE jointly reduces service response time and outsourcing traffic compared with benchmark algorithms.

  • Takeaways & Limitations

    Cooperation among edge nodes can alleviate individual capacity inconsistency while supporting near-optimal caching and polynomial-complexity workload scheduling.

Abstract

from arXiv · show

Mobile edge computing is beneficial to reduce service response time and core network traffic by pushing cloud functionalities to network edge. Equipped with storage and computation capacities, edge nodes can cache services of resource-intensive and delay-sensitive mobile applications and process the corresponding computation tasks without outsourcing to central clouds. However, the heterogeneity of edge resource capacities and inconsistence of edge storage and computation capacities make it difficult to jointly fully utilize the storage and computation capacities when there is no cooperation among edge nodes. To address this issue, we consider cooperation among edge nodes and investigate cooperative service caching and workload scheduling in mobile edge computing. This problem can be formulated as a mixed integer nonlinear programming problem, which has non-polynomial computation complexity. To overcome the challenges of subproblem coupling, computation-communication tradeoff, and edge node heterogeneity, we develop an iterative algorithm called ICE. This algorithm is designed based on Gibbs sampling, which has provably near-optimal results, and the idea of water filling, which has polynomial computation complexity. Simulations are conducted and the results demonstrate that our algorithm can jointly reduce the service response time and the outsourcing traffic compared with the benchmark algorithms.

I. INTRODUCTION

Mobile edge computing places storage and computation at network edges to reduce response time and outsourcing traffic, but heterogeneous and mismatched capacities can waste resources without cooperation. The paper formulates cooperative caching and scheduling as a non-polynomial mixed integer nonlinear problem and proposes ICE to jointly optimize these objectives with lower-complexity components.

  • Motivation: Mobile edge computing caches application services at edge nodes so corresponding computation tasks can be processed near users.Services include program codes and related databases.
  • Motivation: Without cooperation, heterogeneous and mismatched storage and computation capacities cause edge-resource under-utilization and force some tasks toward central clouds.A node may lack storage to cache a service or computation capacity to process its tasks, while another node may have unused capacity.
  • Cooperative design: Cooperation lets tasks from incapable or uncached nodes be offloaded to nearby under-utilized nodes that cache the service, alleviating capacity inconsistency.Nearby edge nodes are connected through local-area or wired peer-to-peer networks.
  • Problem formulation: The study minimizes service response time and outsourcing traffic, addressing an objective not considered as a performance criterion in existing work.Prior cooperative work focused on maximizing edge-served requests under a caching-cost budget, whose practical value is difficult to determine.
  • Challenges: The optimization couples caching with scheduling, requires a computation–communication tradeoff, and must balance workloads across heterogeneous edge nodes.Offloading can reduce computation delay but adds LAN transmission delay, while heterogeneity leads to exponential computation complexity.
  • Algorithm: ICE iteratively updates caching through Gibbs sampling and optimizes scheduling using a water-filling-based heuristic with polynomial computation complexity.Queuing models estimate delay components and the average service response time used for the tradeoff.
  • Contributions: The paper formulates the problem as a mixed integer nonlinear program, proves workload-scheduling convexity, and evaluates ICE through simulations.The contributions include extensive evaluation of effectiveness and convergence.
  • Contributions: The two-layer ICE algorithm combines Gibbs-sampling caching updates with inner-layer workload scheduling and a reduced-complexity water-filling procedure.The conclusion characterizes the caching policy as near-optimal and the scheduling algorithm as polynomial-complexity.

II. RELATED WORK

Prior work studies workload scheduling, service caching, and their joint optimization, but often assumes fully cached services or omits cooperation and service response time. This paper addresses these gaps through cooperative caching and workload scheduling aimed at reducing response time and outsourcing traffic.

  • Workload scheduling research considers edge-cloud placement, hierarchical architectures, and software-defined request scheduling.
  • Many scheduling studies assume every edge node caches all services and can process any computation task, despite limited edge storage.
  • Caching research develops distributed, dynamic, prediction-based, history-based, and content-allocation approaches for edge or CDN systems.
  • Joint caching and routing work targets access delay but does not directly cover applications requiring both data-intensive and computation-intensive processing.
  • Existing joint caching and scheduling studies either omit cooperation among edge nodes or exclude service response time, including transmission and computation delay, as a criterion.
  • This paper investigates cooperative service caching and workload scheduling to minimize service response time and outsourcing traffic to central clouds.
  • The proposed solution combines Gibbs-sampling-based iterative caching updates with a water-filling-based heuristic workload scheduler of polynomial complexity.

III. SYSTEM MODEL AND PROBLEM FORMULATION

The system models heterogeneous edge nodes that cache services and cooperatively process workloads, with cloud outsourcing as an alternative. Caching and scheduling policies determine where services reside and how computation workload is distributed.

  • A. System Model: The system contains multiple edge nodes connected through local-area or wired peer-to-peer links, enabling nearby workload offloading.
  • 1) Edge Caching and Workload Scheduling Policies:: Workloads may be assigned to nearby edge nodes or outsourced to the cloud when local caching or computation capacity is insufficient.
  • A. System Model: Each edge node has computation capacity R_n and storage capacity P_n, while services differ in computation and storage requirements.
  • A. System Model: A service requires storage capacity p_s for caching, and its computation workload follows an exponential distribution with expectation β_s.
  • A. System Model: Requests arrive at each edge node as Poisson processes with expected rate A_ns, while a centralized cloud stores all services and has ample resources.
  • 1) Edge Caching and Workload Scheduling Policies:: The policy questions are which nodes cache each service and how workloads are scheduled among connected nodes caching the same service.
  • 1) Edge Caching and Workload Scheduling Policies:: Caching variables c_ns indicate service placement, whereas λ_ns denotes the workload ratio of service s executed at edge node n.
  • 1) Edge Caching and Workload Scheduling Policies:: Each node’s caching decision c_n belongs to an action space C_n, and cached services cannot exceed its storage capacity.

2) Service Response Time:

The response-time model combines computation and transmission delays across edge nodes, local links, and the cloud. Workload allocation determines queueing loads and the amount of traffic outsourced to the core network.

  • The delay model accounts for workloads processed locally, received from nearby edge nodes, or outsourced to the cloud.
  • The workload arriving at edge node n for service s is λ_ns A_s, with excess workload λ_ns A_s − A_ns originating from nearby edge nodes.
  • Computation capacity is shared among cached services through an allocation mechanism Γ_n, which assigns service-specific capacity r_ns.
  • Edge-node serving processes are modeled as M/M/1 queues because task arrivals are Poisson and serving times are exponential.
  • The edge queue must remain stable, with its service and arrival rates constrained by the computation capacity and a positive slack parameter ε.
  • Outsourced tasks enter the core network at rate λ_os A_s, and each outsourced computation unit generates t_s transmission requests.
  • Core-network transmission delay depends on the service traffic amount and bandwidth B_s, with task transmission size tied to t_s β_s.
  • Average service response time is a weighted sum of edge computation delay, LAN transmission delay, and cloud transmission delay.

B. Problem Formulation

The paper formulates cooperative caching and workload scheduling as a mixed integer nonlinear optimization problem. Complexity analysis identifies coupling, heterogeneity, and computation–transmission tradeoffs as central challenges.

  • B. Problem Formulation: The objective jointly minimizes service response time and overall outsourcing traffic to the cloud.
  • B. Problem Formulation: The formulation enforces storage limits, restricts admitted workloads to nearby eligible nodes, and prevents scheduled computation from exceeding capacity.
  • C. Complexity Analysis: Problem P1 is a mixed integer nonlinear programming problem with non-polynomial computation complexity.
  • C. Complexity Analysis: Without cooperation, tasks are processed locally or outsourced, and outsourcing depends on both computation and individual-node storage capacities.
  • C. Complexity Analysis: With one service type, caching is determined by whether service storage requirements fit each node’s storage capacity, reducing P1 to workload scheduling.
  • C. Complexity Analysis: The reduced scheduling problem distributes workloads among nodes with sufficient storage capacity to cache the service.
  • C. Complexity Analysis: Heterogeneous task arrivals and computation capacities make workload balancing important for reducing response time and cloud-outsourced traffic.
  • C. Complexity Analysis: Moving tasks to lightly loaded nodes or the cloud can reduce computation delay but adds transmission delay, requiring a computation–transmission tradeoff.

IV. ALGORITHM DESIGN

The paper addresses the non-polynomial complexity of jointly optimizing cooperative service caching and workload scheduling by designing the two-layer ICE algorithm. ICE updates caching with Gibbs sampling and solves the coupled scheduling subproblem through a heuristic water-filling approach, with convergence toward optimal caching as ω decreases.

  • Algorithm Design: The algorithm design targets jointly optimized service caching and workload scheduling with reduced computation complexity.The original problem remains non-polynomial even in simplified cases.
  • Algorithm Design: ICE uses an outer layer to update service caching policies through Gibbs sampling and an inner layer to solve workload scheduling for cached services.Given caching policies, the original problem is reduced to a scheduling subproblem among edge nodes caching each service.
  • ICE: Gibbs sampling associates conditional caching updates with the objective value while maintaining other variables unchanged during each iteration.The method uses a conditional probability distribution to determine caching updates iteratively.
  • ICE: The selected caching decision changes with probability ρ = 1/(1+e^(y*−y)/ω), while the current decision is retained with probability 1−ρ.Here, y and y* are objective values before and after the candidate caching change, and ω > 0 is the smoothing parameter.
  • ICE: ICE converges to the globally optimal solution with probability 1 as ω → 0.The theorem states that the probability of convergence to the global optimum increases as ω decreases.
  • ICE: The stationary distribution generated by Gibbs sampling is guaranteed to be the target joint distribution, supporting convergence to optimal caching policies.The paper links this guarantee to Monte Carlo Markov Chain theory and the design of the conditional probabilities.

B. Heuristic Workload Scheduling Algorithm

The heuristic workload scheduling algorithm exploits convexity in the scheduling subproblem to avoid direct enumeration of its constraint cases. It constructs scheduling policies from KKT conditions and uses water filling to obtain the remaining parameter efficiently.

  • Heuristic Workload Scheduling Algorithm: The heuristic algorithm exploits convexity to reduce the computation complexity of solving P2.It replaces direct search over the KKT cases with a structured workload scheduling procedure.
  • Heuristic Workload Scheduling Algorithm: With caching policies fixed, P2 is a convex optimization problem over the workload scheduling policy.For each service, scheduling among edge nodes that cache it is independent of other services.
  • Heuristic Workload Scheduling Algorithm: Directly searching KKT-condition results can require O(2^(2(N+1))) computation complexity because P2 has 2(N+1) inequality constraints.These constraints correspond to edge-node computation-capacity constraints.

2) Algorithm Design:

The scheduling procedure derives workload allocations from KKT conditions after removing inequality constraints, then uses water filling and bisection to enforce edge and core-network resource limits. Simulations evaluate ICE against non-cooperation and greedy baselines in a heterogeneous edge setting.

  • Algorithm Design: The method derives correlations among workload scheduling results of edge nodes and the cloud from computation-capacity and core-network bandwidth constraints.It then searches for KKT-satisfying results within those resource constraints.
  • Algorithm Design: After removing inequality constraints, the KKT conditions retain constraints (C1) and (C3), with (C1) reformulated for each edge node or cloud.The resulting Lagrangian is handled separately around boundary points.
  • Algorithm Design: Water filling models workload allocation to edge nodes or the cloud as filling tubes subject to lower and upper bounds.Bisection searches η_s after combining the allocation expressions with the total-workload constraint.
  • Simulation Setup: The evaluation compares ICE with non-cooperation and greedy algorithms.The non-cooperation baseline uses local processing or cloud outsourcing, while the greedy baseline prioritizes popular services for caching.

A. Performance Comparison

The cooperation algorithm is evaluated against non-cooperation and greedy caching strategies using objective value, service response time, and outsourcing traffic. It achieves the minimum objective value and outsourcing traffic, with service response time close to the minimum.

  • Performance Comparison: The comparison evaluates objective value, total service response time, and total outsourcing traffic while varying the average task arrival rate.The results are shown in Fig. 3.
  • Performance Comparison: The Cooperation algorithm always yields the minimum objective value and outsourcing traffic, with service response time close to the minimum.This comparison is against the Non-cooperation and Greedy algorithms.
  • Performance Comparison: Caching multiple less popular services with low storage requirements can utilize storage and computation capacities more fully than caching one popular service with large storage requirements.The comparison identifies a limitation of popularity-only caching decisions.
  • Performance Comparison: The Greedy algorithm generally produces more outsourcing traffic and service response time than the other two algorithms.It prioritizes popular services without considering service storage requirements.
  • Performance Comparison: Cooperation coordinates storage and computation capacities through service caching and workload scheduling among connected edge nodes.This addresses the underutilization of computation capacity at nodes with low storage capacity under non-cooperation.

B. Convergence of ICE

ICE’s convergence depends strongly on the smooth parameter ω and edge-node connectivity. Smaller ω improves convergence toward near-optimal caching, while greater connectivity increases cooperation benefits and lowers the objective value.

  • ICE can converge to optimal service caching results with probability 1 when the smooth parameter ω approaches 0.
  • When ω ≥10−3, convergence is slow toward a higher value at ω = 10−3 or absent at ω = 10−2.
  • Smaller ω makes selecting a better caching update more probable in each iteration.
  • Impact of edge node connectivity: With all edge nodes connected, the system reaches the minimum objective value, whereas no connectivity produces the highest objective value.
  • Impact of edge node connectivity: As connectivity increases, ICE achieves more cooperation benefits; partial connectivity limits these benefits to connected clusters.

APPENDIX A

The appendix models ICE’s caching evolution as a Markov chain and establishes convexity for the workload-scheduling subproblem. These properties support the algorithm’s analytical treatment and polynomial scheduling approach.

  • ICE’s caching policy evolves as an N-dimension Markov chain, with each dimension representing one edge node’s caching decision.
  • For two edge nodes, the caching state is represented as ⟨c1, c2⟩, and one randomly selected node changes its decision to a random alternative.
  • The stationary probability distribution is derived from the Markov chain’s stationary condition and expressed over caching policies.
  • The workload-scheduling problem P2 is a convex optimization problem over the workload scheduling policy Λ.
Loading 2002.01358v1…