Converging an Overlay Network to a Gradient Topology
For designers of P2P networks requiring gradient topologies (e.g., live streaming), this work provides theoretical guarantees and practical improvement over random sampling.
The paper proves necessary and sufficient conditions for convergence of a gossip-based Gradient overlay network to a complete gradient topology, provides convergence time bounds, and demonstrates via simulation that it enables a more efficient live-streaming P2P system than uniform random peer sampling.
In this paper, we investigate the topology convergence problem for the gossip-based Gradient overlay network. In an overlay network where each node has a local utility value, a Gradient overlay network is characterized by the properties that each node has a set of neighbors with the same utility value (a similar view) and a set of neighbors containing higher utility values (gradient neighbor set), such that paths of increasing utilities emerge in the network topology. The Gradient overlay network is built using gossiping and a preference function that samples from nodes using a uniform random peer sampling service. We analyze it using tools from matrix analysis, and we prove both the necessary and sufficient conditions for convergence to a complete gradient structure, as well as estimating the convergence time and providing bounds on worst-case convergence time. Finally, we show in simulations the potential of the Gradient overlay, by building a more efficient live-streaming peer-to-peer (P2P) system than one built using uniform random peer sampling.