Your Search Results

Use this resource - and many more! - in your textbook!

AcademicPub holds over eight million pieces of educational content for you to mix-and-match your way.

Experience the freedom of customizing your course pack with AcademicPub!
Not an educator but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

LIFO-Backpressure Achieves Near-Optimal Utility-Delay Tradeoff

By: Moeller, S.; Huang, L.; Krishnamachari, B.; Neely, M. J.;

2013 / IEEE


This item from - IEEE Transaction - Communication, Networking and Broadcast Technologies - There has been considerable work developing a stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay-efficient. In this paper, we show that the Backpressure algorithm, when combined with the last-in–first-out (LIFO) queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is within O(1/V) of the optimal value, for any scalar Vgeq 1, while maintaining an average delay of O([log(V)]2) for all but a tiny fraction of the network traffic. This result holds for a general class of problems with Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show a good match between theory and practice. Because some packets may stay in the queues for a very long time under LIFO-Backpressure, we further develop the LIFOp-Backpressure algorithm, which generalizes LIFO-Backpressure by allowing interleaving between first-in–first-out (FIFO) and LIFO. We show that LIFO p-Backpressure also achieves the same O(1/V) close-to-optimal utility performance and guarantees an average delay of O([log(V)]2) for the packets that are served during the LIFO period.