Buffering Dynamics and Stability of Internet Congestion Controllers
Many existing fluid-flow models of the Internet congestion control algorithms make simplifying assumptions on the effects of buffers on the data flows. In particular, they assume that the flow rate of a TCP flow at every link in its path is equal to the original source rate. However, a fluid flow in practice is modified by the queueing processes on its path, so that an intermediate link will generally not see the original source rate. In this paper, a more accurate model is derived for the behavior of the network under a congestion controller, which takes into account the effect of buffering on output flows. It is shown how this model can be deployed for some well-known service disciplines such as first-in–first-out and generalized weighted fair queueing. Based on the derived model, the dual and primal-dual algorithms are studied under the common pricing mechanisms, and it is shown that these algorithms can become unstable. Sufficient conditions are provided to guarantee the stability of the dual and primal-dual algorithms. Finally, a new pricing mechanism is proposed under which these congestion control algorithms are both stable.
© 2013 IEEE. Manuscript received October 20, 2011; revised July 24, 2012; accepted September 23, 2013; Manuscript received October 20, 2011; revised July 24, 2012; accepted September 23, 2013; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor V. Misra. Date of publication November 08, 2013; date of current version December 15, 2014. This work was supported by ONR MURI N00014-08-1-0747 "Scalable, Data-driven, and Provably-correct Analysis of Networks," ARO MURI W911NF-08-1-0233 "Tools for the Analysis and Design of Complex Multi-Scale Networks," the Army's W911NF-09-D-0001 Institute for Collaborative Biotechnology, and the NSF NetSE under Grant CNS-0911041.