The Optimal Replica Distribution to Minimize the Search Size in the Unstructured Overlay

Replication is a widely used technique in unstructured overlays to improve the content availability or the system performance. Among the prior work on replication, a fundamental question is often addressed: how many replicas should be kept for each data item if given the fixed request rates and the limited storage capability? The Square-Root Replication, in which the replica number of an item is proportional to the square root of its global request rate and proportional to its item size, is usually considered to be optimal as far as the minimization of the search size is concerned. However, our work shows that this viewpoint is not always true, especially in the realistic environments. Firstly, we hold that the replica number should be inversely proportional to the square root of the item size in the optimal replication under the theoretical settings. Secondly, the Square-Root Replication is not optimal when TTL (Time to Live) is small or replica density is low in the practical applications. In this paper, we firstly formulate the questions and present the formal proofs, and finally provide some simulations to validate our conclusions.