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

article

Informed content delivery across adaptive overlay networks

Authors:

Jeffrey Considine,

Michael Mitzenmacher,

Stanislav RostAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 32, Issue 4

Pages 47 - 60

https://doi.org/10.1145/964725.633031

Published: 19 August 2002 Publication History

Abstract

Overlay networks have emerged as a powerful and highly flexible method for delivering content. We study how to optimize throughput of large transfers across richly connected, adaptive overlay networks, focusing on the potential of collaborative transfers between peers to supplement ongoing downloads. First, we make the case for an erasure-resilient encoding of the content. Using the digital fountain encoding approach, end-hosts can efficiently reconstruct the original content of size $n$ from a subset of any $n$ symbols drawn from a large universe of encoded symbols. Such an approach affords reliability and a substantial degree of application-level flexibility, as it seamlessly accommodates connection migration and parallel transfers while providing resilience to packet loss. However, since the sets of encoded symbols acquired by peers during downloads may overlap substantially, care must be taken to enable them to collaborate effectively. Our main contribution is a collection of useful algorithmic tools for efficient estimation, summarization, and approximate reconciliation of sets of symbols between pairs of collaborating peers, all of which keep message complexity and computation to a minimum. Through simulations and experiments on a prototype implementation, we demonstrate the performance benefits of our informed content delivery mechanisms and how they complement existing overlay network architectures.

References

[1]

Altavista. www.altavista.com

[2]

Andersen, D., Balakrishnan, H., Kaashoek, F., and Morris, R. Resilient overlay networks. In Proc. of ACM Symposium on Operating Systems Principles (Banff, Canada, October 2001).

Digital Library

[3]

Bloom, B. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13 (July 1970), 422--426.

Digital Library

[4]

Bohman, T., Cooper, C., and Frieze, A. Min-wise independent linear permutations. Electronic Journal of Combinatorics 7, R26 (2000).

[5]

Broder, A. On the resemblance and containment of documents. In Compression and Complexity of Sequences (SEQUENCES) (Positano, Italy, June 1997).

Digital Library

[6]

Broder, A. Z., Charikar, M., Frieze, A. M., and Mitzenmacher, M. Min-wise independent permutations. Journal of Computer and System Sciences 60, 3 (2000), 630--659.

Digital Library

[7]

Byers, J. W., Luby, M., and Mitzenmacher, M. Accessing multiple mirror sites in parallel: Using Tornado codes to speed up downloads. In Proc. of IEEE INFOCOM (March 1999), pp. 275--83.

[8]

Byers, J. W., Luby, M., Mitzenmacher, M., and Rege, A. A digital fountain approach to reliable distribution of bulk data. In Proc. of ACM SIGCOMM (Vancouver, September 1998), pp. 56--67. To appear in IEEE Journal on Selected Areas in Communications.

Digital Library

[9]

Chawathe, Y. Scattercast: An Architecture for Internet Broadcast Distribution as an Infrastructure Service. PhD thesis, University of California, Berkeley, December 2000.

Digital Library

[10]

Chu, Y.-H., Rao, S., and Zhang, H. A case for end system multicast. In ACM SIGMETRICS (Santa Clara, CA, June 2000).

Digital Library

[11]

Considine, J. Generating good degree distributions for sparse parity check codes using oracles. Tech. Rep. BUCS-TR 2001-019, Boston University, October 2001.

[12]

Fan, L., Cao, P., Almeida, J., and Broder, A. Summary cache: A scalable wide-area cache sharing protocol. IEEE/ACM Trans. on Networking 8(3) (2000), 281--293. A preliminary version appeared in Proc. of SIGCOMM '98.

Digital Library

[13]

Jannotti, J., Gifford, D., Johnson, K., Kaashoek, M., and O'Toole, J. Overcast: Reliable multicasting with an overlay network. In Proc. of USENIX Symp. on Operating Systems Design and Implementation) (San Diego, CA, October 2000).

Digital Library

[14]

Klamkin, M., and Newman, D. Extensions of the birthday surprise. Journal of Combinatorial Theory 3 (1967), 279--282.

[15]

Labovitz, C., Malan, G., and Jahanian, F. Internet routing instability. In Proc. of ACM SIGCOMM (September 1997).

Digital Library

[16]

