Throughput Optimal Decentralized Scheduling of Multihop Networks With End-to-End Deadline Constraints: Unreliable Links

We consider multihop networks serving multiple flows in which packets have hard deadlines. Packets not delivered to their destinations by their deadlines are of no value. The throughput of packets delivered within their deadlines is called the timely throughput. We address the design of packet scheduling, transmit power control, and routing policies that maximize any specified weighted average of the timely throughputs of the multiple flows. We determine a tractable linear program (LP) whose solution yields an optimal routing, scheduling, and power control policy, when nodes have average-power constraints. The optimal policy is fully decentralized, with decisions regarding any packet's transmission scheduling, transmit power level, and routing, based solely on the age and location of that packet. No knowledge of states of any other packets in the network is needed. This resolves a fundamental obstacle that arises whenever one attempts to optimally schedule networks. The number of variables in the LP is bounded by the product of the square of the number of nodes, the number of flows, the maximum relative deadline, and the number of transmit power levels. This solution is obtained from decomposition of the Lagrangian of the constrained Markov decision process describing the complete network state. Global coordination is achieved through a price for energy usage paid by a packet each time that its transmission is attempted at a node. It is fundamentally different from the decomposition of the fluid model used to derive the backpressure policy, which is throughput optimal when packets have no deadlines, where prices are related to queue lengths. If nodes instead have peak-power constraints, then a decentralized policy obtained by simple truncation is near optimal as link capacities increase in a proportional way.

• Publication year

  2016

• Venue

  IEEE Transactions on Automatic Control

• Publication date

  2016-06-06

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1109/TAC.2018.2874671arXiv 1606.01608
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• South Bend

  2020cited by this paper
• Closed Form Summation for Classical Distributions: Variations on a Theme

  2016cited by this paper
• Optimal Online Scheduling With Arbitrary Hard Deadlines in Multihop Communication Networks

  2016cited by this paper
• Broadcasting Delay-Constrained Traffic Over Unreliable Wireless Links With Network Coding

  2015cited by this paper
• Decentralized throughput maximizing policies for deadline-constrained wireless networks

  2015cited by this paper
• Optimizing quality of experience of dynamic video streaming over fading wireless networks

  2015cited by this paper
• Millimeter-Wave Cellular Wireless Networks: Potentials and Challenges

  2014cited by this paper
• On Storage and Renewables : A Theory of Sizing and Uncertainty

  2014cited by this paper
• Scheduling Heterogeneous Real-Time Traffic Over Fading Wireless Channels

  2014cited by this paper
• Fluctuation analysis of debt based policies for wireless networks with hard delay constraints

  2014cited by this paper
• Pathwise performance of debt based policies for wireless networks with hard delay constraints

  2013cited by this paper
• Packets with Deadlines: A Framework for Real-Time Wireless Networks

  2013cited by this paper
• Real-time communication over unreliable wireless links: a theory and its applications

  2012cited by this paper
• Scheduling for End-to-End Deadline-Constrained Traffic With Reliability Requirements in Multihop Networks

  2012cited by this paper
• A Novel Architecture for Reduction of Delay and Queueing Structure Complexity in the Back-Pressure Algorithm

  2011cited by this paper
• Scheduling for end-to-end deadline-constrained traffic with reliability requirements in multi-hop networks

  2011cited by this paper
• A Survey of Recent Results on Real-Time Wireless Networking

  2011cited by this paper
• Optimality of periodwise static priority policies in real-time communications

  2011cited by this paper
• Convex optimization

  2010cited by this paper
• Utility-optimal scheduling in time-varying wireless networks with delay constraints

  2010cited by this paper
• Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling

  2010cited by this paper
• Achieving single channel, full duplex wireless communication

  2010cited by this paper
• Full-duplex wireless communications using off-the-shelf radios: Feasibility and first results

  2010cited by this paper
