Truncating Multi-Dimensional Markov Chains with Accuracy Guarantee: Applications to Discriminatory Processor Sharing and Priority Queues

The ability to obtain the steady-state probability distribution of a Markov chain is invaluable for modern service providers who aim to satisfy arbitrary tail performance requirements. However, it is often challenging, and even intractable, to obtain the steady-state distribution for several classes of Markov chains, such as multi-dimensional and infinite state-space Markov chains with state-dependent transitions; two popular examples include the M/M/1 with Discriminatory Processor Sharing (DPS) and the preemptive M/M/c with multiple priority classes and customer abandonment. In this paper, we propose a Lyapunov function based state-space truncation technique for such Markov chains. Our technique leverages the available moments, or bounds on moments, of the state variables of the Markov chain to obtain tight truncation bounds while satisfying arbitrary probability mass guarantees for the truncated chain. We demonstrate the efficacy of our technique for the multidimensional DPS and M/M/c priority queue with abandonment, and highlight the significant reduction in state space (as much as 72%) afforded by our technique compared to the state-of-the-art.