Compress the Gain, Not the Queues: Slowly Varying Weights for Multi-Hop CSMA Back-Pressure

Wireless nodes that share a channel without a central coordinator can still schedule close to optimally, provided they run a randomized access rule. In such a rule each link turns on with a probability tied to a "weight" that summarizes how urgently it needs to transmit. The catch is speed. The random process that decides who transmits takes time to settle, and that settling time grows exponentially with the largest weight. Weights must therefore change slowly, which is why the literature passes queue lengths through very flat functions such as $\log\log q$ or $\log q/g(q)$. This trick has been made rigorous almost exclusively for single-hop traffic, where a packet leaves the network after one transmission. In multi-hop networks packets are relayed, and the natural scheduling signal is back-pressure: the difference between a node's queue and its downstream neighbor's queue. The obvious composition applies the flat function to each queue and then takes the difference. We argue this composition is a trap. Each hop needs a weight difference of order one before the channel favors forwarding, and those differences add up along the route. The source queue must therefore reach the inverse of the flat function evaluated at (hop count × constant), which is exponential in path length for $\log$ and double-exponential for $\log\log$.

We propose a different placement of the slowness. Every link keeps its raw, linear back-pressure differential, and all of them are multiplied by one slowly varying positive gain. That gain is set from the largest differential in the neighborhood, not from the largest queue. The scheduling decision that back-pressure targets, which links form the maximum-weight set, does not change when all weights are multiplied by a common positive number. So the gain controls only how sharply the random access concentrates on that set and how fast it mixes. Because the gain is pinned to differentials rather than absolute backlogs, per-link weights stay bounded by a slow function of the largest differential. The prediction is that source backlog grows linearly in hop count, as in ideal centralized back-pressure, rather than exponentially.

Core Claim

Let $q_i$ be the backlog at node $i$ for a given flow and $D_l=(q_i-q_j)^+$ the positive back-pressure differential on link $l=(i,j)$. The proposed link weight, used as the log-odds of activation in a Glauber-dynamics/CSMA (carrier-sense random access) scheduler, is

$$w_l(t)=\gamma(t)\,D_l(t),\qquad \gamma(t)=\frac{f(\hat D(t))}{\hat D(t)},$$

where $f$ is a slowly growing function of the Ghaderi–Srikant type ($\log(1+x)/g(x)$), and $\hat D(t)$ is a slowly updated, locally gossiped estimate of the largest differential. The largest weight is then at most $f(\hat D)$, so the mixing-time bound has the same form as in the single-hop theory with $\hat D$ in place of $Q_{\max}$. The weights remain proportional to the linear differentials, so the target schedule is that of standard back-pressure.

The claim has three parts. First, with a global gain, the scheme is throughput-optimal for multi-hop flows. The sketch: the random scheduler's shortfall from the maximum weight is an additive entropy term of order $n$ in weight units. In raw units that is $n\hat D/f(\hat D)=o(\hat D)$, while the negative drift of the quadratic Lyapunov function grows linearly in the backlog. Second, at a fixed load the source backlog on an $H$-hop route scales as

$$Q_{\text{src}}\approx H\,f^{-1}(w^\ast)\ \ \text{(gain scaling)}\qquad\text{versus}\qquad Q_{\text{src}}\approx f^{-1}(H\,w^\ast)\ \ \text{(per-queue compression)},$$

where $w^\ast$ is the order-one weight a link needs before the scheduler reliably prefers it. Both forms follow because per-hop weights sum along the route to the source's weight under per-queue compression, but not under a common gain. Third, the gain only needs to vary slowly, so it can come from lagged, neighborhood-level gossip. The usual multi-hop weakness, stale global information, is then tolerable by design. With heterogeneous local gains whose ratios across neighbors are bounded by $1+\delta$, we expect stability over a $(1-O(\delta))$ fraction of capacity.

How This Sits Against Prior Work

