Performance evaluation of the random replacement policy for networks of caches (14

The overall performance of content distribution networks as well as recently proposed information-centric networks rely on both memory and bandwidth capacities. In this frame-work, the hit ratio is the key performance indicator which captures the bandwidth / memory tradeoff for a given global performance. This paper focuses on the estimation of the hit ratio in a network of caches that employ the Random replacement policy. Assuming that requests are independent and iden-tically distributed, general expressions of miss probabilities for a single Random cache are provided as well as exact re-sults for specific popularity distributions. Moreover, for any Zipf popularity distribution with exponent α> 1, we obtain asymptotic equivalents for the miss probability in the case of large cache size. We extend the analysis to networks of Random caches, when the topology is either a line or a homogeneous tree. In that case, approximations for miss probabilities across the net-work are derived by assuming that miss events at any node occur independently in time; the obtained results are com-pared to the same network using the Least-Recently-Used discipline, already addressed in the literature. We further analyze the case of a mixed tandem cache network where the two nodes employ either Random or Least-Recently-Used policies. In all scenarios, asymptotic formulas and approxi-mations are extensively compared to simulations and shown to perform very well. Finally, our results enable us to pro-pose recommendations for cache replacement disciplines in a network dedicated to content distribution. These results also hold for a cache using the First-In-First-Out policy