More Web Proxy on the site http://driver.im/

Article

Free access

A digital fountain approach to reliable distribution of bulk data

Authors:

Michael Mitzenmacher,

Ashutosh RegeAuthors Info & Claims

SIGCOMM '98: Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication

Pages 56 - 67

https://doi.org/10.1145/285237.285258

Published: 01 October 1998 Publication History

Abstract

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal, fully scalable protocol for these applications that we call a digital fountain. A digital fountain allows any number of heterogeneous clients to acquire bulk data with optimal efficiency at times of their choosing. Moreover, no feedback channels are needed to ensure reliable delivery, even in the face of high loss rates.We develop a protocol that closely approximates a digital fountain using a new class of erasure codes that for large block sizes are orders of magnitude faster than standard erasure codes. We provide performance measurements that demonstrate the feasibility of our approach and discuss the design, implementation and performance of an experimental system.

References

[1]

S. Acharya, M. Franklin, and S. Zdonik, "Dissemination Based Data Delivery Using Broadcast Disks," IEEE Personal Communications, December 1995, pp. 50-60.

[2]

A. Bestavros. "AIDA-based real-time fault-tolerant broadcast disks." In Procedings o/the 16th IEEE Real- Time System Symposium, 1996.

Digital Library

[3]

S. Bhattacharyya, J. F. Kurose, D. Towsley, and R. Nagarajan, "Efficient Rate-Controlled Bulk Data Transfer using Multiple Multicast Groups", In Proc. of INFO- COM '98, San Francisco, April 1998.

[4]

.I. B15mer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, and D. Zuckerman, "An XOR-Based Erasure- Resilient Coding Scheme," ICSI Technical Report No. TR-95-O~i8, August 1995.

[5]

S. Floyd, V. Jacobson, C. G. Liu, S. McCanne, and L. Zhang, "A Rehable Multicast Framework for Light- Weight Sessions and Apphcation Level Framing." In ACM SIGCOMM '95, pp. 342-356, August 1995.

Digital Library

[6]

J. Gemmell, "ECSRM- Erasure Correcting Scalable Reliable Multicast," Microsoft Research Technical Report MS- TR-97-20, June 1997.

[7]

C. Huitema, "The Case for Packet Level FEC.' In Proc. o/IFIP 5th Int'l Workshop on Protocols/or High Speed Networks, Sophia Antipolis, France, October 1996.

Digital Library

[8]

Cauchy-based Reed-Solomon codes. Available at http://~w~, icsi. berkeley, edu/~ luby.

[9]

V. Jacobson, "pathchar", available at ht tp://www-mrg, ee. lbl. gov/pathchar.

[10]

J. C. Lin and S. Paul, "RMTP: A Reliable Multicast Transport Protocol." In iEEE INFOCOM '96, pp. 1414-1424, March 1996.

Digital Library

[11]

M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, and V. Stemann, "Practical Loss-Resilient Codes." In Proceedings o/the 29th A CM Symposium on Theory o/Computing, 1997.

Digital Library

[12]

M. Luby, M. Mitzenmacher, and A. Shokrollahi, "Analysis of Random Processes via And-Or Tree Evaluation." In Proceedings o/the 9th Annual A CM-SIAM Symposium on Discrete Algorithms, January 1998.

Digital Library

[13]

N. F. Maxemchuk, Dispersity Routing in Store and Forward Networks. Ph.D. thesis, University of Pennsylvania, May 1975.

[14]

N. F. Maxemchuk, "Dispersity Routing." Proceedings of ICC '75, San Francisco, CA, pp. 41-10- 41-13, 1975.

[15]

S. McCanne, V. Jacobson, and M. Vetterli, "Receiverdriven Layered Multicast." in Proc. o/ A CM SIG- COMM '96, pp. 117-130, 1996.

Digital Library

[16]

