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 i n an arrival process that have gained considerable interest in recent liter ature. The so-called internal and external shuffling have been used to expl ain phenomena observed in traffic traces from LANs. Loosely, the internal s huffling can be viewed as a way of performing local permutations in the arr ival stream, while the external shuffling is a way of performing global per mutations. We derive formulas for the correlation structures of the shuffle d processes in terms of the original arrival process in great generality. T he implications for the correlation structure when shuffling an exactly sec ond-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 experimen ts. 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 genera lity. (C) 2000 Elsevier Science B.V. All rights reserved.