Decentralized Broadcasting Algorithms

Laurent Massoulié, Andy Twigg, Christos Gkantsidis, and Pablo Rodriguez

Abstract

We consider the problem of broadcasting a live stream of data in an unstructured network. The broadcasting problem has been studied extensively for edge-capacitated networks. We give the first proof that whenever demand ? + e is feasible for e > 0, a simple local-control algorithm is stable under demand ?, and as a corollary a famous theorem of Edmonds. We then study the node-capacitated case and show a similar optimality result for the complete graph. We study through simulation the delay that users must wait in order to playback a video stream with a small number of skipped packets, and discuss the suitability of our algorithms for live video streaming.

Details

Publication typeInproceedings
URLhttp://www.comsoc.org/
PublisherIEEE Communications Society
> Publications > Decentralized Broadcasting Algorithms