  For general multi-hop queueing networks, delay optimal network control has
unfortunately been an outstanding problem. The dynamic backpressure (BP)
algorithm elegantly achieves throughput optimality, but does not yield good
delay performance in general. In this paper, we obtain an asymptotically delay
optimal control policy, which resembles the BP algorithm in basing resource
allocation and routing on a backpressure calculation, but differs from the BP
algorithm in the form of the backpressure calculation employed. The difference
suggests a possible reason for the unsatisfactory delay performance of the BP
algorithm, i.e., the myopic nature of the BP control. Motivated by this new
connection, we introduce a new class of enhanced backpressure-based algorithms
which incorporate a general queue-dependent bias function into the backpressure
term of the traditional BP algorithm to improve delay performance. These
enhanced algorithms exploit queue state information beyond one hop. We prove
the throughput optimality and characterize the utility-delay tradeoff of the
enhanced algorithms. We further focus on two specific distributed algorithms
within this class, which have demonstrably improved delay performance as well
as acceptable implementation complexity.
