On Numerical Solution of the Markov Renewal Equation: Tight Upper and Lower Kernel Bounds

We develop tight bounds and a fast parallel algorithm to compute the Markov renewal kernel. Knowledge of the kernel allows us to solve Markov renewal equations numerically to study non-steady state behavior in a finite state Markov renewal process. Computational error and numerical stability for computing the bounds in parallel are discussed using well-known results from numerical analysis. We use our algorithm and computed bounds to study the expected number of departures as a function of time for a two node overflow queueing network.