PaperlayerView exact revision on arXiv

Source-linked AI summary

Analysis of Triggered Packet Streams: A Matrix-Analytic Method for Exponential Triggering Delays

Mehran Rahnamania, Michel Mandjes, Farid Ashtiani

arXiv:2609.02320v1math.PRcs.PF

TL;DR

Triggered packet streams create one-to-one causal dependencies that make their aggregate arrivals non-renewal and difficult to analyze with conventional queueing models. The paper develops an exponential-delay MT/G/1 framework using a two-dimensional Markov description, Laplace–Stieltjes transforms, finite truncation, and matrix-analytic methods. It characterizes class-specific performance and shows close agreement with simulations while retaining modest truncation levels.

  • Problem

    Triggered primary and secondary packets produce aggregate arrivals that are not renewal processes, limiting direct use of conventional queueing results.

  • Method

    The paper uses exponential-delay memorylessness to build a two-dimensional Markov state, then applies LSTs, finite-state truncation, and matrix-analytic methods for general class-dependent service times.

  • Results

    The framework characterizes workload and class-specific waiting- and system-time distributions, with PASTA for primary customers and Palm conditioning for secondary customers.

  • Takeaways & Limitations

    The approach provides accurate and computationally tractable performance evaluation for open-loop triggered packet streams with exponential triggering delays.

  • Takeaways & Limitations

    The finite-dimensional Markovian representation depends on exponential triggering delays; general delays require residual-time information or approximation schemes.

Abstract

from arXiv · show

In many communication networks, the transmission of a packet may automatically trigger the transmission of a subsequent packet from the same source after a (possibly random) delay, without requiring acknowledgment or feedback. Such behavior arises in multi-stage status updating, proactive protocols, and other applications where users generate causally dependent packet streams. In this paper, in order to analyze these systems, we introduce the $\mathrm{M^T/G/1}$ queue. In this model, primary customers arrive according to a Poisson process, and each primary customer triggers a secondary customer to join the queue after an independent delay. This arrival mechanism falls outside the scope of classical queueing models with renewal arrival processes. When the triggering delays follow an exponential distribution, we exploit the memoryless property to set up a tractable Markov description. By truncating the number of pending secondary customers, we derive a finite system of linear algebraic equations in the Laplace--Stieltjes transform domain and solve them using matrix-analytic methods. Based on the resulting workload distribution, we compute class-specific performance metrics using PASTA for primary customers and Palm conditioning for secondary customers. Finally, we validate the accuracy of this truncation through numerical experiments.

I. INTRODUCTION

Triggered packet streams create causally dependent arrivals that standard renewal-based queueing models do not adequately represent. The paper introduces a matrix-analytic framework for analyzing these systems with general class-specific service times and exponential triggering delays.

  • I. INTRODUCTION: Packets can automatically trigger delayed transmissions without acknowledgment, creating causal dependencies within each user’s packet stream.The pattern appears in IoT monitoring, proactive wireless protocols, and other multi-stage communication systems.
  • I. INTRODUCTION: Rigorous performance analysis remains underexplored because aggregated triggered arrivals violate the assumptions of conventional renewal-based queueing models.The aggregate stream is not adequately captured by standard renewal, correlated-arrival, or self-exciting models.
  • I. INTRODUCTION: The paper formalizes the MT/G/1 queue with Poisson primary arrivals, one delayed secondary arrival per primary, and class-distinct general service-time distributions.This extends earlier approximations that were limited in distributional information or service-time assumptions.
  • I. INTRODUCTION: Exponential triggering delays enable a two-dimensional Markovian state description, finite-state truncation, and matrix-analytic solution of the stationary workload distribution.Laplace–Stieltjes transforms and appropriate boundary conditions reduce the analysis to a tractable algebraic system.
  • I. INTRODUCTION: The framework derives class-specific waiting- and system-time distributions and moments, using PASTA for primary customers and Palm conditioning for secondary customers.The resulting distributions and moments are available to any desired accuracy.

B. Proactive Wireless Protocols and URLLC

Proactive communication systems generate delayed, causally linked packets in applications such as URLLC and edge intelligence. The MT/G/1 model captures their non-renewal aggregate arrivals and associated analytical challenges.

  • B. Proactive Wireless Protocols and URLLC: URLLC protocols may send a primary packet and automatically schedule a delayed replica without waiting for feedback.This blind-repetition strategy avoids the latency penalty of feedback cycles.
  • B. Proactive Wireless Protocols and URLLC: Edge-intelligence early-exit architectures transmit a preliminary inference before delayed computation produces a refined secondary result.The secondary transmission is delayed by deeper neural-network processing.
  • B. Proactive Wireless Protocols and URLLC: The MT/G/1 framework unifies these proactive dynamics by modeling primary and secondary customers in a single FCFS, infinite-buffer queue.Primary customers arrive as a Poisson process, while each triggers one secondary customer after a random delay.
  • B. Proactive Wireless Protocols and URLLC: Both primary and secondary marginal streams are Poisson with rate λ, but their aggregate stream is not a renewal process.The dependence arises because each secondary arrival is linked to its corresponding primary by the triggering delay.
  • B. Proactive Wireless Protocols and URLLC: Exact analysis is difficult because pending secondary customers require tracking concurrent residual triggering delays, producing an unbounded and potentially exponentially growing state space.The triggered-arrival structure is not adequately represented by standard correlated-arrival or self-exciting models.

