Informed content delivery across adaptive overlay networks

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).
3. Bloom, B. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13 (July 1970), 422--426.
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).
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.
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.
9. Chawathe, Y. Scattercast: An Architecture for Internet Broadcast Distribution as an Infrastructure Service. PhD thesis, University of California, Berkeley, December 2000.
10. Chu, Y.-H., Rao, S., and Zhang, H. A case for end system multicast. In ACM SIGMETRICS (Santa Clara, CA, June 2000).
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.
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).
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).
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.
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.
20. Merkle, R. A digital signature based on a conventional encryption function. In Advances in Cryptology (CRYPTO) (Santa Barbara, CA, August 1987).
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.
24. Rabin, M. Efficient dispersal of information for security, load balancing and fault tolerance. Journal of the ACM 38 (1989), 335--348.
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).
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.
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).
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).
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).
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.
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).

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

• Networks