Transient and equilibrium analysis of computer networks: Finite memory and matrix geometric recursions

G/M/1 and M/G/1-type Markov processes provide natural models for the activity on multiaccess networks. Efficient recursive solutions for the equilibrium and transient analysis of theses processes are therefore of considerable interest in analyzing and optimizing the performance of these networks. Equilibrium performance analysis of these networks can be efficiently carried out using matrix geometric recursions. Analytical methods to compute the recursion matrix, which is the minimal nonnegative solution of a matrix polynomial equation, are developed. Matrix recursive solutions for the equilibrium and transient probability distributions which are computable in closed form are then investigated. A novel state space expansion technique is developed to arrive at a new class of recursive solutions, called finite memory recursive solutions, for the transient and equilibrium behavior of G/M/1-type Markov processes. The class of finite memory recursive solutions are extended to the equilibrium and transient analysis of finite state space G/M/1-type Markov processes in which there is one state at each level which receives a downward transition. It is also described how the state space expansion technique can be utilized to arrive at a finite memory recursion for the equilibrium and transient behavior of M/G/1-type Markov processes. Finally the analysis of the other stochastic models through the notion of finite memory recursion is investigated. Slotted ALOHA networks with multipacket reception capability are modeled as G/M/1-type Markov processes. The existence of finite memory recursion for the equilibrium and transient behavior of finite as well as infinite state space G/M/1-type processes is utilized in the performance analysis of these networks. Finally various performance measures of interest in the overload control of these networks are defined