PaperlayerView exact revision on arXiv

Source-linked AI summary

Approaching Optimal Scaling of Queue Size for an Input-Queued Switch

Taha Ameen, Weina Wang

arXiv:2610.37521v1cs.PFmath.PR

TL;DR

The paper addresses the conjectured O(n/(1−ρ)) scaling of expected total queue length in an input-queued switch. It develops a k-level batching policy and shows that its queue-size bound can approach the conjectured scaling as k increases.

  • Problem

    The expected total queue-length scaling is conjectured to be O(n/(1−ρ)), up to logarithmic factors, with ρ denoting system load.

    Source: §1 · p. 2

  • Method

    The paper develops a family of k-level batching scheduling policies for the input-queued switch.

    Source: §1.1 · p. 3, §3 · p. 6

  • Results

    For ε≤n^-c, a suitable k puts expected queue size within O(ε^-δ) of the lower bound n/ε for any fixed δ>0.

    Source: §3 · p. 7

  • Takeaways & Limitations

    As k grows, the denominator exponent approaches 1, bringing the bound arbitrarily close to the conjectured scaling.

    Source: §1.1 · p. 4

    The analysis considers the joint limit n→∞ and ρ→1, without constraining the rate at which ρ approaches 1.

    Source: §2 · p. 5

Abstract

from arXiv · show

We study the scaling of the expected total queue length in an $n\times n$ input-queued switch. It has been conjectured that the optimal scaling is $O(n/(1-\rho))$, up to logarithmic factors, where $\rho$ is the system load. This conjecture has been established in the traditional heavy-traffic regime and in certain sub-regimes of the large-system regime. But it remains unresolved over a wide range of load scalings in the large-system regime. In this paper, we develop a family of scheduling policies parameterized by a positive integer $k\ge 2$. We show that under uniform traffic, our policy achieves an expected total queue length of $O\bigl({n\log\max\{n,1/(1-\rho)\}}\big/{(1-\rho)^{2^k/(2^k-1)}}\bigr)$, as long as $\rho\to 1$ in the large-system regime. As $k$ increases, the exponent $2^k/(2^k-1)$ approaches $1$, bringing our bound arbitrarily close to the conjectured scaling. The expected amortized scheduling cost of the policy is $O(n^3 k)$ per time slot. Our policy is of a batching type, with a novel recursive design that allows an arbitrary number of batching levels. This design principle may also be useful for other scheduling problems in which combinatorial constraints restrict which jobs can be served simultaneously.

1 Introduction

An input-queued switch schedules jobs subject to matching constraints, but the optimal scaling of its expected total queue length remains less understood. The conjectured scaling is linear in n, up to logarithmic factors, and the intermediate high-load range in the large-system regime remains unresolved.

1 Introduction

  • The conjecture is O(n/(1−ρ)) expected total queue length, up to logarithmic factors, where ρ is system load.It is expected to hold both when n is fixed and ρ→1 and when n→∞ with ρ scaling with n.Source: §1 · p. 2
  • An n×n input-queued switch has n² queues but only 2n input and output resources, motivating queue scaling linear in resources rather than queues.Under uniform traffic, this conjecture implies mean job delay O(1/(1−ρ)), up to logarithmic factors.Source: §1 · pp. 2–3
  • Matching constraints can leave backlogged input ports idle, unlike an idealized system with independent input service, making the conjectured queue scaling challenging.In that idealized system, uniform traffic gives expected total queue length O(n/(1−ρ)).Source: §1 · p. 3
  • The conjectured scaling has been established in traditional heavy traffic, while large-system results cover fixed load and the range 1/(1−ρ)≥n².Prior large-system bounds include O(n) for ρ<1/2 and O(n log n/(1−ρ)²) for fixed ρ<1.Source: §1 · p. 3
  • For 1/(1−ρ)→∞ with 1/(1−ρ)=o(n²), no existing policy is known to achieve the conjectured scaling.The large-system conjecture had been resolved at the fixed-load and very-high-load ends, but not across this intermediate range.Source: §1 · p. 3

1.1 Our result

The paper develops k-parameterized scheduling policies that make progress toward the conjectured queue-size scaling. Their recursive batching design permits arbitrarily many batching levels, with the bound approaching the conjectured scaling as k grows.

