Decentralized Broadcasting Algorithms

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.

Publisher  IEEE Communications Society
Copyright © 2007 IEEE. Reprinted from IEEE Communications Society. This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to By choosing to view this document, you agree to all provisions of the copyright laws protecting it.


> Publications > Decentralized Broadcasting Algorithms