Throughput Optimal Decentralized Scheduling of Multi-Hop Networks with End-to-End Deadline Constraints: Unreliable Links

Abstract

We consider unreliable multi-hop networks serving multiple flows in which packets not delivered to their destination nodes by their deadlines are dropped. We address the design of policies for routing and scheduling packets that optimize any specified weighted average of the throughputs of the flows. We provide a new approach which directly yields an optimal distributed scheduling policy that attains any desired maximal timely-throughput vector under average-power constraints on the nodes. It pursues a novel intrinsically stochastic decomposition of the Lagrangian of the constrained network-wide MDP rather than of the fluid model. All decisions regarding a packet's transmission scheduling, transmit power level, and routing, are completely distributed, based solely on the age of the packet, not requiring any knowledge of network state or queue lengths at any of the nodes. Global coordination is achieved through a tractably computable "price" for transmission energy. This price is different from that used to derive the backpressure policy where price corresponds to queue lengths. A quantifiably near-optimal policy is provided if nodes have peak-power constraints.

References in corpus (2)

• Millimeter Wave Cellular Wireless Networks: Potentials and Challenges
• Optimizing Quality of Experience of Dynamic Video Streaming over Fading Wireless Networks

Cited by in corpus (4)

• Learning in Markov Decision Processes under Constraints
• Effective Multi-User Delay-Constrained Scheduling with Deep Recurrent Reinforcement Learning
• AoI, Timely-Throughput, and Beyond: A Theory of Second-Order Wireless Network Optimization
• Resource Management for 5G NR Integrated Access and Backhaul: a Semi-centralized Approach