Luby, M. Information Additive Code Generator and Decoder for Communication Systems. U.S. Patent No. 6,307,487, October 23, 2001.

[17]

Luby, M., Mitzenmacher, M., Shokrollahi, A., and Spielman, D. Efficient erasure correcting codes. IEEE Transactions on Information Theory 47(2) (2001), 569--584.

Digital Library

[18]

Macwilliams, F. J., and Sloane, N. The Theory of Error-Correcting Codes. North Holland, Amsterdam, 1977.

[19]

Mahanti, A., Eager, D. L., Vernon, M. K., and Sundaram-Stukel, D. Scalable on-demand media streaming with packet loss recovery. In Proc. of ACM SIGCOMM (August 2001), pp. 97--108.

Digital Library

[20]

Merkle, R. A digital signature based on a conventional encryption function. In Advances in Cryptology (CRYPTO) (Santa Barbara, CA, August 1987).

Digital Library

[21]

Minsky, Y., and Trachtenberg, A. Practical set reconciliation. Tech. Rep. BU ECE 2002-01, Boston University, 2002.

[22]

Minsky, Y., Trachtenberg, A., and Zippel, R. Set reconciliation with nearly optimal communication complexity. In Proc. of IEEE Int'l Symp. on Information Theory (Washington, DC, June 2001).

[23]

Mitzenmacher, M. Compressed bloom filters. In Proc. of the 20th Annual ACM Symposium on Principles of Distributed Computing (2001), pp. 144--150. To appear in IEEE/ACM Trans. on Networking.

Digital Library

[24]

Rabin, M. Efficient dispersal of information for security, load balancing and fault tolerance. Journal of the ACM 38 (1989), 335--348.

Digital Library

[25]

Ratnasamy, S., Francis, P., Handley, M., Karp, R., and Shenker, S. A scalable content-addressable network. In Proc. of ACM SIGCOMM (San Diego, CA, August 2001).

Digital Library

[26]

Rodriguez, P., and Biersack, E. W. Dynamic parallel-access to replicated content in the Internet. IEEE/ACM Transactions on Networking 10(4) (August 2002). A preliminary version appeared in Proc. of IEEE INFOCOM '00.

Digital Library

[27]

Rowstron, A., and Druschel, P. Storage management and caching in past, a large-scale, persistent peer-to-peer storage utility. In Proc. of ACM Symposium on Operating Systems Principles (Banff, Canada, October 2001).

Digital Library

[28]

Savage, S., Collins, A., Hoffman, E., Snell, J., and Anderson, T. The end-to-end effects of Internet path selection. In Proc. of ACM SIGCOMM (August 1999).

Digital Library

[29]

Stoica, I., Morris, R., Karger, D., Kaashoek, F., and Balakrishnan, H. Chord: A scalable peer-to-peer lookup service for internet applications. In Proc. of ACM SIGCOMM (San Diego, CA, August 2001).

Digital Library

[30]

Swarmcast. http://www.opencola.org/projects/swarmcast.

[31]

Vitter, J. S. Random sampling with a reservoir. ACM Trans. on Math. Software 11 (1985), 37--57.

Digital Library

[32]

Zhuang, S., Zhao, B., Joseph, A., Katz, R., and Kubiatowicz, J. Bayeux: An architecture for scalable and fault-tolerant wide area data dissemination. In Proc. of NOSSDAV '01 (Port Jefferson, NY, June 2001).

Digital Library

Cited By

Zhao YDai WWang SXi LWang SZhang F(2023)A Review of Cuckoo Filters for Privacy Protection and Their ApplicationsElectronics10.3390/electronics1213280912:13(2809)Online publication date: 25-Jun-2023
https://doi.org/10.3390/electronics12132809
Lee SByun HLim H(2023)Set Reconciliation Using Ternary and Invertible Bloom FiltersIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.323700935:11(11885-11898)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3237009
Pacífico RSilva LCoelho GSilva PVieira AVieira MCunha ÍVieira LNacif J(2020)BloomTime: space-efficient stateful tracking of time-dependent network performance metricsTelecommunications Systems10.1007/s11235-020-00653-174:2(201-223)Online publication date: 1-Jun-2020
https://dl.acm.org/doi/10.1007/s11235-020-00653-1
Show More Cited By

Index Terms

