Incentive, Resilience and Load Balancing in Multicasting through Clustered de Bruijn Overlay Network (PrefixStream)

Anh-Tuan Gai (1) , Laurent Viennot (1)

1 GYROWEB - Dynamic graphs and the web graph

In this paper, we consider the problem of multicasting a stream of packets in a large scale peer-to-peer environment. In that context peers should have incentive to cooperate. We present PrefixStream, an algorithm that addresses this problem by using reciprocity in packet forwarding. Each node thus has incentive to forward since recipients send back other packets of the stream. To achieve this efficiently, PrefixStream strips the content across two sets of clustered trees built upon the symmetric de Bruijn graph. This both allows to banish nodes that do not respect reciprocity of exchanges and gives resilience to node failures. Furthermore, it reduces the forwarding load of every node to the stream bandwidth (every node uploads as much as it downloads) even when the size of its cluster varies. Conversely to previously proposed hierarchical schemes, PrefixStream promotes disjoint clustering. This enables loose maintenance and network latencies optimization. We sketch the design of PrefixStream and analyze its performances.

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Réseaux et télécommunications [cs.NI]; Web

Anh-Tuan Gai, Laurent Viennot. Incentive, Resilience and Load Balancing in Multicasting through Clustered de Bruijn Overlay Network (PrefixStream). 14th IEEE International Conference on Networks (ICON), Sep 2006, Singapore, Singapore. pp.1-6, ⟨10.1109/ICON.2006.302673⟩. ⟨inria-00471718⟩