Reproduce “Approaching Optimal Scaling of Queue Size for an Input-Queued Switch” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Taha Ameen, Weina Wang

The authors develop a multilevel scheduling policy for input-queued switches, promoting unserved jobs into larger batches when they cannot be matched. For uniform independent Bernoulli arrivals and each fixed level count k ≥ 2, it bounds expected total unserved jobs at every time by O(n log(n/ε)/ε^αk), where ε = 1 − ρ and αk = 2^k/(2^k−1). At k=3, αk is 8/7; the bound approaches but does not attain the conjectured scaling.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.