The single-hop theory supplies the method. Network adiabatic theorem shows that a time-varying Glauber chain tracks its instantaneous stationary distribution when weights change slowly, and it uses $\log\log(q+e)$ with knowledge of $Q_{\max}$. Randomized scheduling algorithm for queueing networks proves throughput optimality for this class in packet- and circuit-switched models. On the Design of Efficient CSMA Algorithms relaxes the growth limit to $\log(1+q)/g(q)$. All three treat a packet as leaving the network after one hop, and they compress queues rather than differentials. Our proof reuses their tracking argument with the gain-scaled differential as the slowly varying parameter.

Two papers motivate the gap. Q-CSMA gives the practical discrete-time split into a contention mini-slot phase and a data phase, which we adopt as the implementation. It evaluates multi-hop interference graphs only with single-hop traffic and explicitly defers multi-hop routing. Delay-Based Back-Pressure Scheduling is fully multi-hop and fixes the "last packet" problem, in which trailing packets of a finished flow stall because queue differentials vanish. It relies on centralized maximum-weight or greedy scheduling, never on random access.

Two other papers modify the back-pressure weight itself. Enhancing the Delay Performance of Dynamic Backpressure Algorithms adds bias terms from queues beyond the next hop. Accelerated Backpressure Algorithm takes approximate Newton steps. Both assume slotted, coordinated control and ignore mixing-time limits, so they are complements to our gain rather than competitors at the MAC (medium access control) layer.

Some work constrains the design space. Fast Mixing of Parallel Glauber Dynamics shows that parallel updates mix in $O(\log n)$ on bounded-degree graphs, which tells us how much the constant $w^\ast$ can be shrunk. Self-synchronizing properties of CSMA wireless multi-hop networks shows that unweighted CSMA can fall into collision-free frames under saturation, but it provides no queue adaptation.

Research Program

The theoretical work has three pieces. The first is a positive-recurrence proof for the global-gain scheme under fixed routes and under dynamic back-pressure routing, where each node forwards the flow with the largest differential. The step that is new relative to the single-hop proofs is bounding the weight perturbation when one transmission decrements $q_i$ and increments $q_j$ at the same time, which shocks every link incident to both nodes. Under the gain, this shock is at most $2\gamma$ per event, and $\gamma\to0$ as differentials grow. The second piece is a $(1-O(\delta))$-capacity result for neighborhood gains whose ratios across adjacent nodes are bounded by $1+\delta$, together with a smoothing rule that enforces that bound. The third piece is the hop-count backlog scaling above, derived at fluid level for line networks. That derivation is what turns the claim into a falsifiable number.

The engineering work builds the scheme into a Q-CSMA-style slotted simulator. One component is a gossip protocol for $\hat D$ with configurable radius $k$ and update lag. The other is a delay-based variant that applies the same gain to sojourn-time differentials, following the D-BP metric. Because packet ages grow at rate one, those differentials cannot be used uncompressed under random access.

Baselines

The naive reference point is linear back-pressure fed directly into CSMA activation odds, with $w_l=D_l$. Network adiabatic theorem reports that linear weights cause queues to explode on its 100-node mesh, but it gives no divergence rate. We expect this baseline to fail and include it to show the failure mode transfers to multi-hop traffic.

The obvious composition is per-queue compression, $w_l=f(q_i)-f(q_j)$, using the same $f$ as our gain. Its weights are the gradient of a Lyapunov function, so it has a clean stability argument. It is therefore the most principled competitor and the direct ablation of our key ingredient: moving the compression from queues to a common gain. Beating it means a measurably smaller slope of log-backlog against hop count, and lower mean end-to-end delay at equal load, with neither stability region shrinking.

Per-link compression, $w_l=f(D_l)$, is the strongest heuristic competitor, discussed below. Both compressed baselines get the same $f$ family and the same tuning grid over its parameters as our method, and they run on identical arrival traces and slot budgets.

The strongest existing multi-hop schedulers are centralized maximum-weight back-pressure and D-BP with greedy scheduling. Both use exact or greedy schedules and so receive a coordination advantage we do not. We treat centralized maximum-weight back-pressure as an upper bound to approach, not a target to beat. On the 10-node, 5-flow mesh, Accelerated Backpressure Algorithm reports total backlog near 8,000 packets for traditional back-pressure and around 6,000 for soft back-pressure. Our scheme should land within a small factor of these with no synchronized coordination.

