PaperlayerView exact revision on arXiv

Source-linked AI summary

DART: Aiming for Tail-Delay Control in Reconfigurable Networks

Hossein Mohammadalizadeh, Holger Karl

arXiv:2609.01071v1cs.PF

TL;DR

High-percentile delay control in reconfigurable networks requires jointly choosing targets, routes, and service at intermediate configurations under stochastic, asymmetric switching times. The paper introduces DART, which commits to a target while serving traversed configurations only when weighted delay or backlog justifies it. Across six stress topologies, DART achieves the lowest P99 sojourn time in every case, up to 23% below the strongest baseline.

  • Problem

    Tail control is challenging because rarely served or pass-through configurations accumulate long-waiting jobs, coupling target, path, and intermediate-service decisions.

  • Method

    DART commits to a target using current system information, follows a path toward it, and opportunistically serves intermediate configurations when delay or backlog guards justify pausing.

  • Results

    DART achieves the lowest P99 sojourn time on all six evaluated graphs, up to 23% below the strongest baseline.

  • Takeaways & Limitations

    Combining commitment, leave-time awareness, and selective en-route service controls the weighted tail across varied configuration topologies and reconfiguration times.

Abstract

from arXiv · show

Many systems serve different job classes by switching among configurations. Often, reconfiguration takes a stochastic amount of time that depends on direction and can differ in distribution between configurations. Reaching a target configuration may require crossing intermediate ones. Under a high-percentile delay objective, rarely served or pass-through configurations accumulate the long-waiting jobs that dominate the sojourn-time tail. Controlling that tail couples three decisions: which target to choose, which path to take, and whether and how many jobs to serve at the configurations crossed on the way. We introduce DART, an opportunistic commitment policy that commits to a target configuration to avoid myopic detours while serving a traversed configuration only when its weighted delay or backlog justifies the pause. We show how these decisions shape the weighted sojourn-time tail. Across six stress topologies, each isolating a different tail-control challenge, DART achieves the lowest P99 sojourn time in every case, up to 23% below the strongest baseline. The advantage holds under heterogeneous, heavy-tailed, and asymmetric reconfiguration times.

I. INTRODUCTION

Configuration switching couples target selection, route selection, and decisions about serving intermediate configurations. DART uses opportunistic commitment to control weighted sojourn-time tails while avoiding myopic detours.

  • Motivation: Stochastic, asymmetric reconfiguration times can make an indirect route faster on average than a direct move.The route through an intermediate configuration may reduce reconfiguration time but delay service at the final target.
  • Problem formulation: The problem couples choosing a target, selecting a path, and deciding whether and how many jobs to serve at intermediate configurations.These decisions arise because intermediate configurations have their own waiting jobs and contribute to the tail.
  • Motivation: High-percentile sojourn time is dominated by jobs accumulating at rarely visited or pass-through configurations.Balancing weighted waiting across classes requires deciding whether and how much to serve along the chosen path.
  • DART: DART chooses a target using current waiting jobs, holding costs, service rates, and reconfiguration times, then commits to a path while remaining opportunistic en route.At intermediate configurations, its service rule decides whether to stop and how many jobs to serve before continuing.
  • Evaluation: DART attains the lowest P99 sojourn time in every evaluated case, up to 23% below the strongest baseline.The evaluation varies configuration graphs, reconfiguration times, and holding costs; the reported results assume each job class has one serving configuration.

III. SYSTEM MODEL

The paper models network reconfiguration as polling on a strongly connected directed configuration graph with pair-dependent stochastic reconfiguration times. Shortest paths are defined by expected reconfiguration duration, while variability still affects waiting.

  • Configuration and service model: Each configuration serves one job class with Poisson arrivals, exponential service, an unbounded FCFS buffer, and a positive holding-cost rate.At most one configuration is active at a time.
  • Configuration graph: The configuration graph is directed and strongly connected, with each edge carrying a positive reconfiguration time of arbitrary distribution and finite mean.Not every configuration pair must have a direct edge.
  • Configuration graph: Reconfiguration-time means may be asymmetric and need not satisfy the triangle inequality.An indirect route can therefore have lower total expected time than a direct edge.
  • Routing: For each current-target pair, the forwarding table returns a shortest directed path and its expected duration.Path duration is computed by summing edge means, although realized variability can lengthen waiting elsewhere.

C. System Dynamics

The system evolves through arrivals, service completions, and reconfiguration completions, with a policy choosing actions from the current location, backlogs, and operating mode. Stability requires sufficient total and per-configuration service.

  • State and events: The state records the backlog vector, current configuration, and whether the system is serving, reconfiguring, or idle.Events change the state between periods of service or transit.
  • Policy actions: When active at configuration i, a policy may serve its head-of-line job, remain idle if the queue is empty, or select a target and reconfiguration path.Actions are selected after reconfiguration completion or when service leaves the system idle.
  • Stability: A stable policy must allocate enough time for both job service and reconfiguration.The aggregate condition is necessary but not sufficient for stability.
  • Stability: Each configuration must receive a service fraction exceeding its load to keep its backlog bounded.The per-configuration margin complements the aggregate time condition.

