The Harmonic Policy for Online Buffer Sharing is ( 2 + ln ⁡ n ) (2+\ln n) -Competitive: A Simple Proof

Vamsi Addanki, Julien Dallot, Leon Kellerhals, Maciej Pacut, Stefan Schmid · 2025

Read The Harmonic Policy for Online Buffer Sharing is ( 2 + ln ⁡ n ) (2+\ln n) -Competitive: A Simple Proof by Vamsi Addanki, Julien Dallot, Leon Kellerhals, Maciej Pacut, Stefan Schmid (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06514.txt.

Introduction

Vamsi Addanki and colleagues give a leaner proof that the Harmonic policy for network buffer sharing is nearly optimal. A switch with many output ports stores arriving packets in one shared buffer and must accept or reject each instantly to maximize throughput. The Harmonic policy was known to achieve the best proven guarantee, but its original proof was long and intricate.

The note first shows the policy needs only a constant number of threshold checks per packet, matching the widely deployed Dynamic Threshold policy in practical cost. A direct new proof then splits packets into three groups to establish the competitive ratio of two plus the natural log of the port count. Simplicity serves both theory and deployment.

Catalog record

CREATORVamsi Addanki, Julien Dallot, Leon Kellerhals, Maciej Pacut, Stefan Schmid
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE13 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-06514

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Harmonic Policy for Online Buffer Sharing is ( 2 + ln ⁡ n ) (2+\ln n) -Competitive: A Simple Proof Vamsi Addanki, Julien Dallot, Leon Kellerhals, Maciej Pacut, Stefan Schmid Abstract . The problem of online buffer sharing is expressed as follows. A switch with n n output ports receives a stream of incoming packets. When an incoming packet is accepted by the switch, it is stored in a shared buffer of capacity B B common to all packets and awaits its transmission through its corresponding output port determined by its destination. Each output port transmits one packet per time unit. The problem is to find an algorithm for the switch to accept or reject a packet upon its arrival in order to maximize the total number of transmitted packets. Building on the work of Kesselman et al. (STOC 2001) on split buffer sharing, Kesselman and Mansour (TCS 2004) considered the problem of online buffer sharing which models most deployed internet switches. In their work, they presented the Harmonic policy and proved that it is ( 2 + ln ⁡ n ) (2+\ln n) -competitive, which is the best known competitive ratio for this problem. The Harmonic policy unfortunately saw less practical relevance as it performs n n threshold checks per packets which is deemed costly in practice, especially on network switches processing multiple terabits of packets per second. While the Harmonic policy is elegant, the original proof is also rather complex and involves a lengthy matching routine along with multiple intermediary results. This note presents a simplified Harmonic policy, both in terms of implementation and proof. First, we show that the Harmonic policy can be implemented with a constant number of threshold checks per packet, matching the widely deployed Dynamic Threshold policy. Second, we present a simple proof that shows the Harmonic policy is ( 2 + ln ⁡ n ) (2+\ln n) -competitive. In contrast to the original proof, the current proof is direct and relies on a 3-partitioning of the packets. 1. Introduction In the online buffer sharing problem, we consider a network switch with n output ports labeled 1\dots n and a shared buffer which can hold at most B packets. A stream of packets \sigma=p_{1},p_{2},\dots arrives in the switch. Each packet p_{i} arrives at some time t_{i} and must be transmitted through a specific output port q_{i}\in 1\dots n . We assume that the packets can be totally ordered by their arrival time — if two packets arrive at the same time, we assume that we break the tie arbitrarily. When a packet p_{i} arrives, the switch decides to either accept or reject it. If p_{i} is accepted, it is stored in the buffer and queued for transmission through the output port q_{i} in a first-in-first-out (FIFO) manner. Each output port transmits up to one packet at each integer time t=1,2,\dots ; the output port does not transmit anything if no packet is queued. The task is to design an acceptance policy for the switch that decides whether to accept or reject each incoming packet. The objective is to maximize the number of accepted packets while respecting the shared buffer capacity at all time. The acceptance policy must be online , which means that the decision to accept or reject a packet must be made at the time of its arrival without knowledge of future packets. Several buffer sharing policies have been established over the years. Among the most relevant are the Sharing with Maximum Queue Lengths (SMXQ) ( 3 ) and Dynamic Thresholds ( 7 ) algorithms, with the latter being the most used in practice. Both have a competitive ratio no better than O(n) , i.e., there exists a sequence of packets such that an optimal, offline acceptance policy accepts O(n) more packets. Following a series of results on switch buffer sharing ( 4 ; 2 ) , Kesselman and Mansour ( 5 ) present the Harmonic policy for online buffer sharing in 2004. The main novelty of the Harmonic policy was to consider the queues sorted by their current size: it assigns roughly a 1/i fraction of the memory to the i -th largest queue, resulting in a competitive ratio of (2+\ln n) . Their policy works as follows. Algorithm 1 (The Harmonic Policy). Accept the incoming packet if, after accepting it, the following would hold for each i\in 1\dots n : the total occupancy of the i queues with greatest occupancies is at most \frac{B}{1+\ln n}\cdot\sum_{k\in 1\dots i}\frac{1}{k} . The Harmonic policy is the best known algorithm with respect to the competitive ratio metric — Kesselman and Mansour also showed a lower bound of \Omega(\log n/\log\log n) for any online, deterministic policy, showing that Harmonic is close to optimal. Even though the alternative algorithms all have a worst-case competitive ratio of O(n) , the Harmonic policy however saw little practical relevance in modern network switches. This is arguably due to the initial presentation of the policy ( 5 ) , which suggests that one must maintain a list of the output ports by queue occupancy and must perform n threshold checks upon each packet arrival, which is deemed too costly in practice. Moreover, the original proof of Harmonic’s competitive ratio is rather complex, involving a lengthy matching routine along with multiple intermediary results, which makes it harder for practicioners to adopt and understand the algorithm. Nowadays, buffer management algorithms are revisited through the lens of learning-augmented algorithms ( 1 ; 8 ; 9 ) , where the acceptance policy uses machine-learned predictions to improve its performances. Most of the algorithms are based on one of the established algorithms and often use competitive analysis as a key metric to evaluate the prediction quality ( 6 ; 1 ) ; The Harmonic algorithm therefore plays a central role as both a reference and a base to build new learning-augmented algorithms. In this work, we first want to point out a quick observation that the Harmonic algorithm can be implemented to use only a constant number of operations per packet. Secondly, and mainly, we present a significantly simpler proof for its competitive ratio. We hope that this simpler proof makes Harmonic more accessible and possibly leads the way to more competitive learning-augmented algorithms for buffer sharing. 2. Efficiency of the Harmonic Policy We briefly show that the Harmonic policy can be implemented very efficiently. Central to the Harmonic policy are the thresholds , which are proportional to the harmonic series. Definition 2.1 (Thresholds). For all k=1\dots n , we define the threshold T_{k}=\frac{B}{1+\ln n}\cdot\frac{1}{k} . Algorithm 2 (The Modified Harmonic Policy). When packet p_{i} arrives, compute the smallest T_{k} such that the occupancy of queue q_{i} is strictly lower than T_{k} . Accept p_{i} if and only if accepting it results in at most k queues with occupancy no lower than T_{k} . For each queue, the smallest threshold T_{k} greater than its occupancy can be tracked in constant time per packet: each time a new packet is accepted or transmitted for a given queue, compare the new queue’s occupancy with the current threshold T_{k} and update it to T_{k+1} or T_{k-1} accordingly. Finally, it is possible to track the number of queues

Read the complete text