Generating a Jump Distance Based Synthetic Disk Access Pattern

As part of our on-going research into improving the quality of synthetic, block-level I/O workloads, we have developed an algorithm that generates a synthetic (i.e., random) disk access pattern based on both (1) a given distribution of sectors accessed and (2) a given distribution of ``jump distances\u27\u27 between successive disk accesses. Generating a synthetic disk access pattern that maintains both distributions exactly is an NP-complete problem (similar to the Traveling Salesman problem). In this paper, we (1) discuss our approximation algorithm, (2) show that it runs in a reasonable amount of time, (3) show that it reproduces both distributions with reasonable accuracy, and (4) demonstrate its overall effect on the quality of block-level synthetic workloads