Proportional Replication in Peer-to-Peer Networks

We recently showed for peer-to-peer networks, that
having the number of replicas of each object proportional to the
request rate for these objects has many per-node advantages. In
this paper we complement those results to show that this
distribution has network-wide advantages as well. Given these
benefits of proportional replication, the next issue is achieving
proportional replication in a decentralized manner. We show that
local storage management algorithms like LRU automatically
achieve near-proportional replication and that the system
performance with the replica distribution achieved by LRU is
very close to optimal. We also show that the LRU responds to a
change in user access pattern quickly (the number of accesses
taken to reach the new steady-state replica distribution with LRU
is close to the minimum possible with any cache replacement
algorithm). Analytical models are provided for computing the
steady-state network-wide replica distribution and the transient
period for LRU.
www.cs.ucla.edu