QQueueing networks Research companionRead the paper ↗
WORKING PROJECTUnpublished preprint · current version: 22 November 2026 (updated periodically) · Version history & planned work · All network projects

WORKING PROJECT · PREPRINT · 22 NOVEMBER 2026

When a node fails,
where do the queues go?

A research companion to a study of critical diffusion limits in queueing networks with unreliable nodes and two-stage dynamic routing.

EK
El'mira Yu. Kalimulina
Lomonosov Moscow State University

Unpublished preprint · author manuscript dated 22 November 2026 · 16 pages

NETWORK STATEt = 0.84
01
ACTIVE
02
ACTIVE
03
ACTIVE
04
UNAVAILABLE
WORKING POOL FAILED POOL
QUEUEING THEORY·RANDOM ENVIRONMENTS·HEAVY TRAFFIC·NETWORK DIFFUSIONS

THE QUESTION

A network of pools,
moving together.

Each node is a pool of parallel queues. A failure interrupts service at one pool, while the remaining network continues to move customers.

Model and assumptions in the paper ↗
01

Choose a destination

After service, a customer either leaves the network or is routed to an available node according to the current environmental phase.

02

Choose a queue

At the destination, sample d queues uniformly with replacement and join a shortest sampled queue.

03

Respond to failure

A failed pool keeps its customers and stops service until repair. Routing changes immediately with the environment.

A NOTE ON TERMINOLOGY

What does “pool” mean here?

A pool is a group of parallel, individually served queues at one network node. The shortest-of-d rule selects a queue inside that group. In the standard polling system, a server visits different queues according to a polling discipline. The manuscript studies the former model; links between these subjects can be developed separately.

INTERACTIVE LAB · RESEARCH PROTOTYPE

Explore the network
and its diffusion.

Choose a graph, follow the finite queueing system and inspect the associated switching diffusion.

NETWORK STATE

Finite network and environment

PHYSICAL TIME s0.00ACCELERATED t = s/N 0.000
WorkingBusy ≥ 90%Unavailable━━ active route┄┄ disabled route

OBSERVED POOL

Centered mean and diffusion

Pool 1
Network: centered mean Xᴺᵢ of the selected poolDiffusion: numerical SDE solution Xᵢ

For the selected pool i, the network curve averages all N queues: Xᴺᵢ(t) = (1/N)∑ᵦ Qᵢᵦ(Nt) − ⌊logdN⌋. The other curve is one numerical realisation of the limiting SDE for the same pool. Both curves use the same environmental path.

ACCELERATED TIME0
QUEUE EVENTS0
PROFILE W₁—
PATH GAP |Xᴺ−X|—
QUEUE COMPUTE TIME0 s
DIFFUSION COMPUTE TIME0 s
EULER STEPS0

The paths are sampled every 100 queue events and joined by lines. Their gap describes this chosen coupling; the theorem gives convergence in distribution, not a pathwise error estimate. Profile W₁ compares the empirical queue measure with Π at its current mean. Omitted tail contribution is at most —; this excludes floating-point error.

THE OBSERVED POOL

How the diffusion is constructed

The numbers below are computed for the current state of the selected network and the displayed numerical diffusion path. The displayed process Xᵢ is one coordinate of the switching diffusion in Theorem 1.

dXi=(Hih(Xi)−∑jpjieh(Xj))dt+dMi,h=gθ−1

Hᵢ is the availability indicator: 1 when pool i works and 0 when it is down. Here e is the current environment phase and Pᵉ is the corresponding active routing matrix. The simulator uses the same environmental path for the network and the numerical diffusion.

Build a network to compute the current values.
Calculations appear after the network is built.
How are P, h and the martingale term defined?

Routing. The entry pᵉᵢⱼ is the probability that a completion at active pool i is routed to active pool j. The laboratory starts with a base routing matrix and sets all entries incident to the failed pool to zero. The remaining probability is the probability of leaving the network.

aie=1−∑jpjie,pi0e=1−∑jpije.

For an active pool, the external arrival rate in physical time is (N−1)aᵉᵢ. The diagonal entries of Pᵉ are zero. For a ring the base probabilities are χ/2 to each neighbour; for a directed tandem they are χ along each forward edge; for a complete graph they are χ/(K−1). The sparse graph uses χ/max(deg i, deg j). An uploaded CSV supplies the base probabilities directly.

Profile function. The fractional part θ = {logdN} and the profile determine h:

h(x)=gθ(x)−1,gθ(x)=(d−1)dθω(x),ω=r−1.

The function r(w) is the mean of the integer-valued profile with tail probability exp(−wdʲ):

r(w)=∑j≥1e−wdj−∑j≤0(1−e−wdj).

The code numerically inverts r and interpolates gθ. Thus the displayed h values are numerical approximations.

Martingale noise. During a phase in which i is active, one representation of dMᵢ uses mutually independent Brownian motions Bᵢ and Bᵢⱼ for external events and directed routes:

dMi=ai+pi0dBi+∑jpjidBji−∑jpijdBij.

The Brownian route noise has opposite signs at its source and destination. For an active pool the total bracket rate is aᵢ+pᵢ₀+∑ⱼpⱼᵢ+∑ⱼpᵢⱼ = 2. Between two active pools, the cross-bracket rate is −(pᵢⱼ+pⱼᵢ). When a pool is down, both its drift and bracket rates are zero. The quantity dMᵢ is random, while these are its predictable covariance rates.

