PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Adaptive Computation Reuse in Collaborative Edge Computing: A Two-Timescale Approach

Xingqiu He, Chaoqun You, Peng Wang, Xiaoyu Liu, Tony Q. S. Quek

arXiv:2610.11224v1cs.NI

TL;DR

Dynamic demand makes it difficult to coordinate computation reuse with caching-update costs in collaborative edge networks. The paper proposes an online two-timescale algorithm that coordinates caching and scheduling. It reports consistent performance gains over benchmarks across diverse network and workload settings.

  • Problem

    CEC computation reuse must adapt caching and scheduling to changing popularity and arrivals, even though cache reconfiguration costs and the decisions are coupled.

    Source: §I · pp. 1–2

  • Method

    The algorithm uses recent workload observations to decompose a frame-level surrogate into caching and scheduling subproblems, with frame-level caching and slot-level scheduling.

    Source: §I · p. 2

  • Results

    The algorithm demonstrates consistent performance gains over existing schemes across a wide range of network and workload settings.

    Source: §I · p. 2, §VI · p. 13

  • Takeaways & Limitations

    The simulations highlight the benefits of coordinating computation reuse across timescales while accounting for cache-update costs.

    Source: §VI · p. 13

    Cloud offloading is not explicitly modeled, though the paper says it can be represented as a neighboring base station with sufficient compute capacity and large transmission delays.

    Source: B. Task Scheduling Model · p. 5

Abstract

from arXiv · show

Collaborative Edge Computing (CEC) is an efficient computing paradigm that enables neighboring edge servers to share computational resources with each other. Although CEC can enhance resource utilization, it still suffers from duplicate computations because nearby end-users often offload tasks with similar inputs. To improve system efficiency, the computation results of previously executed tasks can be cached and reused by subsequent tasks. However, time-varying task popularity and arrival rates require caching and scheduling decisions to adapt to demand changes, while frequent cache updates incur additional costs. To address this issue, this paper develops a two-timescale computation reuse algorithm for CEC networks. We formulate an optimization problem that jointly considers weighted response time and cache update cost, with result caching decisions determined at the frame level and workload scheduling, cache searching, and computational resource allocation adjusted at the slot level. Using recent workload observations, we construct a frame-level surrogate problem and decompose it into a caching subproblem and a scheduling subproblem. For the caching subproblem, we introduce marginal storage efficiency and incorporate cache update costs into a bisectionbased algorithm. Under bounded normalized marginal sensitivity, the algorithm achieves a near-optimal objective value for the single-BS caching subproblem when individual result sizes are small relative to the cache capacity and the relaxed solution is sufficiently accurate. For the scheduling subproblem, we utilize projected gradient descent and backtracking with warm starts across consecutive slots. Numerical results demonstrate consistent performance gains over benchmark schemes across diverse network and workload settings.

I. INTRODUCTION

The introduction motivates computation reuse in collaborative edge computing as a way to avoid repeated task execution, then proposes coordinating caching and scheduling on different timescales to respond to changing demand while limiting cache-update costs.

B. Computation Reuse

  • Computation reuse exploits similar task inputs to cache and reuse previous results, avoiding duplicate execution and potentially reducing response time.The paper cites AR/VR rendering and surveillance image analysis as examples of similar inputs.Source: §I · p. 1

I. INTRODUCTION

  • Time-varying task popularity and arrival rates call for different adaptation timescales: caching changes incur communication and storage I/O overhead, while scheduling must react to short-term traffic.The paper frames this mismatch as motivation for jointly optimizing caching and workload scheduling online.Source: §I · p. 1
  • The proposed algorithm jointly minimizes long-term weighted response time and cache-update cost, using frame-level caching and slot-level scheduling, cache searching, and computational power allocation.It builds a frame-level surrogate from recent workloads and decomposes it into caching and scheduling subproblems.Source: §I · p. 2
  • The algorithm demonstrates consistent performance gains over existing schemes across a wide range of network and workload settings.The evaluation compares against a static counterpart and representative caching and scheduling baselines, with a look-ahead scheme as a performance reference.Source: §I · p. 2

A. Scheduling and Caching in CEC Networks

  • Prior CEC scheduling work addresses load balancing and latency, while content-caching work targets retrieval costs; computation reuse instead caches computed results and couples caching with scheduling.The related-work discussion distinguishes computation reuse from content caching and positions this paper against earlier time-invariant reuse optimization.Source: A. Scheduling and Caching in CEC… · p. 2, B. Computation Reuse · p. 3

