PaperlayerView exact revision on arXiv

Source-linked AI summary

Prediction-Robust Service Deployment with Capacity-Aware Edge Admission

Hailiang Zhao, Ziqi Wang, Yifei Zhang, Mingyi Liu, Xinkui Zhao, Kingsum Chow, Shuiguang Deng

arXiv:2609.00877v1cs.DC

TL;DR

Edge deployment must balance finite-TTL instantiation costs against uncertain, shifting demand while respecting capacity. The paper proposes CAPSUM and CAPSUM-E, combining local prediction guards with capacity-aware admission and proving elastic prediction guarantees. Across the reported common-model experiments, CAPSUM has the lowest cost across synthetic regimes and a sampled trace, while its finite-capacity extension has no claimed capacity-competitive ratio.

  • Problem

    The central problem is deciding when to instantiate finite-TTL edge services under prediction uncertainty, localized demand shifts, and capacity coupling.

  • Method

    CAPSUM-E applies a local two-threshold PFSUM rule, while CAPSUM adds size-scaled evidence, a utilization-dependent shadow price, and evidence-density eviction.

  • Results

    CAPSUM has the lowest cost in all three synthetic regimes and the sampled Globus trace across 895 common-model runs.

  • Takeaways & Limitations

    The paper’s practical consequence is a decentralized elastic guarantee with a finite-capacity policy that is feasible and scale-invariant under its stated model.

  • Takeaways & Limitations

    Finite-capacity CAPSUM has no claimed capacity-competitive ratio because capacity couples node-service pairs and invalidates the elastic decomposition.

Abstract

from arXiv · show

Edge platforms instantiate executable services close to users to reduce request-serving cost, but each instance incurs a one-time deployment cost and remains useful only for a finite time-to-live (TTL). The resulting online decision is both prediction-sensitive and capacity-coupled: an optimistic forecast can waste deployment cost, whereas a delayed decision misses the burst it is intended to serve. We study this problem under a common TTL cost model and propose CAPSUM, a capacity-aware admission policy with an elastic specialization, CAPSUM-E. In the local elastic setting, every node-service trace is exactly a variable-price Bahncard instance. This reduction lets CAPSUM-E inherit PFSUM's tight prediction-error-dependent ratio, including $2/(1+β)$ consistency and $1/β$ robustness for $β>0$. A redirect-aware variant preserves the same local deployment schedule. For finite-capacity nodes, CAPSUM combines size-scaled break-even tests, a utilization-dependent shadow price, and evidence-density eviction; we prove capacity feasibility, scale invariance, and exact agreement with CAPSUM-E under an elastic configuration. We implement an exact local offline dynamic program and compare against direct common-model baselines and documented source-derived adapters for EDP-A, OREO, and uEDC-L. Experiments cover controlled prediction error, three synthetic demand regimes, a causal predictor on a public Globus Compute trace, and joint scaling to 1,024 nodes and 10,000 services. Under the common model, CAPSUM reduces normalized cost by 33.7-42.9% relative to the best source-derived adapter across the synthetic regimes and by 45.5% on the sampled trace.

I. INTRODUCTION

The paper isolates decentralized TTL service deployment as a prediction-sensitive rent-or-buy decision under localized, shifting demand. It proposes CAPSUM variants that separate elastic prediction robustness from finite-capacity admission and preserve analyzable local behavior.

  • Motivation: Localized demand shifts make globally accurate popularity forecasts potentially uneconomic at individual edge nodes.Nearby instances reduce request-serving cost, but deployment incurs a one-time cost and finite useful lifetime.
  • Motivation: Origin-only, forecast-only, and history-only policies respectively forgo burst savings, risk false-alarm costs, or deploy too late.Demand may migrate between edge zones before an instance expires, making both timing and locality consequential.
  • Problem Scope: The paper isolates an uncapacitated TTL deployment layer whose exact break-even point depends only on post-deployment workload before expiry.Past requests cannot amortize a newly purchased instance, while finite-capacity admission is treated separately.
  • Approach: Redirect-aware execution preserves the local deployment schedule by consulting remote instances only after the local policy declines deployment.This avoids changing the schedule on which the local competitive analysis depends.
  • Approach: CAPSUM-E applies learning-augmented guards locally, while CAPSUM extends admission to finite-capacity nodes.The contributions include a PFSUM reduction, trace equivalence, prediction-error guarantees, feasibility, and scale invariance.
  • Scope: Elastic guarantees do not extend automatically to hard resource coupling, which CAPSUM handles separately without a claimed capacity-competitive ratio.The elastic theorem provides pathwise prediction robustness, whereas finite capacity requires distinct analysis.

III. PROBLEM FORMULATION AND SYSTEM MODEL

