PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Scheduling in Generalized Switch in Heavy Traffic

Runhan Xie, Ziv Scully, Rhonda Righter, Izzy Grosof

arXiv:2609.17735v1cs.PF

TL;DR

Known-duration scheduling and mean-response-time optimality remain open problems for generalized switches, where serving the smallest jobs can leave resources unused. The paper introduces SEB, which balances duration-index buckets while prioritizing smaller ones, and proves its heavy-traffic optimality under stated assumptions.

  • Problem

    Generalized-switch policies largely target unknown job durations, leaving known-duration scheduling and mean-response-time optimality open.

    Source: §1 · p. 2

  • Method

    SEB groups jobs by priority index into buckets, balances each bucket, and gives smaller buckets priority when their preferred service option is feasible.

    Source: §5.2 · p. 15, §6 · p. 18

  • Results

    SEB is heavy-traffic optimal for load vectors approaching an interior point of a capacity-region facet under the paper’s assumptions.

    Source: §6 · p. 18

  • Takeaways & Limitations

    SEB is the first proven heavy-traffic optimal scheduling policy for multiserver systems with general service constraints.

    Source: §11 · p. 38

    The analysis assumes bounded job durations and independence between job priority index and job class.

    Source: §11 · p. 38

Abstract

from arXiv · show

The generalized switch is a highly flexible queueing model, covering multiclass, multiserver, and multiresource queueing systems as well as a wide variety of stochastic networks. Although many scheduling policies have been developed for this model, they almost entirely address unknown job duration settings. How to optimally use known job durations in the generalized switch has remained open. Moreover, optimizing mean response time remains open in both settings. We introduce the first policy to guarantee heavy-traffic optimal mean response time in the generalized switch, our Smallest Equalizing Bucket (SEB) policy. The key challenge in designing an optimal scheduling policy is that we must simultaneously prioritize small jobs and also minimize resource waste, all while fitting within the generalized switch's service options. SEB overcomes this challenge by grouping jobs into duration-based buckets and enforcing an "equalizing" service structure that keeps each bucket balanced while still prioritizing the smallest jobs. We prove SEB's heavy-traffic optimality. Simulations further confirm the effectiveness of SEB-inspired heuristics.

1. Introduction

Known-duration scheduling and mean-response-time optimality remain open in the generalized switch, where existing policies largely target unknown durations. The paper introduces SEB to balance small-job priority with resource use and outlines its analysis and simulations.

1. Introduction

  • Existing generalized-switch policies largely address unknown-duration settings, while known-duration scheduling and heavy-traffic optimal mean response time remain open.The paper proposes SEB as the first policy proved to achieve heavy-traffic optimal mean response time in the generalized switch.Source: §1 · p. 2

1.1. Challenges and Policy Intuition

  • Greedily serving the smallest jobs can leave capacity unused when their resource demands are imbalanced, so SEB balances jobs of similar priority indices and favors smaller buckets when their preferred service is feasible.SEB assigns jobs a scaled-duration priority index, partitions indices into buckets, and seeks an equalizing service option within each bucket.Source: §1.1 · pp. 2–3

1.2. Paper Outline

  • The paper reviews prior work, defines the model, develops SEB and its heavy-traffic proof, then evaluates SEB-inspired dynamic policies by simulation.Its roadmap includes stability and bucket-balance lemmas, a response-time upper bound, and the main optimality result.Source: §1.2 · p. 3

2. Prior work

Prior work studies generalized-switch scheduling and special cases, but the paper identifies a gap in known-duration scheduling and heavy-traffic mean-response-time optimality. Existing results vary by policy and model assumptions.

2.1. Generalized Switch Scheduling

  • Generalized-switch policies include MaxWeight, Randomized Timers, and MSR, but these policies do not use individual job-duration information.MaxWeight and MSR have mean-response-time results and are reported as constant-competitive.Source: §2.1 · pp. 3–4

