Scaling unstructured peer-to-peer networks with multi-tier capacity-aware overlay topologies

The peer to peer (P2P) file sharing systems such as Gnutella have been widely acknowledged as the fastest growing Internet applications ever. The P2P model has many potential advantages due to the design flexibility of overlay networks and the server-less management of cooperative sharing of information and resources. However, these systems suffer from the well-known performance mismatch between the randomly constructed overlay network topology and the underlying IP layer topology for packet routing. This paper proposes to structure the P2P overlay topology using a capacity-aware multi-tier topology to better balance load at peers with heterogeneous capacities and to prevent low capacity nodes from downgrading the performance of the system. To study the benefits and cost of the multi-tier capacity aware topology with respect to basic and advanced routing protocols, we also develop a probabilistic broadening scheme for efficient routing, which further utilizes capacity-awareness to enhance the P2P routing performance of the system. We evaluate our design through simulations. The results show that our multi-tier topologies alone can provide eight to ten times improvements in the messaging cost, two to three orders of magnitude improvement in terms of load balancing characteristics, and seven to eight times lower topology construction and maintenance costs when compared to Gnutellas random power-law topology.