Placement Algorithms for Hierarchical Cooperative Caching

Consider a hierarchical network of machines in which each machine periodically issues a request for an object drawn from a fixed set of unit-size objects. Assume that: (i) the frequency with which each machine accesses each object is known, (ii) each machine has a cache of known capacity, (iii) any cache can be accessed by any machine, and (iv) any request is satisfied by the closest machine with a copy of the desired object. In such an environment, it is desirable to fill the available cache space with copies of objects in such a way that the average access cost is minimized. We provide both exact and approximate polynomial-time algorithms for this hierarchical placement problem. Our exact algorithm is based on a reduction to min-cost flow, and does not appear to be practical for large problem sizes. Thus we are motivated to search for a faster approximation algorithm. Our main result is a simple constant-factor approximation algorithm for the hierarchical placement problem that admits an efficient distributed implementation.