A. Computation Reuse Model

  • In the system model, caching decisions stay fixed within a frame, while scheduling adapts each slot to current arrivals because cache updates incur communication and storage costs.Task popularity is assumed approximately unchanged within a frame and arrival rates within a slot.Source: A. Computation Reuse Model · pp. 3–4
  • The reuse model searches for a result matching a task’s input and returns it when similarity exceeds a threshold and that result is cached; otherwise, the task is computed from scratch.The model allows searching to be skipped when its hashing and similarity-calculation costs outweigh the expected benefit.Source: A. Computation Reuse Model · p. 3

B. Task Scheduling Model

The task-scheduling model defines response time through computation and transmission delays, then distributes workloads and computational capacity across collaborative base stations.

B. Task Scheduling Model

  • Application response time comprises computation delay and transmission delay for tasks and results transmitted among base stations.The model uses a quasistationary queueing approximation within each slot and assumes Poisson task arrivals.Source: B. Task Scheduling Model · p. 4
  • Each application’s workload is divided among base stations using allocation fractions that sum to one, with computational capability allocated to each application at each station.Task workload is assumed exponentially distributed, following,.Source: B. Task Scheduling Model · p. 4
  • Cache searching changes the computation-delay model: a reused result incurs search cost, while a miss still requires task processing, and neighboring results add transmission delay.The model uses M/M/1 queueing without cache searching and M/G/1 queueing with it.Source: B. Task Scheduling Model · p. 4
  • The model does not explicitly include cloud offloading, although it could represent a cloud as a neighboring base station with sufficient compute capacity and large transmission delays.With limited core-network bandwidth, transmission delay could instead be modeled as an M/M/1 queue.Source: B. Task Scheduling Model · p. 5

C. Problem Formulation

The paper formulates a long-term optimization that jointly chooses caching, cache searching, workload distribution, and computational allocation to balance weighted response time against cache-update cost.

C. Problem Formulation

  • The objective combines weighted response time across applications with cache-update cost, controlled by a coefficient that sets their tradeoff.The decisions include frame-level caching and slot-level cache searching, workload distribution, and computational capability allocation.Source: C. Problem Formulation · p. 5
  • The optimization is a mixed-integer nonlinear problem and is NP-hard even with time-invariant system states, one base station, and one application.The paper notes that realistic inter-base-station caching interactions and dynamic workloads further complicate the problem.Source: C. Problem Formulation · p. 5

IV. ALGORITHM DESIGN AND THEORETICAL ANALYSIS

The algorithm coordinates caching and scheduling across frames and slots, using recent workload observations to form and solve a frame-level surrogate problem.

IV. ALGORITHM DESIGN AND THEORETICAL ANALYSIS

  • Caching is set at the frame timescale, while workload scheduling, cache searching, and computational resource allocation adapt to current arrivals at the slot timescale.Caching remains fixed during each frame.Source: §IV · p. 5

A. Problem Decomposition

  • The frame-level surrogate uses recent workload samples to estimate demand because caching decisions must be made before future arrivals are known.Recent workload samples are used to characterize workload and task popularity.Source: A. Problem Decomposition · p. 5
  • Alternating minimization separates caching from sample-specific scheduling; binary cache candidates are accepted only if they strictly reduce the complete surrogate objective.With caching fixed, scheduling decisions can be optimized independently across workload samples.Source: A. Problem Decomposition · p. 6

B. Caching Subproblem

The caching subproblem is optimized one base station at a time because caching decisions across base stations are coupled. A marginal-storage-efficiency threshold supports a bisection-based solution that accounts for response-time effects, storage, and cache-update costs.

