On the statistical implications of certain Random permutations in Markovian Arrival Processes (MAPs) and second order self-similar processes

In this paper, we examine the implications of certain random permutations in an arrival process that have gained considerable interest in recent literature. The so-called internal and external shuffling have been used to explain phenomena observed in traffic traces from LANs. Loosely, the internal shuffling can be viewed as a way of performing local permutations in the arrival stream, while the external shuffling is a way of performing global permutations.

We derive formulas for the correlation structures of the shuffled processes in terms of the original arrival process in great generality. The implications for the correlation structure when shuffling an exactly second-order self-similar process are examined. We apply the Markovian arrival process (MAP) as a tool to investigate whether general conclusions can be made with regard to the statistical implications of the shuffling experiments.

In Appendix A we show that, in principle, it is possible to derive MAP representations of the processes defined by shuffling a MAP in great generality.