Analysis and performance study for coordinated hierarchical cache placement strategies

Data caching has been shown to be efficient in reducing network bandwidth consumption and accelerating information access. In a caching system, an important issue is coordinating data placement to achieve optimal system performance. This paper studies cache placement strategies and their performance in cooperative hierarchical caching environments. A theoretical model is introduced to analyze the access cost of placing a set of object copies in the routing path. Using this model, the object placement problem can be formulated as an optimization problem. It is proved that the problem can be divided into subproblems, thus optimal solutions can be obtained by using dynamic programming. It is further proved that if some nodes are known to be in the optimal solution, the calculation cost of the dynamic programming algorithms can be reduced. A heuristic greedy algorithm is also presented for efficient implementation. Performance of these strategies are evaluated using simulations under both synthetic workload traces and real workload traces. It is shown that both the optimal and the heuristic strategies perform well in cooperative hierarchical caching systems.