Linear Programming, Lyapunov Functions, and Performance Analysis

Many of the stochastic models that are used in the performance engineering context can be viewed as Markov processes, evolving in either discrete time or continuous time. In this talk, we will discuss the use of Lyapunov functions in computing steady-state performance bounds for such Markov processes. We will further discuss how such bounds can be used to develop linear programming-based algorithms that are capable of accurately computing system performance for infinite state models, in which the Markov state descriptor is either a discrete or continuous variable. We will illustrate these linear programming ideas by discussing their application to numerical computation of stationary distributions of reflected Brownian motion (RBM); such RBMs arise as "heavy-traffic" limits of conventional queuing networks. This work is joint with Denis Saure and Assaf Zeevi.