Informed content delivery across adaptive overlay networks

By John W. Byers, Jeffrey Considine, Michael M. Mitzenmacher, Stanislav Rost. IEEE/ACM Transactions on Networking, 2002

378 citations recorded by the source corpus.

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 encoding 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 encoding 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 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.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/1927958be3b360d26f8673a75718698e2303ae33

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

SplitStream: high-bandwidth multicast in cooperative environments (2003, background): “In [10, 26], algorithms and content encodings are described that enable parallel downloads and increase packet loss resilience in richly connected, collaborative overlay networks by exploiting downloads from multiple peers.”
Bullet: high bandwidth data dissemination using an overlay mesh (2003, methodology): “A number of techniques have been proposed to recover from losses and hence improve the available bandwidth in an overlay tree [2, 6].”
Erasure-coding based routing for opportunistic networks (2005, background): “Erasure codes have recently been discussed and applied to many network applications, including achieving efficient distribution of bulk data in overlay networks [1] and P2P networks [10], coping with unreliable transmissions in wireless sensor networks [13], and achieving reliability in large-scale ”
Network Applications of Bloom Filters: A Survey (2004, methodology): “Reynolds and Vahdat use Bloom ﬁ lters in a similar fashion as [Byers et al. 02a], except that their goal is to ﬁ nd the set intersection instead of the set di ﬀ erence [Reynolds and Vahdat 03].”
Analyzing and Improving a BitTorrent Networks Performance Mechanisms (2006, methodology): “More details can be found in [7].”
A digital fountain approach to asynchronous reliable multicast (2002, methodology): “Related applications which we have considered include downloading content in parallel from multiple mirror sites [7] and cont nt delivery in overlay networks such as peer-to-peer networks [5].”
Simple Load Balancing for Distributed Hash Tables (2003, background): “Such replication can maintain good load balancing while also allowing additional functionality, such as parallel downloading from multiple sources [3, 2].”
Network coding for large scale content distribution (2005, methodology): “To overcome this problem [16] proposes techniques to efficiently reconciliate encoded content among different nodes using sketches, bloom filters, etc.”
On-the-fly verification of rateless erasure codes for efficient content distribution (2004, background): “In decentralized P2P-CDNs, such a trusted party might not exist.”
Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks (Awarded Best Paper!) (2004, neutral): “The second is epidemic and gossiping algorithms for maintaining data consistency in distributed systems [2, 4, 5].”
A survey of autonomic communications (2006, background): “These are already influencing the next generation of algorithms for peer-to-peer content distribution [Byers et al. 2004; Gkantsidis and Rodriguez 2005].”
Survey of research towards robust peer-to-peer networks: Search methods (2006, background): “Storage Consistency & Replication [101-112] Eventual consistency Trade-offs Distribution [39, 42, 90, 92, 113-131] Epidemics, Bloom Filters Fault Tolerance [40, 105, 132-139] Erasure Coding Byzantine Agreement Locality [24, 43, 47, 140-160] Load Balancing [37, 86, 100, 107, 151, 161-171]”
Theory and Practice of Bloom Filters for Distributed Systems (2012, neutral): “filter-based structures have been developed [73], [74].”
LT codes (2002, background): “…robust distributed storage, delivery of streaming content, delivery of content to mobile clients in wireless networks, peer-to-peer applications [3], delivery of content along multiple paths to ensure resiliency to network disruptions [24], and a number of other applications too numerous to…”
Growth codes: maximizing sensor network data persistence (2006, methodology): “optimize large transfers in [14] using codes by having the source re-code data as it learns from receivers what information they still require.”