COMPARING STRENGTH OF LOCALITY OF REFERENCE — Popularity, majorization, and some folk theorems

The performance of demand-driven caching is known to depend on the locality of reference exhibited by the stream of requests made to the cache. Yet, like the notion of burstiness used in traffic modeling, locality of reference, while endowed with a clear intuitive content, admits no simple definition. In spite of numerous efforts, no consensus has been reached on how to formalize this notion, let alone on how to compare streams of requests on the basis of their locality of reference.

We take on this issue with an eye towards validating operational expectations associated with the notion of locality of reference. More specifically, we focus on two "folk theorems," namely (i) The stronger the locality of reference, the smaller the miss rate of the cache; (ii) Good caching is expected to produce an output stream
of requests exhibiting less locality of reference than the input stream.

We discuss results concerning these two folk theorems in the context of a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). As we propose to measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution, we introduce the notion of majorization as a means of capturing this degree of skewness.

We show that these folk theorems hold for caches operating under a large class of cache replacement policies, including the optimal policy A_0 and the random policy, but may fail under the LRU and CLIMB policies. In addition, we explore how the majorization of popularity distributions translates into comparisons of three well-known locality of reference metrics, namely the inter-reference time, the working set size and the stack distance.