Optimal queue-size scaling in switched networks

We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. In the main result of this paper, we provide a new class of online scheduling policies that achieve optimal average queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a conjecture about optimal queue-size scaling for input-queued switches.

• Publication year

  2011

• Venue

  Measurement and Modeling of Computer Systems

• Publication date

  2011-10-21

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1145/2254756.2254762arXiv 1110.4697
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Qualitative properties of α-fair policies in bandwidth-sharing networks

  2014influential reference
• On Queue-Size Scaling for Input-Queued Switches

  2014cited by this paper
• Fluid models of congestion collapse in overloaded switched networks

  2011influential reference
• Optimal scaling of average queue sizes in an input-queued switch: an open problem

  2011influential reference
• Qualitative properties of $\alpha$-fair policies in bandwidth-sharing networks

  2011cited by this paper
• Qualitative properties of α-weighted scheduling policies

  2010cited by this paper
• Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse

  2010influential reference
• State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy

  2009cited by this paper
• Resource pooling in congested networks: proportional fairness and product form

  2009cited by this paper
• Asymptotic optimality of maximum pressure policies in stochastic processing networks.

  2008influential reference
• Stability and Asymptotic Optimality of Generalized MaxWeight Policies

  2008influential reference
• Analysis and Simulation of a Fair Queuing Algorithm

  2008cited by this paper
• Large Deviations of Queues Sharing a Randomly Time-Varying Server

  2008cited by this paper
• Optimal delay scheduling in networks with arbitrary constraints

  2008cited by this paper
• Proportional fairness and its relationship with multi-class queueing networks

  2008influential reference
• Logarithmic delay for N × N packet switches under the crossbar constraint

  2007cited by this paper
• Structural Properties of LDP for Queue-Length Based Wireless Scheduling Algorithms

  2007influential reference
• Optimal throughput-delay scaling in wireless networks

  2006cited by this paper
• Optimal Throughput–Delay Scaling in Wireless Networks—Part II: Constant-Size Packets

  2006cited by this paper
• A Note on Insensitivity in Stochastic Networks

  2006influential reference
• Maximum Pressure Policies in Stochastic Processing Networks

  2005influential reference
• STATE SPACE COLLAPSE AND DIFFUSION APPROXIMATION FOR A NETWORK OPERATING UNDER A FAIR BANDWIDTH SHARING POLICY

  2004cited by this paper
• MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic

  2004influential reference
• AN OVERVIEW OF SOME STOCHASTIC STABILITY METHODS( Network Design, Control and Optimization)

  2004cited by this paper
• AN OVERVIEW OF SOME STOCHASTIC STABILITY METHODS

  2004cited by this paper
• A broader view of Brownian networks

  2003cited by this paper
• Insensitive Bandwidth Sharing in Data Networks

  2003influential reference
• Applied probability and queues, Second Edition

  2003cited by this paper
• Insensitivity in processor-sharing networks

  2002influential reference
• Lectures on discrete geometry

  2002influential reference
• The throughput of data switches with and without speedup

  2000cited by this paper
• Correction: Brownian models of open processing networks: canonical representation of workload

  2000influential reference
• Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse

  1998influential reference
• State space collapse with application to heavy traffic limits for multiclass queueing networks

  1998cited by this paper
• Balanced fluid models of multiclass queueing networks: a heavy traffic conjecture

  1995cited by this paper
• Markov Chains and Stochastic Stability

  1993cited by this paper
• A generalized processor sharing approach to flow control in integrated services networks-the single node case

  1992cited by this paper
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

  1990influential reference
• Analysis and simulation of a fair queueing algorithm

  1989cited by this paper
• Applied Probability and Queues

  1987cited by this paper
• Reversibility and Stochastic Networks

  1980cited by this paper
• On Queues in Heavy Traffic

  1962cited by this paper
• 1. A Certain Zero-sum Two-person Game Equivalent to the Optimal Assignment Problem

  1953cited by this paper
• Contributions to the theory of games

  1953cited by this paper