The model describes continuous-time requests for executable services, fixed-TTL edge instances, heterogeneous origin-serving costs, and short-horizon workload predictions. It separates an elastic deployment layer from finite-capacity resource coupling.

  • A. System Architecture and Scope: The system comprises edge nodes, stateless executable services, an always-available origin, and continuous time.A service must be instantiated at an edge before serving requests there.
  • A. System Architecture and Scope: The uncapacitated assumption lets each node host every elected service without eviction or changes to other pairs’ serving costs.This isolates online deployment from cache admission, CPU scheduling, and hard placement constraints.
  • B. Request and Cost Model: Each request has an increasing arrival time, ingress node, requested service, and positive regular cost aggregating origin resource and network cost.The request sequence is finite and revealed online.
  • B. Request and Cost Model: Instantiation costs C, active instances serve requests at βw_i, and inactive requests cost w_i at the origin, yielding saving (1−β)w_i.The analysis permits heterogeneous request costs without a bounded-request-cost assumption.
  • C. Deployment State and Objective: A deployment remains active on [τ, τ+T), and an online algorithm pays deployment costs plus discounted local or regular origin-serving costs.Deployments may occur immediately before requests, and overlapping deployments are unnecessary.
  • C. Deployment State and Objective: The local offline benchmark minimizes costs over valid TTL schedules while serving inactive requests from the origin.This benchmark is defined for local-only service.
  • D. Learning-Augmented Information: At inactive requests, predictions estimate workload in the next TTL window, with error measured in workload units rather than mispredicted-request counts.The predictor is a black box and may differ across nodes.
  • D. Learning-Augmented Information: The break-even workload γ is the future regular workload required for a deployment to recoup C over its TTL.The algorithm maintains sliding-window history and receives a prediction at inactive decision points.

E. Competitive Criterion and Problem Statement

The paper seeks a decentralized policy using only local history and predictions that achieves a tight consistency-robustness trade-off. It also analyzes a redirectable extension against a stronger offline benchmark.

  • Competitive Criterion: Consistency bounds cost with accurate predictions, while robustness requires a bound for every prediction-error level η.These properties are defined through the competitive-ratio function CRA(η).
  • Problem Statement: The target is a local-history and local-prediction policy with a tight consistency-robustness trade-off under local service.The policy is evaluated at each node-service pair.
  • Problem Statement: The redirectable extension permits inactive local requests to use live remote instances and therefore requires a separate analysis against a stronger offline benchmark.This distinguishes local-only guarantees from redirect-aware guarantees.

IV. ALGORITHM DESIGN AND THEORETICAL ANALYSIS

CAPSUM-E runs a two-guard PFSUM rule independently for each node-service pair, exactly reducing local traces to variable-price Bahncard instances. The analysis establishes trace equivalence, tight error-dependent bounds, and schedule-preserving redirection.

  • Algorithm Design: CAPSUM-E deploys only when both preceding-TTL history and following-TTL predicted workload reach γ.The historical window includes the current and all previous observed requests, regardless of serving location.
  • Algorithm Design: The future guard tests post-purchase amortization, while the past guard rejects purchases supported only by optimistic forecasts.Half-open windows ensure the current request belongs to both tests and the request at t+T belongs to neither active interval.
  • Algorithm Design: Forecast-only deployment has no bounded competitive ratio under arbitrary predictions.A single ε-cost request can induce deployment cost C+βε against offline cost ε, while CAPSUM-E rejects it when historical workload is below γ.
  • Design Rationale: Past and future workloads remain separate because elapsed requests cannot benefit from a deployment bought now; realized future workload breaks even at W=γ.A timestamped queue maintains the historical window in O(1) amortized update time.
  • Design Rationale: A single weighted threshold cannot generally preserve both certificates, so CAPSUM-E requires each quantity to meet the same economic threshold.The minimal decision state includes active-until time, exact sliding-window workload, and predictor information.
  • Exact Reduction: Each node-service trace maps exactly to a variable-price Bahncard instance with ticket price p_i=w_i, card cost C, TTL T, and discount β.A live local instance changes request cost from w_i to βw_i, matching the Bahncard rule.
  • Redirection and Guarantees: Redirect-aware CAPSUM-E+ consults the directory only after the local rule declines deployment, preserving the analytically required local schedule.The local guarantee is parameterized by each pair’s maximum prediction error and remains tight for a single pair.
  • Exact Reduction: A centralized implementation maintaining separate PFSUM states produces identical deployments, serving actions, and total cost to decentralized CAPSUM-E.The equivalence follows because actions for another pair do not alter the local state under the uncapacitated assumption.

D. Global Guarantee