D. Performance Objective

The objective is to keep the system stable while minimizing high-percentile weighted sojourn times across classes. DART addresses this objective through opportunistic commitment and state-dependent intermediate service, while remaining a heuristic.

  • Objective: Weighted sojourn time is a job’s sojourn time multiplied by its configuration’s holding-cost rate.The system-wide objective uses a percentile of these weighted times.
  • Objective: A good policy keeps the system stable and high-percentile weighted sojourn times small across all classes.The next section develops DART for this objective.
  • DART: DART turns opportunistic commitment into a decision rule intended to control the weighted tail.The policy section develops the rule and explains its tail-control rationale.
  • Scope: DART is a heuristic because optimal-policy computation is intractable and the objective depends on future arrivals and realized reconfiguration times.The state space grows exponentially in N, and the related asymmetric ordering problem is NP-hard.

A. Policy Design

DART chooses a committed target using anticipated delay and reconfiguration costs, then follows a shortest path while opportunistically serving intermediate configurations when delay or backlog warrants it.

  • Target selection: The policy commits to the highest-urgency target and follows a shortest path to it, avoiding repeated target changes and myopic detours.The target remains fixed until reached, after which DART serves one job and makes a new decision.
  • Target selection: DART selects a nonempty target by ranking anticipated delay against the expected times to reach and leave each candidate.Anticipated delay combines head-of-line age with an estimate of the time needed to clear the remaining backlog.
  • En-route service: A skipped intermediate configuration may wait at least d + r before the system reaches the target and later returns, with detours or extra service making the wait longer.This lower bound motivates protecting an old head-of-line job from being skipped indefinitely.
  • En-route service: At an intermediate configuration, DART serves jobs only when either the delay guard or backlog guard justifies pausing before continuing toward the target.The delay guard accounts for the wait caused by skipping the configuration, while the backlog guard compares weighted service pressure with target pressure.
  • Policy parameters: The policy uses α to discount the time to leave a configuration and β to weight the delay caused by skipping it against its current age.Together, the rules choose the target and determine whether and how many jobs to serve at intermediate configurations.

B. Structural Properties

The weighted sojourn-time tail at a configuration is shaped by residual backlog, time until the next visit, and arrivals during that absence; DART directly controls the first two.

  • Structural properties: The tail depends on residual backlog left at a configuration, inter-visit time, and arrivals during that time.DART acts directly on residual backlog and inter-visit time, while arrivals are exogenous.

1) Eligibility:

DART prevents starvation by ensuring every nonempty configuration eventually becomes eligible and every committed trip reaches its target in finite time.

  • Eligibility: A nonempty unserved configuration's urgency eventually overtakes any finite competing urgency because its head-of-line age grows at rate wj/∆.Weights and reconfiguration times affect the threshold, but not eventual eligibility.
  • Eligibility: The wait until a configuration is selected is finite because its urgency grows without bound while it remains nonempty and unserved.Once its head-of-line age exceeds the finite threshold ∆H/wk, it becomes the urgency maximizer.
  • Inter-visit time: Commitment keeps the selected configuration as the target until reached, so the trip follows a finite shortest path with only finite intermediate service.Since service drains work faster than arrivals and intermediate batches are capped, the travel time is finite.
  • Inter-visit time: Both selection and travel times are finite, so every configuration is eventually revisited and no configuration is starved.This finiteness supports the subsequent tail decomposition.
  • Departure bound: When DART leaves an intermediate configuration, its residual backlog is bounded by the destination-dependent threshold B_kj⋆.A larger backlog would trigger service before departure; the delay guard also prevents leaving a sufficiently old head-of-line job behind.

4) Sojourn-time tail:

The sojourn-time tail is decomposed into residual backlog, absence duration, and arrivals during absence, with DART controlling the first two and the arrival process controlling the third.

  • Backlog decomposition: A job arriving during an absence sees residual backlog from the last departure plus arrivals accumulated since that departure.The arrival count over the absence interval is determined by the exogenous arrival process.
  • Backlog decomposition: The backlog tail has three possible causes: large residual backlog, a long absence from the configuration, or many arrivals during a fixed window.A window length θ separates the absence-time effect from the arrival-count effect.
  • Tail control: For each configuration, the weighted tail follows by applying the sojourn-time bound at threshold z/wk, and the system-wide tail is bounded by summing configuration-level tails.The finite number of configurations preserves the same three tail components at the system level.
  • Tail control: DART controls residual backlog through its departure guards and absence duration through finite inter-visit times, while the arrival process determines arrivals during absence.This links the structural bounds to the weighted sojourn-time tail.

V. EVALUATION

The evaluation tests weighted P99 sojourn time across six stress topologies using common simulation conditions, paired comparisons, and fixed policy parameters. It separately reports high- and low-priority classes because policies may protect one class while allowing the other’s tail to grow.

  • Evaluation design: Six stress topologies test distinct tail-control challenges, with three baselines sharing DART’s routing and service capabilities.One parameter set is fixed across all graphs.
  • Simulation model: Simulations use Poisson arrivals, independent exponential service times, and FCFS non-preemptive service.All results come from a discrete-event simulator.
  • Metrics: The primary metric is system-wide weighted P99 sojourn time, with results also reported separately for high- and low-priority configuration classes.Separating classes exposes cases where a policy protects one class while the other develops a tail.
  • Statistical protocol: 16 independent replications support each point, using 95% confidence intervals and paired per-replication significance tests under shared arrival and service draws.Topology loads range from about 0.80 to 0.96, near the stability limit where tail control is hardest.

B. Stress Topologies and Reconfiguration Times

The stress suite varies topology structure, reconfiguration-time distributions, and routing challenges to test DART’s target, path, and en-route service decisions. Baselines receive matched graph-distance treatment and an adjusted transit-service variant for fair comparison.

  • Stress topologies: Six topologies exercise target selection, path choice, and en-route service, with nodes labeled by holding-cost weight and arrival rate and µ_i = 1.Each topology isolates one difficulty in tail control.
  • Reconfiguration times: Topologies A–C are single-path graphs with exponential edge times, while D–F are multipath graphs using role-matched distribution families.D–F can combine up to four families, and τ_ij may differ from τ_ji without changing edge means.
  • Single-path tests: A tests protecting both line ends without starving the middle; B increases load so intermediate configurations cannot be skipped and isolates en-route service.B specifically tests the en-route service rule in eq. (11).
  • Single-path tests: C tests whether the policy accounts for a long return edge before leaving a dominant configuration, using the leave penalty α d(j, i).The only return path is long, so frequent returns can starve the rest of the line.
  • Multipath tests: D and E require asymmetric multipath routing, while F combines dominant-backlog, long-return, asymmetric-route, and parallel-path difficulties.E is the larger graph with longer paths.
  • Multipath tests: D–F use heavy-tailed Lomax return edges with κ = 3, while shortest routes can sometimes avoid those edges.κ = 3 gives finite variance for stable weighted-P99 estimation.
  • Baselines and fairness: Tian and DVO are compared with a fair transit-service variant, and all policies use matching shortest-path distances for reach and return.Tian-T serves crossed configurations when weighted backlog meets its transit threshold.
  • DART configuration: DART uses α = 0.5 and β = 6 across all graphs rather than graph-specific tuning.The delay guard is intended to protect intermediate configurations strongly, and performance remains stable over a range of β.

D. Tail Performance

DART achieves the lowest system-wide weighted P99 across the six evaluated topologies, with its strongest gains where return times, transit service, and routing choices jointly stress tail control. The results show that DART reduces the pooled upper tail by balancing class-specific delays, especially near saturation.

  • System-wide tail performance: DART has the lowest system-wide weighted P99 on all six graphs and wins significantly on five; the sixth is a tie with DVO.DVO is the strongest baseline on A, C, D, and E, while Tian-T is strongest on F.
  • Tail distribution: DART’s complementary CDF has the lightest upper tail, although its median is not lowest because it gives more service to high-priority configurations.The curves are close through the body and separate in the upper tail, especially on C and F.
  • Class-tail balance: DART lowers the pooled P99 by keeping low-priority tails low while maintaining high-priority performance near the best baseline.Its en-route guards accept some high-priority delay when that removes many low-priority jobs from the pooled distribution’s extreme upper tail.
  • Load and tuning robustness: As offered load approaches saturation on F, DART separates from the baselines and reaches 442s versus 575s for the best baseline and 812s for the weakest.At ρ = 0.6, the policies are within a few percent; the gap opens near ρ = 0.94 as backlog and the tail grow.
  • Load and tuning robustness: Across every topology, the full DART tuning range exceeds Tian-T’s range in weighted-P99 reduction against Tian K = 4.DART’s β trades delay between high- and low-priority jobs, while Tian-T’s η is swept as its own tuning parameter.

VI. CONCLUSION

DART frames reconfigurable-network tail control as a path-level problem and combines commitment with selective en-route service. This prevents intermediate configurations from accumulating enough weighted delay to dominate pooled P99.

  • DART treats network reconfiguration as a path-level delay-tail control problem.
  • Figure 10 measures DART’s margin over the best baseline across weight dominance and reconfiguration asymmetry, with blue indicating a win.
  • The policy combines commitment, leave-time awareness, and selective en-route service.These choices address both target commitment and whether to pause at crossed configurations.
  • Intermediate configurations do not accumulate enough weighted delay to dominate the pooled P99.
Loading 2609.01071v1…