2.1.1. Complete Resource Pooling (CRP) Condition

  • Under Complete Resource Pooling, MaxWeight exhibits one-dimensional state-space collapse and maximizes throughput and minimizes mean work in heavy traffic.Without CRP, prior work characterizes collapse to a higher-dimensional subspace and heavy-traffic stationary behavior.Source: §2.1.1 · p. 4

2.2. Scheduling in Special Cases of the Generalized Switch

  • Special-case scheduling research spans multiserver-job and compatibility models, with many compatibility results focused on load balancing or many-server limits.The paper reports no prior study of known-duration scheduling in compatibility systems.Source: §2.2 · p. 4, §2.2.2 · p. 6

2.2.1. MSJ Scheduling

  • Other MSJ policies include FCFS, ServerFilling/DivisorFilling, and backfilling variants, while general heavy-traffic optimality remains open for many policies.ServerFilling/DivisorFilling assumes job server needs divide the number of servers.Source: §2.2.1 · pp. 4–6
  • ServerFilling/DivisorFilling-SRPT policies are throughput- and heavy-traffic mean-response-time optimal for MSJ systems, but assume server needs divide the server count.This paper relaxes that divisibility assumption.Source: §2.2.1 · pp. 5–6

2.2.2. Compatibility Scheduling

  • Compatibility-scheduling studies often treat jobs as indistinguishable and establish optimality in mean-field or many-server limits, rather than studying known-duration scheduling.The paper notes that it is aware of no prior study of known-duration jobs in this setting.Source: §2.2.2 · p. 6

3. Model

The generalized switch models classes of jobs served through a finite set of service options. Its scheduling policy chooses which option to use and which jobs to serve.

3. Model

  • Each service option specifies the number of jobs from each class that can be served simultaneously, subject to a cap on jobs served.The model has n_c job classes and a service-option set R.Source: §3 · p. 6
  • Class-i arrivals are Poisson, job durations are independently sampled from class-specific distributions, and the scheduler knows each job’s class and remaining service time.Jobs may be preempted and resumed without overhead or lost work.Source: §3 · p. 6
  • Class-i load is ρ_i = λ_iE[D_i], and the system is stabilizable exactly when the arrival-rate vector lies inside the convex hull of service options.In an MSJ special case, job classes correspond to server needs and a service option cannot exceed the total server count.Source: §3 · p. 7

4. Comparison with a Resource-Pooled System

The paper constructs response-time lower bounds by mapping the generalized switch to a single-server queue, then selects mappings that become tight in the stated heavy-traffic regime. Its results use CRIB assumptions and address nonsaturated classes separately.

4. Comparison with a Resource-Pooled System

  • The proof compares a policy’s upper bound with a universal lower bound from a suitably chosen resource-pooled single-server queue.The resource-pooled queue has more service options than the generalized switch, so its SRPT mean response time lower-bounds the switch’s minimum.Source: §4 · p. 7, §4.1 · p. 8

4.1. Lower Bounds from Resource-Pooled Systems

  • A valid conversion vector scales each class’s job duration so every original service option uses at most unit pooled service capacity.For any valid vector, Theorem 1 maps every original scheduling policy to a pooled-system policy with identical mean response time, yielding an SRPT lower bound.Source: §4.1 · pp. 9–10

4.2. Tight Lower Bounds in Heavy Traffic

  • A useful lower-bound mapping must make the pooled system approach heavy traffic whenever the original system does.Different heavy-traffic load compositions can require different conversion vectors.Source: §4.2.1 · p. 10

4.2.1. Motivation and Example

  • When most load comes from class-1 jobs in the seven-server example, mapping A leaves pooled capacity unused, while mapping B saturates it for service options [3,0] and [2,1].The passage identifies B as the mapping used for this scenario’s lower bound.Source: §4.2.1 · pp. 10–11

4.2.2. Generalization

  • For each stability-region facet, the paper defines a valid conversion vector by setting its inner product with every extreme service option on that facet to one.The resulting scaled duration is the k-mapped priority index; the heavy-traffic load vectors approach an interior point of a limiting facet.Source: §4.2.2 · pp. 11–12

