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

Eliran Sherzer

cs.LGMar 11, 2026

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

Authors: Eliran Sherzer

Organizations: Industrial Engineering, Ariel University, Ramat HaGolan St 65, Ariel, 4070000, Israel.

Abstract

The superposition of arrival processes is a fundamental yet analytically intractable operation in queueing networks when inputs are general non-renewal streams. Classical methods either reduce merged flows to renewal surrogates, rely on computationally prohibitive Markovian representations, or focus solely on mean-value performance measures. We propose a scalable data-driven superposition operator that maps low-order moments and autocorrelation descriptors of multiple arrival streams to those of their merged process. The operator is a deep learning model trained on synthetically generated Markovian Arrival Processes (MAPs), for which exact superposition is available, and learns a compact representation that accurately reconstructs the first five moments and short-range dependence structure of the aggregate stream. Extensive computational experiments demonstrate uniformly low prediction errors across heterogeneous variability and correlation regimes, substantially outperforming classical renewal-based approximations. When integrated with learning-based modules for departure-process and steady-state analysis, the proposed operator enables decomposition-based evaluation of feed-forward queueing networks with merging flows. The framework provides a scalable alternative to traditional analytical approaches while preserving higher-order variability and dependence information required for accurate distributional performance analysis.

Figures & tables

Method	Discription	Autocorrelation	SCV	Skewness	Kurtosis
1	Strong Negative Correlation	(-0.99,0)	(0.15, 1.81)	(0.065,2.64)	(1.09, 13.09)
2	Strong Positive Correlation	(0,0.99)	(0.01,15)	(-2.41, 50)	(1.11, 100)
3	Mild Correlation	(-0.43, 0.44)	(0.15, 15)	(1.74, 25.1)	(9.01,100)

Table 1: Generating MAPs domain

Panel of Figure 4 — Figure 4: Statistical measures of the MAP generating process.

Panel of Figure 5 — Figure 5: Moment analysis

Panel of Figure 6 — Figure 6: Autocorrelation analysis

	SCV			PARE				Second moment PARE
	Stream 1	Stream 2	Moment ratio	2	3	4	5	Whitt R	Whitt A	Albin
1	$<3$	$<3$	$<0.5$	0.66	0.76	0.94	1.27	50.37	50.37	13.54
2	$<3$	$<3$	$>0.5$	0.65	0.79	1.01	1.32	62.94	62.94	11.9
3	$<3$	$>3$	$<0.5$	1.44	2	2.38	2.85	28.96	28.96	10.43
4	$<3$	$>3$	$>0.5$	1.99	2.45	2.8	3.32	53.85	53.85	17.6
5	$>3$	$<3$	$<0.5$	2.38	2.41	2.35	2.92	359.73	359.73	108.97

Table 2: Moment accuracy by SCV

	$\rho$			PARE				Second moment PARE
	Stream 1	Stream 2	Moment ratio	2	3	4	5	Whitt R	Whitt A	Albin
1	$<-0.25$	$<-0.25$	$<0.5$	0.47	0.54	0.61	0.71	44.73	44.73	8.61
2	$<-0.25$	$<-0.25$	$>0.5$	0.47	0.55	0.72	0.81	63.96	63.96	12.22
3	$<-0.25$	$(-0.25,0)$	$<0.5$	0.89	1.22	1.47	1.75	30.42	30.42	7.09
4	$<-0.25$	$(-0.25,0)$	$>0.5$	1.41	1.70	1.98	2.26	53.85	53.85	11.93
5	$<-0.25$	$(0,0.25)$	$<0.5$	0.85	1.12	1.40	1.70	47.26	47.26	11.29

Table 3: Moment accuracy by first lag autocorrelation

	SCV			MAE
	Stream 1	Stream 2	Moment ratio	1	2	3	4	5	6	7	8
1	$<3$	$<3$	$<0.5$	0.005	0.004	0.004	0.005	0.008	0.006	0.006	0.009
2	$<3$	$<3$	$>0.5$	0.006	0.004	0.004	0.005	0.008	0.007	0.007	0.009
3	$<3$	$>3$	$<0.5$	0.009	0.005	0.005	0.006	0.011	0.008	0.008	0.009
4	$<3$	$>3$	$>0.5$	0.007	0.005	0.005	0.006	0.010	0.008	0.008	0.010
5	$>3$	$<3$	$<0.5$	0.009	0.007	0.007	0.008	0.013	0.011	0.011	0.014

Table 4: Autocorrelation accuracy by SCV

	$\rho$			MAE
	Stream 1	Stream 2	Moment ratio	1	2	3	4	5	6	7	8