C. K. Miller, "Reliable Multicast Protocols: A Practical View." In Proc. o/the ~~nd Annual Con/erence on Local Computer Networks (LCN '97), 1997.

Digital Library

[17]

J. Nonnenmacher and E. W. Biersack, "Reliable Multicast: Where to Use Forward Error Correction." In Proc. o/IFIP 5th Int'l Workshop on Protocols/or High Speed Networks, pp. 134-148, Sophia Antipolis, France, October 1996. Chapman and Hall.

Digital Library

[18]

J. Nonnenmacher and E.W. Biersack, "Asynchronous Multicast Push: AMP." In Proc. o/International Conference on Computer Communications, Cannes, France, November 1997.

[19]

J. Nonnenmacher, M. Lacher, M. Jung, G. Carl, and E.W. Biersack, "How Bad is Reliable Multicast Without Local Recovery?" In Proc. o/iNFOCOM '98, San Francisco, April 1998.

[20]

J. Nonnenmacher, E. W. Biersack, and D. Towsley, "Parity-Based Loss Recovery for Reliable Multicast Transmission." In Proc. o/ACM SIGCOMM '97, 1997.

Digital Library

[21]

M. O. Rabin, "Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance." In Journal o/the A CM, Volume 38, pp. 335-348, 1989.

Digital Library

[22]

L. Rizzo, "Effective Erasure Codes for Reliable Computer Communication Protocols." In Computer Communication Review, April 1997.

Digital Library

[23]

L. Rizzo and L. Vicisano, "A Reliable Multicast data Distribution Protocol Based on Software FEC Techniques.'' In Proc. of HPCS '97, Greece, June 1997.

[24]

E. Schooler and J. Gemmell, "Using multicast FEC to solve the midnight madness problem," Microsoft Research Technical Report MS-TR-97-~5, September 1997.

[25]

L. Vicisano, L. Rizzo, and J. Crowcroft. "TCP-like congestion control for layered multicast data transfer." in Proc. of INFOCOM '98, San Francisco, April 1998.

[26]

M. Yajnik, J. Kurose, and D. Towsley, "Packet Loss Correlation in the MBone Multicast Network." In Proceedings of IEEE Global Internet '96, London, November 1996.

[27]

R. Yavatkar, J. Griffoen and M. Sudan, "A Reliable Dis~ semination Protocol for Interactive Collaborative Applications.'' in Proceedings of A CM Multimedia '95, San Francisco, 1995, pp. 333-344.

Digital Library

Cited By

Yang LGilad YAlizadeh MSekar VYu MSeneviratne AVeitch D(2024)Practical Rateless Set ReconciliationProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672219(595-612)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672219
Podile VKulshrestha NGoswami SDurga LRachanasree BPavan Reddy TShreya Sarojini P(2024)1The Future of Business Management with the Power of Distributed Systems and ComputingMeta Heuristic Algorithms for Advanced Distributed Systems10.1002/9781394188093.ch1(1-20)Online publication date: 8-Mar-2024
https://doi.org/10.1002/9781394188093.ch1
Luo JXu ZLin JChen CXiong R(2023)CH-MAC: Achieving Low-latency Reliable Communication via Coding and Hopping in LPWANACM Transactions on Internet of Things10.1145/36175054:4(1-25)Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1145/3617505
Show More Cited By

Index Terms

A digital fountain approach to reliable distribution of bulk data

Recommendations

A digital fountain approach to reliable distribution of bulk data

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal, fully scalable protocol for these applications that we ...
Fountain codes over fading relay channels

This paper discusses cooperative protocols based on fountain codes in a relay network. Unlike traditional fixed-rate codes, fountain codes are capable of adapting the bit rate to the channel realization blindly, i.e., without channel information at the ...
Trapping sets of fountain codes

The remarkable results of Fountain codes over the binary erasure channel (BEC) have motivated research on their practical implementation over noisy channels. Trapping sets are a phenomenon of great practical importance for certain graph codes on noisy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '98: Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication

October 1998

328 pages

ISBN:1581130031

DOI:10.1145/285237

Chairmen:
Gerald Neufeld
Univ. of British Columbia, Vancouver, B.C., Canada
,
Gary Delp
IBM Server Group
,
Jonathan Smith
Univ. of Pennsylvania, Philadelphia
,
Editor:
Martha Steenstrup
BBN Technologies, Cambridge, MA

ACM SIGCOMM Computer Communication Review Volume 28, Issue 4
Oct. 1998
311 pages
ISSN:0146-4833
DOI:10.1145/285243
Chairmen:
Gerald Neufeld
Univ. of British Columbia, Vancouver, B.C., Canada
,
Gary Delp
IBM Server Group
,
Jonathan Smith
Univ. of Pennsylvania, Philadelphia
,
Editor:
Martha Steenstrup
BBN Technologies, Cambridge, MA
Issue’s Table of Contents

Copyright © 1998 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGCOMM98

Sponsor:

SIGCOMM

SIGCOMM98: ACM SIGCOMM'98

August 31 - September 4, 1998

British Columbia, Vancouver, Canada

Acceptance Rates

SIGCOMM '98 Paper Acceptance Rate 26 of 247 submissions, 11%;

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

829
Total Citations
View Citations
3,900
Total Downloads

Downloads (Last 12 months)261
Downloads (Last 6 weeks)34

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang LGilad YAlizadeh MSekar VYu MSeneviratne AVeitch D(2024)Practical Rateless Set ReconciliationProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672219(595-612)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672219
Podile VKulshrestha NGoswami SDurga LRachanasree BPavan Reddy TShreya Sarojini P(2024)1The Future of Business Management with the Power of Distributed Systems and ComputingMeta Heuristic Algorithms for Advanced Distributed Systems10.1002/9781394188093.ch1(1-20)Online publication date: 8-Mar-2024
https://doi.org/10.1002/9781394188093.ch1
Luo JXu ZLin JChen CXiong R(2023)CH-MAC: Achieving Low-latency Reliable Communication via Coding and Hopping in LPWANACM Transactions on Internet of Things10.1145/36175054:4(1-25)Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1145/3617505
Manthamkarn VTuntoolavest USriratanapochai NChuenjit S(2022)Methods to Convert Error & Error-Erasure channel to Erasure Channel for Fountain Code Decoding2022 International Electrical Engineering Congress (iEECON)10.1109/iEECON53204.2022.9741697(1-4)Online publication date: 9-Mar-2022
https://doi.org/10.1109/iEECON53204.2022.9741697
Fanari LIradier EBilbao ICabrera RMontalban JAngueira PSeijo OVal I(2022)A Survey on FEC Techniques for Industrial Wireless CommunicationsIEEE Open Journal of the Industrial Electronics Society10.1109/OJIES.2022.32196073(674-699)Online publication date: 2022
https://doi.org/10.1109/OJIES.2022.3219607
Zeng GChen LYi BChen K(2022)Cutting Tail Latency in Commodity Datacenters with CloudburstIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796898(600-609)Online publication date: 2-May-2022
https://doi.org/10.1109/INFOCOM48880.2022.9796898
Keller J(2021)Multilevel Network Steganography in Fountain CodesProceedings of the 2021 European Interdisciplinary Cybersecurity Conference10.1145/3487405.3487420(72-76)Online publication date: 10-Nov-2021
https://dl.acm.org/doi/10.1145/3487405.3487420
Al-Dawood AAlhajhussein SYarosh S(2021)Saudi Arabian Parents' Perception of Online Marital Matchmaking TechnologiesProceedings of the ACM on Human-Computer Interaction10.1145/34329104:CSCW3(1-32)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1145/3432910
Yue JXiao M(2021)Coding for Distributed Fog Computing in Internet of Mobile ThingsIEEE Transactions on Mobile Computing10.1109/TMC.2019.296366820:4(1337-1350)Online publication date: 1-Apr-2021
https://doi.org/10.1109/TMC.2019.2963668
Chatzigeorgiou I(2021)Spark Optimization of Linear Codes for Reliable Data Delivery by Relay DronesMILCOM 2021 - 2021 IEEE Military Communications Conference (MILCOM)10.1109/MILCOM52596.2021.9653053(1-6)Online publication date: 29-Nov-2021
https://doi.org/10.1109/MILCOM52596.2021.9653053
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents