On Scheduling for Minimizing End-to-End Buffer Usage Over Multihop Wireless Networks

While there has been much progress in designing backpressure based stabilizing algorithms for multihop wireless networks, end-to-end performance (e.g., End-to-end buffer usage) results have not been as forthcoming. This paper studies the end-to-end buffer usage (Sum of buffer utilization along a flow path) over a network with general topology and with fixed, loop free routes using a large-deviations approach. The authors first derive bounds on the best performance that any scheduling algorithm can achieve.