# Self-Similar Markovian Sources
## 2 Markov Chains and the Markov Traffic Sources  
Several models have been introduced for self-similar and LRD traffic source modeling. The majority of these models have been based on approaches which are different than the Markovian approach. Some of them use the \(\alpha\)-stable distribution [21], chaotic maps [22], fractional autoregressive integrated moving average (fARIMA) [23] or fractional Levy motion [24]. The advantage of the non-Markovian models is the easiness of obtaining a good description of the network traffic (degree of self-similarity, traffic intensity). The disadvantage of these solutions is their inability to use the traditional and well-known queueing models and modeling techniques for computer network analysis.  
Markov models were introduced by [PERSON] in 1907. They have been used in efficiency analysis tasks since the 1950s. Due to the advances made in the field of numerical methods, they have gained popularity as an analytical tool. The behaviour of a physical system can be described as a set of possible states, which are the possible actions or events that happen in the system, and the transitions between these states. If the next system's state depends only on the current one (i.e., it is memoryless), the examined system can be represented using a Markov process, which is one of the stochastic processes. For a discrete number of states, a Markov process is called a Markov chain. The states of a Markov chain can be defined using the parameters describing the system. The transitions between the states are represented by the transition matrix. They are defined using transition intensities in the case of a CTMC and transition probabilities in the case of a DTMC.  
Over the years, many different software tools have been developed to deal with the Markov models; e.g., OPEDo [25], PARSECS [26], WinPEPSY-QNS [27], PRISM [28], GTAexpress [29] or our own Olymp2 [4]. Olymp2 uses the Java language to define the network nodes and the interactions between them. Due to the potentially very large sizes of the models' transition matrices, their generation is parallelized, and they can be compressed in real-time using a dedicated compression method based on a finite-state automata. Markov based models are currently applied to analyze and evaluate self-similar network traffic [30; 31; 32; 33; 34]. We are currently able to generate and solve Markov chains with 150 million states. The solution uses one of the projection methods based on the Arnoldi process using Krylov subspaces to determine the approximate eigensolution. It is achieved using the orthogonal projection of a large matrix onto a small Krylov subspace--see [35]--then, the computations using the uniformization method and Pade approximations [36] are made much easier. This approach is supplemented by a direct numerical solution of large systems of ordinary differential equations (ODE) using uniformization--i.e., discretization--which replaces a continuous Markov chain with a discrete-time Markov chain and a Poisson process. We are also increasing the size of tractable Markov chains by several orders through the use of graphical processing units and a careful design of computational algorithms for parallel computing and the optimization of memory usage. We make these remarks to underline that we are well prepared to integrate Markov self-similar traffic models with known queue and server models and obtain quantitative results which are important in the engineering use of these models.  
Below, we briefly describe two Markovian models--the special semi-Markov process (SSMP) and Markov modulated Poisson process (MMPP)--and a non-Markovian model--Poisson Pareto burst process (PPBP). An SSMP may be a part of a DTMC model, an MMPP may be used in a CTMC model, and a PPBP is frequently used in network traffic simulations.