1.1 Our result

  • The denominator exponent is 4/3 for k=2 and 8/7 for k=3, and approaches 1 as k increases, bringing the bound arbitrarily close to the conjectured scaling.The stated result applies under uniform traffic when 1/(1−ρ)→∞.Source: §1.1 · p. 4

1.2 Policy design

  • Unlike earlier batching refinements that start service earlier within a window, the policy uses a recursive design with an arbitrary number of batching levels.Earlier work refined batching by starting service before the window ended.Source: §1.2 · p. 4
  • The policy shortens the initial batching window, then pools jobs left unserved at one level into larger blocks for higher-level service.Higher-level jobs experience longer delays, but their fraction progressively decreases.Source: §1.2 · p. 4
  • For fixed ρ<1, virtual-job load inflation yields a queue-length scaling of O(n(log n)(log log n)²).The construction inflates the load to ρ′ with 1/(1−ρ′)=log log n before applying the result.Source: §1.2 · p. 4
  • Randomly assigning a small fraction of arrivals to intermediate levels helps ensure enough perfect matchings can be formed at each level.The analysis combines this randomness with structural properties of residual jobs.Source: §1.2 · p. 5

2 Problem setup

The setup models an n×n switch with a separate queue for every input–output pair and matching-constrained service. It studies expected total queue size as n and load ρ jointly approach their limits.

2 Problem setup

  • Each input–output pair has its own queue, and a job requires one service slot before leaving.The switch operates in discrete time.Source: §2 · p. 5
  • A feasible schedule is a matching: each input and each output can participate in at most one selected queue per slot.The schedule indicator σij(t) specifies whether queue (i,j) is selected.Source: §2 · p. 5
  • Within each slot, the scheduler observes queue lengths, then arrivals occur, and selected jobs are served.The queues start empty, and the target quantity is expected total queue size.Source: §2 · p. 5
  • The scaling regime takes n→∞ and ρ→1 jointly, without constraining how quickly ρ approaches 1.The excess capacity is ε=1−ρ and satisfies ε=o(1).Source: §2 · p. 5
  • A job set can be represented as a bipartite multigraph, with jobs as edges and feasible schedules as matchings.Parallel edges represent distinct jobs in the same queue.Source: §2 · p. 6

3 Main result and scheduling policy

The k-level batching policy approaches the conjectured queue-size scaling as the number of levels grows. Its recursive service schedule batches jobs across nested time blocks, while randomized initial levels help keep higher-level batches balanced.

3 Main result and scheduling policy

  • The policy uses nested time blocks; at each of the first k−1 levels it serves an s-factor with s perfect matchings and passes leftovers onward, while the last level queues matchings in first-come, first-served order.Source: §3 · p. 6, §3.1 · p. 8
  • The exponent 2^k/(2^k−1) approaches 1 as k grows, and polynomial decay of ε lets the logarithmic factor be absorbed into a small power of 1/ε.Source: §3 · p. 6
  • O(ε^-δ) factor of the n/ε lower bound is achievable when ε ≤ n^-c, for any fixed δ > 0, with a suitable choice of k.The constants in the stated bound depend on δ and c.Source: §3 · pp. 6–7

3.1 The k-level batching policy

  • A small random fraction of arrivals starts at intermediate levels to keep higher-level batches suitably spread and support forming enough perfect matchings.Source: §3.1 · p. 7
  • Jobs become eligible in a later block at their level, and any unserved batch is promoted after that level’s final service slot.Jobs that reach level k are served through a queue of matchings.Source: §3.1 · pp. 7–8
  • O(n^3 k) is the expected amortized scheduling cost per time slot.Each level has amortized cost O(n^3) per time slot.Source: §3.1 · p. 9

4 Proof of Theorem 1 when k = 3

The three-level proof bounds the expected number of jobs at each level and combines those bounds to complete Theorem 1 for k = 3.

4 Proof of Theorem 1 when k = 3

  • The three-level analysis uses service-slot allocations S1 = ρT1 − a1, S2 = L2a1 − a2, and S3 = εT3 + L3a2.The proof bounds the number of unserved jobs separately at each level before combining the bounds.Source: §4 · p. 10

4.4 Completing the three-level proof

  • Each level contributes O(nhε^-8/7) in expected jobs, uniformly over time, completing the proof of Theorem 1 for k = 3.The analysis sums the three level-specific bounds.Source: §4 · p. 10, §4.4 · p. 15