B. Caching Subproblem

  • The method optimizes each base station's caching decisions while fixing the decisions at other base stations because joint caching decisions are tightly coupled.For a given base station, sample-specific scheduling and cache-searching decisions are held fixed during its caching optimization.Source: B. Caching Subproblem · p. 6
  • The marginal storage efficiency of the objective accounts for both response-time change and cache-update cost per unit of allocated storage.Storage is allocated to results that contribute most to reducing the objective.Source: B. Caching Subproblem · pp. 6–7
  • The algorithm searches for a marginal-storage-efficiency threshold by bisection, enabled by total storage usage being nondecreasing in that threshold.The search adjusts the threshold until the storage constraint is satisfied within a prescribed tolerance.Source: B. Caching Subproblem · p. 7
  • For results that increase the overall hit rate, the method orders caching priorities using popularity, result size, and update cost, then solves for additional hit rate by bisection.Results already cached at other base stations are handled separately using their marginal storage efficiencies.Source: B. Caching Subproblem · pp. 7–8
  • Under bounded normalized marginal sensitivity, rounding down the relaxed solution is asymptotically optimal as the maximum result size becomes small relative to cache capacity.The guarantee concerns the single-base-station caching subproblem.Source: B. Caching Subproblem · p. 8
  • An acceptance rule rejects rounded caching candidates that do not decrease the original frame-level objective.The single-base-station analysis does not itself guarantee a decrease in the network-wide objective after numerical approximation and rounding.Source: B. Caching Subproblem · pp. 8–9

C. Scheduling Subproblem

The scheduling subproblem uses projected gradient descent, with projection onto a feasible region represented by probability simplices. Backtracking supports objective decrease and feasibility, while warm starts reuse the preceding slot's solution.

C. Scheduling Subproblem

  • Projected gradient descent updates the scheduling variables and projects each update back into the feasible region.Variable substitution makes the relevant feasible regions probability simplices, whose projection has complexity O(NA log(NA)).Source: C. Scheduling Subproblem · p. 9
  • Backtracking selects a step that decreases the objective while satisfying the stability constraint.The method shrinks the step size until the objective-decrease and feasibility requirements are met.Source: C. Scheduling Subproblem · p. 9
  • For slot t > 1, the scheduling algorithm warm-starts from the preceding slot's solution, reducing iterations when task arrival rates vary smoothly across slots.Source: C. Scheduling Subproblem · p. 9

D. Online Implementation and Analysis

At each frame, recent observations inform workload estimates and sample-specific scheduling and caching decisions; the selected cache is then fixed within the frame. Slot-level scheduling uses current arrival rates and a warm start.

D. Online Implementation and Analysis

  • The frame-level process alternates sample-specific scheduling optimization with per-base-station caching updates, accepting a binary caching candidate only when it reduces the frame-level objective.The candidate is generated using the caching objective and the previous-frame cache state.Source: D. Online Implementation and Analysis · pp. 9–10
  • After frame-level optimization, the resulting caching decision is deployed and held fixed during the frame; each slot then uses observed arrival rates and a warm start for scheduling.Source: D. Online Implementation and Analysis · pp. 9–10
  • The frame-level objective sequence converges because scheduling updates do not increase it and caching updates either decrease it or leave the decision unchanged.At slot level, convergence yields a solution stationary in the continuous variables and locally optimal with respect to y[t].Source: D. Online Implementation and Analysis · p. 9
  • Frame-level planning has complexity O(If(NCc + LIsNA log(NA))), while each slot-level update has complexity O(IsNA log(NA)).Source: D. Online Implementation and Analysis · p. 10

V. PERFORMANCE EVALUATION

The paper evaluates through numerical simulations how the proposed algorithm adapts computation reuse to time-varying workloads.

V. PERFORMANCE EVALUATION

  • Numerical simulations evaluate the algorithm's effectiveness in adapting computation reuse to time-varying workloads.Source: §V · p. 10

A. Simulation Setup

The simulations evaluate Prop on a 24-hour, 48-frame trace with time-varying arrival loads and evolving input popularity, comparing it with static, value-aware, look-ahead, no-reuse, and no-collaboration policies.

A. Simulation Setup

  • Prop is evaluated over 48 half-hour frames, each containing 60 slots of 30 seconds, in a default network of 10 BSs and 5 applications.The first four frames are excluded from aggregate performance metrics.Source: A. Simulation Setup · p. 10
  • Arrival loads vary through correlated multiplicative fluctuations, with load bursts and 30% BS-side traffic redistribution at frames 17 and 33.Input popularity evolves independently, with a persistent hot set whose membership changes gradually and more sharply at frames 17 and 33.Source: A. Simulation Setup · p. 10
  • Prop estimates demand from the preceding 60 slots and limits frame-level AM and slot-level PGD to 3 and 25 iterations, respectively.Both procedures use a relative-change tolerance of 10^-3.Source: A. Simulation Setup · p. 10
  • The comparison includes a static policy, VaRe-C, a look-ahead oracle, No Reuse, and No Collaboration.No Collaboration is tested under a reduced workload because the default workload exceeds its processing capacity.Source: A. Simulation Setup · pp. 10–11

