📊 statistics

Uncovering the topology of an infinite-server queueing network from population data

This paper proposes and validates a consistent method-of-moments estimator for inferring the topology and parameters of an infinite-server queueing network using population data observed at Poisson time points, offering both parametric and model-free approaches.

Original authors: Hritika Gupta, Michel Mandjes, Liron Ravner, Jiesen Wang

Published 2026-09-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hritika Gupta, Michel Mandjes, Liron Ravner, Jiesen Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of operations research, scientists often study systems where things arrive, wait, get processed, and then leave. Think of a busy airport, a call center, or a network of computer servers. To understand how these systems work, researchers usually build a mathematical model that describes how fast things arrive, how long they stay, and where they go next. The goal is typically to predict how the system will behave so that it can be improved. However, in the real world, the rules of the game are rarely written down. The arrival rates, the service speeds, and the paths people take are hidden. The only thing an observer might see is a snapshot of how many items are present at different locations at specific moments in time. The challenge is to work backward from these snapshots to figure out the invisible rules that govern the flow. This is known as an inverse problem: trying to deduce the causes from the observed effects.

A team of researchers has developed a new way to solve this puzzle for a specific type of system called an infinite-server queueing network. In these networks, unlike a single checkout line where customers must wait their turn, every customer is served immediately and in parallel. There is no waiting time because there are always enough servers available. The researchers wanted to know if they could uncover the hidden structure of such a network—specifically, how fast customers arrive, where they go after being served, and how long they stay—using only data about the number of customers present at random points in time. They found that by looking at the statistical patterns in these counts, particularly how the numbers at one location relate to the numbers at another location a moment later, they could reconstruct the entire map of the network.

The researchers focused on a network made up of several stations. At each station, customers arrive from the outside world, receive service, and then either move to another station or leave the system entirely. The path a customer takes is determined by a set of probabilities, forming a routing map. The team's method relies on a technique called the method of moments. Instead of trying to guess the exact sequence of every single customer, they looked at the average number of customers at each station and, more importantly, how the number of customers at one station at a given time is related to the number at another station a short time later. By observing the network at random intervals, they could calculate these relationships. The key insight is that the way these numbers correlate over time reveals the direction of the flow. If a spike in the number of customers at Station A is consistently followed by a rise at Station B, it suggests a direct link from A to B.

To test their idea, the researchers created a series of computer simulations. They built virtual networks with different shapes, such as a straight line of stations, a circle, and more complex clusters. In these simulations, they knew the true rules of the game: the exact arrival rates, the service speeds, and the routing probabilities. They then fed their method only the simulated population counts, pretending they did not know the underlying rules. The results were striking. Even in networks with many stations and complex connections, the method accurately recovered the hidden structure. It correctly identified which stations were connected and the direction of those connections. It also successfully estimated the rates at which customers arrived and the speed of service, even when the researchers did not know the specific mathematical shape of the service times beforehand.

One of the most significant findings was the method's ability to distinguish between networks that look identical in terms of their total population but have different internal structures. For instance, two networks might have the same number of people at every station on average, yet one could have traffic flowing clockwise while the other flows counter-clockwise. Because the researchers' method looked at how the population at one station influenced the next station over time, it could tell these two scenarios apart. This is crucial because it means the method can reveal the true causal direction of flow, not just the static presence of connections.

The researchers also explored what happens when the data is imperfect. In many real-world situations, an observer might not see every single customer; some might be missed due to noise or limited visibility. The team adapted their method to account for this by estimating the probability that a customer is actually seen. Their simulations showed that even with this added layer of uncertainty, the method remained robust. It could still recover the network's structure and parameters with high accuracy. Furthermore, they demonstrated that their approach works even when they do not assume a specific mathematical formula for how long customers stay at a station. This "model-free" version of their method proved effective, showing that the technique does not rely on rigid assumptions about the nature of the service times.

The implications of this work extend beyond theoretical mathematics. Understanding the hidden structure of a network allows for better management and design. In social networks, for example, identifying the true flow of information could help pinpoint who the real influencers are or how misinformation spreads. In communication networks, it could help engineers find bottlenecks and optimize data flow. The researchers emphasize that their work provides a reliable way to infer the invisible architecture of complex systems using only the visible population counts. By turning simple observations of numbers into a detailed map of connections and flows, they have provided a powerful tool for uncovering the hidden logic of dynamic systems. The method is mathematically proven to be consistent, meaning that as more data is collected, the estimates get closer and closer to the true values, offering a solid foundation for future applications in diverse fields.

Technical Summary: Uncovering the Topology of an Infinite-Server Queueing Network from Population Data

Problem Statement
This paper addresses the statistical inference problem in a network of $n$ infinite-server queues ( $M/G/\infty$ ). In standard operations research, model parameters are often assumed known to evaluate performance metrics. However, in practice, these parameters must be inferred from data. The specific challenge tackled here is an "inverse problem": estimating the underlying exogenous parameters of the system based solely on indirect, periodic observations of the network's state.

The system is characterized by:

External Arrivals: Poisson processes with rates $\boldsymbol{\lambda}$ .
Service Times: Independent, identically distributed (per station) non-negative random variables $G_i$ with finite means.
Routing: A routing matrix $Q$ where $q_{ij}$ is the probability a customer moves from station $i$ to $j$ after service.
Observations: The network population vector $\mathbf{M}(t)$ is observed at random time points generated by a Poisson process with rate $\beta$ . The paper also considers "noisy" observations where only a fraction of customers are detected with unknown probabilities $\mathbf{p}$ .

The primary objective is to estimate the routing matrix $Q$ , the external arrival rates $\boldsymbol{\lambda}$ , and potentially the service-time distribution parameters (or the distribution itself) using only the observed queue lengths. A secondary goal is to recover the directed structure of the network, distinguishing between different topologies that may share the same stationary distribution.

Methodology
The authors propose a method-of-moments estimator. The approach relies on deriving explicit analytical expressions for the moments of the network population vector observed at Poisson time points.

Moment Derivation:
- The paper establishes that the stationary distribution of the population vector has Poisson marginals with independent components.
- The core of the method involves calculating the cross-moments between queue lengths at two distinct observation times. Specifically, the authors derive expressions for $E[\mathbf{M}(0)\mathbf{M}(T_\beta)^\top]$ , where $T_\beta$ is an exponentially distributed inter-observation time.
- To handle cases with more unknown parameters (e.g., unknown service-time parameters or observation probabilities), the method extends to Erlang-2 inter-observation times ( $E_{\beta,2}$ ), corresponding to observations at the $k$ -th and $(k+2)$ -nd Poisson epochs. This provides additional moment equations without requiring new data collection mechanisms.
- The derivations utilize the Laplace-Stieltjes transforms of the service-time distributions and the residual service-time distributions (excess life) to account for customers present at the initial observation time.
Estimator Construction:
- The estimator is defined by solving a system of moment equations where the theoretical moments (functions of $\boldsymbol{\lambda}$ , $Q$ , and service parameters) are equated to their empirical counterparts calculated from the data.
- In the case of known service-time distributions, the system of $n^2 + n$ moment equations (from means and lag-1 cross-moments) matches the number of unknown parameters ( $n$ arrival rates and $n^2$ routing entries).
- For unknown service-time parameters or observation probabilities, the system is augmented with lag-2 cross-moments to ensure the number of equations matches the increased number of unknowns.
- Since the raw solution to the moment equations may fall outside the valid parameter space (e.g., negative rates or row sums $>1$ ), the authors employ a projection step to ensure the final estimator lies within the feasible set $\Theta$ .
Model-Free Approach:
- A "model-free" variant is proposed where the parametric form of the service-time distribution is unknown. Instead of estimating distribution parameters, the method estimates the first moment, the Laplace-Stieltjes transform at $\beta$ , and its derivative at $\beta$ for each station. This requires $3n$ additional parameters but avoids model misspecification.

Key Contributions and Results

Consistency: The paper proves that the proposed estimator is consistent. Under mild assumptions (non-trivial flow and non-explosive system), the estimator converges almost surely to the true parameter values as the number of observations $m \to \infty$ . The proof utilizes a coupling argument with a majorizing $M/G/\infty$ process to establish the almost sure convergence of empirical moments.
Identifiability: The authors demonstrate that there is a one-to-one mapping between the moment vector (means and cross-moments) and the model parameters $(\boldsymbol{\lambda}, Q)$ . This ensures that the network topology (routing matrix) can be uniquely recovered, even in cases where different topologies might yield the same stationary distribution. The use of cross-moments at different time lags breaks the symmetry that would otherwise prevent distinguishing the direction of flow.
Handling Noise and Unknowns: The framework is extended to handle censored observations (unknown detection probabilities) and unknown service-time distributions, showing that the method remains applicable by increasing the number of moment equations used.
Numerical Performance: Extensive numerical experiments validate the method.
- The estimator accurately recovers the routing matrix structure across various topologies (line, circle, symmetric circle, cliques).
- The method performs well even with a large number of parameters and in high-dimensional networks ( $n=10$ ).
- The model-free approach is shown to be robust against model misspecification; while parametric methods fail when the assumed service distribution (e.g., exponential) does not match the data (e.g., Erlang-2), the model-free approach yields accurate estimates in both scenarios.

Significance and Claims
The paper claims that its main contribution is a procedure capable of estimating all model parameters, including the routing matrix, arrival rates, service-time characteristics, and observation probabilities, using only population counts at Poisson times.

A significant theoretical claim is the ability to uncover the directed topology of the network. The authors note that this capability is linked to the concept of causality, as the method infers the direction of flow (cause and effect) between nodes, which is not possible using only stationary distribution data.

The work is positioned as a solution to a challenging class of inverse problems in operations research where direct observation of the stochastic processes is unavailable. The authors modestly note that while the consistency proof is rigorous for the case of known service distributions, the theoretical treatment for the fully extended case (unknown service parameters and observation probabilities) requires further identifiability conditions and is left as an open area for future research, though the practical implementation is demonstrated to be effective.

The paper concludes by highlighting the practical relevance of such inference in domains like social network analysis (identifying influencers and communities) and communication networks (inferring internal characteristics from end-point data), while suggesting future work on single-server queues and endogenous routing dynamics.

More like this