Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks

The topology have profound impact on the efficiency of search on unstructured peer-to-peer (P2P) networks as well as other networks. It has been well-known that search on scale-free (power-law) topologies offer outstanding search efficiency as good as $O(\ln \ln N)$ for a range of degree distribution exponents. However, generation and maintenance of such scale-free topologies are hard to realize in a distributed and potentially uncooperative environments as in the P2P networks. A key limitation of scale-free topologies is the high load (i.e. high degree) on very few number of hub nodes. In a typical unstructured P2P network, peers are not willing to maintain high degrees/loads as they may not want to store large number of entries for construction of the overlay topology. So, to achieve fairness and practicality among all peers, hard cutoffs on the number of entries are imposed by the individual peers. Thus, efficiency of the flooding search reduces as the size of the hard cutoff does. Interestingly, we observe that the efficiency of normalized flooding and random walk search algorithms increases as the hard cutoff decreases.