The Harmonic Policy for Online Buffer Sharing is \((2 + \ln n)\)-Competitive: A Simple Proof
Abstract
The problem of online buffer sharing is expressed as follows. A switch with 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\) 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.
Fields of Study & Subjects
Optimization and Search Problems
Advanced Queuing Theory Analysis
Distributed systems and fault tolerance
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 472–475
- Publication date
- 1 January 2026
- Language
- EN