• A Distributed CSMA Algorithm for Throughput and Utility Maximization in Wireless Networks

  2010cited by this paper
• Scheduling Periodic Real-Time Tasks with Heterogeneous Reward Requirements

  2010cited by this paper
• On Combining Shortest-Path and Back-Pressure Routing Over Multihop Wireless Networks

  2009cited by this paper
• A Theory of QoS for Wireless

  2009cited by this paper
• Optimal Scheduling for Fair Resource Allocation in Ad Hoc Networks With Elastic and Inelastic Traffic

  2009cited by this paper
• A Stable On-line Algorithm for Energy Efficient Multi-user Scheduling

  2009cited by this paper
• Admission control and scheduling for QoS guarantees for variable-bit-rate applications on wireless channels

  2009cited by this paper
• Scheduling Heterogeneous Real-Time Traffic over Fading Wireless Channels

  2009cited by this paper
• Delay Analysis for Multi-Hop Wireless Networks

  2009cited by this paper
• Utility Maximization for Delay Constrained QoS in Wireless

  2009cited by this paper
• Resource Allocation for OFDMA System with Orthogonal Relay using Rateless Code

  2008cited by this paper
• Stochastic Approximation: A Dynamical Systems Viewpoint

  2008cited by this paper
• Polynomial Complexity Algorithms for Full Utilization of Multi-Hop Wireless Networks

  2007cited by this paper
• Rethinking information theory for mobile ad hoc networks

  2007cited by this paper
• Joint congestion control, routing, and MAC for stability and fairness in wireless networks

  2006cited by this paper
• A tutorial on cross-layer optimization in wireless networks

  2006cited by this paper
• Fundamentals of Wireless Communication

  2005cited by this paper
• Joint rate control and scheduling in multihop wireless networks

  2004influential reference
• Dynamic power allocation and routing for time varying wireless networks

  2003cited by this paper
• Communication over fading channels with delay constraints

  2002cited by this paper
• Scheduling algorithms for a mixture of real-time and non-real-time data in HDR

  2001cited by this paper
• Constrained Markov Decision Processes

  1999cited by this paper
• Rate control for communication networks: shadow prices, proportional fairness and stability

  1998cited by this paper
• Stochastic approximation with two time scales

  1997cited by this paper
• Wireless Communications: Principles and Practice

  1996cited by this paper
• Constrained Markov decision processes with total cost criteria: Occupation measures and primal LP

  1996influential reference
• Multi‐Armed Bandit Allocation Indices

  1990cited by this paper
• On an index policy for restless bandits

  1990cited by this paper
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

  1990cited by this paper
• Multi-armed Bandit Allocation Indices

  1989cited by this paper
• Control of Markov Chains with Long-Run Average Cost Criterion

  1988cited by this paper
• Restless bandits: activity allocation in a changing world

  1988influential reference
• Walras' Economics. A Pure Theory of Capital and Money.

  1978cited by this paper
• Walras' economics : a pure theory of capital and money

  1977cited by this paper
• Stochastic approximation algorithms and applications

  1973cited by this paper
• Linear Programming and Sequential Decisions

  1960cited by this paper
• A Stochastic Approximation Method

  1951cited by this paper

• A Constrained RL Approach for Cost-Efficient Delivery of Latency-Sensitive Applications

  2026cites this paper
• Utility Maximization in Wireless Backhaul Networks with Service Guarantees

  2026cites this paper
• Delay-Constrained Dynamic Network Control with Multi-Agent Deep Reinforcement Learning

  2025cites this paper
• Causality-driven RL-based Scheduling Policies for Diverse Delay Constraints

  2025influential citation
• Sequential Fair Allocation With Replenishments: A Little Envy Goes An Exponentially Long Way

  2025cites this paper
• Learning-Based Cost-Aware Defense of Parallel Server Systems against Malicious Attacks

  2025cites this paper
• Region-based coordination for distributed resource allocation in sidelink mesh networks

  2025cites this paper
