Workshop on
Mathematical Modeling and Analysis of Computer Networks
"Epidemic Dissemination and Efficient Broadcasting
in PeertoPeer Systems"
Laurent Massoulie
Thomson Research
This talk focuses on the problem of relaying a live stream of information from a source to nodes of a peertopeer system. Several scheduling rules for neighbour and packet selection based on local information are proposed.
In a symmetric system where capacity constraints are associated with nodes, and all nodes have the same capacities, we show that the socalled ``random neighbour / latestpacketfirst'' rule achieves optimal delay for rates below 11/e of the optimal broadcast rate.
For arbitrary node capacities, we establish that the ``mostdeprived neighbour / random useful packet'' rule achieves optimal broadcast rate.
For edgecapacitated graphs, we show that ``random useful packet'' rule achieves optimal broadcast rate. A classical characterization, due to Edmonds, of the number of spanning trees that can be packed in a graph is retrieved as a corollary.
We next discuss a more general scenario where several live streams of information are to be disseminated concurrently. In this context, we show rate optimality of ``bundled random useful packet'' rule. As a byproduct we obtain an extension to multiple commodities of Edmonds' theorem on packing of spanning trees.
