Performance of the Move-To-Front Algorithm with Markov-Modulated Request Sequences

We study the classical move-to-front (MTF) algorithm for self-organizing lists within the Markov-modulated request (MMR) model. Such models are useful when list accesses are generated within a relatively small set of modes, with the request sequences in each mode being i.i.d. These modes are often called localities of reference and are known to exist in such applications as traffic streams of Ethernet or ATM networks and the locus of control or data accesses of executing computer programs. Our main results are explicit formulas for the mean and variance of the search-cost, the number of accesses required to find a given list element.