4.3. Setting Assumptions (CRIB)

  • The CRIB setting requires complete resource pooling, independence between job class and priority index, and bounded job durations.The paper states that CRIB still retains the central challenge of prioritizing small jobs while maintaining class balance for resource utilization.Source: §4.3 · pp. 12–13

4.4. Handling non-saturated classes

  • A class with zero mapping weight is nonsaturated in heavy traffic and has negligible mean response time; removing such classes does not change the heavy-traffic result.The analysis assumes all classes on the limiting facet are saturated, while allowing nonsaturated classes to be reintroduced under an arbitrary stabilizing policy on that facet.Source: §4.4 · p. 13

5. Our Policy: Shortest Equalizing Bucket (SEB)

SEB is designed to combine small-job priority with efficient use of generalized-switch capacity by balancing jobs in duration-based buckets. It prioritizes the smallest eligible bucket and uses geometric bucket widths to obtain heavy-traffic optimality.

5.1. What are the essential qualities of an optimal policy?

  • SEB addresses the need to prioritize small jobs without wasting capacity, which can occur when their resource demands are imbalanced.The policy aims to keep service capacity utilized while prioritizing jobs by duration.Source: §5.1 · p. 14

5.2. Intuition for our policy

  • For jobs with multiple priority indices, SEB balances each bucket separately and gives smaller-index buckets priority when their preferred service option is feasible.Buckets are disjoint intervals, and each job stays in its arrival-assigned bucket until completion.Source: §5.2 · p. 15
  • SEB uses geometric buckets whose smallest-to-largest priority-index ratio is a chosen constant, a construction shown to yield heavy-traffic optimality.The paper draws inspiration from geometric bucketing in dispatching settings.Source: §5.2 · p. 15

5.3. Defining Our Policy

  • The scheduler scans buckets in increasing priority-index order and serves the first bucket able to fulfill its ideal service option.If no bucket can fulfill its preferred option, the system idles; jobs within a class and bucket are selected FCFS.Source: §5.3 · p. 16

5.4. Basic property of SEB

  • For any workload vector not parallel to the load vector, SEB’s preferred service option has a non-vanishing drift toward the load vector.The stated proposition gives an epsilon bound independent of the workload vector.Source: §5.4 · p. 17

5.5. Further Notation

  • The paper defines k-mapped inefficiency as one minus the k-mapped service rate, and bucket-relevant inefficiency as the corresponding measure for jobs below a priority threshold.Under SEB, the threshold at a bucket boundary defines inefficiency for the first buckets.Source: §5.5 · pp. 17–18

6. Main Results and Roadmap

The paper establishes that SEB is heavy-traffic optimal under stated assumptions by comparing its response time with a resource-pooled lower bound. Its proof bounds response time by controlling when buckets can waste service capacity.

6. Main Results and Roadmap

  • SEB converges to optimal as the load vector approaches a capacity-region point in the interior of a facet, under the stated assumptions.The paper identifies this as the first heavy-traffic optimality result for the generalized switch under the CRIB assumption.Source: §6 · p. 18
  • With bounded priority indices, resource-pooled PSJF-1 is also heavy-traffic mean-response-time optimal.The SEB response-time characterization compares against resource-pooled PSJF-1, with bucket-width multiplier c.Source: §6 · p. 19

6.1. Roadmap to Mean Response Time Optimality

  • The proof bounds the chance that a bucket with substantial work is ineligible for service by showing work drifts toward a cone and large in-cone workloads are service-eligible.State-space collapse supplies the bound on work far from the cone; combining bounds compares SEB response time with the resource-pooled system, which is a lower bound on optimal response time.Source: §6.1 · pp. 20–21

7. SEB Analysis: Stability and Balancing Each Bucket

The analysis formalizes bucket balance using a cone around the load vector, then uses drift and Lyapunov arguments to establish stability and bucket state-space collapse. Each bucket’s work vector converges to the same cone under SEB.

