Title: A New Backpressure Algorithm for Joint Rate Control and Routing with Vanishing Utility Optimality Gaps and Finite Queue Lengths,
Abstract: The backpressure algorithm has been widely used as a distributed solution to
the problem of joint rate control and routing in multi-hop data networks. By
controlling a parameter $V$ in the algorithm, the backpressure algorithm can
achieve an arbitrarily small utility optimality gap. However, this in turn
brings in a large queue length at each node and hence causes large network
delay. This phenomenon is known as the fundamental utility-delay tradeoff. The
best known utility-delay tradeoff for general networks is $[O(1/V), O(V)]$ and
is attained by a backpressure algorithm based on a drift-plus-penalty
technique. This may suggest that to achieve an arbitrarily small utility
optimality gap, the existing backpressure algorithms necessarily yield an
arbitrarily large queue length. However, this paper proposes a new backpressure
algorithm that has a vanishing utility optimality gap, so utility converges to
exact optimality as the algorithm keeps running, while queue lengths are
bounded throughout by a finite constant. The technique uses backpressure and
drift concepts with a new method for convex programming.