IV. MATRIX-ANALYTIC SOLUTION

For exponential triggering delays, the paper models delayed secondary arrivals through an auxiliary queue and constructs a Markovian workload state. Steady-state equations are transformed and solved through finite truncation and matrix-analytic methods.

  • IV. MATRIX-ANALYTIC SOLUTION: The steady-state workload equations are converted into a finite matrix-algebraic system by Laplace–Stieltjes transformation and truncation of pending secondary customers.The truncation is paired with a boundary condition to solve the otherwise infinite-dimensional algebraic system.
  • IV. MATRIX-ANALYTIC SOLUTION: The auxiliary queue QA represents each pending secondary customer, with triggering delay Y serving as its conceptual service time.A primary arrival enters the main queue QM and simultaneously enters QA; completion in QA releases the secondary customer to QM.
  • IV. MATRIX-ANALYTIC SOLUTION: Exponential triggering delays make the pair consisting of QM workload and pending-secondary count a tractable continuous-time Markov process.The memoryless property eliminates the need to track each pending customer’s residual delay individually.
  • IV. MATRIX-ANALYTIC SOLUTION: Infinitesimal state transitions yield forward Chapman–Kolmogorov equations with convolution terms for general primary and secondary service-time distributions.The equations account for no arrivals, primary arrivals, and secondary arrivals caused by auxiliary-queue service completions.
  • IV. MATRIX-ANALYTIC SOLUTION: The state tracks VM(t), the remaining service workload in QM, and NA(t), the number of secondary customers currently undergoing triggering delays.Primary arrivals increase NA and QM workload, while completed triggering delays decrease NA and add secondary service workload.

C. Transform Domain Analysis

The transform-domain analysis converts steady-state integro-differential equations into linear algebraic equations involving workload transforms and idle probabilities. Truncation then makes the infinite system computationally solvable.

  • C. Transform Domain Analysis: Laplace–Stieltjes transformation with respect to workload converts convolution operators and integro-differential equations into algebraic relations.The transforms use the service-time LSTs for primary and secondary customers.
  • C. Transform Domain Analysis: The transform system contains workload LSTs together with idle probabilities P_n for states having n pending secondary customers.P_n denotes the steady-state probability that QM is idle while QA contains n customers.
  • C. Transform Domain Analysis: After transformation and rearrangement, the formulation becomes an infinite-dimensional system of linear algebraic equations.The next step is truncation with an appropriate boundary condition.

D. Finite-State Matrix Formulation

Truncating the pending-secondary-customer state at nmax converts the unbounded recurrence into a finite linear system. The resulting matrix formulation uses workload transforms, idle probabilities, and a tridiagonal characteristic matrix while balancing accuracy against computational cost.

  • Finite-state truncation: Truncation at nmax reduces the unbounded recurrence to nmax+1 linear equations solvable by matrix-analytic methods.The threshold is chosen so that exceeding nmax has negligible probability.
  • Boundary condition: At n = nmax, a new secondary customer is blocked from QA, while its corresponding primary customer still joins QM.Thus, a primary arrival increases workload without changing the pending-secondary state.
  • Matrix formulation: The finite system uses Φ(s) for unknown transforms and p for idle probabilities.Φ(s) contains the transforms eϕn(s), while p contains P0 through Pnmax.
  • Matrix formulation: The characteristic matrix M(s) is tridiagonal, with a modified final row encoding the nmax boundary condition.Its inverse, represented through the determinant and adjugate, yields the formal solution for Φ(s).
  • Truncation accuracy: Choose nmax so the Poisson tail of the untruncated auxiliary M/M/∞ queue is below a small tolerance such as 10^-6.This choice trades model accuracy against computational cost.

E. Boundary Conditions and Idle Probabilities

Idle probabilities are determined by analyticity constraints at the characteristic roots together with a normalization condition from the system at s = 0. The known distribution of pending secondary customers supplies the boundary information needed for a unique solution.

  • Root conditions: Analyticity of each transform in Re(s) > 0 requires cancellation of potential poles where det(M(s)) = 0.The nonzero characteristic roots provide nmax homogeneous constraints on the idle-probability vector.
  • Root conditions: Under ρ < 1, det(M(s)) = 0 has exactly nmax+1 roots in the closed right half-plane.One root is at s0 = 0, while the remaining roots generate the analyticity conditions.
  • Normalization: The nmax root constraints do not determine all nmax+1 components of p, so one additional independent equation is required.The final equation is obtained from system behavior at s = 0.
  • Normalization: At s = 0, Φ(0) gives the stationary distribution of QA in an M/M/nmax/nmax loss system with load ρ̄ = λ/γ.The underlying process has birth rate λ and state-dependent death rate nγ.
  • Normalization: Combining the nmax root equations with the s = 0 condition produces a full-rank system that uniquely determines p.Once p is known, the LST vector Φ(s) is fully specified.

