Computer Science > Networking and Internet Architecture
[Submitted on 8 Jul 2014]
Title:Deterministic Near-Optimal P2P Streaming
View PDFAbstract:We consider streaming over a peer-to-peer network with homogeneous nodes in which a single source broadcasts a data stream to all the users in the system. Peers are allowed to enter or leave the system (adversarially) arbitrarily. Previous approaches for streaming in this setting have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have poor connectivity guarantees, while structured trees have good connectivity but have proven hard to maintain under peer churn. We improve upon both approaches by presenting a novel distribution structure with a deterministic and distributed algorithm for maintenance under peer churn; our result is inspired by a recent work proposing deterministic algorithms for rumor spreading in graphs. A key innovation in our approach is in having redundant links in the distribution structure. While this leads to a reduction in the maximum streaming rate possible, we show that for the amount of redundancy used, the delay guarantee of the proposed algorithm is near optimal. We introduce a tolerance parameter that captures the worst-case transient streaming rate received by the peers during churn events and characterize the fundamental tradeoff between rate, delay and tolerance. A natural generalization of the deterministic algorithm achieves this tradeoff near optimally. Finally, the proposed deterministic algorithm is robust enough to handle various generalizations: ability to deal with heterogeneous node capacities of the peers and more complicated streaming patterns where multiple source transmissions are present.
Submission history
From: Shaileshh Bojja Venkatakrishnan [view email][v1] Tue, 8 Jul 2014 02:37:17 UTC (1,376 KB)
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.