Randomized Decentralized Broadcasting Algorithms
Authors:
- L. MassoulieLML. Massoulie
- A. TwiggATA. Twigg
- C. GkantsidisCGC. Gkantsidis
- P. RodriguezPRP. Rodriguez
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 1073-1081
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
This publication has 9 references indexed in Scilit:
- Analyzing and Improving a BitTorrent Networks Performance Mechanisms2006
- Stability of Data Networks: Stationary and Bursty ModelsOperations Research, 2005
- Stochastic Networks and Queues2003
- Packing algorithms for arborescences (and spanning trees) in capacitated graphsMathematical Programming, 1998
- An ε-Relaxation method for generalized separable convex cost network flow problems1996
- A Matroid Approach to Finding Edge Connectivity and Packing ArborescencesJournal of Computer and System Sciences, 1995
- On Positive Harris Recurrence of Multiclass Queueing Networks: A Unified Approach Via Fluid Limit ModelsThe Annals of Applied Probability, 1995
- A faster algorithm for finding edge-disjoint branchingsInformation Processing Letters, 1983
- On two minimax theorems in graphJournal of Combinatorial Theory, Series B, 1976