7.1. Defining the Cone-based State-space Collapse

  • Because arrivals to each bucket have load parallel to the system load vector, bucket work drifts toward a cone around that vector rather than collapsing to the vector itself.The parallel-load property follows from the assumption that job class and priority index are independent.Source: §7.1 · p. 21

7.2. Stability

  • The stability proof uses a Lyapunov function combining distance from the cone with total work, using arrival drift and service eligibility for large in-cone buckets.When a bucket has sufficiently large work and lies in the cone, it can fulfill a service option; the policy then provides full-capacity service.Source: §7.2 · p. 22

7.3. Bucket State-space Collapse

  • Under SEB, each bucket’s work vector collapses to the common cone around the load vector.The paper develops a continuous-time state-space-collapse theorem using the Rate Conservation Law, then applies it to the bucket work vectors.Source: §7.3 · pp. 22–23

8. SEB Analysis: Mean Response Time

The analysis bounds SEB’s mean response time by controlling service waste and comparing its performance with resource-pooled single-server policies. It establishes heavy-traffic optimality under the stated assumptions.

8.1. Bounding Waste

  • Cone state-space collapse makes waste small when workload is in or near the cone, enabling bounds on per-bucket work and response time.Source: §8.1 · p. 24

8.2. Bounding Mean Response Time

  • The mean-response analysis bounds waiting through expected work in each bucket, incorporating waste bounds and resource-pooled PSJF-1 response time.Source: §8.1 · p. 24, §8.2 · p. 27

8.3. Heavy-traffic Optimality

  • SEB is heavy-traffic optimal as the load vector approaches any capacity-region point in a facet’s interior, under the assumptions in Sections 4.3 and 4.4.Source: §8.3 · p. 28

9. Practical variant: Dynamic SEB

Dynamic SEB variants address Static SEB’s idling at practical loads by using nested buckets based on remaining priority indices and relaxing its equalizing-service requirements.

9. Practical variant: Dynamic SEB

  • Static SEB may idle nonempty buckets at practical, underloaded loads, motivating three dynamic variants intended to improve its performance.Source: §9 · p. 29
  • Dynamic buckets are nested and constructed from jobs’ remaining priority indices, preserving priority for smaller-index jobs while reducing idling from sparse buckets.Source: §9 · p. 29
  • Dynamic SEB-best seeks the preferred equalizing option, good-enough accepts an option with non-vanishing drift, and any takes the first feasible facet option without equalizing.Source: §9 · pp. 29–30
  • If no sufficiently equalizing option is feasible across the dynamic buckets, the fallback selects any feasible option maximizing total mapped service rate.Source: §9 · p. 30

10. Numerical Evaluation via Simulation

Simulations find that dynamic SEB policies outperform benchmark policies across compatibility, multiserver-job, and multiresource-job settings. The evaluations compare these policies across system loads and against reference lower bounds.

10.1. Benchmark Policies

  • The evaluations compare dynamic SEB with adapted prior policies and use multiserver-SRPT as a tighter but unattainable reference lower bound.The authors do not use resource-pooled SRPT as the experimental reference because it is significantly more optimistic across practical load regimes.Source: §10.1 · pp. 31–32

10.2. Evaluation of compatibility scheduling

  • In both compatibility settings, dynamic SEB policies outperform all benchmarks across loads; SEB-any closes more than 70% of the gap under most loads.In the two-server case, SEB-best and good-enough each close more than 40% of gaps under most loads; in the three-server case, gap closure increases with load.Source: §10.2 · pp. 33–34

10.3. Evaluation of multiserver-job scheduling

  • In the two-class MSJ setting, dynamic SEB closes around 50% of the gap to MaxWeight-Queue SRPT at high loads, while in the three-class setting its best and good-enough variants regain advantages as load rises.In the two-class setting, SEB policies gain an advantage over serverFilling-SRPT as load increases; in the three-class setting, serverFilling-SRPT and MaxWeight-Queue SRPT are slightly better at moderate loads.Source: §10.3 · p. 36

