2017/01/17 by Hao Yu, Yu, Hao, Michael J. Neely +1
Computer Science · Engineering · #Advanced Wireless Network Optimization #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Network Traffic and Congestion Control #Networking and Internet Architecture (cs.NI) #Optimization and Control (math.OC) #Systems and Control (eess.SY) #Wireless Networks and Protocols #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1701.04519
openalex publication_date 2017/01/17 · openalex created_date 2017/01/26 · openalex updated_date 2026/07/28
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.