Delay optimal control and its connection to the dynamic backpressure algorithm

For general multi-hop queueing networks, delay optimal network control has unfortunately been an outstanding problem for some time. The dynamic backpressure (DBP) algorithm is an elegant network control algorithm achieving throughput optimality. However, it does not yield good delay performance in general. In this paper, we formulate the delay optimal network control problem for general multi-hop queueing networks. We obtain an asymptotically delay optimal control policy. Surprisingly, we show that the asymptotically delay optimal control resembles the DBP algorithm in basing resource allocation and routing on a backpressure calculation, but differs from the DBP algorithm in the form of the backpressure calculation employed. This difference suggests a possible reason for the poor delay performance of the DBP algorithm. To the best of our knowledge, this is the first work which provides an analytical connection between delay optimal control and the throughput optimal DBP algorithm. The connection provides a theoretical basis for designing enhanced DBP algorithms with improved delay performance via the use of QSI beyond one hop.