10.4. Evaluation of multiresource-job scheduling

  • In the MRJ setting, all dynamic SEB policies outperform benchmarks across loads, and SEB-best and good-enough outperform SEB-any at high loads.SEB-best and good-enough have nearly identical response times across most evaluated loads.Source: §10.4 · pp. 37–38

10. Numerical Evaluation via Simulation

  • Dynamic SEB policies outperform benchmark policies across compatibility, MSJ, and MRJ settings over a wide range of loads, often by substantial margins.The paper reports this as the overall pattern across the evaluated special cases.Source: §10 · p. 31, §10.4 · p. 38

11. Conclusion

The paper introduces Smallest Equalizing Bucket (SEB), proves it heavy-traffic optimal, and proposes dynamic SEB policies evaluated by simulation. Its assumptions include bounded job durations and independence between job priority index and class.

11. Conclusion

  • SEB is presented as the first proven heavy-traffic-optimal scheduling policy for multi-server systems with general service constraints.The policy balances prioritizing small jobs with keeping servers busy.Source: §11 · p. 38
  • The authors propose three dynamic SEB policies and report excellent simulation performance.The conclusion identifies prioritizing small jobs while keeping servers busy as central to SEB's design.Source: §11 · p. 38
  • The analysis assumes bounded job-duration distributions and independence between job priority index and job class.The authors identify designing and analyzing a good policy without these assumptions as future work.Source: §11 · p. 38

A.1. Proof of Proposition 2

The proof uses a Lyapunov argument to control bucket work and establish negative drift outside a compact set. It connects bucket eligibility to the geometry of bucket work vectors and concludes via stationary expectations and Little’s law.

A.1. Proof of Proposition 2

  • The proof takes stationary expectations and invokes Little’s law to complete the proposition’s argument.The passage identifies these as the final steps of the proof.Source: §A.1 · p. 42
  • When total work is large and every bucket work vector is close enough to the cone, at least one bucket is eligible for service.The proof's lemma establishes this eligibility condition.Source: §A.1 · p. 42
  • The proof applies the continuous-time Foster-Lyapunov theorem by constructing a differentiable, nonnegative Lyapunov function with bounded drift on a compact set and negative drift outside it.The function combines the total distance of bucket work vectors to cones with total system work.Source: §A.1 · p. 44
  • The proof shows that the Lyapunov drift is at most -1 outside the compact set in the cases it analyzes.The derivation separates cases according to bucket distance from the cone and whether a bucket is in service.Source: §A.1 · pp. 47–48

A.3. Proof of Theorem 5

These appendices prove theorems and lemmas supporting the paper’s state-space-collapse analysis and compare SEB with a single-server PSJF policy.

A.3. Proof of Theorem 5

  • Theorem 5’s proof applies rate conservation under drift and exponential-increment conditions, then takes n→∞ using monotone convergence.Source: §A.3 · pp. 49, 51

A.4. Proof of Theorem 6

  • Theorem 6 states that, for any bucket i, the SEB policy yields state-space collapse when the assumptions in Section 4.3 are met.The proof analyzes drift separately in pure work-accumulation mode, where the bucket receives no service, and service mode, where all servers work on it.Source: §A.4 · pp. 51–52

A.5. Proof of Theorem 7

  • Theorem 7’s stated condition allows any service option in RF to be fulfilled using jobs from bucket i.Its proof invokes a lemma relating ℓ1 and ℓ∞ norms for workload vectors in cone C.Source: §A.5 · pp. 54–55

A.6. Proof of Lemma 2

  • The Lemma 2 proof uses ℓ1 linearity to locate the minimum under a fixed-norm constraint in its cone-distance argument.Source: §A.6 · p. 55

A.7. Proof of Lemma 4

  • The Lemma 4 proof applies WINE to jobs waiting to enter service, retaining their original priority indices until they receive service.Source: §A.7 · p. 56

A.8. Proof of Proposition 4

  • Proposition 4’s proof bounds the first two E[W_M/G/1] terms by cE[T_PSJF-1] and completes the comparison using bounds for T1 and T2.Source: §A.8 · pp. 57–58
Loading 2609.17735v1…