Informed content delivery across adaptive overlay networks
1. Hardware
  1. Communication hardware, interfaces and storage
2. Networks

Recommendations

Informed content delivery across adaptive overlay networks
SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications

Overlay networks have emerged as a powerful and highly flexible method for delivering content. We study how to optimize throughput of large transfers across richly connected, adaptive overlay networks, focusing on the potential of collaborative ...
Informed content delivery across adaptive overlay networks

Overlay networks have emerged as a powerful and highly flexible method for delivering content. We study how to optimize throughput of large transfers across richly connected, adaptive overlay networks, focusing on the potential of collaborative ...
Understanding overlay characteristics of a large-scale peer-to-peer IPTV system

This article presents results from our measurement and modeling efforts on the large-scale peer-to-peer (p2p) overlay graphs spanned by the PPLive system, the most popular and largest p2p IPTV (Internet Protocol Television) system today. Unlike other ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 32, Issue 4

Proceedings of the 2002 SIGCOMM conference

October 2002

332 pages

ISSN:0146-4833

DOI:10.1145/964725

Issue’s Table of Contents

SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications
August 2002
368 pages
ISBN:158113570X
DOI:10.1145/633025
Conference Chairs:
Matt Mathis
Pittsburgh Supercomputing Center
,
Peter Steenkiste
Carnegie Mellon University
,
Program Chairs:
Hari Balakrishnan
Massachusetts Institute of Technology
,
Vern Paxson
ICIR

Copyright © 2002 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 August 2002

Published in SIGCOMM-CCR Volume 32, Issue 4

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

207
Total Citations
View Citations
1,473
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)11

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao YDai WWang SXi LWang SZhang F(2023)A Review of Cuckoo Filters for Privacy Protection and Their ApplicationsElectronics10.3390/electronics1213280912:13(2809)Online publication date: 25-Jun-2023
https://doi.org/10.3390/electronics12132809
Lee SByun HLim H(2023)Set Reconciliation Using Ternary and Invertible Bloom FiltersIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.323700935:11(11885-11898)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3237009
Pacífico RSilva LCoelho GSilva PVieira AVieira MCunha ÍVieira LNacif J(2020)BloomTime: space-efficient stateful tracking of time-dependent network performance metricsTelecommunications Systems10.1007/s11235-020-00653-174:2(201-223)Online publication date: 1-Jun-2020
https://dl.acm.org/doi/10.1007/s11235-020-00653-1
Byers JLuby MMitzenmacher M(2019)A digital fountain retrospectiveACM SIGCOMM Computer Communication Review10.1145/3371934.337196049:5(82-85)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3371934.3371960
Milosavljevic NPawar SEl Rouayheb SGastpar MRamchandran K(2016)Efficient Algorithms for the Data Exchange ProblemIEEE Transactions on Information Theory10.1109/TIT.2016.252398062:4(1878-1896)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1109/TIT.2016.2523980
Shirvanimoghaddam MLi YTian SVucetic B(2013)Distributed Raptor Coding for Erasure Channels: Partially and Fully Coded CooperationIEEE Transactions on Communications10.1109/TCOMM.2013.072913.12072461:9(3576-3589)Online publication date: Sep-2013
https://doi.org/10.1109/TCOMM.2013.072913.120724
Amarilli ABen Hamouda FBourse FMorisset RNaccache DRauzy P(2012)From Rational Number Reconstruction to Set Reconciliation and File SynchronizationRevised Selected Papers of the 7th International Symposium on Trustworthy Global Computing - Volume 819110.1007/978-3-642-41157-1_1(1-18)Online publication date: 7-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-41157-1_1
Eppstein DGoodrich MUyeda FVarghese G(2011)What's the difference?ACM SIGCOMM Computer Communication Review10.1145/2043164.201846241:4(218-229)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.1145/2043164.2018462
Eppstein DGoodrich MUyeda FVarghese GKeshav SLiebeherr JByers JMogul J(2011)What's the difference?Proceedings of the ACM SIGCOMM 2011 conference10.1145/2018436.2018462(218-229)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.1145/2018436.2018462
Li JChao C(2010)An efficient P2P content distribution system based on altruistic demand and recoding disseminationIEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans10.1109/TSMCA.2010.204488140:5(1083-1093)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1109/TSMCA.2010.2044881
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents