A Tree-Based Peer-to-Peer Network with Quality Guarantees

Peer-to-peer (P2P) networks often demand scalability, low communication latency among nodes, and low systemwide overhead. For scalability, a node maintains partial states of a P2P network and connects to a few nodes. For fast communication, a P2P network intends to reduce the communication latency between any two nodes as much as possible. With regard to a low systemwide overhead, a P2P network minimizes its traffic in maintaining its performance efficiency and functional correctness. In this paper, we present a novel tree-based P2P network with low communication delay and low systemwide overhead. The merits of our tree-based network include 1) a tree-shaped P2P network, which guarantees that the degree of a node is constant in probability, regardless of the system size (the network diameter in our tree-based network increases logarithmically with an increase in the system size, and in particular, given a physical network with a power-law latency expansion property, we show that the diameter of our tree network is constant), and 2) provable performance guarantees. We evaluate our proposal by a rigorous performance analysis, and we validate this by extensive simulations.

1 Introduction

Peer-to-peer (P2P) networks (or overlays) have recently become an active research area. Applications over P2P networks include information retrieval, content distribution, processor cycle sharing, etc. These applications often demand that their underlying P2P network infrastructures be scalable and have low diameter and overhead. For example, an Internet-scale file sharing system, namely, Oceanstore [1], is designed and deployed on top of a P2P network Tapestry [2]. Tapestry is scalable in that each node participates in the network by using connections. Its overlay diameter is equal to , where is the total number of nodes in the system.