What are buffers for?

Frank Kelly

Workshop on buffer sizing, Stanford, 2-3 December 2019.


Appropriate buffer sizes in a communication network depend intimately on the control algorithms and feedback mechanisms deployed across the network and its end-points. Nevertheless there are certain general principles that provide insight into what is, and what is not, possible.

Buffers in a communication network serve at least two essential purposes. They are needed to cope with: the randomness inherent in the multiplexing of many flows; and the speed of light propagation delays that necessarily constrain source responses to congestion. The talk will begin with an analysis of how queueing delays scale under regimes of increasing speed, volume and multiplexing. It is not a surprise that under a variety of scaling regimes queueing delays become small in comparison with propagation delays.

Congestion control algorithms cannot avoid propagation delays, and this limits their speed of response to feedback signals. Robust algorithms need to be stable for general topologies with multiple constrained resources, and ways of achieving this are now well understood. If feedback based on rate mismatch is available, then feedback based on queue size is not useful for stabilizing long-lived flows. Feedback based on queue size is however important for clearing transient overloads caused by, for example, incasts or failures. If feedback based on rate mismatch is available, then buffer sizes should primarily be determined by potential transient overloads.


Papers:
Sizing router buffers
Guido Appenzeller, Isaac Keslassy and Nick McKeown
ACM SIGCOMM Computer Communication Review 34 (2004) 281-292.

Routers with very small buffers
Mihaela Enachescu, Yashar Ganjali, Ashish Goel, Nick McKeown and Tim Roughgarden
ACM SIGCOMM Computer Communication Review 35 (2005) 83-90.

Control theory for buffer sizing
Gaurav Raina, Don Towsley and Damon Wischik
ACM SIGCOMM Computer Communication Review 35 (2005) 79-82.

Update on buffer sizing in Internet routers
Yashar Ganjali and Nick McKeown
ACM SIGCOMM Computer Communication Review 36 (2006) 67-70.

Sizing router buffers (redux)
Guido Appenzeller, Isaac Keslassy and Nick McKeown
ACM SIGCOMM Computer Communication Review 49 (2019) 69-74.

Models for a self-managed Internet
Philosophical Transactions of the Royal Society A358 (2000) 2335-2348.

Fairness and stability of end-to-end congestion control.
European Journal of Control 9 (2003) 159-176.

Stability and fairness of explicit congestion control with small buffers.
FK, Gaurav Raina and Thomas Voice
ACM SIGCOMM Computer Communication Review 38 (2008) 51-62.

HPCC: High Precision Congestion Control
Yuliang Li, Rui Miao, Hongqiang Liu, Yan Zhuang, Fei Feng, Lingbo Tang, Zheng Cao, Ming Zhang, Frank Kelly, Mohammad Alizadeh, Minlan Yu
Proceedings of the ACM Special Interest Group on Data Communication (2019), 44-58.