Throughput optimal scheduling policies in networks of constrained queues

DOI10.1007/S11134-014-9407-9zbMATH Open1316.60138arXiv1304.2554OpenAlexW2149613569MaRDI QIDQ475136FDOQ475136

Sumit K. Garg, J. Herrera

Publication date: 25 November 2014

Published in: Queueing Systems (Search for Journal in Brave)

Abstract: This report considers a fairly general model of constrained queuing networks that allows us to represent both MMBP (Markov Modulated Bernoulli Processes) arrivals and time-varying service constraints. We derive a set of sufficient conditions for throughput optimality of scheduling policies that encompass and generalize all the previously obtained results in the field. This leads to the definition of new classes of (non diagonal) throughput optimal scheduling policies. We prove the stability of queues by extending the traditional Lyapunov drift criteria methodology.

Full work available at URL: https://arxiv.org/abs/1304.2554

zbMATH Keywords

stabilityconstrained queueing networksoptimal scheduling policies

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Stochastic scheduling theory in operations research (90B36)

Cites Work

• Markov chains and stochastic stability
• Stochastic stability and control
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks
• Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits
• Stability and Asymptotic Optimality of Generalized MaxWeight Policies
• Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
• Maximum Pressure Policies in Stochastic Processing Networks
• On the Stability of Isolated and Interconnected Input-Queueing Switches Under Multiclass Traffic
• Qualitative properties of \(\alpha\)-fair policies in bandwidth-sharing networks
• Bounds on delays and queue lengths in input-queued cell switches
• Scheduling and performance limits of networks with constantly changing topology
• Throughput optimal scheduling policies in networks of constrained queues

Cited In (13)

• Utility Optimization in Congested Queueing Networks
• Title not available (Why is that?)
• On Throughput Optimality With Delayed Network-State Information
• Study on optimal queue-length-threshold scheduling policy for an ATM multiplexer with finite buffers and batch Poisson arrivals
• Queueing dynamics and maximal throughput scheduling in switched processing systems
• Throughput optimal scheduling policies in networks of constrained queues
• Asymptotically Optimal Policies for Hard-Deadline Scheduling Over Fading Channels
• Minimizing Congestion in Single-Source, Single-Sink Queueing Networks
• On the Asymptotic Optimality of the Gradient Scheduling Algorithm for Multiuser Throughput Allocation
• Optimal scheduling for constant-rate multi-mode systems
• Dynamic scheduling for queueing networks derived from discrete-review policies
• Scheduling Using Interactive Optimization Oracles for Constrained Queueing Networks
• Optimal scheduling in heterogeneous two-station queueing networks

This page was built for publication: Throughput optimal scheduling policies in networks of constrained queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475136)