pith. sign in

arxiv: 1907.04399 · v1 · pith:MRSUL7SHnew · submitted 2019-07-09 · 💻 cs.NI · cs.DS

New Competitiveness Bounds for the Shared Memory Switch

Ivan Bochkov , Alex Davydow , Nikita Gaevoy , Sergey I. Nikolenko This is my paper

Pith reviewed 2026-05-24 23:49 UTC · model grok-4.3

classification 💻 cs.NI cs.DS
keywords competitive analysisbuffer managementshared memory switchlongest queue droponline algorithmspacket bufferinglower bounds
0
0 comments X

The pith

Every deterministic online algorithm for the shared memory switch is at least √2-competitive.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a new lower bound of √2 on the competitive ratio of all deterministic online algorithms for the shared memory switch, improving on the prior bound of 4/3. The improvement comes from a reduction of the discrete packet model to a continuous equivalent that preserves the ratio. It also gives a simplified proof of the √2 bound for the Longest Queue Drop policy and raises that specific bound to 1.44546086 using simulations and linear programming on an explicit optimal offline algorithm. These results matter because they provide tighter guarantees on the worst-case performance of online buffer management compared to optimal offline decisions in network switches.

Core claim

The central claim is that a reduction to the continuous case shows every deterministic online algorithm is at least √2-competitive, while for the Longest Queue Drop policy an explicit construction of the optimal clairvoyant algorithm proves a lower bound of 1.44546086, with a linear programming relaxation giving 1.4427902.

What carries the argument

Reduction from the discrete to the continuous packet model that preserves competitive ratios exactly, together with explicit construction of the optimal clairvoyant algorithm for analyzing LQD.

If this is right

  • The general lower bound of √2 applies to every deterministic online algorithm.
  • LQD has a competitiveness lower bound of at least 1.44546086.
  • A simplified proof is given for the √2 lower bound on LQD.
  • The linear programming method yields a lower bound of 1.4427902 for LQD.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The continuous reduction may help analyze competitiveness in other buffer management architectures.
  • Further refinements to the clairvoyant construction could produce even tighter lower bounds.
  • Closing the remaining gap between √2 and the known upper bound of 2 may require new techniques.

Load-bearing premise

The reduction from the discrete packet model to the continuous case preserves the competitive ratio exactly, without additional loss factors.

What would settle it

A deterministic online algorithm that maintains a competitive ratio below √2 on an adversarial packet sequence in the shared memory switch would disprove the general lower bound.

Figures

Figures reproduced from arXiv: 1907.04399 by Alex Davydow, Ivan Bochkov, Nikita Gaevoy, Sergey I. Nikolenko.