4.1 Analysis of level-1 jobs

  • At level 1, the expected number of jobs is at most 2nρT1, and the analysis separately bounds jobs that proceed to level 2.The bound counts arrivals from at most the current and preceding level-1 blocks.Source: §4.1 · pp. 10–11

4.2 Analysis of level-2 jobs

  • The expected number of level-2 jobs is at most 4nL2a1, using the level-1 bound across the current and preceding level-2 blocks.The proof bounds level-2 jobs by counting jobs that entered level 2 across at most 2L2 level-1 blocks.Source: §4.2 · p. 11

4.3 Analysis of level-3 jobs

  • Level-3 jobs include those awaiting matching formation and those already queued, so the proof controls matching arrivals and the queue of matchings.The matching queue receives batches from earlier level-3 arrival blocks and is served during level-3 service slots.Source: §4.3 · pp. 13–14

5 Proofs of supporting lemmas for Section 4

The supporting proofs establish factor existence and control leftover jobs through randomized initial levels, arrival fluctuations, and bounds on idle service.

5 Proofs of supporting lemmas for Section 4

  • Randomized initial levels support s-factor existence at each level below the last, while a separate lemma controls fluctuations in leftover jobs at their ports.These are the two shared ingredients used across the level-by-level proofs.Source: §5 · p. 15

5.1 Proofs for level-1 jobs

  • At level 1, degree and cut conditions let the proof apply the factor lemma to obtain an S1-factor with high probability.The resulting failure probability is bounded using Chernoff bounds, a union bound over ports, and the factor lemma.Source: §5.1 · p. 16

5.2 Proofs for level-2 jobs

  • For level 2, expected idle service satisfies E[F2] ≤ a2, and the expected number of jobs entering level 2 is at most 2na2.The factor-test failure bound is used to control idle service slots before bounding leftover jobs.Source: §5.2 · p. 18

A Proofs of technical lemmas

The technical appendix supplies concentration bounds, graph-factor criteria, matching decompositions, and fluctuation estimates used in the proof.

A.1 Chernoff bounds

  • Chernoff bounds provide lower-tail and two-sided deviation estimates for sums of independent Bernoulli variables.The appendix applies these estimates in the theorem proof.Source: §A.1 · p. 21

A.2 Factors and decompositions into matchings

  • An s-factor exists exactly when the stated cut inequalities hold, and a graph of maximum degree M decomposes into M matchings.An s-regular graph decomposes into s perfect matchings, allowing an s-factor to be served in s slots.Source: §A.2 · pp. 21–22

A.3 Matching arrivals and service slack

  • The maximum port-arrival fluctuation and idle service together yield a matching-arrival variance bound of 34Th.The appendix combines the fluctuation estimate with the contribution from failed tests to obtain the mean, variance, and service-slack bounds.Source: §A.3 · pp. 24–25

B Proof for general k

For fixed k, the general proof bounds the total queue by summing contributions from the k job levels.

B Proof for general k

  • The proof fixes k ≥ 2 and bounds the number of jobs at each level, then the jobs from each arrival block that enter higher levels.The constants in O_k(·) may depend on k, but not on n, ρ, or time.Source: B Proof for general k · p. 25

B.1 Parameters and notation

  • The level counts Xj(t) partition the jobs present, and their sum gives the total queue QΣ(t).The proof aims to bound each of the k contributions separately.Source: §B.1 · p. 26
  • Each level contribution is bounded by O_k(nhε^-αk).This bound is stated for each contribution to the total queue.Source: §B.1 · p. 26

B.2 Analysis of level-1 jobs

The level-1 analysis carries forward its graph definitions and earlier bounds, then adapts the edge-distribution and failure-bound argument to the level-1 parameters. The resulting estimate also covers k = 2.

B.2 Analysis of level-1 jobs

  • The definitions of G1, F1, R1, J1, and D(v), along with the bounds in Lemmas 1–3 and identity (13), are retained.R1 now also includes jobs that started above level 1.Source: §B.2 · p. 26
  • The edge-distribution and failure-bound argument replaces θ with τ1 and the mean degree with µ1 = ρT1 − m1.Lemma 18 supplies the factor-test and concentration inequalities used in the revised argument.Source: §B.2 · p. 26
  • The final estimate T1e−40h ≤ a1 follows as before and also covers k = 2, when τ1 = m1 = 0.The estimate follows from (34) and 1 < αk ≤ 4/3.Source: §B.2 · p. 26

