Price of Asynchrony: Queuing under Ideally Smooth Congestion Control

In this paper, we present a model for investigating lower bounds on queuing under smooth congestion control with overprovisioned buffers. We consider an idealized protocol where all flows always transmit at equal rates. The ideally smooth transmission does not eliminate queuing altogether because packets of different flows might arrive to a node simultaneously due to asynchronous arrivals of the flows, which is intrinsic to computer networks. A prominent feature of our model is its simplicity, making analysis tractable and experiments scalable. Our results reveal steady-state queues of at least O(radicN) packets, where N is the number of flows. Hence, no congestion control protocol is able to avoid losses at a fully utilized link with a constant buffer shared by arbitrarily many flows.