  The overall performance of content distribution networks as well as recently
proposed information-centric networks rely on both memory and bandwidth
capacities. In this framework, 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 identically distributed, general expressions of miss
probabilities for a single Random cache are provided as well as exact results
for specific popularity distributions. Moreover, for any Zipf popularity
distribution with exponent $\alpha$ > 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 network
are derived by assuming that miss events at any node occur independently in
time; the obtained results are compared 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 approximations are extensively compared to simulations and shown
to perform very well. Finally, our results enable us to propose 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.
