PrefixStream: A Balanced, Resilient and Incentive Peer-to-Peer Multicast Algorithm

We consider the problem of multicasting a stream of packets in a large scale peer-to-peer environment. In that context, we stress three features: forwarding load should be equally balanced among nodes, the scheme should be resilient to node failures and peers should have incentive to cooperate. Mainly based on the seminal work of SplitStream which partially achieves this goals, we propose an algorithm gathering together these three features. Its main advantage is to reduce the forwarding load of every node to the stream bandwidth (every node uploads as much as it downloads). This ultimate load balancing is achieved together with a clustering scheme allowing bi-directional exchanges. This results in resilience to node failures and the possibility of banishing nodes that do not respect reciprocity of exchanges. This paper promotes disjoint clustering as opposed to previously proposed hierarchical clustering schemes. Interestingly, varying the size of clusters allows to obtain different trade-offs between delay optimization and resilience to node failures. The performances of several algorithms are analyzed and compared with respect to these goals. The propagation delays of these algorithms appear to be within a factor 1.5 to 2 from theoretical optimal