B.3 Analysis of level-j jobs, 2 ≤j < k

For intermediate levels, the analysis proceeds by induction, bounding the level-j population and the failures that leave service slots idle. Factor tests use jobs starting at level j together with degree balance to handle lower-level failures.

B.3 Analysis of level-j jobs, 2 ≤j < k

  • Induction bounds the number of level-j jobs using the preceding level's Jj−1 bound; for k = 2, there are no intermediate levels.Jobs counted for a slot arrived during the current or preceding level-j block and belong to the corresponding Rj−1 graph.Source: §B.3 · p. 27
  • Jobs starting at level j provide edges across input–output pairs; with degree balance, they ensure an Sj-factor with high probability, including when lower-level services fail.The argument combines degree and cut events with success at lower levels to imply an Sj-factor.Source: §B.3 · p. 27
  • The level-j residual graph Rj includes jobs promoted from level j and jobs that started above level j, and subsequent service does not remove them from the graph.The residual count uses arrivals and the jobs removed by service at levels 1 through j.Source: §B.3 · p. 28

B.4 Analysis of level-k jobs

The level-k analysis treats matchings formed from each arrival block as arrivals to a queue, with fixed level-k service between additions. It bounds the jobs waiting for batching and those already in the matching queue.

B.4 Analysis of level-k jobs

  • Matchings formed from jobs reaching level k in each arrival block are added to a queue at a fixed offset, followed by Sk service slots before the next addition.The queue evolves from an empty switch with no other additions between successive blocks.Source: §B.4 · p. 28
  • The level-k job count is bounded by combining jobs awaiting addition to the matching queue with jobs already in that queue.The waiting jobs are drawn from the current or preceding level-k block; each queued matching contains at most n jobs.Source: §B.4 · pp. 28–29
  • A scalar queue bound uses the variance of matching arrivals and the service slack δk = Sk − E[Ak] to bound the expected queue of matchings.The argument uses qk ≤ Var(Ak)/(2δk) + δk/2, alongside bounds on matching arrivals and service slack.Source: §B.4 · p. 29

B.5 Completing the proof for general k

The appendix completes the fixed-k proof by combining the level-wise bounds and verifying the parameters required by the factor tests. Its supporting arguments establish parameter feasibility and bound intermediate-level failures.

B.5 Completing the proof for general k

  • The level-wise bounds combine to prove Theorem 1 for every fixed k ≥ 2.The intermediate-level sum is empty when k = 2.Source: §B.5 · pp. 29–30

B.6 Supporting proofs for general k

  • The supporting proofs follow the level order and begin by verifying the parameter bounds used in factor tests.The appendix then treats parameter validity and the intermediate-level job bounds.Source: §B.6 · p. 30

B.6.1 Parameters for the factor tests

  • For sufficiently large n, the initial-level distribution is valid, Sj = dj − aj > 0 for every j < k, and the service counts are feasible.The parameter inequalities hold simultaneously for all j < k when k is fixed.Source: §B.6.1 · pp. 30–31

B.6.2 Proofs for level-j jobs, 2 ≤j < k

  • The intermediate-level failure analysis bounds E[Fj] by aj for sufficiently large n.The factor-test argument combines degree and cut events with success at lower levels to imply an Sj-factor.Source: §B.6.2 · pp. 31–32

B.6.3 Proofs for level-k jobs

The proof builds a level-k queue from periodically allocated service slots and bounds its arrival and service quantities using matching identities and concentration lemmas.

B.6.3 Proofs for level-k jobs

  • König’s edge-coloring theorem gives A_k = max_v D(v), and the port-count bound yields 0 ≤ A_k ≤ nT_k.Source: §B.6.3 · pp. 32–33
  • Because 0 ≤ F_k ≤ T_k and E[F_k] ≤ h, Lemma 12 applies with fixed D when k is fixed; its corresponding parts give the mean and variance bounds without requiring independence between Z_k and F_k.Source: §B.6.3 · p. 32
  • Insertions are spaced by T_k, with exactly S_k level-k service slots between them; serving a matching whenever the queue is nonempty yields (42), and the matching counts are iid.Source: §B.6.3 · p. 33
  • With δ_k = S_k − E[A_k] > 0, the proof applies Lemma 10 using E[A_k], Var(A_k), and S_k, then uses the estimates in Lemma 23(ii)–(iii).Source: §B.6.3 · p. 33
Loading 2610.37521v1…