Concave switching in single-hop and multihop networks

DOI10.1007/S11134-015-9447-9MaRDI QIDQ747723zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Neil Walton

Publication date 19 October 2015

Published in Queueing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

utility maximizationproportional fairnessbackpressure policymax-weight policyswitched queueing networks

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: Switched queueing networks model wireless networks, input queued switches and numerous other networked communications systems. For single-hop networks, we consider a {($alpha,g$)-switch policy} which combines the MaxWeight policies with bandwidth sharing networks -- a further well studied model of Internet congestion. We prove the maximum stability property for this class of randomized policies. Thus these policies have the same first order behavior as the MaxWeight policies. However, for multihop networks some of these generalized polices address a number of critical weakness of the MaxWeight/BackPressure policies. For multihop networks with fixed routing, we consider the Proportional Scheduler (or (1,log)-policy). In this setting, the BackPressure policy is maximum stable, but must maintain a queue for every route-destination, which typically grows rapidly with a network's size. However, this proportionally fair policy only needs to maintain a queue for each outgoing link, which is typically bounded in number. As is common with Internet routing, by maintaining per-link queueing each node only needs to know the next hop for each packet and not its entire route. Further, in contrast to BackPressure, the Proportional Scheduler does not compare downstream queue lengths to determine weights, only local link information is required. This leads to greater potential for decomposed implementations of the policy. Through a reduction argument and an entropy argument, we demonstrate that, whilst maintaining substantially less queueing overhead, the Proportional Scheduler achieves maximum throughput stability.

Recommendations

• Proportional switching in first-in, first-out networks
• Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
• Stability and Asymptotic Optimality of Generalized MaxWeight Policies
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Optimal queue-size scaling in switched networks

Cites work

• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 786513 (Why is no real title available?)
• Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks
• Ergodicity of stochastic processes describing the operation of open queueing networks
• Fluid model for a network operating under a fair bandwidth-sharing policy.
• Fluid models of congestion collapse in overloaded switched networks
• From local to global stability in stochastic processing networks through quadratic Lyapunov functions
• Large Deviations for the Stationary Measure of Networks Under Proportional Fair Allocations
• Large number of queues in tandem: scaling properties under back-pressure algorithm
• Logarithmic regret algorithms for online convex optimization
• MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• Open, Closed, and Mixed Networks of Queues with Different Classes of Customers
• Optimal queue-size scaling in switched networks
• Randomized scheduling algorithm for queueing networks
• Reversibility and stochastic networks. With a new preface
• SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATES
• Stability of queueing networks
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Structural properties of proportional fairness: stability and insensitivity
• Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse

Cited in

(9)

• Fluid models of congestion collapse in overloaded switched networks
• Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
• Stability and Asymptotic Optimality of Generalized MaxWeight Policies
• Queue-proportional rate allocation with per-link information in multihop wireless networks
• Stability conditions for a decentralised medium access algorithm: single- and multi-hop networks
• Optimal queue-size scaling in switched networks
• Switching near a network of rotating nodes
• Proportional switching in first-in, first-out networks
• Log-weight scheduling in switched networks

This page was built for publication: Concave switching in single-hop and multihop networks

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