• Beyond Static Populations: Efficient Delay-Constrained Scheduling for Dynamic Users via Deep Reinforcement Learning

  2025influential citation
• A Flexible Multi-Agent Deep Reinforcement Learning Framework for Dynamic Routing and Scheduling of Latency-Critical Services

  2025cites this paper
• Segment EDF: A Scheduling Policy With Tight Deterministic Latency Under Multi-Hop Networks

  2025cites this paper
• Measurement Based Delay and Jitter Constrained Wireless Scheduling With Near-Optimal Spectral Efficiency

  2025cites this paper
• P2S-XR: Predictive and Scalable Scheduling for Concurrent Multi-User XR Services

  2025cites this paper
• Resilient and Reliable Cloud Network Control for Mission-Critical Latency-Sensitive Service Chains

  2025cites this paper
• Distributed Delay-Aware Link Scheduling and Route Selection in mmWave IAB Networks

  2024cites this paper
• User-Perceived Capacity: Theory, Computation, and Achievable Policies

  2024cites this paper
• Offline Learning-Based Multi-User Delay-Constrained Scheduling

  2024influential citation
• AoI, Timely-Throughput, and Beyond: A Theory of Second-Order Wireless Network Optimization

  2024cites this paper
• Distributed Scheduling for Throughput Maximization Under Deadline Constraint in Wireless Mesh Networks

  2024cites this paper
• Near-Optimal Packet Scheduling in Multihop Networks with End-to-End Deadline Constraints

  2024cites this paper
• Optimal Slicing and Scheduling with Service Guarantees in Multi-Hop Wireless Networks

  2024cites this paper
• Toward Natively Intelligent Semantic Communications and Networking

  2024cites this paper
• Multi-User Delay-Constrained Scheduling With Deep Recurrent Reinforcement Learning

  2024influential citation
• Semi-Infinitely Constrained Markov Decision Processes and Provably Efficient Reinforcement Learning

  2024cites this paper
• Scheduling Stochastic Traffic With End-to-End Deadlines in Multi-hop Wireless Networks

  2024cites this paper
• Semi-Infinitely Constrained Markov Decision Processes and Efficient Reinforcement Learning

  2023cites this paper
• Meeting Coflow Deadlines in Data Center Networks With Policy-Based Selective Completion

  2023influential citation
• Near-Optimal Packet Scheduling in Multihop Networks with End-to-End Deadline Constraints

  2023cites this paper
• Enhancing XR Application Performance in Multi-Connectivity Enabled mmWave Networks

  2023cites this paper
• Age-Dependent Distributed MAC for Ultra-Dense Wireless Networks

  2023cites this paper
• Randomized Scheduling of Real-Time Traffic in Wireless Networks Over Fading Channels

  2023cites this paper
• Resource Scheduling in Vehicular Networks with Age of Information and Channel Awareness

  2022cites this paper
• Two stage downlink scheduling for balancing QoS in multihop IAB networks

  2022cites this paper
• Effective multi-user delay-constrained scheduling with deep recurrent reinforcement learning

  2022influential citation
• Ultra-Reliable Distributed Cloud Network Control With End-to-End Latency Constraints

  2022influential citation
• Robust Wireless Scheduling under Arbitrary Channel Dynamics and Feedback Delay (Invited Paper)

  2021cites this paper
• Randomized Scheduling of Real-Time Traffic in Wireless Networks Over Fading Channels

  2021cites this paper
• Resource Management for 5G NR Integrated Access and Backhaul: A Semi-Centralized Approach

  2021cites this paper
• Scheduling of Wireless Edge Networks for Feedback-Based Interactive Applications

  2021cites this paper
• Adaptive CSMA for Decentralized Scheduling of Multi-Hop Networks With End-to-End Deadline Constraints

  2021influential citation
• Age-Dependent Distributed MAC for Ultra-Dense Wireless Networks

  2021cites this paper
