Novel Architectures and Algorithms for Delay Reduction in Back-pressure Scheduling and Routing
arXiv:0901.1312
Abstract
The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its delay performance may be quite poor even when the traffic load is not close to network capacity due to the following two reasons. First, each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. Second, the back-pressure routing algorithm may route some packets along very long routes. In this paper, we present solutions to address both of the above issues, and hence, improve the delay performance of the back-pressure algorithm. One of the suggested solutions also decreases the complexity of the queueing data structures to be maintained at each node.
A short version of this paper is accepted to the INFOCOM 2009 Mini-Conference
Cited by in corpus (19)
- Throughput Optimizing Localized Link Scheduling for Multihop Wireless Networks Under Physical Interference Model
- Throughput-Optimal Scheduling Design with Regular Service Guarantees in Wireless Networks
- Delay-Guaranteed Cross-Layer Scheduling in Multi-Hop Wireless Networks
- Backpressure-based Packet-by-Packet Adaptive Routing in Communication Networks
- The Power of Online Learning in Stochastic Network Optimization
- Congestion Control and Routing over Challenged Networks
- Towards a Queueing-Based Framework for In-Network Function Computation
- Index Policies for Optimal Mean-Variance Trade-Off of Inter-delivery Times in Real-Time Sensor Networks
- Throughput Optimal Routing in Overlay Networks
- A Benes Packet Network
- Cross-Layer Control for Worse Case Delay Guarantees in Heterogeneous Powered Wireless Sensor Network via Lyapunov Optimization
- Max-Weight Scheduling in Queueing Networks with Heavy-Tailed Traffic
- Timely-Throughput Optimal Scheduling with Prediction
- LIFO-Backpressure Achieves Near Optimal Utility-Delay Tradeoff
- Throughput-Optimal Load Balancing for Intra Datacenter Networks
- Optimal Control for Generalized Network-Flow Problems
- BRPL: Backpressure RPL for High-throughput and Mobile IoTs
- Learning-aided Stochastic Network Optimization with Imperfect State Prediction
- Delay-Aware Cross-Layer Design for Network Utility Maximization in Multi-hop Networks