# Self-Similar Markovian Sources
###### Abstract  
Markov queueing models are a powerful tool to evaluate the performance of computer networks and have been used in telecommunication studies for over 100 years. To apply them to the evaluation of the modern Internet, we should not only adapt them to the contemporary network structures but also include a description of the complex stochastic patterns (self-similarity and long-range dependance) of transmitted flows. We examine the features of two Markov models of an almost self-similar process, keeping in mind the modeling of Internet traffic. We have found that the obtained results are comparable with those achieved using a well-known generator of self-similar traffic. long-range dependence (LRD); self-similarity; traffic sources; Hurst parameter; Markov models +
Footnote †: journal: Applied Informatics  
14 April 2  
software. Two well-known simulators are OMNeT++ [1] and ns-3 [2], both of which strictly follow the behavior of network protocols and the router's performance. Analytical models are much simpler, leading to a decrease in the number of computational operations, and as a result, these models have a shorter execution time. This is especially beneficial in transient analysis, in which the discrete event simulation of such network behavior is very time-consuming due to the large number of randomized repetitions required to achieve a reasonable level of a statistical accuracy. This is even more critical in the case of self-similar traffic where, due to the complex changes of traffic, the simulations should be longer to assure a desired accuracy level. Additionally, the analytical models efficiently compute very small probabilities, e.g., loss probabilities, while a simulation needs to be long enough to observe rare events a sufficient number of times. The question examined in this article is the following: are analytical models of traffic, which may be a part of entire analytical queueing models, correct and featured by sufficiently strong performance to compete with simulation traffic models? It seems that the answer is positive. In Markov models, each state of a studied system corresponds to a state of a Markov chain. They may use continuous-time (CTMC) or discrete-time (DTMC) chains. In the first case, a change of state may occur at any time; in the second case, only at defined time moments can this change take place. The transition matrix defining the changes of states in a Markov chain contains transition intensities in the case of CTMS and transition probabilities in the case of DTMC. If we solve a system of Chapman-Kolmogorov equations determining the state probabilities in a Markov chain, we also obtain the state probabilities of the system (i.e., the number of equations and the number of states are the same). The main feature of Markov chains is that they are memoryless, implying that the sojourn time at a state is exponentially distributed in the case of a continuous-time Markov chain and geometrically distributed in the case of a discrete-time chain. Therefore, the first Markov queueing models assumed exponentially distributed interarrival times (i.e., Poisson input stream) and exponentially distributed service times. These assumptions are distinct from what we observe in real networks. However, practically any distribution may be represented by a linear combination of exponentially distributed phases, so if we also include the number of the current phase in the state definition, we may construct a queueing Markov model with any interarrival and service time distributions. Of course, the number of states to be considered and the number of equations to be solved are increasing. Moreover, only a numerical solution is possible. Consequently, the number of states, which rapidly increase with the complexity of the model and result in so-called state explosion, limit the range of utility of Markov models. Nevertheless, the constant increase of the computing power makes increasingly complex models feasible.