Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present and analyze techniques to efficiently solve the partial content distribution problem-distributing a logical data set to receivers which individually desire only subsets of the total data. This is a more general and fundamentally different problem than traditional whole-file content distribution; providing new challenges and new optimization opportunities. It supports a wider variety of use models, e.g., striped file transfer, scatter/gather, or distributed editing.

This work develops new metadata management and transfer scheduling techniques providing good results on high performance networks. Distributed applicationsin such systems tend to have data requirements more complicated than just total overlap at every node: transfers desired differ dramatically from whole-file content distribution. Traditional approaches perform poorly in such cases. We provide empirical data exhibiting these limitations, evaluate a new BitTorrent-based implementation of our ideas, and show order of magnitude improvements in bandwidth and latency.

REFERENCES

• 1: Akamai Technologies Inc. Akamai content distribution system. http://www.akamai.com/.
• 2: B. Cohen. The BitTorrent file sharing protocol. http://bittorrent.com.
• 3: Cluster File Systems Inc. Lustre: scalable, secure, robust, highly-available cluster file system. http://www.lustre.org, 2006.
• 4: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 5: John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.56-67, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 6: L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
• 7: Randall Dougherty , Chris Freiling , Kenneth Zeger, Unachievability of network coding capacity, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2365-2372, June 2006 [doi>10.1109/TIT.2006.874405]
• 8: Sally Floyd , Van Jacobson , Ching-Gung Liu , Steven McCanne , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.784-803, Dec. 1997 [doi>10.1109/90.650139]
• 9: Bill Allcock , Joe Bester , John Bresnahan , Ann L. Chervenak , Ian Foster , Carl Kesselman , Sam Meder , Veronika Nefedova , Darcy Quesnel , Steven Tuecke, Data management and transfer in high-performance computational grid environments, Parallel Computing, v.28 n.5, p.749-771, May 2002 [doi>10.1016/S0167-8191(02)00094-7]
• 10: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 11: R. H. Inc. Global file system. http://www.redhat.com/software/rha/gfs/.
• 12: J. Hoffman a.k.a. TheShad0w. BitTornado. http://www.bittornado.com/.
• 13: R. Jain, D. Chiu, and W. Hawe. A quantitative measure of fairness and discrimination for resource allocation in shared systems. Technical Report TR-301, Digital Equipment Corporation, Littleton, MA, 1984.
• 14: 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
• 15: Jae-Yong Lee , Alan Sussman, High Performance Communication between Parallel Programs, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 4, p.177.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.243]
• 16: S.-Y. Li, R. W. Yeun, and N. Cai. Linear network coding. IEEE Transactions on Information Theory, 49(2):371--381, February 2003.
• 17: A. Parker. P2P in 2005. Technical report, Cache Logic, 2005. http://www.cachelogic.com/research/p2p2005.php.
• 18: M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, and A. Venkataramani. Do incentives build robustness in BitTorrent? In USENIX Symposium on Networked Systems Design and Implementation (NSDI2007), April 2007.
• 19: Luigi Rizzo, Dummynet: a simple approach to the evaluation of network protocols, ACM SIGCOMM Computer Communication Review, v.27 n.1, p.31-41, Jan. 1997 [doi>10.1145/251007.251012]
• 20: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 21: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 22: Various. ns, the network simulator, version 2.1b7. http://www.isi.edu/nsnam/ns/.
• 23: E. Weigle , A. A. Chien, The Composite Endpoint Protocol (CEP): scalable endpoints for terabit flows, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.1126-1134, May 09-12, 2005
• 24: Wikipedia. Comparison of BitTorrent software. http://en.wikipedia.org/wiki/ComparisonofBitTorrentsoftware.
• 25: Joe Shang-chieh Wu , Alan Sussman, Flexible Control of Data Transfers between Parallel Programs, Proceedings of the Fifth IEEE/ACM International Workshop on Grid Computing, p.226-234, November 08-08, 2004 [doi>10.1109/GRID.2004.31]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
CEP, content distribution, high performance networks