New Bounds on the Competitive Ratio of Longest Queue Drop: 1.46929591 <= CR(LQD) <= 1.683652

Improved lower and upper bounds for the canonical buffer management policy in shared memory switches

Alex Davydow; Sergey Nikolenko· 2026· DOI 10.48550/arXiv.2609.19157

The core problem

Longest Queue Drop (LQD) is a canonical buffer management policy for shared memory switches, where the switch maintains a single shared buffer for all output queues. The competitive ratio (CR) of LQD measures its worst-case performance relative to an optimal offline policy. Prior to this work, the best known bounds were CR(LQD) in [1.44546086, 1.6918]. This paper improves both ends: the lower bound is raised to CR (LQD) \geq 184815365566285/125784985866185 = 1.46929591..., and the upper bound is lowered to CR (LQD) \leq 1.683652 . The authors also identify and repair a gap in the derivation of a previously published proof.

The main results are: - Lower bound: CR (LQD) \geq \frac{184815365566285}{125784985866185} = 1.46929591... - Upper bound: CR (LQD) \leq 1.683652 These improve upon the previous bounds of 1.44546086 and 1.6918, respectively. The lower bound is certified on a specific finite instance and is independent of the tie rule. The upper bound is proven via a closed-form solution of a continuum envelope relaxation and holds for every tie rule. The repair of the aggregation step also restores the previously published bounds.

Longest Queue Drop (LQD) is a canonical buffer management policy for shared memory switches, where the switch maintains a single shared buffer for all output queues. The competitive ratio (CR) of LQD measures its worst-case performance relative to an optimal offline policy. Prior to this work, the best known bounds were CR(LQD) in [1.44546086, 1.6918]. This paper improves both ends: the lower bound is raised to CR (LQD) \geq 184815365566285/125784985866185 = 1.46929591..., and the upper bound is lowered to CR (LQD) \leq 1.683652 . The authors also identify and repair a gap in the derivation of a previously published proof.

For the lower bound, the authors introduce a new instance family called the *front-loaded family*. They provide an exact-integer certificate on a specific finite instance, evaluated against the exactly optimal offline policy. The bound is shown to be independent of the tie rule: an adaptive coupling transfers the certified value to every non-clairvoyant deterministic tie rule and to every randomized tie rule in the adaptive adversary sense. For the upper bound, the authors replace the per-packet endpoint relaxation in the endgame of Antoniadis et al. (2024) with a continuum envelope relaxation of the same payment expression, which they solve exactly in closed form. This upper bound holds for every tie rule. Additionally, they find a gap in the aggregation step (Lemma 18) of the published proof and repair it with one amortized lemma and an exact finite-head analysis. The repair restores the published 1.6918 bound and the weaker conference guarantee 1.707 of Antoniadis et al. (ICALP 2021), and also supports the further improvement.

The improved bounds narrow the gap in the competitive ratio of LQD, bringing the lower and upper bounds closer. The lower bound construction uses a novel instance family and an adaptive coupling argument that generalizes the bound across tie rules. The upper bound employs a continuum envelope relaxation, which is solved exactly, providing a tighter guarantee. The identification and repair of the gap in the published proof is significant, as it validates previous results and enables further improvements. The authors note that the lower bound is exact for the specific instance and tie rule, but the adaptive coupling ensures it applies broadly. The upper bound, being rule-independent, is a robust guarantee. Future work may focus on closing the remaining gap between 1.46929591 and 1.683652.

CS practitioners and researchers

Opening member content…