Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse

Devavrat Shah, Damon Wischik

TL;DR

This paper establishes multiplicative state space collapse for switched networks running generalized maximum-weight scheduling policies under heavy traffic conditions. Crucially, by removing the standard but restrictive "complete resource pooling" assumption, the authors demonstrate that the relationship between a network's multi-dimensional workload and its individual queue sizes is governed by a non-linear optimization problem.

What Problem Does This Paper Address?

Switched networks are mathematical models used to design and analyze complex engineering systems like input-queued internet routers and multi-hop wireless networks. In these systems, physical constraints (like hardware limitations or wireless interference) prevent all queues from being served simultaneously. A scheduling policy must decide which combination of queues to serve at any given time slot.

An input-queued switch architecture with input and output ports

While the classic Maximum Weight (MW) scheduling policy is known to maximize network throughput, understanding its behavior under heavy traffic (the diffusion limit) is notoriously difficult. To make the math tractable, prior literature heavily relied on a condition called Complete Resource Pooling (CRP). CRP assumes the network has a single dominant bottleneck that perfectly balances all heavily loaded queues, collapsing the network's state into a simple one-dimensional line.

However, real-world networks often feature multiple bottlenecks and do not satisfy CRP. This paper tackles the challenge of analyzing single-hop and multi-hop switched networks under generalized maximum-weight policies ($MW-f$) without the simplifying crutch of complete resource pooling.

Methods

The authors use a rigorous sample-path mathematical framework consisting of several key steps:

  1. Fluid Approximation: They define a deterministic "fluid model" that describes the network's dynamics at the rate level rather than tracking discrete packets. Using Bramson’s cluster-point method, they prove that the stochastic network processes converge uniformly to the solutions of this fluid model when scaled appropriately.
  2. Static Planning Framework: They formulate primal and dual linear optimization problems to identify the network's critically loaded virtual resources (bottlenecks).
  3. Nonlinear Lifting Map: Under CRP, mapping total workload to individual queue sizes is a simple linear operation. Without CRP, the authors show this relationship becomes a nonlinear lifting map ($\Delta W$), defined as the unique solution to a convex optimization problem.
  4. Lyapunov Functions: They use a convex Lyapunov function to show that the fluid model naturally drives the network state toward a set of invariant states characterized by this lifting map.

Datasets

Not discussed in the paper. This is a purely theoretical paper rooted in probability theory and queueing network analysis; no empirical datasets or simulation logs were used.

Key Insights and Ideas

  • The Geometry of Heavy Traffic is Nonlinear: The most significant conceptual shift is that without CRP, a network's state space does not collapse into a simple line. Instead, it collapses onto a multi-dimensional, nonlinear surface defined by a network-wide optimization problem.
  • Backpressure Dynamics: In multi-hop networks, the generalized maximum-weight policy naturally manifests as a "backpressure" algorithm. The incentive to route data between queues depends on the difference in "pressure" (a function of queue size) between upstream and downstream nodes.
  • Validating the $\alpha \to 0$ Conjecture: Engineers have long observed in simulations that the $MW-\alpha$ policy reduces average queueing delays as $\alpha$ gets closer to 0. This paper provides a theoretical justification: under a "complete loading" condition (where every port is a bottleneck), the fluid model solutions approach absolute optimality (minimizing total network backlog) as $\alpha \to 0$.

Key Results

  • Multiplicative State Space Collapse (Theorem 7.1): The authors prove that under heavy traffic scaling ($r \to \infty$), the deviation of the scaled queue size process $\hat{\mathbf{q}}^r(\cdot)$ from its optimal nonlinear lifting map representation $\Delta W(\hat{\mathbf{q}}^r(\cdot))$ becomes negligible relative to the overall size of the queues: $$\mathbb{P}\left( \frac{\|\hat{\mathbf{q}}^r(\cdot) - \Delta W(\hat{\mathbf{q}}^r(\cdot))\|}{\|\hat{\mathbf{q}}^r(\cdot)\| \vee 1} < \delta \right) \to 1$$
  • Near-Optimality under Complete Loading (Theorem 8.2): They prove that for a single-hop network under complete loading, the total fluid backlog under the $MW-\alpha$ policy is tightly bounded: $$1 \cdot \mathbf{q}(t) \le N^{\alpha/(1+\alpha)}1 \cdot \mathbf{q}(0)$$ As $\alpha \to 0$, the coefficient matches the absolute theoretical lower bound for any scheduling policy.

Limitations and Future Work

  • The Diffusion Approximation Gap: While the authors successfully prove state space collapse (showing where the queue trajectories live in heavy traffic), they stop short of proving a full diffusion approximation (proving that the fluctuations around this surface behave like a reflected Brownian motion). They highlight this as a vital next step for networks without CRP.
  • Computational Complexity: Maximum-weight policies require solving a complex optimization problem (like max-weight matching) at every single time slot, which is too slow for high-speed internet routers. The authors note that future work should focus on applying these fluid techniques to simpler, more practical heuristic policies.
  • Open Conjectures: The paper introduces a new scheduling policy called MSMW-log and conjectures (Conjecture 8.5) that it minimizes the expected sum of queue sizes in the diffusion limit under complete loading.

Summary updated

Abstract

We consider a queueing network in which there are constraints on which queues may be served simultaneously; such networks may be used to model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time. We consider a family of scheduling policies, related to the maximum-weight policy of Tassiulas and Ephremides [IEEE Trans. Automat. Control 37 (1992) 1936--1948], for single-hop and multihop networks. We specify a fluid model and show that fluid-scaled performance processes can be approximated by fluid model solutions. We study the behavior of fluid model solutions under critical load, and characterize invariant states as those states which solve a certain network-wide optimization problem. We use fluid model results to prove multiplicative state space collapse. A notable feature of our results is that they do not assume complete resource pooling.
BibTeX
@inproceedings{shah2010switched,
  author = {Devavrat Shah and Damon Wischik},
  title = {{Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse}},
  booktitle = {DSpace@MIT},
  year = {2010},
  doi = {10.48550/arxiv.1004.1995},
}
Figure