Replica Distribution for Search Size Minimization in Unstructured Overlay
Feng Guo · Chinese Journal of Computers · 2011
Replication is a widely used technique in unstructured overlays to improve the system performance.A fundamental question on replication is often addressed: how many replicas should be kept for each data item if given the fixed file sizes,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.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.Although our conclusions are drawn under the background of P2P(Peer-to-Peer),they also apply to those fully distributed systems,whose resources are managed by means of the unstructured application-layer overlay.