THE FRACTAL STRUCTURE OF DATA REFERENCE- P11:For purposes of understanding its performance, a computer system is traditionally viewed as a processor coupled to one or more disk storage devices, and driven by externally generated requests (typically called transactions). Over the past several decades, very powerful techniques have become available to the performance analyst attempting to understand, at a high level, the operational behavior of such systems. | 36 THE FRACTAL STRUCTURE OF DATA REFERENCE proves to be useful for comparison against the proposed synthetic pattern of requests. To estimate X t assume that some initial request occurs at time t 0 time is measured relative to whatever initial request we choose to examine . Consider the number N t of requests that occur at some time 0 t t. Let us now assume that the i o requests are being serviced by a cache whose single-reference residency time is given by T t. To determine the expectation of N t we must examine all potential choices of the initial i o request. Let us divide these potential choices into groups depending upon the cache visit within which they occur. For any given initial i o request let V t be the largest number of i o s that occurs during any time period of length t that falls within the cache visit that contains the request. Note that V t is identical for all initial i o requests that fall within the same cache visit. Also for all such i o s 0 N t V t - 1 the case N t V t cannot occur since the count ofi o s given by N t does not include the i o at time t 0 . Moreover values must occur throughout this range including both extremes. For the identified cache visit we therefore adopt the rough estimate E N t x 2 V t - 1 . For all cache visits we estimate that F N r 72 W -1 But the expected number of i o s per cache visit is just 1 m t . Although not all of these must necessarily occur during any single time period of length t such an outcome is fairly likely due to the tendency ofi o s to come in bursts. Thus E V t 1 m t which implies I iV r 72 -4 1 L 0 J Asymptotically for sufficiently small miss ratios Based upon we can now state the asymptotic behavior ofthe arrival rate X t . For sufficiently small miss ratios we have X t -E 7V r at 0 G 12-21 This is the asymptotic behavior that we wish to emulate. Hierarchical Reuse Daemon 37 2. DEFINITION OF THE SYNTHETIC APPLICATION We now define a synthetic toy application that performs a random walk