Figure 1
Figure 1. Figure 1: Sample operation of a shared memory switch with [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Sample operation of LateQD for N = 3, B = 4. Numbers on packets show provisional transmission moments for an algorithm with infinite buffer (shown on the right). Letters in light blue circles mark the identities of individual packets. 5 Model extensions 5.1 Fractional packets We begin our extensions to the basic model by considering fractional packets. In this setting, we allow algorithms to drop and store… view at source ↗
Figure 3
Figure 3. Figure 3: Sample operation of LateQD for N = 3, B = 6. Numbers on packets show provisional transmission moments for an algorithm with infinite buffer. Q(1) receives B packets on t ∈ {1, 2}, Q(2) receives B packets on t ∈ {2, 3, 4}, Q(3) receives B packets on t ∈ {3, 4, 5, 6}. Packets shaded in red are pushed out. The right column shows LQD buffer state after transmission on the same input. Although this significantl… view at source ↗
Figure 4
Figure 4. Figure 4: Queue occupancy for LQD at time moment t. The shaded polygon shows the number of packets in nonempty queues. LQD tries to equalize queue size as much as possible. p ≈ q 2(B − a) a Queues Packets p t t+p+a 0 1 t+p [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Queue occupancy for ALG at time moment t. ALG leaves one packet in every live queue and tries to preserve as many packets from dying queues as possible. Now C+ √ √ 2 C2+2 achieves maximum at √ 2 for C = √ 2. It remains to show that we can construct a sequence of tests such that the competitiveness of LQD tends to √ 2 on this sequence. To do that, it suffices to construct a sequence of (ai , Bi) ∞ i=1 such … view at source ↗
Figure 6
Figure 6. Figure 6: Sample operation on the Φk input instance for k = 4 and two input cycles: (a) live queues in Φk; (b) LQD operation on this instance for B = 6; (c) LateQD operation for B = 6. Numbers show the number of packets left in a queue after transmission. We again consider instances of the form Φk where queue Q(j) receives packets during the time interval kb j−1 k c + 1; j [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Experimental results: competitive ratio as a function of [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Number of packets accepted and transmitted from dying queues on three cycles of [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗
read the original abstract

We consider one of the simplest and best known buffer management architectures: the shared memory switch with multiple output queues and uniform packets. It was one of the first models studied by competitive analysis, with the Longest Queue Drop (LQD) buffer management policy shown to be at least $\sqrt{2}$- and at most $2$-competitive; a general lower bound of $4/3$ has been proven for all deterministic online algorithms. Closing the gap between $\sqrt{2}$ and $2$ has remained an open problem in competitive analysis for more than a decade, with only marginal success in reducing the upper bound of $2$. In this work, we first present a simplified proof for the $\sqrt{2}$ lower bound for LQD and then, using a reduction to the continuous case, improve the general lower bound for all deterministic online algorithms from $\frac 43$ to $\sqrt{2}$. Then, we proceed to improve the lower bound of $\sqrt{2}$ specifically for LQD, showing that LQD is at least $1.44546086$-competitive. We are able to prove the bound by presenting an explicit construction of the optimal clairvoyant algorithm which then allows for two different ways to prove lower bounds: by direct computer simulations and by proving lower bounds via linear programming. The linear programming approach yields a lower bound for LQD of $1.4427902$ (still larger than $\sqrt{2}$).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims a simplified proof that LQD is √2-competitive, a reduction from the discrete packet model to a continuous fluid model that raises the general lower bound on all deterministic online algorithms from 4/3 to exactly √2, and a tighter LQD lower bound of 1.44546086 obtained via an explicit construction of the optimal clairvoyant algorithm, with supporting computer simulations and an LP formulation that yields 1.4427902.

Significance. If the reduction preserves competitive ratios exactly, the result would be significant by closing the gap between the general lower bound and the known LQD lower bound after more than a decade. The explicit construction enabling both simulation and LP lower bounds is a methodological strength that allows verifiable, falsifiable claims.

major comments (2)
  1. [reduction to the continuous case] The reduction to the continuous case (invoked after the simplified LQD √2 proof): the manuscript must explicitly demonstrate that the mapping from discrete arrival sequences to continuous fluid instances preserves the competitive ratio with no multiplicative loss or relaxation factor. If the reduction introduces even an arbitrarily small (1+ε) term or relies on a limit argument that does not translate back exactly, the claimed improvement from 4/3 to precisely √2 does not follow.
  2. [LQD lower bound via explicit construction] LQD lower-bound section: the simulation reports 1.44546086 while the LP reports 1.4427902; the paper must clarify which bound is rigorously proven, how the simulation is turned into a formal proof (or why it is presented as the primary result), and whether the explicit construction of the clairvoyant algorithm is used to certify both.
minor comments (2)
  1. [Abstract] Abstract: computer simulations are mentioned without reference to error analysis, number of trials, or code availability; this should be added for reproducibility.
  2. [model definitions] Notation: the continuous fluid model should include a short table comparing the discrete and continuous parameters to make the reduction easier to follow.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments. We address the major concerns point by point below, and will revise the manuscript accordingly where needed.

read point-by-point responses

  1. Referee: [reduction to the continuous case] The reduction to the continuous case (invoked after the simplified LQD √2 proof): the manuscript must explicitly demonstrate that the mapping from discrete arrival sequences to continuous fluid instances preserves the competitive ratio with no multiplicative loss or relaxation factor. If the reduction introduces even an arbitrarily small (1+ε) term or relies on a limit argument that does not translate back exactly, the claimed improvement from 4/3 to precisely √2 does not follow.

    Authors: The reduction is designed to preserve the competitive ratio exactly. We map discrete packet arrivals to fluid flows by considering infinitesimal packet sizes in the limit, ensuring that the cost and benefit ratios are identical in both models. No multiplicative factor is introduced. To address the concern, we will add an explicit lemma proving that the competitive ratio in the discrete model is at least as high as in the corresponding fluid instance, with equality in the limit, thus establishing the bound of exactly √2 without relaxation. revision: yes

  2. Referee: [LQD lower bound via explicit construction] LQD lower-bound section: the simulation reports 1.44546086 while the LP reports 1.4427902; the paper must clarify which bound is rigorously proven, how the simulation is turned into a formal proof (or why it is presented as the primary result), and whether the explicit construction of the clairvoyant algorithm is used to certify both.

    Authors: The explicit construction of the optimal clairvoyant algorithm is used for both. The simulation provides a numerical lower bound of 1.44546086 based on the construction, but we acknowledge that it relies on computational verification rather than a purely analytical proof. The LP formulation provides a rigorous lower bound of 1.4427902 that can be formally proven. We will revise the text to clarify that the proven rigorous bound is 1.4427902 from the LP, while the simulation suggests the bound may be higher, and explain the role of the construction in enabling both approaches. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives its improved lower bounds via explicit adversarial constructions for the LQD-specific bound (yielding 1.44546086 via simulation and 1.4427902 via LP) and invokes a reduction to the continuous fluid model to lift the general deterministic lower bound from 4/3 to √2. These steps rest on direct comparison against the model definition and optimization, not on parameters fitted to the target quantity or equations that define the output in terms of itself. No self-citation chain is load-bearing for the central claims, and the reduction is presented as a technical mapping rather than a renaming or self-definitional step. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on standard definitions of competitive ratio and the shared-memory switch model with uniform packets; no free parameters, new entities, or ad-hoc axioms beyond the reduction step are introduced.

axioms (2)
  • standard math Standard definition of competitive ratio for online algorithms against an optimal offline adversary
    Invoked throughout to define all bounds including the new √2 and 1.44546 values.
  • domain assumption The discrete arrival process reduces to a continuous fluid model while preserving the exact competitive ratio
    Central to raising the general lower bound from 4/3 to √2.

pith-pipeline@v0.9.0 · 5800 in / 1263 out tokens · 24056 ms · 2026-05-24T23:49:15.593202+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · 1 internal anchor

  1. [1]

    Competitive buffer man- agement for shared-memory switches

    William Aiello, Alexander Kesselman, and Yishay Mansour. Competitive buffer man- agement for shared-memory switches. ACM Transactions on Algorithms, 5(1), 2008. 20

    work page 2008

  2. [2]

    Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

    Kamal Al-Bawani, Matthias Englert, and Matthias Westermann. Online Packet Scheduling for CIOQ and Buffered Crossbar Switches. Algorithmica, 80(12):3861–3888, 2018

    work page 2018

  3. [3]

    Competitive queueing policies for QoS switches

    Nir Andelman, Yishay Mansour, and An Zhu. Competitive queueing policies for QoS switches. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algo- rithms, pages 761–770, 2003

    work page 2003

  4. [4]

    Maximizing throughput in multi-queue switches

    Yossi Azar and Arik Litichevskey. Maximizing throughput in multi-queue switches. Algorithmica, 45(1):69–90, 2006

    work page 2006

  5. [5]

    Management of multi-queue switches in QoS networks

    Yossi Azar and Yossi Richter. Management of multi-queue switches in QoS networks. Algorithmica, 43(1-2):81–96, 2005

    work page 2005

  6. [6]

    An improved algorithm for CIOQ switches

    Yossi Azar and Yossi Richter. An improved algorithm for CIOQ switches. ACM Trans- actions on Algorithms , 2(2):282–295, 2006

    work page 2006

  7. [7]

    New Competitiveness Bounds for the Shared Memory Switch

    Ivan Bochkov, Alex Davydow, Nikita Gaevoy, and Sergey I. Nikolenko. Code for re- producing the experiments in “New Competitiveness Bounds for the Shared Memory Switch”. https://gitlab.com/networking-lqd/networking-gcc, 2019

    work page 2019

  8. [8]

    Online Computation and Competitive Analysis

    Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cam- bridge University Press, 1998

    work page 1998

  9. [9]

    Nikolenko, and Kirill Kogan

    Pavel Chuprikov, Sergey I. Nikolenko, and Kirill Kogan. Priority queueing with multiple packet characteristics. In 2015 IEEE International Conference on Computer Commu- nications, pages 1418–1426, 2015

    work page 2015

  10. [10]

    Nikolenko, Kirill Kogan, and Alexei P

    Pavel Chuprikov, Sergey I. Nikolenko, Kirill Kogan, and Alexei P. Davydow. Prior- ity queueing for packets with two characteristics. IEEE Transactions on Networking , 26(1):342–355, 2018

    work page 2018

  11. [11]

    Davydow, Pavel Chuprikov, Sergey I

    Alexei P. Davydow, Pavel Chuprikov, Sergey I. Nikolenko, and Kirill Kogan. Through- put optimization with latency constraints. In 2017 IEEE International Conference on Computer Communications, 2017

    work page 2017

  12. [12]

    Buffer management problems

    Leah Epstein and Rob van Stee. Buffer management problems. SIGACT News , 35(3):58–66, 2004

    work page 2004

  13. [13]

    Nikolenko, and Alexander V

    Patric Eugster, Kirill Kogan, Sergey I. Nikolenko, and Alexander V. Sirotkin. Shared- memory buffer management for heterogeneous packet processing. In Proceedings of the 34th International Conference on Distributed Computing Systems , 2014

    work page 2014

  14. [14]

    A survey of buffer management policies for packet switches

    Michael Goldwasser. A survey of buffer management policies for packet switches. SIGACT News, 41(1):100–128, 2010

    work page 2010

  15. [15]

    Hahne, Alexander Kesselman, and Yishay Mansour

    Ellen L. Hahne, Alexander Kesselman, and Yishay Mansour. Competitive buffer man- agement for shared-memory switches. In SPAA, pages 53–58, 2001. 21

    work page 2001

  16. [16]

    Tight Analysis of Priority Queuing Policy for Egress Traffic

    Jun Kawahara, Koji Kobayashi, and Tomotaka Maeda. Tight analysis of priority queu- ing policy for egress traffic. CoRR, abs/1207.5959, 2012

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  17. [17]

    Providing perfor- mance guarantees in multipass network processors

    Isaac Keslassy, Kirill Kogan, Gabriel Scalosub, and Michael Segal. Providing perfor- mance guarantees in multipass network processors. IEEE/ACM Transactions of Net- working, 20(6):1895–1909, 2012

    work page 1909

  18. [18]

    Packet mode and QoS al- gorithms for buffered crossbar switches with FIFO queuing

    Alexander Kesselman, Kirill Kogan, and Michael Segal. Packet mode and QoS al- gorithms for buffered crossbar switches with FIFO queuing. Distributed Computing , 23(3):163–175, 2010

    work page 2010

  19. [19]

    Improved competitive perfor- mance bounds for CIOQ switches

    Alexander Kesselman, Kirill Kogan, and Michael Segal. Improved competitive perfor- mance bounds for CIOQ switches. Algorithmica, 63(1-2):411–424, 2012

    work page 2012

  20. [20]

    Buffer overflow management in QoS switches.SIAM J

    Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, and Maxim Sviridenko. Buffer overflow management in QoS switches.SIAM J. Comput., 33(3):563–583, 2004

    work page 2004

  21. [21]

    Harmonic buffer management policy for shared memory switches

    Alexander Kesselman and Yishay Mansour. Harmonic buffer management policy for shared memory switches. Theor. Comput. Sci. , 324(2-3):161–182, 2004

    work page 2004

  22. [22]

    Improved competitive guar- antees for QoS buffering

    Alexander Kesselman, Yishay Mansour, and Rob van Stee. Improved competitive guar- antees for QoS buffering. Algorithmica, 43(1-2):63–80, 2005

    work page 2005

  23. [23]

    Scheduling policies for CIOQ switches

    Alexander Kesselman and Adi Ros´ en. Scheduling policies for CIOQ switches. Journal of Algorithms, 60(1):60–83, 2006

    work page 2006

  24. [24]

    Controlling CIOQ switches with priority queu- ing and in multistage interconnection networks

    Alexander Kesselman and Adi Ros´ en. Controlling CIOQ switches with priority queu- ing and in multistage interconnection networks. Journal of Interconnection Networks , 9(1/2):53–72, 2008

    work page 2008

  25. [25]

    A tight bound on online buffer management for two-port shared-memory switches

    Koji Kobayashi, Shuichi Miyazaki, and Yasuo Okabe. A tight bound on online buffer management for two-port shared-memory switches. IEICE - Trans. Inf. Syst. , E91- D(8):2105–2114, August 2008

    work page 2008

  26. [26]

    Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms

    Koji Kobayashi, Shuichi Miyazaki, and Yasuo Okabe. Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms. In Proceed- ings of the 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA) , pages 328–336, 2009

    work page 2009

  27. [27]

    Nikolenko, and Alexander Sirotkin

    Kirill Kogan, Alejandro L´ opez-Ortiz, Sergey I. Nikolenko, and Alexander Sirotkin. Multi-queued network processors for packets with heterogeneous processing require- ments. In Proceedings of the 5th International Conference on Communication Systems and Networks (COMSNETS 2013) , pages 1–10, 2013

    work page 2013

  28. [28]

    Nikolenko, and Alexander V

    Kirill Kogan, Alejandro L´ opez-Ortiz, Sergey I. Nikolenko, and Alexander V. Sirotkin. A taxonomy of semi-FIFO policies. In Proceedings of the 31st IEEE International Per- formance Computing and Communications Conference (IPCCC 2012) , pages 295–304, 2012. 22

    work page 2012

  29. [29]

    Nikolenko, and Alexander V

    Kirill Kogan, Alejandro L´ opez-Ortiz, Sergey I. Nikolenko, and Alexander V. Sirotkin. Online scheduling fifo policies with admission and push-out. Theory of Computing Systems, 58(2):322–344, 2016

    work page 2016

  30. [30]

    Nikolenko, Alexander V

    Kirill Kogan, Alejandro L´ opez-Ortiz, Sergey I. Nikolenko, Alexander V. Sirotkin, and Denis Tugaryov. FIFO queueing policies for packets with heterogeneous processing. In Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg 2012), Lecture Notes in Computer Science , volume 7659, pages 248–260, 2012

    work page 2012

  31. [31]

    Nikolenko and Kirill Kogan

    Sergey I. Nikolenko and Kirill Kogan. Single and multiple buffer processing. In Ency- clopaedia of Algorithms, pages 1–9. Springer, 2014

    work page 2014

  32. [32]

    T. Ralphs. An introduction to the coin-or optimization suite: Open source tools for building and solving optimization models. In Optimization Days, Montreal, 2013

    work page 2013

  33. [33]

    Analysis of queueing policies in QoS switches.Journal of Algorithms, 53(2):137– 168, 2004

    An Zhu. Analysis of queueing policies in QoS switches.Journal of Algorithms, 53(2):137– 168, 2004. 23

    work page 2004