Failure and repair rates. In this laboratory exactly one of K pools is down. On accelerated time the whole phase changes at rate γ. An active specified pool fails at rate αᵢ=γ/(K−1), and the down pool is repaired at rate βᵢ=γ. Divide these rates by N for physical time. See the model and Theorem 1 in the paper.

The SDE is simulated numerically with the Euler–Maruyama scheme; gθ is interpolated. The displayed drift and weights are evaluated at the current numerical state.

COMPARE DISTRIBUTIONS

Empirical W₁ at a fixed time

Replicas are independent repetitions of the experiment. At accelerated time T, the curves below show the empirical quantiles for the observed pool, for the finite network and the numerically approximated diffusion.

Choose a comparison to start. Stop cancels the comparison; Pause above controls the network animation.

Distributions at the chosen N

Horizontal axis: quantile level. Vertical axis: centered mean. The empirical W₁ equals the average vertical gap between the two sorted samples.

Finite networkNumerical diffusion

Estimated W₁ as N changes

“Compare several N” repeats the experiment with N = dᵏ ≤ 200. These powers keep θ = {logdN} equal to zero. Each point is an estimated W₁ between two one-dimensional distributions at time T.

Estimated empirical W₁

Finite sample noise, finite N, approximate initialisation, interpolation and the Euler–Maruyama step affect both comparisons. These values are not a path-space W₁ or the Skorokhod J₁ metric. Displayed timings measure different numerical operations on this device.

THE MATHEMATICS

From discrete queues
to a switching diffusion.

Two results connect the finite queueing system with the behaviour of large networks. The paper states the precise assumptions and proofs.

THEOREM 1 · FIXED NETWORK

A diffusion for the
pool means.

Under critical loading, centered mean queue lengths and the environment converge jointly to a switching diffusion along subsequences of the fractional part of logdN. The empirical distribution in each pool tracks a profile indexed by its mean. A Brownian representation uses independent vertex and directed-route drivers whose combined covariance equals Γ; the theorem itself uses the symmetric positive semidefinite square root of Γ.

dXt = RJ(gθ(Xt) − 1)dt + ΓJ1/2dBt
Read the full statement ↗
THEOREM 6 · GROWING NETWORKS

Local limits on
large graphs.

On locally stabilizing routing graphs, the stationary diffusions converge on each fixed set of nodes along subsequences with the prescribed fractional logarithmic phase θ. The paper gives an exponential spatial bound and sufficient conditions for simultaneous growth of the graph and pool sizes.

W1,∞(ℒGK, ℒG) ≤ CT,δ e−δL
Read the full statement ↗

These summaries are guides to the manuscript. Consult the linked theorem statements for topology, assumptions, and the explicit constant.

EXPLORE THE ESTIMATE

How local is
the local limit?

This separate calculator evaluates the explicit upper bound in Theorem 6. T is the observation horizon in accelerated time; L is the graph distance within which two networks must agree, including the incident weights required by the theorem.

The bound uses a*, q*, T and L and does not explicitly use K. For fixed parameter values, the same bound applies to networks of different sizes when both satisfy its hypotheses. Their actual errors may differ.

Assumptions and complete estimate ↗

Set a* and q* manually or use the current network.

Neighbourhood of the observed pool

Build a network to see how many nodes lie within radius L.

Distances use the undirected union of phase graphs. This diagram is schematic. The theorem compares two graphs that agree locally.
THEOREM 6 UPPER BOUND—

For a* = 1, there are no internal routes and the spatial error is zero. For 0 < a* < 1, δ = −½ log(1−a*) and D = [1−eδ(1−a*)]−1. Graphs must agree on the specified radius-L neighbourhood with the phase labels and incident weights required by Theorem 6.

THE PAPER

Abstract

El'mira Yu. Kalimulina

Critical diffusion limits and a spatial convergence rate in queueing networks with unreliable nodes and two-stage dynamic routing

We study an open queueing network in which each node is a pool of N parallel queues. After service, a customer who remains in the network first chooses an available destination according to the current routing probabilities, then joins the shortest of d queues sampled there. A failed node holds its customers until repair. The offered load is 1-1/N per active node; the environmental transition rates scale as 1/N. We start from the joint stationary law of all queue lengths and the environmental phase specifying node availability and routing. Along subsequences on which the fractional part of log_d N converges, we prove joint convergence at times Nt of the centered node means and the phase to a switching diffusion and its driving chain. At repair, the first Wasserstein distance between the centered empirical queue-length distribution and the profile indexed by the centered mean at failure vanishes in probability. On growing, locally stabilizing graphs we obtain a stationary infinite-network limit on every fixed set of nodes. For the limiting diffusions, the Wasserstein error in the law of a node's trajectory decays exponentially in the radius of graph agreement. Under either a volume-growth bound or a bound on incoming routing weights, the numbers of nodes and queues per node may grow at arbitrary relative rates.

FURTHER READING

Sources & context.

Selected primary sources referenced by the manuscript, with direct links for further reading. The complete bibliography is in the paper.