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. By adjusting the number of modes, one can use the MMR methodology to trade off the quality of an approximation with the computational effort it requires. Thus, our results provide a useful new tool for evaluating the MTF rule in linear-search applications with correlated request sequences. We illustrate the computations with several examples. (C) 1999 Elsevier Science B.V. All rights reserved.