Q-CSMA's Hybrid scheme, which switches from greedy to CSMA above a queue threshold, will be run with back-pressure weights substituted. Its threshold gets the same tuning budget as our $f$.

For any CSMA scheduler under multi-hop traffic, there is no reported result found on Lacuna. The closest number is single-hop: On the Design of Efficient CSMA Algorithms reports average queues above 4,000 packets per link for $\log\log$ versus under 100 for its log-like function on the 24-link grid at $\rho=0.85$, and instability for $\sqrt q$ at $\rho=0.92$. We will reproduce these single-hop figures first, to validate the simulator.

Why not just…?

Why not just compress each queue and take the difference, which already has a Lyapunov proof? The proof concerns throughput, not delay. The scaling argument predicts that the backlog this design needs grows like $f^{-1}(Hw^\ast)$, exponential in hop count for $\log$-type $f$. The single-hop data already shows that flat functions can cost a factor of 40 in queue length (Ghaderi & Srikant), and summing along routes should make this worse. The line-network sweep over $H$ settles the question directly. If per-queue compression's log-backlog does not grow with $H$, our central prediction is wrong.

Why not just compress each link's differential, $f(D_l)$? This is a real threat. It bounds per-link weights the same way our gain does, and the same fluid argument gives it linear-in-$H$ backlog. What it gives up is the scale invariance of the maximum-weight decision. A concave $f$ favors two links with modest differentials over one link with a large differential, so it no longer targets back-pressure's schedule, and we know of no Lyapunov function for it. We will search for an instability instance: crafted bottlenecks, the 9-link ring with multi-hop flows, and chessboard traffic on the 10×10 mesh. If no instance appears and delays match, we will report that the contribution reduces to supplying a proof for a heuristic that already works, and recommend whichever form is simpler to deploy.

Why not just use greedy maximal scheduling, or Hybrid Q-CSMA, with back-pressure weights? Greedy scheduling is proven to reach only two-thirds of capacity on the 9-link ring, and Q-CSMA confirms that its queues grow without bound there. Hybrid Q-CSMA inherits CSMA's optimality but needs a hand-set threshold, which that paper leaves untuned. In multi-hop networks, edge nodes and central relays sit at very different backlogs, so one threshold is unlikely to suit both. We test this by comparing a best-tuned uniform threshold against our parameter-light gain on the grid with 9 multi-hop flows.

Why not just run synchronized slotted back-pressure? It requires solving an NP-hard maximum-weight set problem every slot, plus network-wide clock synchronization. On the scalability of IEEE 802.11 ad hoc networks shows that synchronization struggles to scale even in single-hop groups. We keep it only as the upper bound above.

Proposed Experiments

The decisive experiment is a line network with $H$ from 2 to 16 hops, a single flow, and loads from $\rho=0.5$ to $0.95$. We measure steady-state source backlog under per-queue compression, per-link compression, and gain scaling. Gain scaling succeeds if log-backlog is flat in $H$ while per-queue compression's grows linearly in $H$.

Next come the topologies from the file. The 24-link grid uses the 9 multi-hop flows from Delay-Based Back-Pressure. The 9-link ring is the known counterexample for greedy scheduling. The 10×10 mesh runs chessboard traffic from Network adiabatic theorem. The 10-node, 5-flow mesh is run both with static sources and with the active sources switching every 10 iterations, as in Accelerated Backpressure. On each we report the largest load with bounded queues, mean end-to-end delay against load, and control overhead for gossiping $\hat D$. On graphs small enough to solve exactly, we also report the gap between the scheduler's average weight and the exact maximum.

To probe the local-information question, we sweep the gossip radius $k$ and update lag. Stability that is insensitive to lag would support the claim that slowness makes stale estimates harmless. A breakdown when neighboring gains diverge would test the $(1-O(\delta))$ prediction.

The H-type topology, which is built to stall trailing packets, tests the delay-based variant against the last-packet problem. The criterion is that head-of-line delay for trailing packets stays bounded, as D-BP achieves with centralized scheduling, while plain queue-based weights let it grow without limit.