Load balancing with multiple hash functions in peer-to-peer networks

Peer-to-peer (P2P) networks have grown in popularity in recent years. One of the typical applications of P2P networks is file-sharing. Effective load balancing in such applications is important since the distribution of the number of requests for individual files can be heavily skewed. In the basic design of these networks each file is stored at a single node (i.e., server) which will become a hotspot if the file is popular. In this paper, we focus on the file-replication strategy that utilize multiple hash functions. Such a strategy typically sets aside a large number of hash functions. When the demand for a file exceeds the overall capacity of the current servers, a previously unused hash function is used to obtain a new server ID where the file will be replicated. The central problems are how to choose an unused hash function when replicating a file and how to choose a used hash function when requesting the file. Our solution to the file-replication problem is to choose the unused hash function with the smallest index, and our solution to the file-request problem is to choose a used hash function uniformly at random. Our main contribution is to develop a set of distributed algorithms that implement the above solutions and to evaluate their performance. In particular, we analyze a random binary search algorithm and random gap-removal algorithm