Deterministic near-optimal P2P streaming

Shaileshh Bojja Venkatakrishnan; Pramod Viswanath

doi:10.1145/2745844.2745888

Deterministic near-optimal P2P streaming

Shaileshh Bojja Venkatakrishnan, Pramod Viswanath

Research output: Contribution to journal › Conference article › peer-review

Abstract

We consider live-streaming over a peer-to-peer network in which peers are allowed to enter or leave the system adversarially and arbitrarily. Previous approaches for streaming have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have only probabilistic 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. The algorithm has a constant repair time for connectivity, and near optimal delay. As opposed to order results, the guarantees provided by our algorithm are exact and hold for any network size.

Original language	English (US)
Pages (from-to)	451-452
Number of pages	2
Journal	Performance Evaluation Review
Volume	43
Issue number	1
DOIs	https://doi.org/10.1145/2745844.2745888
State	Published - Jun 24 2015
Externally published	Yes
Event	ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015 - Portland, United States Duration: Jun 15 2015 → Jun 19 2015

All Science Journal Classification (ASJC) codes

Software
Hardware and Architecture
Computer Networks and Communications

Keywords

Deterministic
One-to-many content distribution
Peer-to-peer
Streaming

Access to Document

10.1145/2745844.2745888

Cite this

@article{94b216a9574d442bbdf6140c75ac2193,

title = "Deterministic near-optimal P2P streaming",

abstract = "We consider live-streaming over a peer-to-peer network in which peers are allowed to enter or leave the system adversarially and arbitrarily. Previous approaches for streaming have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have only probabilistic 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. The algorithm has a constant repair time for connectivity, and near optimal delay. As opposed to order results, the guarantees provided by our algorithm are exact and hold for any network size.",

keywords = "Deterministic, One-to-many content distribution, Peer-to-peer, Streaming",

author = "Venkatakrishnan, {Shaileshh Bojja} and Pramod Viswanath",

note = "Publisher Copyright: {\textcopyright} Copyright 2015 ACM.; ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015 ; Conference date: 15-06-2015 Through 19-06-2015",

year = "2015",

month = jun,

day = "24",

doi = "10.1145/2745844.2745888",

language = "English (US)",

volume = "43",

pages = "451--452",

journal = "Performance Evaluation Review",

issn = "0163-5999",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - Deterministic near-optimal P2P streaming

AU - Venkatakrishnan, Shaileshh Bojja

AU - Viswanath, Pramod

PY - 2015/6/24

Y1 - 2015/6/24

N2 - We consider live-streaming over a peer-to-peer network in which peers are allowed to enter or leave the system adversarially and arbitrarily. Previous approaches for streaming have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have only probabilistic 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. The algorithm has a constant repair time for connectivity, and near optimal delay. As opposed to order results, the guarantees provided by our algorithm are exact and hold for any network size.

AB - We consider live-streaming over a peer-to-peer network in which peers are allowed to enter or leave the system adversarially and arbitrarily. Previous approaches for streaming have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have only probabilistic 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. The algorithm has a constant repair time for connectivity, and near optimal delay. As opposed to order results, the guarantees provided by our algorithm are exact and hold for any network size.

KW - Deterministic

KW - One-to-many content distribution

KW - Peer-to-peer

KW - Streaming

UR - http://www.scopus.com/inward/record.url?scp=84955618264&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84955618264&partnerID=8YFLogxK

U2 - 10.1145/2745844.2745888

DO - 10.1145/2745844.2745888

M3 - Conference article

AN - SCOPUS:84955618264

SN - 0163-5999

VL - 43

SP - 451

EP - 452

JO - Performance Evaluation Review

JF - Performance Evaluation Review

IS - 1

T2 - ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015

Y2 - 15 June 2015 through 19 June 2015

ER -

Deterministic near-optimal P2P streaming

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this