Competitive queue management for latency sensitive packets

Abstract

For who knows most, grieves him loss of time most Dante Alighieri (1265-1321) The Divine Comedy, Purgatory, Canto III We consider the online problem of non-preemptive queue management. An online sequence of packets arrive, each of which has an associated intrinsic value. Packets can be accepted to a FIFO queue, or discarded. The profit gained by transmitting a packet diminishes over time and is equal to its value minus the delay. This corresponds to the well known and strongly motivated Naor’s model in operations research. We give a queue management algorithm with a competitive ratio equal to the golden ratio (φ ≈ 1.618) in the case that all packets have the same value, along with a matching lower bound. We also derive Θ(1) upper and lower bounds on the competitive ratio when packets have different intrinsic values (in the case of differentiated services). We can extend our results to deal with more general models for loss of value over time. Finally, we re-interpret our online algorithms in the context of selfish agents, producing an online mechanism that approximates the optimal social welfare to within a constant factor.