A Learning-Based Superposition Operator for Non-Renewal Arrival Processes in Queueing Networks

This paper proposes a scalable, deep learning-based superposition operator trained on Markovian Arrival Processes to accurately predict the higher-order moments and dependence structures of merged non-renewal arrival streams, thereby enabling more precise distributional performance analysis of queueing networks than classical renewal-based approximations.

The Gist

Imagine you are running a busy coffee shop. Customers arrive in two different ways:

1. The Regulars: They come in a steady, predictable rhythm (like a metronome).
2. The Rush Hour Crowd: They arrive in unpredictable bursts, sometimes waiting in long lines, sometimes arriving all at once.

Now, imagine you have a second coffee shop next door with the exact same problem. At lunchtime, customers from both shops decide to merge into a single line to order a special "fusion" drink.

The Problem:
If you try to predict how long the line will be or how long people will wait, you run into a mathematical nightmare.

• If the customers arrived perfectly evenly, math is easy.
• If they arrived in perfect bursts, math is hard but doable.
• But when you mix a steady stream with a chaotic bursty stream, the resulting line becomes a "monster" that standard math formulas can't solve. The old ways of guessing either ignore the chaos (leading to wrong predictions) or try to calculate every single possibility (which takes so long the computer crashes).

The Solution: The "Smart Mixer" (This Paper)
The author, Eliran Sherzer, has built a neural network (a type of AI) that acts like a super-smart "Mixer."

Instead of trying to solve the impossible math equation for every new situation, the AI was trained by watching millions of simulations. It learned a simple trick: "If I see these specific patterns in the two incoming lines, I know exactly what the merged line will look like."

Here is how the paper works, broken down with everyday analogies:

1. The "Fingerprint" of the Line

The AI doesn't need to know the name of every customer or the exact second they arrived. Instead, it looks at the "Fingerprint" of the arrival streams.

• The Fingerprint: It looks at simple stats like "How bumpy is the arrival?" (Variability) and "Do big bursts tend to follow other big bursts?" (Correlation).
• The Magic: The AI learned that if it knows the fingerprint of Stream A and Stream B, it can instantly predict the fingerprint of the Merged Stream C. It doesn't need to know the exact math; it just needs to recognize the pattern.

2. Training the AI (The "Gym")

How did the AI learn this?

• The researchers created a massive "gym" of fake traffic using a complex mathematical model called a MAP (Markovian Arrival Process). Think of this as a video game where they generated millions of different traffic scenarios: some with heavy rain (high variability), some with traffic jams (positive correlation), and some with alternating red and green lights (negative correlation).
• They used the "hard way" (exact math) to solve these millions of scenarios to get the correct answers.
• They fed these "Input Fingerprints" and "Correct Answers" into the AI. The AI practiced until it could predict the answer almost instantly, without doing the heavy math.

3. The Result: A Super-Powered Calculator

Once trained, this AI acts as a Universal Translator.

• Old Way: "Let's try to calculate the exact probability of 100 people waiting..." (Takes hours, often fails).
• New Way: "Here are the fingerprints of the two lines. Beep-boop. Here is the fingerprint of the merged line." (Takes a fraction of a second).

The paper shows that this AI is much better than the old "guessing" methods.

• Old Guessing: "It's probably about 5 minutes." (Often wrong by 50% or more).
• AI Prediction: "It's about 5 minutes and 12 seconds." (Wrong by less than 1%).

4. Building a Network of Coffee Shops

The real power comes when you chain these together.
Imagine a network of 3 coffee shops.

1. Shop A merges two lines.
2. Shop B merges two lines.
3. The customers from A and B merge again at Shop C.

In the past, analyzing Shop C was impossible because the math got too messy after the first merge. But now, you can use the AI at Shop A, pass the result to Shop B, and then use the AI again at Shop C. It's like passing a baton in a relay race. The AI keeps the "fingerprint" of the chaos alive so the next station knows exactly what to expect.

Why This Matters

• Speed: It turns a calculation that used to take hours (or was impossible) into something that happens in milliseconds.
• Accuracy: It captures the "chaos" of real life (bunching, delays, bursts) that old math ignored.
• Versatility: It works for any kind of traffic, not just the simple, perfect types.

In a Nutshell:
This paper introduces a smart, data-driven "translator" that can instantly figure out what happens when two chaotic streams of people (or data, or cars) merge. It replaces impossible math with a learned pattern, allowing us to predict traffic jams, server crashes, and waiting lines with incredible speed and accuracy.

Technical Summary

Here is a detailed technical summary of the paper "A Learning-Based Superposition Operator for Non-Renewal Arrival Processes in Queueing Networks" by Eliran Sherzer.

1. Problem Statement

The superposition (merging) of arrival processes is a fundamental operation in queueing networks, occurring when multiple traffic streams converge at a service node. While the superposition of Poisson processes remains Poisson, and Markovian Arrival Processes (MAPs) admit exact representations via Kronecker constructions, the superposition of general non-renewal processes is analytically intractable.

• The Challenge: The merged stream of general non-renewal processes is typically neither renewal nor Markovian. Consequently, closed-form expressions for inter-arrival time distributions, higher-order moments, and temporal correlations are unavailable.
• Limitations of Existing Methods:
  • Renewal Approximations: Classical methods (e.g., Whitt, Albin) reduce merged flows to renewal surrogates using only low-dimensional descriptors (mean rate and Squared Coefficient of Variation, SCV). These discard higher-order variability and serial dependence, leading to unreliable predictions in heavily loaded or correlated systems.
  • Exact MAP Superposition: While exact, this approach suffers from "state-space explosion," where the dimension of the merged process grows multiplicatively ($m_1 \times m_2$), making it computationally prohibitive for large networks.
  • Diffusion Approximations: These preserve only first- and second-order information, failing to capture full distributional behavior.

