Concave switching in single-hop and multihop networks

DOI10.1007/S11134-015-9447-9zbMATH Open1328.60206DBLPjournals/questa/Walton15arXiv1404.2725OpenAlexW2570207273WikidataQ59427661 ScholiaQ59427661MaRDI QIDQ747723FDOQ747723

Neil Walton

Publication date: 19 October 2015

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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
• Logarithmic regret algorithms for online convex optimization
• MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Fluid models of congestion collapse in overloaded switched networks
• Structural properties of proportional fairness: stability and insensitivity
• Ergodicity of stochastic processes describing the operation of open queueing networks
• Randomized scheduling algorithm for queueing networks
• Optimal queue-size scaling in switched networks
• Stability of queueing networks
• SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATES
• Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks
• Fluid model for a network operating under a fair bandwidth-sharing policy.
• Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
• Title not available (Why is that?)
• Large number of queues in tandem: scaling properties under back-pressure algorithm
• Title not available (Why is that?)
• 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

Cited In (4)

• 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
• Switching near a network of rotating nodes

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)