• Optimal weighted-delay scheduling in 2×2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2\times 2$$\end{document} inpu

  2025cites this paper
• Multi-dimensional State Space Collapse in Non-complete Resource Pooling Scenarios

  2024cites this paper
• Heavy Traffic Joint Queue Length Distribution withoutResource Pooling

  2022cites this paper
• On the Optimality of Greedy Policies in Dynamic Matching

  2022cites this paper
• An algorithm for improved delay-scaling in input-queued switches

  2022cites this paper
• Optimal Control in Fluid Models of nxn Input-Queued Switches under Linear Fluid-Flow Costs

  2021cites this paper
• Low-Complexity Switch Scheduling Algorithms: Delay Optimality in Heavy Traffic

  2020cites this paper
• Heavy-Traffic Universality of Redundancy Systems with Assignment Constraints

  2020cites this paper
• On the Optimal Control of Parallel Processing Networks with Resource Collaboration and Multitasking

  2020cites this paper
• Redundancy Scheduling with Locally Stable Compatibility Graphs.

  2020cites this paper
• Optimal Scheduling Control in Fluid Models of General $n\times n$ Input-Queued Switches

  2019cites this paper
• Improved Queue-Size Scaling for Input-Queued Switches via Graph Factorization

  2019influential citation
• Optimal Energy Procurement for Geo-distributed Data Centers in Multi-timescale Electricity Markets

  2018cites this paper
• Delay Scaling in Many-Sources Wireless Networks without Queue State Information

  2018cites this paper
• Centralized performance control for datacenter networks

  2017cites this paper
• Queue-Proportional Sampling

  2017cites this paper
• Coflow scheduling in input-queued switches: Optimal delay scaling and algorithms

  2017cites this paper
• Centralized Congestion Control and Scheduling in a Datacenter

  2017influential citation
• Collaboration and Multitasking in Networks: Prioritization and Achievable Capacity

  2017cites this paper
• Optimal Weighted-Delay Scheduling in $2\times 2$ Input-Queued Switches

  2017cites this paper
• Competitive Analysis of Constrained Queueing Systems

  2016cites this paper
• Stochastic Processing Networks

  2016cites this paper
• Queue-proportional rate allocation with per-link information in multihop wireless networks

  2016cites this paper
• Optimal heavy-traffic queue length scaling in an incompletely saturated switch

  2016cites this paper
• Heavy Traffic Queue Length Behavior in a Switch Under the MaxWeight Algorithm

  2016cites this paper
• Delay Optimal CSMA With Linear Virtual Channels Under a General Topology

  2016cites this paper
• Collaboration and Multitasking in Networks : Aligning Task Priorities and Collaboration Levels

  2015cites this paper
• Heavy-Traffic Behavior of the MaxWeight Algorithm in a Switch with Uniform Traffic

  2015cites this paper
• Concave switching in single-hop and multihop networks

  2015cites this paper
• Queue Length Behavior in a Switch under the MaxWeight Algorithm

  2015cites this paper
• Queue-Proportional Rate Allocation with Per-Link Information in Multihop Networks

  2015cites this paper
• Collaboration and Multitasking in Networks: Aligning Task Priorities and Collaboration Levels

  2015cites this paper
• Concave switching in single and multihop networks

  2014cites this paper
• Provable per-link delay-optimal CSMA for general wireless network topology

  2014cites this paper
• Store-forward and its implications for proportional scheduling

  2014cites this paper
• Fastpass

  2014cites this paper
• On Queue-Size Scaling for Input-Queued Switches

  2014cites this paper
• Scheduling in Switched Queueing Networks with Heavy-Tailed Trac

  2013cites this paper
• Deadline aware packet scheduling in switches for multimedia streaming applications

  2013cites this paper
• Stability of MaxWeight-({\alpha},g)

  2013cites this paper
• Diffusion approximation for an input-queued switch operating under a maximum weight matching policy

  2012cites this paper
• Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic

  2011cites this paper