Stability of multiclass queueing networks under longest-queue and longest-dominating-queue scheduling

DOI10.1017/JPR.2016.10MaRDI QIDQ3188574zbMATH OpenOpenAlexFDO

Authors Ramtin Pedarsani, Jean Walrand

Publication date 11 August 2016

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.6582, https://projecteuclid.org/euclid.jap/1466172864

zbMATH Keywords

fluid modellongest-queue schedulingmulticlass queueing networksstability

Mathematics Subject Classification ID

Sample path properties (60G17) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic network models in operations research (90B15) Queues and service in operations research (90B22)

Abstract: We consider the stability of robust scheduling policies for multiclass queueing networks. These are open networks with arbitrary routing matrix and several disjoint groups of queues in which at most one queue can be served at a time. The arrival and potential service processes and routing decisions at the queues are independent, stationary and ergodic. A scheduling policy is called robust if it does not depend on the arrival and service rates nor on the routing probabilities. A policy is called throughput-optimal if it makes the system stable whenever the parameters are such that the system can be stable. We propose two robust polices: longest-queue scheduling and a new policy called longest-dominating-queue scheduling. We show that longest-queue scheduling is throughput-optimal for two groups of two queues. We also prove the throughput-optimality of longest-dominating-queue scheduling when the network topology is acyclic, for an arbitrary number of groups and queues.

Recommendations

• Stability of Kumar-Seidman networks under longest queue first policy
• Stability of queueing networks and scheduling policies
• Scheduling in multiclass networks with deterministic service times
• Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies
• scientific article; zbMATH DE number 786512

Cites work

• Dynamic server allocation to parallel queues with randomly varying connectivity
• Fluctuation smoothing policies are stable for stochastic re-entrant lines
• scientific article; zbMATH DE number 1190409 (Why is no real title available?)
• scientific article; zbMATH DE number 1278394 (Why is no real title available?)
• M-matrix characterizations. I: nonsingular M-matrices
• Maximum Pressure Policies in Stochastic Processing Networks
• Networks and dynamical systems
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• Stability analysis of parallel server systems under longest queue first
• Stability and Instability of Fluid Models for Reentrant Lines
• Stability of Kumar-Seidman networks under longest queue first policy
• Stability of queueing networks
• Stability of queueing networks and scheduling policies
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits
• The Stability of Two-Station Multitype Fluid Networks

Cited in

(14)

• Delay-optimal scheduling for two-hop relay networks with randomly varying connectivity: join the shortest queue-longest connected queue policy
• Pathwise stability of multiclass queueing networks
• A polling system with `join the shortest -- serve the longest' policy
• Stability of longest-queue-first scheduling in linear wireless networks with multihop traffic and one-hop interference
• Stability of Multiclass Queueing Networks Under FIFO Service Discipline
• Stability of Kumar-Seidman networks under longest queue first policy
• Stability and Instability of the MaxWeight Policy
• Subdiffusive load balancing in time-varying queueing systems
• Robust scheduling for flexible processing networks
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits
• A 3-queue polling system with join the shortest-serve the longest policy
• The non-preemptive `join the shortest queue-serve the longest queue' service system with or without switch-over times
• Longest path analysis in networks of queues: dynamic scheduling problems

This page was built for publication: Stability of multiclass queueing networks under longest-queue and longest-dominating-queue scheduling

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