Lower Bounds on Queuing and Loss at Highly Multiplexed Links

Explicit and delay-driven congestion control protocols strive to preclude overflow of link buffers by reducing transmission upon incipient congestion. In this paper, we explore fundamental limitations of any congestion control with respect to minimum queuing and loss achievable at highly multiplexed links. We present and evaluate an idealized protocol where all flows always transmit at equal rates. The ideally smooth congestion control causes link queuing only due to asynchrony of flow arrivals, which is intrinsic to computer networks. With overprovisioned buffers, our analysis and simulations for different smooth distributions of flow interarrival times agree that minimum queuing at a fully utilized link is O(sqrt(N)), where N is the number of flows sharing the link. This result raises concerns about scalability of any congestion control. However, our simulations of the idealized protocol with small buffers show its surprising ability to provide bounded loss rates regardless of the number of flows. Finally, we experiment with RCP (Rate Control Protocol) to examine how existing practical protocols compare with our idealized scheme in small-buffer settings