PaperlayerView exact revision on arXiv

Source-linked AI summary

Age of Information in Queueing Systems with Merging Server Streams

Lucrezia Rossi, Leonardo Badia, Andrea Munari

arXiv:2610.09632v1cs.NI

TL;DR

Merging server streams make AoI analysis difficult in distributed processing systems that split or duplicate traffic. The paper derives exact analyses for split-merge and duplicate-merge, correcting prior split-merge models and formally analyzing duplicate-merge. Its results also support tuning routing and injection rates to minimize average AoI.

  • Problem

    AoI analysis is needed for systems that split or duplicate traffic across servers and merge their outputs, but existing split-merge models are incorrect at high loads and duplicate-merge lacks formal analysis.

    Source: §I · p. 1

  • Method

    The paper develops an analytical framework for split-merge and duplicate-merge queueing topologies and uses its results for system-level optimization.

    Source: §I · p. 1

  • Results

    The framework gives exact split-merge analysis and the first formal duplicate-merge analysis; when µ2 = 1.0, split-merge has minimum AoI 2.221 at α = 0.50 versus 2.600 at α = 0.72 for duplicate-merge.

    Source: §I · p. 1, §V · p. 9

  • Takeaways & Limitations

    The results provide guidelines for tuning randomized routing probabilities and traffic injection rates to minimize average AoI.

    Source: §VI · p. 10

Abstract

from arXiv · show

We present a novel analytical framework for evaluating the age of information (AoI) in multi-path queueing topologies where output streams from multiple servers converge into a single pipeline. This theoretical scenario finds immediate application in ultra-reliable low-latency networks and edge computing architectures, where multi-path routing and stream merging can be vital strategies for maintaining fresh status updates. Specifically, we investigate two setups: a split-merge network and a duplicate-merge network. The split-merge case has been addressed in prior work, but we show that existing studies are incorrect, and our approach provides instead an exact analytical formulation. Moreover, building on similar reasoning, we provide the first formal analysis of the previously unexplored duplicate-merge scenario. Finally, we show how to leverage our theoretical results to solve key system-level optimization problems, deriving the optimal randomized routing probabilities and traffic injection rates that minimize average AoI.

I. INTRODUCTION

The paper develops exact AoI analysis for split-merge and duplicate-merge queueing topologies, where server outputs converge into one pipeline. It also uses the results to optimize routing probabilities and traffic injection rates.

I. INTRODUCTION

  • The framework addresses freshness analysis in merging systems, a fundamental design issue for future communication networks.Distributed processing often splits or duplicates data across heterogeneous servers before merging outputs, increasing the analytical complexity of AoI evaluation.Source: §I · p. 1
  • Split-merge routes each packet to one of two M/M/1 queues, whereas duplicate-merge copies traffic onto a secondary path with probability α.In duplicate-merge, the first queue receives all traffic and the second receives a fraction α.Source: §I · p. 1
  • The framework corrects existing split-merge analyses that become incorrect at high loads and gives an exact closed-form formulation.The authors also provide the first exact formal AoI analysis of duplicate-merge.Source: §I · p. 1
  • The theoretical results support system-level optimization of randomized routing probabilities and traffic injection rates to minimize average AoI.Source: §I · p. 1

II. RELATED WORK

Prior AoI research covers independent sources, correlated observations, and several parallel or converging queue models, but not exact analysis of the split-merge and duplicate-merge topologies considered here. The paper positions its framework as correcting the former literature and solving the latter open problem.

II. RELATED WORK

  • Earlier AoI frameworks primarily address multiple independent sources, including work on correlated content whose packets remain associated with separate sources,,,,,,,.Source: §II · p. 2
  • Existing studies examine tributary traffic merging, MEC splitting, and parallel-channel freshness limits, but these models differ from the split-merge topology analyzed here,,.Source: §II · p. 2
  • Prior parallel-server AoI expressions for a similar setting introduce approximations that make them inexact and produce discrepancies in AoI values [9].Source: §II · p. 2
  • The paper presents an exact framework for both split-merge and duplicate-merge, correcting prior split-merge models and addressing duplicate-merge as an open problem.Source: §II · p. 2

III. SPLIT-MERGE: ANALYTICAL DERIVATION

The split-merge analysis computes average AoI from the system time of informative packets and the intervals between informative departures. It accounts for cross-queue overtaking and derives the required moments in closed form.

