Performance evaluation of the random replacement policy for networks of caches

International audienceThe overall performance of content distribution networks as well as recently proposedinformation-centric networks rely on both memory and bandwidth capacities. The hit ratiois the key performance indicator which captures the bandwidth/memory tradeoff for agiven global performance.This paper focuses on the estimation of the hit ratio in a network of caches thatemploy the Random replacement policy (RND). Assuming that requests are independentand identically distributed, general expressions of miss probabilities for a single RND cacheare provided as well as exact results for specific popularity distributions (such results alsohold for the FIFO replacement policy). Moreover, for any Zipf popularity distribution withexponent α > 1, we obtain asymptotic equivalents for the miss probability in the case oflarge cache size.We extend the analysis to networks of RND caches, when the topology is either aline or a homogeneous tree. In that case, approximations for miss probabilities across thenetwork are derived by neglecting time correlations between miss events at any node;the obtained results are compared to the same network using the Least-Recently-Useddiscipline, already addressed in the literature. We further analyze the case of a mixedtandem cache network where the two nodes employ either Random or Least-Recently-Used policies. In all scenarios, asymptotic formulas and approximations are extensivelycompared to simulation results and shown to be very accurate. Finally, our results enableus to propose recommendations for cache replacement disciplines in a network dedicatedto content distribution