CAPSUM-E achieves a tight prediction-error-dependent consistency–robustness guarantee in the local model, with an instance-dependent aggregate certificate that prevents economically insignificant pairs from dominating the trace-level bound.

  • 2/(1+β) consistency and 1/β robustness for β > 0 characterize CAPSUM-E’s tight local-model guarantee.The guarantee is tight, and κ(0) = 2/(1 + β) while its limit as prediction error grows is 1/β.
  • κ is continuous and strictly increasing with prediction error, and becomes unbounded when β = 0.The endpoint behavior follows from the stated properties of κ.
  • The instance-dependent aggregate certificate weights each node-service pair by its offline local cost.This prevents an inaccurate but economically insignificant pair from determining the trace-level certificate.

E. Interpretation of the Guarantee and Its Scope

The guarantee depends on dimensionless prediction error and preserves scale invariance, but its separable theorem is limited to local-only elastic service; finite capacity requires a separate policy and analysis.

  • Scaling deployment cost, workloads, and predictions by one positive factor leaves decisions and the competitive ratio unchanged.The same scaling applies to γ, online cost, and offline cost.
  • The parameter β links robustness to the economic value of local service, with poor-forecast robustness limited by 1/β when β is small.As β approaches one, the ratio approaches one because local and origin service become economically similar.
  • The local theorem does not imply that centralized control cannot improve practical metrics.It only states that central knowledge cannot couple independent subproblems under the local-only assumption.
  • Finite-capacity coupling invalidates the elastic decomposition, so CAPSUM handles admission separately without extending the separable competitive theorem.The full policy adds local admission while retaining feasibility rather than claiming a capacity competitive ratio.

A. Capacity Model and Shadow-Priced Evidence

CAPSUM handles finite node capacity through size-aware break-even admission, utilization-dependent pricing, and evidence-density eviction, while preserving feasibility, scale invariance, and the CAPSUM-E elastic limit.

  • Capacity Model and Shadow-Priced Evidence: A service of size a_s incurs deployment cost C_s = a_sC and must justify both its scaled break-even workload and consumed capacity.The unpriced break-even workload is a_sγ.
  • Capacity Model and Shadow-Priced Evidence: The utilization shadow price rises near saturation but is an engineering choice rather than a derived dual optimum.Other nonnegative local price curves can replace the square without changing the feasibility argument.
  • Capacity Model and Shadow-Priced Evidence: CAPSUM evicts active residents in increasing admission-evidence-density order, only when their density is strictly below the candidate’s.If sufficient capacity cannot be freed, the request is forwarded without deployment cost.
  • Capacity Model and Shadow-Priced Evidence: CAPSUM maintains capacity feasibility after every request and exactly matches CAPSUM-E when service size is one, capacity is elastic, pricing is zero, and eviction is disabled.In that configuration, the admission gate reduces to H, F̂ ≥ γ.
  • Capacity Model and Shadow-Priced Evidence: Scaling costs, workloads, and forecasts by ζ > 0 preserves CAPSUM decisions while scaling all incurred costs by ζ.The gates, density orderings, active sets, and routing remain unchanged.
  • Capacity Model and Shadow-Priced Evidence: Capacity coupling establishes feasibility and invariance, not a capacity-competitive ratio.A capacity-aware offline benchmark and separate analysis would be required for such a guarantee.

B. CAPSUM-E+: Redirect-Aware Service

CAPSUM-E+ keeps CAPSUM-E’s local deployment schedule while redirecting otherwise origin-served requests to verified remote instances when beneficial, yielding a separate redirectable-model guarantee.

  • Redirect-Aware Service: CAPSUM-E+ preserves CAPSUM-E’s local deployment decisions and redirects only when the local policy would otherwise use the origin.It selects the nearest verified active instance when available, otherwise using the origin.
  • Redirect-Aware Service: CAPSUM-E+ has the same local deployment schedule as CAPSUM-E and no greater service cost under the routing-overhead assumption.Deployment costs are identical, while verified remote service is no more expensive than origin service.

D. Practical Considerations

The evaluation separates analytical guarantees from finite-capacity results, uses controlled and causal prediction studies, and reports reproducible comparisons across workloads, seeds, and scaling settings. Practical deployment must separately measure control overhead and preserve local deployment decisions when claiming the theoretical guarantee.

  • CAPSUM-E is evaluated separately from finite-capacity CAPSUM, so capacity results are not evidence for the PFSUM guarantee.
  • The evaluation covers local-optimum tracking, prediction-error robustness, finite-capacity comparisons, ablations, capacity–quality interactions, scalability, and transfer to a public FaaS trace.The redirect extension is evaluated analytically through schedule preservation, while finite-capacity runs use a common redirect overlay.
  • Synthetic workloads span stationary, regional flash-crowd, and moving-hotspot demand on a 9-node grid with 60 services over 72 hours.The default configuration uses T = 6 hours, C = 1000, β = 0.25, α = 0.12, and Bn = 9.
  • The 895 policy runs use paired event streams and seeded choices where possible, with uncertainty intervals describing run-to-run variation rather than population sampling uncertainty.Trace-block intervals are descriptive because adjacent chronological blocks need not be independent.
  • The primary metric is total deployment, local, remote, and origin cost normalized by origin-only cost, alongside service rate, cost composition, deployments, evictions, and runtime.Finite-capacity local misses use nearest-copy redirection when available and otherwise fall back to the origin.
  • Controlled synthetic prediction errors use an oracle-style predictor, whereas the public-trace study uses a strictly causal predictor without forecast leakage.The controlled predictor is constructed from realized future demand and is therefore not deployable as a forecaster.

