research-article

rStream: Resilient and Optimal Peer-to-Peer Streaming with Rateless Codes

Authors:

Baochun LiAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 19, Issue 1

Pages 77 - 92

https://doi.org/10.1109/TPDS.2007.1119

Published: 01 January 2008 Publication History

Abstract

Due to the lack of stability and reliability in peer-topeer networks, multimedia streaming over peer-to-peer networks represents several fundamental engineering challenges. First, multimedia streaming sessions need to be resilient to volatile network dynamics and node departures that are characteristic in peer-to-peer networks. Second, they need to take full advantage of the existing bandwidth capacities, by minimizing the delivery of redundant content and the need for content reconciliation among peers during streaming. Finally, streaming peers need to be optimally selected to construct high-quality streaming topologies, so that end-to-end latencies are taken into consideration. The original contributions of this paper are two-fold. First, we propose to use a recent coding technique, referred to as rateless codes, to code the multimedia bitstreams before they are transmitted over peer-to-peer links. The use of rateless codes eliminates the requirements of content reconciliation, as well as the risks of delivering redundant content over the network. Rateless codes also help the streaming sessions to adapt to volatile network dynamics. Second, we minimize end-to-end latencies in streaming sessions by optimizing towards a latency-related objective in a linear optimization problem, the solution to which can be efficiently derived in a decentralized and iterative fashion. The validity and effectiveness of our new contributions are demonstrated in extensive experiments in emulated realistic peer-to-peer environments with our rStream implementation.

References

[1]

J. Byers, J. Considine, M. Mitzenmacher, and S. Rost, “Informed Content Delivery across Adaptive Overlay Networks,” Proc. ACM SIGCOMM '02, Aug. 2002.

Digital Library

[2]

X. Zhang, J. Liu, B. Li, and T.P. Yum, “CoolStreaming/DONet: A Data-Driven Overlay Network for Peer-to-Peer Live Media Streaming,” Proc. IEEE INFOCOM '05, Mar. 2005.

[3]

M. Luby, “LT Codes,” Proc. 43rd Symp. Foundations of Computer Science (FOCS '02), Nov. 2002.

Digital Library

[4]

A. Shokrollahi, “Raptor Codes,” Proc. IEEE Int'l Symp. Information Theory (ISIT '04), June 2004.

[5]

P. Maymounkov and D. Mazieres, “Rateless Codes and Big Downloads,” Proc. Second Int'l Workshop Peer-to-Peer Systems (IPTPS '03), Feb. 2003.

[6]

J. Byers, M. Luby, M. Mitzenmacher, and A. Rege, “A Digital Fountain Approach to Reliable Distribution of Bulk Data,” Proc. ACM SIGCOMM '98, Sept. 1998.

Digital Library

[7]

A. Medina, A. Lakhina, I. Matta, and J. Byers, “BRITE: Boston University Representative Internet Topology Generator,” technical report, http://www.cs.bu.edu/brite, 2000.

[8]

D.A. Tran, K.A. Hua, and T.T. Do, “A Peer-to-Peer Architecture for Media Streaming,” IEEE J. Selected Areas in Comm., vol. 22, pp.121-133, Jan. 2004.

Digital Library

[9]

S. Banerjee, B. Bhattacharjee, and C. Kommareddy, “Scalable Application Layer Multicast,” Proc. ACM SIGCOMM '02, Aug. 2002.

Digital Library

[10]

Z. Li, B. Li, D. Jiang, and L.C. Lau, “On Achieving Optimal Throughput with Network Coding,” Proc. IEEE INFOCOM '05, Mar. 2005.

[11]

C. Wu and B. Li, “Optimal Peer Selection for Minimum-Delay Peer-to-Peer Streaming with Rateless Codes,” Proc. ACM Workshop Advances in Peer-to-Peer Multimedia Streaming (P2PMMS '05) in conjunction with the 13th ACM Int'l Conf. Multimedia (Multimedia '05), Nov. 2005.

Digital Library

[12]

D. Bertsekas, Nonlinear Programming. Athena Scientific, 1995.

[13]

N.Z. Shor, Minimization Methods for Non-Differentiable Functions. Springer, 1985.

Digital Library

[14]

D.P. Bertsekas and D.A. Castanon, “The Auction Algorithm for the Transportation Problem,” Annals of Operations Research, vol. 20, pp. 67-96, 1989.

Digital Library

[15]

R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

Digital Library

[16]

D.P. Bertsekas and J.N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Prentice Hall, 1989.

Digital Library

[17]

D.P. Bertsekas and R. Gallager, Data Networks, second ed. Prentice Hall, 1992.

Digital Library

[18]

H.D. Sherali and G. Choi, “Recovery of Primal Solutions When Using Subgradient Optimization Methods to Solve Lagrangian Duals of Linear Programs,” Operations Research Letter, vol. 19, pp.105-113, 1996.

Digital Library

[19]

All-Sites-Pings for PlanetLab, http://ping.ececs.uc.edu/ping/, 2007.

[20]

J. Li, “PeerStreaming: A Practical Receiver-Driven Peer-to-Peer Media Streaming System,” Technical Report MSR-TR-2004-101, Microsoft Research, Sept. 2004.

[21]

H. Deshpande, M. Bawa, and H. Garcia-Molina, “Streaming Live Media over a Peer-to-Peer Network,” Technical Report 2001-20, Stanford Database Group, Aug. 2001.

[22]

D.A. Tran, K.A. Hua, and T. Do, “ZIGZAG: An Efficient Peer-to-Peer Scheme for Media Streaming,” Proc. IEEE INFOCOM '03, Mar. 2003.

[23]

V.N. Padmanabhan, H.J. Wang, P.A. Chow, and K. Sripanidkulchai, “Distributing Streaming Media Content Using Cooperative Networking,” Proc. 12th Int'l Workshop Network and Operating System Support for Digital Audio and Video (NOSSDAV '02), May 2002.

Digital Library

[24]

M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh, “SplitStream: High-Bandwidth Multicast in Cooperative Environments,” Proc. 19th ACM Symp. Operating Systems Principles (SOSP '03), Oct. 2003.

Digital Library

[25]

V. Pai, K. Kumar, K. Tamilmani, V. Sambamurthy, and A.E. Mohr, “Chainsaw: Eliminating Trees from Overlay Multicast,” Proc. Fourth Int'l Workshop Peer-to-Peer Systems (IPTPS '05), Feb. 2005.

Digital Library

[26]

M. Zhang, L. Zhao, Y. Tang, J. Luo, and S. Yang, “Large-Scale Live Media Streaming over Peer-to-Peer Networks through Global Internet,” Proc. 13th ACM Int'l Conf. Multimedia (Multimedia '05), Nov. 2005.

Digital Library

[27]

M. Hefeeda, A. Habib, B. Botev, D. Xu, and B. Bhargava, “PROMISE: Peer-to-Peer Media Streaming Using CollectCast,” Proc. 11th ACM Int'l Conf. Multimedia (Multimedia '03), Nov. 2003.

Digital Library

[28]

C. Huang, R. Janakiraman, and L. Xu, “Loss-Resilient On-Demand Media Streaming Using Priority Encoding,” Proc. 12th ACM Int'l Conf. Multimedia (Multimedia '04), Oct. 2004.

Digital Library

[29]

M. Adler, R. Kumar, K.W. Ross, D. Rubenstein, T. Suel, and D.D. Yao, “Optimal Peer Selection for P2P Downloading and Streaming,” Proc. IEEE INFOCOM '05, Mar. 2005.

Cited By

Saltarin JBourtsoulatze EThomos NBraun T(2017)Adaptive Video Streaming With Network Coding Enabled Named Data NetworkingIEEE Transactions on Multimedia10.1109/TMM.2017.273795019:10(2182-2196)Online publication date: 14-Sep-2017
https://dl.acm.org/doi/10.1109/TMM.2017.2737950
Heo KKim JYoon C(2016)Tree construction algorithm for virtual content distribution networkMultimedia Tools and Applications10.1007/s11042-014-2277-775:1(131-144)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s11042-014-2277-7
Fen Zhou Jiayi Liu Simon GBoutaba R(2015)Joint Optimization for the Delivery of Multiple Video Channels in Telco-CDNsIEEE Transactions on Network and Service Management10.1109/TNSM.2015.240091512:1(87-100)Online publication date: 16-Mar-2015
https://dl.acm.org/doi/10.1109/TNSM.2015.2400915
Show More Cited By

Index Terms

rStream: Resilient and Optimal Peer-to-Peer Streaming with Rateless Codes

Recommendations

rStream: resilient peer-to-peer streaming with rateless codes
MULTIMEDIA '05: Proceedings of the 13th annual ACM international conference on Multimedia

The inherent instability and unreliability of peer-to-peer networks introduce several fundamental engineering challenges to multimedia streaming over peer-to-peer networks. First, multimedia streaming sessions need to be resilient to the volatile ...
Dynamic Bandwidth Auctions in Multioverlay P2P Streaming with Network Coding

In peer-to-peer (P2P) live streaming applications such as IPTV, it is natural to accommodate multiple coexisting streaming overlays, corresponding to channels of programming. In the case of multiple overlays, it is a challenging task to design an ...
Incentive Mechanisms in P2P Media Streaming Systems

Free riding, whereby a peer utilizes network resources but doesn't contribute services, could have a huge impact on the efficacy of streaming systems, leading to scalability issues and service degradation. BitTorrent-like tit-for-tat mechanisms can't ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 19, Issue 1

January 2008

144 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © 2008.

Publisher

IEEE Press

Publication History

Published: 01 January 2008

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Saltarin JBourtsoulatze EThomos NBraun T(2017)Adaptive Video Streaming With Network Coding Enabled Named Data NetworkingIEEE Transactions on Multimedia10.1109/TMM.2017.273795019:10(2182-2196)Online publication date: 14-Sep-2017
https://dl.acm.org/doi/10.1109/TMM.2017.2737950
Heo KKim JYoon C(2016)Tree construction algorithm for virtual content distribution networkMultimedia Tools and Applications10.1007/s11042-014-2277-775:1(131-144)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s11042-014-2277-7
Fen Zhou Jiayi Liu Simon GBoutaba R(2015)Joint Optimization for the Delivery of Multiple Video Channels in Telco-CDNsIEEE Transactions on Network and Service Management10.1109/TNSM.2015.240091512:1(87-100)Online publication date: 16-Mar-2015
https://dl.acm.org/doi/10.1109/TNSM.2015.2400915
Zhou FAhmad SBuyukkaya EHamzaoui RSimon GLi BShirmohammadi S(2012)Minimizing server throughput for low-delay live streaming in content delivery networksProceedings of the 22nd international workshop on Network and Operating System Support for Digital Audio and Video10.1145/2229087.2229106(65-70)Online publication date: 7-Jun-2012
https://dl.acm.org/doi/10.1145/2229087.2229106
Abboud OPussep KKovacevic AMohr KKaune SSteinmetz R(2011)Enabling resilient P2P video streamingMultimedia Systems10.1007/s00530-011-0229-x17:3(177-197)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s00530-011-0229-x
Huang FKhan MRavindran B(2010)On minimizing average end-to-end delay in P2P live streaming systemsProceedings of the 14th international conference on Principles of distributed systems10.5555/1940234.1940277(459-474)Online publication date: 14-Dec-2010
https://dl.acm.org/doi/10.5555/1940234.1940277
Magnetto AGaeta RGrangetto MSereno MOlmo GTimmerer CFrossard PMitchell K(2010)P2P streaming with lt codesProceedings of the 2010 ACM workshop on Advanced video streaming techniques for peer-to-peer networks and social networking10.1145/1877891.1877894(7-12)Online publication date: 29-Oct-2010
https://dl.acm.org/doi/10.1145/1877891.1877894
Karimov IKamilov MPark ESong JKim HHan S(2009)Managing alternative parent peers for providing fast reconnection between peersProceedings of the 11th international conference on Advanced Communication Technology - Volume 310.5555/1701655.1701670(1566-1571)Online publication date: 15-Feb-2009
https://dl.acm.org/doi/10.5555/1701655.1701670
Grangetto MGaeta RSereno M(2009)Rateless codes network coding for simple and efficient P2P video streamingProceedings of the 2009 IEEE international conference on Multimedia and Expo10.5555/1698924.1699292(1500-1503)Online publication date: 28-Jun-2009
https://dl.acm.org/doi/10.5555/1698924.1699292
Cataldi PTomatis AGrilli GGerla M(2009)A novel data dissemination method for vehicular networks with rateless codesProceedings of the 2009 IEEE conference on Wireless Communications & Networking Conference10.5555/1688345.1688851(2903-2908)Online publication date: 5-Apr-2009
https://dl.acm.org/doi/10.5555/1688345.1688851
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents