Degree biased random walk in unstructured peer-to-peer networks

Existing search protocols can effectively locate highly popular files or achieve low message overhead, but it is very difficult for them to achieve balance between search effectiveness and robustness, especially when the search mechanisms exploit the nodes heterogeneity. In this paper, we propose a family of search mechanisms named degree biased random walk to exploit the nodes heterogeneity and control the query load distribution on them. The search mechanisms are light-weight, tunable without the need for knowing global information. First, we obtain the mathematic formula of degree biased function, demonstrate the load distribution and search effectiveness through theoretical analysis. Then, we further evaluate our degree biased algorithms using simulator-based experiments with taking both the file distribution and query distribution into consideration. We validate the degree biased random walk and find it can work well in a wide range of query distribution and file distribution. Moreover, we show it can shift the query load to the different nodes by controlling the degree distribution of the visited nodes in search process, and realize high search performance and robustness in the power-law like load distribution with the given exponent.