Title :
Randomized Decentralized Broadcasting Algorithms
Author :
Massoulie, Laurent ; Twigg, Andy ; Gkantsidis, Christos ; Rodriguez, Pablo
Author_Institution :
Thomson Res., Paris
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 lambda + epsiv is feasible for epsiv > 0, a simple local-control algorithm is stable under demand lambda, 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.
Keywords :
digital video broadcasting; directed graphs; randomised algorithms; video streaming; Edmonds theorem; directed graph; edge-capacitated network; live video streaming; local-control algorithm; randomized decentralized broadcasting algorithm; Broadcasting; Communications Society; Delay; Heuristic algorithms; Motion pictures; Multimedia communication; Network topology; Peer to peer computing; Scheduling algorithm; Streaming media;
Conference_Titel :
INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE
Conference_Location :
Anchorage, AK
Print_ISBN :
1-4244-1047-9
DOI :
10.1109/INFCOM.2007.129