B. Implementation and Reproducibility

The implementation provides an exact local offline dynamic program, deterministic reproducibility checks, and explicitly scoped common-model comparisons. Experiments validate prediction robustness, finite-capacity behavior, cost composition, and scaling across synthetic and trace settings.

  • Offline implementation: The exact offline dynamic program computes optimal suffix costs independently for every node-service stream using a two-pointer scan and suffix workload sums.It is used only for the local uncapacitated ratio, not as a finite-capacity oracle.
  • Reproducibility: A reproducible driver regenerates manifests, per-seed rows, tables, and figures while auditing counts, cost decomposition, ranges, bounds, and trace checksums.Tests cover TTL boundaries, admission gates, the dynamic program, capacity, renewal, prediction, and adapter paths.
  • Comparison methodology: The evaluation compares direct TTL baselines with explicitly translated EDP-A, OREO, and uEDC-L adapters under common deployment, routing, and origin-cost accounting.The adapters preserve neither their native objectives nor their native decision objects exactly, so the paper documents each translation.
  • Finite-capacity results: CAPSUM has the lowest normalized cost in stationary, flash-crowd, and moving-hotspot regimes: 0.895 ± 0.005, 0.765, and 0.726 ± 0.004, respectively.The ranking applies to the explicitly scoped adapters in the common model.
  • Cost anatomy: On flash crowds, EDP-A costs 1.340 ± 0.004 at 76.5% edge service, while immediate-admission LRU/LFU/Random reach 100% only with costs 7.35–8.31.These comparisons show why edge-service rate alone does not capture deployment cost.

F. Public-Trace Validation

The public-trace evaluation constructs a causal deployment workload from Globus Compute data and reports CAPSUM’s cost and edge-service performance under the common TTL accounting model.

  • Trace construction: The trace retains 13,543 requests across 20 endpoints and 217 functions over 212.9 days.The preprocessing parses 39,764 unique tasks and filters to valid durations after endpoint/function selection.
  • Trace construction: The trace evaluation uses T = 7 days and Bn = 24 after mapping durations to w ∈ [70, 130] and argument-size ranks to as ∈ {1, 2, 3}.The construction also resolves one tied timestamp to satisfy the strictly ordered model.
  • Trace construction: The causal predictor uses only records observed by each arrival time, excluding future blocks and future records in the current block.This enforces the stated no-forecast-leakage condition.

G. Component Ablation and Cross-Factor Robustness

The ablations and cross-factor sweeps examine guard necessity, capacity and workload sensitivity, decision-time scaling, and the validity limits of the reported comparisons.

  • Component ablation: Removing the forecast guard raises flash-crowd cost from 0.765 to 0.796 and mobility cost from 0.726 to 0.751.Forecast-only and no-price variants can be slightly cheaper on some accurate traces, but the forecast-only saving fails under positive bias.
  • Capacity–quality interactions: Increasing capacity from 4 to 18 changes cost by 0.002 at q = .2 but lowers it from 0.759 to 0.751 at q = 1.At burst multiplier 2, CAPSUM costs 0.665 and beats the best source-derived adapter by 39.9%, excluding a single-amplitude artifact.
  • Cross-factor robustness: When C rises from 500 to 2000, CAPSUM increases from 0.684 to 0.873, versus 2.134, 5.662, and 2.116 for EDP-A, OREO, and uEDC-L.CAPSUM’s shadow price keeps its cost curve nearly flat as extra capacity affects other adapters’ deployment costs.
  • Scalability: CAPSUM decision time changes from 4.64 to 5.27 µs over 30–240 services, while OREO changes from 12.99 to 14.39 µs.These are simulator decision times, not network or cold-start latency.
  • Scalability: At 1,024 nodes and 10,000 services, mean times are 50.38, 287.43, 962.12, and 1,334.10 µs/request for CAPSUM, uEDC-L, OREO, and EDP-A.The joint sweep exposes global-placement overhead absent from one-dimensional sweeps.
  • Validity boundary: The reported rankings characterize the stated TTL model rather than the source systems universally.The scope is limited by proxy costs and image sizes, unavailable edge locations or shorter horizons in comparison datasets, and omitted transfer, cold-start, prediction, directory, reliability, energy, and latency costs.
Loading 2609.00877v1…