1	$<-0.25$	$<-0.25$	$<0.5$	0.003	0.002	0.002	0.002	0.006	0.005	0.005	0.006
2	$<-0.25$	$<-0.25$	$>0.5$	0.003	0.002	0.002	0.003	0.006	0.005	0.005	0.006
3	$<-0.25$	$(-0.25,0)$	$<0.5$	0.003	0.002	0.002	0.002	0.006	0.004	0.004	0.004
4	$<-0.25$	$(-0.25,0)$	$>0.5$	0.003	0.002	0.002	0.002	0.006	0.005	0.005	0.005
5	$<-0.25$	$(0,0.25)$	$<0.5$	0.003	0.002	0.002	0.002	0.006	0.005	0.005	0.005

Table 5: Autocorrelation accuracy by first lag autocorrelation

	SCV			$\rho$			SAE	REM
	Stream 1	Stream 2	Service	Stream 1	Stream 2	Utilization	NN	NN	Whitt
1	$<3$	$<3$	$<3$	$<0$	$<0$	$<0.7$	0.026	2.542	7.070
2	$<3$	$<3$	$<3$	$<0$	$<0$	$>0.7$	0.018	2.882	2.083
3	$<3$	$<3$	$<3$	$<0$	$>0$	$<0.7$	0.016	0.940	2.644
4	$<3$	$<3$	$<3$	$<0$	$>0$	$>0.7$	0.024	2.661	5.216
5	$<3$	$<3$	$<3$	$>0$	$<0$	$<0.7$	0.012	2.761	6.788

Table 6: System 1 results

	SCV			$\rho$				REM
	Stream 1	Stream 2	Service	Stream 1	Stream 2	utilization	SAE	NN	Whitt
1	$<3$	$<3$	$<3$	$<0$	$<0$	$<0.7$	0.064	3.132	8.734
2	$<3$	$<3$	$<3$	$<0$	$<0$	$>0.7$	0.086	2.615	2.652
3	$<3$	$<3$	$<3$	$<0$	$>0$	$<0.7$	0.074	4.310	4.332
4	$<3$	$<3$	$<3$	$<0$	$>0$	$>0.7$	0.078	4.280	7.753
5	$<3$	$<3$	$<3$	$>0$	$<0$	$<0.7$	0.073	4.129	7.199

Table 7: System 2 results

Panel of Figure 9 — Figure 9: Examples of steady-state probabilities approximations

Figure 10: Queueing networks with splitting streams.

Queueing Theory

See all 18 papers

Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems
Oct 13, 2026Cristian Palma Foster, Eva TardosQueueing Theory Regret Minimization
Cornell University
Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds
Jun 16, 2026Hao Liang, Cheng Tang, Yunzong XuQueueing Theory
University of Illinois Urbana–Champaign
Extending Causal Metamodeling to a non-Markovian Queue
May 30, 2026Pracheta Amaranath, Anant Bhide, David Jensen +1Surrogate Modeling Bayesian Networks
Manning College of Information and Computer Sciences, University of Massachusetts Amherst, MA, USA

Oct 13, 2026J/K move · Enter open · S save

Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems

Cristian Palma Foster, Eva Tardos

Cornell University

Queueing Theory Regret Minimization

Open paper AskPDF arXiv

We study packet routing in queuing systems where queues act as selfish, myopic agents that use no-regret learning algorithms to select servers with unknown service rates. To model the small buffers used in data centers, we assume that each server has a single-packet buffer. Even such a tiny buffer already captures the features of buffering: routers can exploit multiple servers while accepted packets remain in service, but packets can occupy servers for multiple rounds, complicating future service and learning. We first analyze a single queue routing packets to

m

buffered servers with service rates

μ_1, \dots, μ_m

. This setting is equivalent to an instance of the recharging bandits problem with geometric recharge. We prove that any no-regret learner achieves a long-run average throughput of at least the Hamacher sum of the server rates, and that this bound is tight. Consequently, a single no-regret queue is stable if and only if its arrival rate is below the Hamacher sum of the server rates. Moreover, comparing against an optimal policy, we show that any no-regret learner is at least

0.77

-competitive, which is also tight. We then study multi-queue systems where

n

queues with arrival rates

λ_1, \dots, λ_n

, each at most

λ_{\max}

, compete for service from

m

buffered servers. We show that the smallest overprovisioning factor that guarantees the system to be stable under high-probability no-regret learning is

\frac{1}{1-λ_{\max}}

. Equivalently, in terms of the total arrival and service rates, the condition

\sum_{i=1}^n λ_i < (1-λ_{\max})\sum_{j=1}^m μ_j

is sufficient, and sometimes necessary, for stability under no-regret learning. In particular, for

λ_{\max} = 1/2

, this improves the upper bound of Abel et al. (EC 2026) from

3

2

, matching their lower bound and resolving their open question.

Abstract

Queueing Theory

Explore similar work

Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems

Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds

Extending Causal Metamodeling to a non-Markovian Queue