B. Convergence Behavior and Running Time

The convergence evaluation reports objective reductions across sampled frames, better finite-iteration response time with warm starts, and runtime overhead for Prop relative to VaRe-C.

B. Convergence Behavior and Running Time

  • The surrogate objective decreases by 16.8%–23.7% across six sampled frames, with most of the reduction achieved by the first AM iteration.Source: B. Convergence Behavior and Running Time · p. 11
  • 18.8% lower final weighted response time is achieved with warm starts than cold starts under the prescribed iteration budget.Mean weighted response time changes from 0.6190 to 0.6162 s with warm starts and from 0.8647 to 0.7584 s with cold starts.Source: B. Convergence Behavior and Running Time · p. 11
  • Prop requires an average of 11.44 s per 30-minute frame, compared with 1.23 s for VaRe-C using the same slot-level controller.The authors report that Prop's runtime is negligible relative to frame duration and note that the implementation is in Python.Source: B. Convergence Behavior and Running Time · p. 11

C. Performance under Dynamic Workloads

Under dynamic demand, Prop lowers the mean objective relative to VaRe-C, Static, and NoR. The remaining evaluations show sensitivity to workload changes, network size, and design choices across the two timescales.

C. Performance under Dynamic Workloads

D. Load and Popularity Sensitivity

  • As load increases, Prop has the lowest objective among causal algorithms; under popularity drift, Prop, VaRe-C, and Static generally have higher objectives.NoR and Static exceed processing capacity in most runs at ρ ≥1.2 and ρ = 1.4, respectively; Look-ahead is only weakly affected by popularity drift.Source: D. Load and Popularity Sensitivity · pp. 11–12, Figure 4 · p. 12

E. Impact of Network Size

  • As the network grows, Look-ahead, Prop, and Static generally perform better, while VaRe-C's mean objective rises from 1.6097 to 1.8002.VaRe-C's mean response time falls from 1.3568 s to 1.0804 s, while its mean update cost rises from 2.5288 to 7.1976.Source: E. Impact of Network Size · p. 12, Figure 5 · p. 12

F. Two-Timescale Design and Ablation Study

  • Using L = 60 instead of L = 1 reduces the mean objective from 1.3116 to 1.1136, a 15.1% improvement.Neglecting update costs raises mean cache update cost from 1.1649 to 5.7013 and mean objective to 1.5979; cold starts raise mean response time to 1.5352 s and mean objective to 1.6517.Source: F. Two-Timescale Design and Ablation… · p. 12
  • At η = 0.1, Prop's objective is 42.7% lower than Static's; increasing η consistently reduces cache writes, while response time varies nonmonotonically.At η = 1, fewer cache writes accompany increased response time, indicating insufficient adaptation to demand variations.Source: F. Two-Timescale Design and Ablation… · pp. 12–13, Figure 6 · p. 13
  • Among 20 tested frame and history-window combinations, a 15-minute frame with a 120-minute history reduces the objective by 11.1% versus the 30-minute/30-minute default.Within the tested range, history duration has greater impact than frame duration; performance varies modestly across frame durations.Source: F. Two-Timescale Design and Ablation… · p. 13, Figure 7 · p. 13

VI. CONCLUSIONS

  • The conclusion reports that simulations show adaptation to dynamic demand and better performance than benchmarks under varied settings.The analysis establishes near-optimality for single-BS caching when result sizes are small relative to cache capacity.Source: §VI · p. 13

APPENDIX A PROOF OF THEOREM 1

The appendix reduces the one-BS, one-application case to a maximum-hit-rate knapsack, characterizes convexity and KKT conditions for the relaxed problem, and bounds rounding loss to establish asymptotic optimality under stated conditions.

APPENDIX A PROOF OF THEOREM 1

  • With one BS and one application, maximizing hit rate reduces the response-time problem to a 0–1 knapsack, which is NP-hard.Source: Appendix A · p. 13

APPENDIX B PROOF OF THEOREM 2

  • The stability assumption makes delay finite and differentiable on the unit box; delay plus linear update cost is convex, so KKT conditions characterize the relaxed feasible problem.Source: Appendix B · p. 13

APPENDIX C PROOF OF THEOREM 3

  • The relaxed optimum can have at most A+1 fractional entries; rounding down preserves capacity and stability, and its convexity-based loss bound yields asymptotic optimality for fixed A and bounded κ_n.Source: Appendix C · pp. 13–14
Loading 2610.11224v1…