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

Article

Free access

Informed content delivery across adaptive overlay networks

Authors:

Jeffrey Considine,

Michael Mitzenmacher,

Stanislav RostAuthors Info & Claims

SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications

Pages 47 - 60

https://doi.org/10.1145/633025.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

Yang JZhang YQiu ZYue YVinayak RDruschel PKaufmann AMace JFlinn JSeltzer M(2023)FIFO queues are all you need for cache evictionProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613147(130-149)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613147
Alkhatib BUdayashankar SQunaibi SAlquraan AAlfatafta MAl-Manasrah WDepoutovitch AAl-Kiswany S(2023)Partial Network PartitioningACM Transactions on Computer Systems10.1145/357619241:1-4(1-34)Online publication date: 18-Dec-2023
https://dl.acm.org/doi/10.1145/3576192
Tschudin CZhang KGherbi ABellavista P(2022)A connectionless grow-only set CRDTProceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good10.1145/3565383.3566110(25-30)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3565383.3566110
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
Proceedings of the 2002 SIGCOMM conference

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 Conferences

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

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

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 August 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGCOMM02

Sponsor:

SIGCOMM02: SIGCOMM 2002 Conference

August 19 - 23, 2002

Pennsylvania, Pittsburgh, USA

Acceptance Rates

SIGCOMM '02 Paper Acceptance Rate 25 of 300 submissions, 8%;

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

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

Yang JZhang YQiu ZYue YVinayak RDruschel PKaufmann AMace JFlinn JSeltzer M(2023)FIFO queues are all you need for cache evictionProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613147(130-149)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613147
Alkhatib BUdayashankar SQunaibi SAlquraan AAlfatafta MAl-Manasrah WDepoutovitch AAl-Kiswany S(2023)Partial Network PartitioningACM Transactions on Computer Systems10.1145/357619241:1-4(1-34)Online publication date: 18-Dec-2023
https://dl.acm.org/doi/10.1145/3576192
Tschudin CZhang KGherbi ABellavista P(2022)A connectionless grow-only set CRDTProceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good10.1145/3565383.3566110(25-30)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3565383.3566110
Parikh PMistry MKothari DKhachane S(2020)Spectral Bloom Filters for Client Side Search2020 11th IEEE Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON)10.1109/IEMCON51383.2020.9284946(0867-0875)Online publication date: 4-Nov-2020
https://doi.org/10.1109/IEMCON51383.2020.9284946
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
Yu BBai F(2018)PYRAMID: Probabilistic Content Reconciliation and Prioritization for V2V CommunicationsIEEE Transactions on Vehicular Technology10.1109/TVT.2018.281592567:7(6615-6626)Online publication date: Jul-2018
https://doi.org/10.1109/TVT.2018.2815925
Parisis GSourlas VKatsaros KChai WPavlou GPaschos GVassilaras STassiulas L(2016)Enhancing multi-source content delivery in content-centric networks with fountain codingProceedings of the 1st Workshop on Content Caching and Delivery in Wireless Networks10.1145/2836183.2836187(1-7)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1145/2836183.2836187
Ze LRuichun TYe TXin S(2016)Design of multicast protocol for underwater multimedia data transmission2016 3rd International Conference on Systems and Informatics (ICSAI)10.1109/ICSAI.2016.7811045(710-715)Online publication date: Nov-2016
https://doi.org/10.1109/ICSAI.2016.7811045
Bo Yu Bai F(2015)PYRAMID: Informed content reconciliation for vehicular peer-to-peer systems2015 IEEE Vehicular Networking Conference (VNC)10.1109/VNC.2015.7385579(212-219)Online publication date: Dec-2015
https://doi.org/10.1109/VNC.2015.7385579
Gerbet TKumar ALauradoux C(2015)The Power of Evil Choices in Bloom FiltersProceedings of the 2015 45th Annual IEEE/IFIP International Conference on Dependable Systems and Networks10.1109/DSN.2015.21(101-112)Online publication date: 22-Jun-2015
https://dl.acm.org/doi/10.1109/DSN.2015.21
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