The paper addresses the need for a scalable framework that preserves higher-order variability and dependence information to enable accurate distributional performance analysis in non-Markovian networks.

2. Methodology

The authors propose a data-driven, neural network (NN) based superposition operator that maps statistical descriptors of input streams to those of the merged process.

A. Core Concept

Instead of modeling the underlying stochastic process explicitly, the operator learns a structural mapping between statistical descriptors:

• Input: The first $n$ moments and selected autocorrelation coefficients of two independent arrival streams.
• Output: The first 5 moments and short-range dependence descriptors (autocorrelations up to lag 2 and polynomial order 2) of the superposed process.

B. Data Generation and Training

• Training Data Source: The model is trained on Markovian Arrival Processes (MAPs). MAPs are used because they are dense in the class of non-negative distributions and allow for exact superposition via Kronecker sums (providing ground truth labels).
• Diversity: Three distinct algorithms generate MAPs to cover a wide regime of variability (SCV, skewness, kurtosis) and dependence (strong positive, strong negative, and mild autocorrelation).
• Labeling: For each pair of input MAPs, the exact merged MAP is computed. From this, 10 marginal moments and 135 autocorrelation descriptors are extracted to form the training labels.
• Network Architecture: A fully connected feed-forward neural network (ANN). The input is log-transformed moments to handle dynamic range issues.
• Loss Function: A weighted combination of Mean Squared Errors (MSE) for the log-moments and the autocorrelation descriptors.

C. Integration into Queueing Networks

The superposition operator (NN 1) is part of a modular framework (building on Sherzer, 2025) for analyzing feed-forward networks:

1. NN 1 (Superposition): Merges external arrival streams.
2. NN 2 (Departure): Approximates the departure process from a node given arrival and service descriptors.
3. NN 3 (Steady-State): Predicts the steady-state distribution of queue lengths.
   This allows for the recursive decomposition of complex networks with merging flows without constructing a global state space.

3. Key Contributions

1. Neural Superposition Operator: Introduction of a scalable, learning-based operator that accurately reconstructs the first five moments and short-range dependence of merged non-renewal streams, outperforming classical renewal approximations.
2. Compact Representation: Demonstration that the superposition mapping is identifiable from a compact set of statistical descriptors (moderate-order moments and short-range lags), avoiding the need for full state-space construction.
3. Open-Source Implementation: Provision of a fast inference framework (GitHub) enabling practical application.
4. Extension of Tractable Networks: The framework extends decomposition-based analysis to general feed-forward networks with merging flows, a class previously considered analytically inaccessible for distributional analysis.

4. Experimental Results

The authors conducted extensive experiments comparing the neural operator against classical methods (Whitt's renewal/asymptotic approximations and Albin's method).

A. Superposition Accuracy

• Moment Prediction: The neural network achieved uniformly low errors across heterogeneous regimes.
  • Second Moment (SCV) Error: Ranged between 0.47% and 2.73% for the neural model.
  • Comparison: Classical methods (Whitt) exhibited errors ranging from 30% to over 3000% in high-variability regimes. Albin's method improved this but still showed errors of 10–130%.
• Autocorrelation Prediction: The Mean Absolute Error (MAE) for autocorrelation descriptors was extremely low (typically 0.002–0.013), indicating the model successfully captures temporal dependence structures that renewal approximations discard.
• Robustness: Performance remained stable across varying SCV levels (up to 15) and autocorrelation strengths (both positive and negative).

B. Queueing Network Performance

The operator was integrated into two network topologies (a single-node G/GI/1 system and a three-station feed-forward network).

• Metrics: Sum of Absolute Errors (SAE) for distribution and Relative Error of the Mean (REM) for queue length.
• Results:
  • System 1 (Single Node): The neural decomposition achieved an average REM of 2.86%, compared to 9.20% for Whitt's approximation (a ~69% improvement).
  • System 2 (Three Nodes): Despite error propagation through multiple nodes, the neural approach maintained an average REM of 4.177% versus 10.733% for the benchmark.
• Observation: The neural framework remained stable even in high-utilization ($\rho > 0.7$) and high-variability regimes where classical methods failed to capture congestion amplification caused by dependence.

C. Computational Efficiency

• Inference Time: Extremely fast. Processing 5,000 instances took 0.004 seconds on a standard CPU.
• Scalability: The framework avoids the multiplicative state-space growth of exact MAP methods, making it suitable for real-time evaluation and large-scale design-space exploration.

5. Significance

This work represents a paradigm shift in queueing network analysis:

• Bridging the Gap: It successfully bridges the gap between the analytical intractability of general non-renewal superposition and the computational infeasibility of exact Markovian methods.
• Preservation of Information: By preserving higher-order moments and dependence structures, the method enables distributional analysis (predicting the full probability distribution of queue lengths), which is critical for tail-risk assessment in modern systems (e.g., telecommunications, cloud computing).
• Scalability: It offers a practical, scalable alternative for analyzing complex, multi-node networks with merging flows, removing the structural restriction to tandem systems or simple renewal assumptions.
• Future Potential: The modular nature of the approach suggests a path toward analyzing networks with feedback loops and integrating uncertainty quantification, potentially revolutionizing how stochastic networks are modeled and optimized.