F. Workload Moments

Workload moments are extracted from derivatives of the total workload LST at s = 0. Because the coefficient matrix is singular there, successive derivative systems require null-vector-based constraints to obtain unique solutions.

  • Moment extraction: The total workload LST is 1TΦ(s), and its derivatives at s = 0 yield workload moments.This provides the transform-based route from the state LST vector to workload statistics.
  • Mean workload: The mean workload is E[VM] = −1TΦ′(0).The derivative vector Φ′(0) is obtained from a singular linear system requiring an added constraint.
  • Mean workload: Left-multiplying the differentiated equation by the left null vector 1T eliminates the unknown second-derivative term.Replacing one dependent equation with this constraint produces a full-rank system for Φ′(0).

2) Higher Moments:

The framework derives class-specific waiting and system-time metrics from the workload distribution. PASTA applies to primary customers, whereas secondary customers require Palm conditioning because their arrivals are causally linked to earlier primary arrivals.

  • Primary customers: Primary customers see the queue in steady state because their externally generated Poisson arrivals are causally independent.Consequently, primary waiting time has the steady-state workload distribution.
  • Secondary customers: Secondary arrivals are not causally independent because each is determined by a prior primary arrival plus a triggering delay.Therefore, secondary customers do not necessarily observe the steady-state queue distribution, so PASTA does not directly apply.
  • System times: For both classes, mean system time equals mean waiting time plus mean service time, and variances add under service-time independence.These formulas complete the class-specific performance metrics for exponential triggering delays.
  • Secondary customers: Palm conditioning determines the state distribution seen by secondary arrivals in proportion to the rate of triggering-delay completions.With n customers in QA, the relevant departure and secondary-arrival rate is nγ.
  • Secondary customers: The secondary waiting-time LST averages e−sVM over the arrival-stationary distribution induced by those state-dependent arrival rates.Its moments follow by differentiating this LST.

V. NUMERICAL RESULTS

The numerical section validates the truncated analytical model against simulation and examines its behavior across loads and service-time variability. It also compares the proposed matrix-analytic framework with prior exponential-service approximations.

  • Experimental design: Experiments vary system load, service-time squared coefficients of variation, and triggering-delay means while comparing analytical predictions with discrete-event simulation.Service distributions include deterministic, generalized Erlang, and hyperexponential families; triggering delays remain exponential.
  • Validation: The truncation achieves high accuracy across the considered parameter space, with relative errors near simulation statistical noise.The maximum required truncation level was nmax = 22 when enforcing P(NA > nmax) < 10^-9.
  • Validation: The compact truncation is justified by the auxiliary queue's Poisson pending-customer count and factorially decaying tail.The auxiliary queue QA operates as an M/M/∞ queue, keeping the finite-state formulation computationally tractable.
  • Comparison with existing approximations: Prior approximations provide reasonable estimates for common exponential service times but deteriorate substantially when service-time distributions deviate from exponential.Those approximations are restricted to c2_X = 1.00 and cannot account for service-time variability across general distributions.
  • Comparison with existing approximations: The proposed matrix-analytic framework captures service-time variability accurately while retaining the computational tractability of the finite-state formulation.This comparison covers both mean and higher-order system-time metrics for primary and secondary customers.

VI. CONCLUSION

The paper establishes a matrix-analytic framework for open-loop triggered packet streams with exponential triggering delays and validates its accuracy numerically. It also identifies exponential triggering delays as the main limitation.

  • The one-to-one causal dependence between primary and secondary packets creates a non-renewal aggregate arrival process, preventing direct use of conventional renewal-based queueing results.
  • Exponential triggering delays enable a two-dimensional Markovian representation using queue workload and pending secondary-customer count.
  • The finite-state matrix-analytic formulation handles general class-dependent service times and characterizes workload, waiting-time, and system-time distributions.
  • PASTA applies to primary customers, whereas Palm conditioning is required for secondary customers.
  • Numerical experiments show close agreement with discrete-event simulations across system loads, service-time variabilities, and triggering-delay means, with very small relative errors and modest truncation levels.
  • The main limitation is the assumption of exponential triggering delays; general delays would require residual-triggering-time information or suitable approximations.

APPENDIX A PROOF OF LEMMA 1

The appendix proves that the aggregate triggered-arrival counting process is not a stationary renewal process for any triggering-delay distribution. It decomposes the process into independent pending-secondary and current-arrival components, then derives a contradiction using transform structure.

  • The counting process N(t) is decomposed into independent components representing pending secondary arrivals and customers entering during (0,t].
  • Pending secondary customers at time 0 are Poisson distributed, with residual triggering times governing their arrivals in (0,t].
  • A primary arrival contributes one count, while its secondary contributes another exactly when its triggering delay expires before t−u.
  • The aggregate transform is obtained by multiplying the transforms of the two independent components.
  • Even for Y∼Exp(4λ), the aggregate transform contains a non-rational Laplace structure, contradicting the rational transform required for a stationary renewal process.
Loading 2609.02320v1…