• Optimal Cloud Network Control with Strict Latency Constraints

  2021cites this paper
• Model-Based Reinforcement Learning for Infinite-Horizon Discounted Constrained Markov Decision Processes

  2021cites this paper
• Achieving QoS for Real-Time Bursty Applications over Passive Optical Networks

  2021influential citation
• Safe Exploration for Constrained Reinforcement Learning with Provable Guarantees

  2021cites this paper
• Spider: A Multi-Hop Millimeter-Wave Network for Live Video Analytics

  2021cites this paper
• DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning

  2021cites this paper
• Multihop Wireless Networks With Quality-of-Service: Fluid and Diffusion Approximations

  2020cites this paper
• Spider: Next generation Live Video Analytics over Millimeter-Wave Networks

  2020influential citation
• Multi-armed bandits with dependent arms

  2020cites this paper
• Reinforcement Learning for Multi-Hop Scheduling and Routing of Real-Time Flows

  2020influential citation
• Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs

  2020cites this paper
• Optimal Mode Selection in D2D Communication With Deadline Constraint: A CMDP Perspective

  2020cites this paper
• Learning in Constrained Markov Decision Processes

  2020cites this paper
• Diffusion Approximation Analysis of MultihopWireless Networks: Quality-of-Service and Convergence of Stationary Distribution

  2020cites this paper
• Minimizing Age of Information With Power Constraints: Multi-User Opportunistic Scheduling in Multi-State Time-Varying Channels

  2019influential citation
• Online Routing and Scheduling With Capacity Redundancy for Timely Delivery Guarantees in Multihop Networks

  2019cites this paper
• Packet Scheduling in Multihop Networks with Individual Packet Delay Constraints

  2019cites this paper
• Resource Allocation for Real-Time D2D Communications Underlaying Cellular Networks

  2019cites this paper
• Broadcasting Real-Time Flows in Integrated Backhaul and Access 5G Networks

  2019cites this paper
• Optimal Decentralized Dynamic Policies for Video Streaming over Wireless Channels

  2019cites this paper
• Minimizing Age of Information with Power Constraints: Opportunistic Scheduling in Multi-State Time-Varying Networks

  2019influential citation
• Optimal Age-Energy Trade-off via Sleep-Wake Scheduling

  2019cites this paper
• Scheduling to Minimize Age of Information in Multi-State Time-Varying Networks with Power Constraints

  2019cites this paper
• Optimal Information Updating based on Value of Information

  2019cites this paper
• Quality-of-Service in Multihop Wireless Networks: Diffusion Approximation

  2018cites this paper
• Reduced-complexity delay-efficient throughput-optimal distributed scheduling with heterogeneously delayed network-state information

  2018cites this paper
• Routing and Scheduling Transient Flows for QoS in Multi-hop Wireless Networks

  2018cites this paper
• Network Utility Maximization Under Maximum Delay Constraints and Throughput Requirements

  2018cites this paper
• Wireless scheduling with deadline and power constraints

  2018cites this paper
• Throughput Optimal Decentralized Scheduling of Multi-Hop Networks with End-to-End Deadline Constraints: II Wireless Networks with Interference

  2017cites this paper
• Optimal Routing for Delay-Sensitive Traffic in Overlay Networks

  2017cites this paper
• A Distributed Scheduling Algorithm to Provide Quality-of-Service in Multihop Wireless Networks

  2017influential citation
• Timely-Throughput Optimal Scheduling with Prediction

  2017cites this paper
• Distributed Control and Quality-of-Service in Multihop Wireless Networks

  2017cites this paper
• Risk-sensitive optimal control of queues

  2017cites this paper
• Node-Based Service-Balanced Scheduling for Provably Guaranteed Throughput and Evacuation Time Performance

  2015cites this paper
• MIT Open Access Articles Risk-sensitive optimal control of queues

  year unknowncites this paper