Exploring the inefficiency and instability of Back-Pressure algorithms

In this paper, we focus on the issue of stability in multihop wireless networks under flow-level dynamics, and explore the inefficiency and instability of the celebrated Back-Pressure algorithms. It has been well-known that the Back-Pressure (or Max-Weight) algorithms achieve queue stability and throughput optimality in a wide variety of scenarios. Yet, these results all rely on the assumptions that the set of flows is fixed, and that all the flows are long-lived and keep injecting packets into the network. Recently, in the presence of flow-level dynamics, where flows arrive and request to transmit a finite amount of packets, it has been shown that the Max-Weight algorithms may not guarantee stability due to channel fading or inefficient spatial reuse. However, these observations are made only for single-hop traffic, and thus have resulted in partial solutions that are limited to the single-hop scenarios. An interesting question is whether straightforward extensions of the previous solutions to the known instability problems would achieve throughput optimality in multihop traffic setting. To answer the question, we explore potential inefficiency and instability of the Back-Pressure algorithms, and provide interesting examples that are useful to obtain insights into developing an optimal solution. We also conduct simulations to further illustrate the instability issue of the Back-Pressure algorithms in various scenarios. Our study reveals that new types of inefficiencies may arise in the settings with multihop traffic due to underutilization of the link capacity or inefficient routing, and the stability problem becomes more challenging than in the single-hop traffic counterpart.