III. SPLIT-MERGE: ANALYTICAL DERIVATION

  • Only packets not overtaken by a later completion in the competing queue are informative and reset AoI; therefore T is not the raw Poisson interarrival time.The filtering makes informative departures non-Markovian and their consecutive discards statistically dependent.Source: §III · pp. 2–3
  • Average AoI is evaluated from the system time S of an informative packet and the inter-departure time T between consecutive informative departures.T is the interval over which AoI grows before resetting.Source: §III · pp. 2–3
  • For each queue, the mean interval between informative departures is obtained from the reciprocal of their long-run rate, without requiring T's full distribution.The aggregate informative-departure rate sums the contributions of both queues.Source: §III · p. 3
  • The cross moment E[ST] requires joint conditioning because longer packet system time changes both the chance of competing-queue overtaking and the tagged queue's residual state.The derivation conditions on S and combines survival of competing-queue completions with the tagged queue's next-departure survival.Source: §III · pp. 3–4
  • Expanding the survival-function integrand reduces the moment calculation to elementary integrals, yielding E[ST | i] in closed form without numerical integration.Source: §III · p. 4
  • The second moment E[T^2 | i] is obtained by the same survival-function expansion, and queue-level moments are weighted by each queue's share of informative departures.Together with the mean system time, these moments provide all ingredients for closed-form average AoI.Source: §III · p. 4

IV. DUPLICATE-MERGE: ANALYTICAL DERIVATION

Duplicate-merge sends every packet through queue 1 and copies some packets to queue 2, coupling the queues’ occupancies despite unchanged marginal behavior. The analysis separates record-setting packet cases and derives informative-departure quantities, with Case 1’s overtaking probability reducing exactly to the earlier transform result.

IV. DUPLICATE-MERGE: ANALYTICAL DERIVATION

  • Queue-2 arrivals are a thinned copy of queue 1’s stream, so the queues’ occupancies are correlated and require separate overtaking-probability and joint-law derivations.The split-merge queues instead receive independent Poisson sub-streams.Source: §IV · p. 4
  • Poisson thinning gives the duplicated stream rate λ′ = αλ, and informative departures divide into three cases according to duplication and which copy departs first.The mean informative inter-departure time is 1/λinf; the informative rate counts a fraction Pinf,1 of non-duplicated arrivals and all duplicated arrivals.Source: §IV · p. 4, Case 1: non-duplicated record · p. 5
  • For each queue, the next candidate departure is Cj = max(Xj, Sj) + Yj, and the next informative inter-departure time is min(C1, C2) − Z.For a non-duplicated record, Z = S1; for a duplicated record, Z = min(S1, S2).Source: §IV · pp. 4–5

Case 1: non-duplicated record

  • In Case 1, the overtaking probability uses the split-merge competing-completion transform with competing rate λ′ evaluated at ν1, and the full construction reproduces equation (18) exactly.The passage identifies this as a genuine identity, not an approximation.Source: Case 1: non-duplicated record · p. 5
  • Although the Case 1 transform yields the overtaking probability, the moments require a joint law because C1 and C2 can share an arrival; the resulting nested integrals reduce to exact finite sums without numerical quadrature.The shared-arrival branch occurs with probability α; otherwise the first duplicated arrival follows X1 after an independent exponential delay.Source: Case 1: non-duplicated record · pp. 5–6
  • For Case 1, F(y) gives queue 2’s survival probability conditional on an arrival at y, accounting for its stationary busy or idle state and possible clearance times.The analysis averages this factor over the branch-specific arrival timing; F(y) = 1 when y ≥ t.Source: Case 1: non-duplicated record · p. 5

Cases 2 and 3: duplicated record

Cases 2 and 3 require accounting for dependence between the duplicated packet’s queue completion times. The analysis constructs their joint survival and moments, then combines case-conditional moments to evaluate average AoI.

