Lessons on stability of rate control mechanisms in the presence of feedback delays

We study the issue of rate control in a communication network with feedback delays between network resources and end users. In particular, we adopt Kelly's primal and dual algorithms. First, we provide asymptotic stability conditions for these algorithms with arbitrary communication delays. We also derive a lower bound on the convergence rate of the system as a function of the maximum delay in the control loop in the example with isoelastic utility and price functions. Secondly, we show that the stability of the system with arbitrary delays can be studied by looking at a much simpler discrete time system that emerges from the underlying market structure of the rate control system. In the process, we also demonstrate the existence of a fundamental trade-off between users' price elasticity of demand (through a choice of utility functions) and the responsiveness of resources (through a choice of price functions). Finally, we consider the case in which a finite upper bound on the delay is known, with the isoelastic utility and price functions used earlier. We derive a sufficient condition for asymptotic stability for the primal algorithm. The derived condition is consistent with the known conditions in two extreme cases – no delay case and arbitrary delays case we study earlier.
Richard J. La received the B.S.E.E. from the University of Maryland at College Park in 1994, and the M.S. and PhD. degrees in Electrical Engineering from the University of California at Berkeley in 1997 and 2000, respectively. From 2000 to 2001 he was a senior engineer in the Mathematics of Communication Networks group at Motorola. Since August 2001 he has been on the faculty of the ECE department at the University of Maryland at College Park. His research interests include resource allocation in communication networks and application of game theory. He is a recipient of an NSF CAREER award in 2003.