A scalable, efficient and general Monte Carlo scheme for generating synthetic web request streams.

We propose a Monte Carlo scheme (GRAPES) for generating synthetic web request streams. These request streams obey the Zipf page popularity distribution and temporal locality in the form of log-normal stack-distance distribution. Our algorithm avoids the use of an explicit stack; it uses a precomputed set of coefficients representing stack-distance distribution to generate web page requests. Using these coefficients our the algorithm runs in time proportional to the number of generated requests in contrast to other request stream generators that run in time proportional to the product of the stack size and the number of generated requests. The performance plots suggest a speedup of an order of magnitude for large inputs. We use an intricate randomization strategy to produce a uniform and random request stream. Our scheme is amenable to an efficient parallel implementation. [ABSTRACT FROM AUTHOR]