Cases 2 and 3: duplicated record

  • For Cases 2 and 3, exactly one duplicate is informative, so the relevant ordering probability is Pr(S1 < S2).The analysis does not require the split-merge quantity Pinf,1 for these cases.Source: Cases 2 and 3: duplicated record · p. 6
  • Queue 1’s and queue 2’s service times are positively correlated because queue 2 receives a sub-sample of queue 1’s arrivals, requiring their exact joint law.Although each time is marginally exponential, an independent-exponential race identity does not apply.Source: Cases 2 and 3: duplicated record · p. 6
  • Conditional on queue occupancies at duplication, the service times are Erlang; averaging their moments over the joint stationary distribution yields case-conditional moments.The occupancy distribution comes from a bivariate Markov chain, and its geometrically convergent series is truncated at negligible error.Source: Cases 2 and 3: duplicated record · pp. 6–7
  • The candidate joint survival is built by cases: for w ≤ u it reduces to the reference queue’s survival, while for w > u it accounts for both queues’ thresholds.For w > u, branch A yields two exponential terms and is symmetric under exchanging the reference and competing queues.Source: Cases 2 and 3: duplicated record · p. 6
  • The branch-B survival construction is asymmetric: queue 1 contributes an elementary factor, while queue 2’s factor is composite because it receives the thinned duplicate stream.Which queue is the reference changes the threshold bookkeeping; queue 2’s factor distinguishes different regions in the two cases.Source: Cases 2 and 3: duplicated record · pp. 6–7
  • Case-conditional E[ST] and E[T 2] moments are weighted by each case’s long-run share of informative departures and, together with (19), enable analytical evaluation of average AoI via (1).Fig. 5 plots average AoI for the duplicate-merge model against duplication parameter α, comparing closed-form results with Monte Carlo simulation for λ = 0.5, µ1 = 1, and µ2 = 0.8.Source: Cases 2 and 3: duplicated record · pp. 7–8, Figure 5 · p. 8

V. NUMERICAL RESULTS

The numerical results validate the analytical moments and AoI against simulation, then compare how optimal AoI and routing depend on server capacity. The preferred policy and tuning change with the secondary server’s speed.

Validation

  • For split-merge, closed-form moments and resulting AoI match Monte Carlo simulation; the prior derivation gives close but not fully exact AoI values.The prior derivation reflects the optimal split rate but slightly biases the AoI value.Source: §V · p. 8

AoI across routing parameters

  • At low arrival rate, split-merge AoI curves are nearly flat and close across µ2; at high arrival rate, stable ranges constrain α and curves develop interior minima.For split-merge, small-µ2 curves are truncated at small α when queue 2 approaches instability.Source: §V · p. 8, Figure 7 · p. 8
  • The duplicate-merge figures plot AoI against duplication α at low and high arrival rates; queue 1 remains stable when λ<µ1, while queue 2 receives traffic at rate αλ.The supplied captions identify the plotted operating conditions, including λ=0.2 and λ=0.8 with µ1=1.Source: Figure 8 · p. 9, Figure 9 · p. 9

Optimal operating points

  • For split-merge, the optimal α shifts from about 0.7 at µ2=0.4 to 0.5 at µ2=1; for duplicate-merge, it shifts from about 0.3 to 0.7.The optimal arrival rate varies over 0.25–1.07 for split-merge and 0.44–0.69 for duplicate-merge; minimum AoI decreases monotonically with µ2 in both models.Source: §V · p. 9

Policy comparison

  • With µ2=0.3, the optimal AoI is 3.194 at α=0.78 for split-merge and 3.310 at α=0.27 for duplicate-merge; with µ2=1.0, it is 2.221 at α=0.50 versus 2.600 at α=0.72.At µ2=1.0, the reported optimal split-merge arrival rate is λ∗=1.067.Source: §V · p. 9, Figure 10 · p. 9

VI. CONCLUSION

The paper presents exact closed-form AoI analyses for split-merge and duplicate-merge M/M/1 architectures, correcting prior split-merge inaccuracies and formally analyzing the previously unaddressed duplicate-merge case. It also offers practical guidelines for tuning routing probabilities and traffic injection rates to minimize average AoI.

Analytical framework

  • The framework characterizes AoI in multi-path queueing topologies where outputs from multiple server streams converge.The conclusion describes these as converging server streams.Source: §VI · p. 9
  • The exact closed-form split-merge solutions correct inaccuracies in existing models, while the duplicate-merge derivation provides its first formal analysis.The studied architectures are split-merge and duplicate-merge M/M/1 networks.Source: §VI · p. 10

System-level use

  • The findings provide guidelines for choosing randomized routing probabilities and traffic injection rates to minimize average AoI.The stated application areas include ultra-reliable low-latency communications, edge computing, and real-time cyber-physical systems.Source: §VI · p. 10

USE OF AI DISCLOSURE

The disclosure distinguishes the authors’ analytical work from ChatGPT’s limited role in cross-validation.

Authorship

AI use

Loading 2610.09632v1…