On the channel-sensitive delay behavior of LIFO-backpressure

In this paper, we study the delay performance of backpressure routing algorithms using LIFO schedulers (LIFO-backpressure). We uncover a surprising behavior in which, under certain channel conditions, the average delay of packets decreases as the traffic load in the network increases. We propose and analyze a queueing-theoretic model under which the scheduler can transmit packets only if the queue length (i.e., the number of packets in the queue) meets or exceeds a threshold, and we show that the model analytically bears out the observed phenomenon. Using matrix geometric methods, we derive a numerical solution for the average packet delay in the general case, and, using z-transform techniques, we further provide closed-form solutions for the average delay in special cases. Our analysis indicates that when the threshold is fixed (as may happen under lossless channel conditions), the average delay increases with increasing traffic load, as expected. On the other hand, when the threshold fluctuates (as may happen under changing, lossy channel conditions), the average delay may decrease, sometimes substantially, with the traffic load. We corroborate these findings with TOSSIM simulations using real channel traces and run on different types of networks.