|
 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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.
|
| |
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
|
Sally Floyd , Van Jacobson , Steve McCanne , Ching-Gung Liu , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.342-356, August 28-September 01, 1995, Cambridge, Massachusetts, United States
|
| |
6
|
J. Gemmell, "ECSRM- Erasure Correcting Scalable Reliable Multicast," Microsoft Research Technical Report MS- TR-97-20, June 1997.
|
| |
7
|
|
| |
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.
|
| |
11
|
Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi , Daniel A. Spielman , Volker Stemann, Practical loss-resilient codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.150-159, May 04-06, 1997, El Paso, Texas, United States
[doi> 10.1145/258533.258573]
|
| |
12
|
Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi, Analysis of random processes via And-Or tree evaluation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.364-373, January 25-27, 1998, San Francisco, California, United States
|
| |
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
|
Steven McCanne , Van Jacobson , Martin Vetterli, Receiver-driven layered multicast, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.117-130, August 28-30, 1996, Palo Alto, California, United States
|
| |
16
|
|
| |
17
|
|
| |
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örg Nonnenmacher , Ernst Biersack , Don Towsley, Parity-based loss recovery for reliable multicast transmission, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.289-300, September 14-18, 1997, Cannes, France
|
| |
21
|
|
| |
22
|
|
| |
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
|
Rajendra Yavatkar , James Griffoen , Madhu Sudan, A reliable dissemination protocol for interactive collaborative applications, Proceedings of the third ACM international conference on Multimedia, p.333-344, November 05-09, 1995, San Francisco, California, United States
[doi> 10.1145/217279.215288]
|
CITED BY 94
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John Byers , Michael Frumin , Gavin Horn , Michael Luby , Michael Mitzenmacher , Alex Roetter , William Shaver, FLID-DL: congestion control for layered multicast, Proceedings of NGC 2000 on Networked group communication, p.71-81, November 08-10, 2000, Palo Alto, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sergey Gorinsky , Sugat Jain , Harrick Vin , Yongguang Zhang, Robustness to inflated subscription in multicast congestion control, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
|
|
|
|
|
|
Mohamed Hefeeda , Ahsan Habib , Boyan Botev , Dongyan Xu , Bharat Bhargava, PROMISE: peer-to-peer media streaming using CollectCast, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Seung-Jong Park , Ramanuja Vedantham , Raghupathy Sivakumar , Ian F. Akyildiz, A scalable approach for reliable downstream data delivery in wireless sensor networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dejan Kostić , Adolfo Rodriguez , Jeannie Albrecht , Amin Vahdat, Bullet: high bandwidth data dissemination using an overlay mesh, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xiaosong Ma , Vincent W. Freeh , Tao Yang , Sudharshan S. Vazhkudai , Tyler A. Simon , Stephen L. Scott, Coupling prefix caching and collective downloads for remote dataset access, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
|
|
|
Shang-Ming Chang , Shiuhpyng Shieh , Warren W. Lin , Chih-Ming Hsieh, An efficient broadcast authentication scheme in wireless sensor networks, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan
|
|
|
Liqi Shi , Phillipa Sessini , Anirban Mahanti , Zongpeng Li , Derek L. Eager, Scalable streaming for heterogeneous clients, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
|
|
|
|
|
|
Dejan Kostić , Alex C. Snoeren , Amin Vahdat , Ryan Braud , Charles Killian , James W. Anderson , Jeannie Albrecht , Adolfo Rodriguez , Erik Vandekieft, High-bandwidth data dissemination for large-scale distributed systems, ACM Transactions on Computer Systems (TOCS), v.26 n.1, p.1-61, February 2008
|
|
|
|
|
|
|
|
|
|
|
|
Junning Liu , Zhen Liu , Don Towsley , Cathy H. Xia, Maximizing the data utility of a data archiving & querying system through joint coding and scheduling, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA
|
|
|
|
|
|
Zongpeng Li , Baochun Li , Dongyan Xu , Xin Zhou, iFlow: Middleware-assisted Rendezvous-based Information Access for Mobile Ad Hoc Applications, Proceedings of the 1st international conference on Mobile systems, applications and services, p.71-84, May 05-08, 2003, San Francisco, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zhu Xuqi , Zhang Lin , Liu Yu, A practical and efficient code design for distributed source coding using multilevel codes, Proceedings of the International Conference on Mobile Technology, Applications, and Systems, September 10-12, 2008, Yilan, Taiwan
|
|
|
Yunjung Yi , Jiejun Kong , Mario Gerla , Joon-Sang Park, CORA: Collaborative Opportunistic Recovery Algorithm for loss controlled, delay bounded ad hoc multicast, Computer Communications, v.31 n.15, p.3672-3682, September, 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Samer Al-Kiswany , Abdullah Gharaibeh , Elizeu Santos-Neto , George Yuan , Matei Ripeanu, StoreGPU: exploiting graphics processing units to accelerate distributed storage systems, Proceedings of the 17th international symposium on High performance distributed computing, June 23-27, 2008, Boston, MA, USA
|
|
|
|
|
|
Phillipa Gill , Liqi Shi , Anirban Mahanti , Zongpeng Li , Derek L. Eager, Scalable on-demand media streaming for heterogeneous clients, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.5 n.1, p.1-24, October 2008
|
|
|
|
|
|
|
|
|
Hakim Weatherspoon , Lakshmi Ganesh , Tudor Marian , Mahesh Balakrishnan , Ken Birman, Smoke and mirrors: reflecting files at a geographically remote location without loss of performance, Proccedings of the 7th conference on File and stroage technologies, p.211-224, February 24-27, 2009, San Francisco, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
C.2