Randomized scheduling algorithm for queueing networks

DOI10.1214/11-AAP763zbMath1411.60135arXiv0908.3670MaRDI QIDQ2428047

Jinwoo Shin, Devavrat Shah

Publication date: 20 April 2012

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

stabilityschedulingmixing timealohabuffered circuit switched networkslowly varying Markov chainwireless medium access

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Network protocols (68M12) Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20)

Related Items

Adding edge dynamics to bipartite random-access networks ⋮ Stability conditions for a discrete-time decentralised medium access algorithm ⋮ Limit theorems and structural properties of the cat-and-mouse Markov chain and its generalisations ⋮ Queue-proportional rate allocation with per-link information in multihop wireless networks ⋮ Performance of CSMA in multi-channel wireless networks ⋮ Delay performance in random-access networks ⋮ Lingering issues in distributed scheduling ⋮ Transition time asymptotics of queue-based activation protocols in random-access networks ⋮ Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms ⋮ Queue-Based Random-Access Algorithms: Fluid Limits and Stability Issues ⋮ Concave switching in single-hop and multihop networks ⋮ A stochastic analysis of resource sharing with logarithmic weights ⋮ Stability of a Markov-modulated Markov Chain, with application to a wireless network governed by two protocols ⋮ Stability and moment bounds under utility-maximising service allocations: Finite and infinite networks ⋮ Distributed link scheduling in wireless networks ⋮ Crossover times in bipartite networks with activity constraints and time-varying switching rates

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Markov chains and stochastic stability
• Geometric bounds for eigenvalues of Markov chains
• Loss networks
• Gibbs measures and phase transitions
• MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
• Asymptotic optimality of maximum pressure policies in stochastic processing networks
• Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
• Polynomial-Time Approximation Algorithms for the Ising Model
• Matrix Analysis
• A random polynomial-time algorithm for approximating the volume of convex bodies
• AN OVERVIEW OF SOME STOCHASTIC STABILITY METHODS(<Special Issue>Network Design, Control and Optimization)
• Applied Probability and Queues
• Allocation of interdependent resources for maximal throughput
• Non-approximability results for optimization problems on bounded degree instances
• Distributed Random Access Algorithm: Scheduling and Congestion Control
• 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
• Monte Carlo sampling methods using Markov chains and their applications