Bullet: high bandwidth data dissemination using an overlay mesh

ABSTRACT

In recent years, overlay networks have become an effective alternative to IP multicast for efficient point to multipoint communication across the Internet. Typically, nodes self-organize with the goal of forming an efficient overlay tree, one that meets performance targets without placing undue burden on the underlying network. In this paper, we target high-bandwidth data distribution from a single source to a large number of receivers. Applications include large-file transfers and real-time multimedia streaming. For these applications, we argue that an overlay mesh, rather than a tree, can deliver fundamentally higher bandwidth and reliability relative to typical tree structures. This paper presents Bullet, a scalable and distributed algorithm that enables nodes spread across the Internet to self-organize into a high bandwidth overlay mesh. We construct Bullet around the insight that data should be distributed in a disjoint manner to strategic points in the network. Individual Bullet receivers are then responsible for locating and retrieving the data from multiple points in parallel.Key contributions of this work include: i) an algorithm that sends data to different points in the overlay such that any data object is equally likely to appear at any node, ii) a scalable and decentralized algorithm that allows nodes to locate and recover missing data items, and iii) a complete implementation and evaluation of Bullet running across the Internet and in a large-scale emulation environment reveals up to a factor two bandwidth improvements under a variety of circumstances. In addition, we find that, relative to tree-based solutions, Bullet reduces the need to perform expensive bandwidth probing. In a tree, it is critical that a node's parent delivers a high rate of application data to each child. In Bullet however, nodes simultaneously receive data from multiple sources in parallel, making it less important to locate any single source capable of sustaining a high transmission rate.

REFERENCES

• 1: Suman Banerjee , Bobby Bhattacharjee , Christopher Kommareddy, Scalable application layer multicast, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 2: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 3: Bittorrent. http://bitconjurer.org/BitTorrent.
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 6: John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 7: 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
• 8: Ken Calvert, Matt Doar, and Ellen~W. Zegura. Modeling Internet Topology. IEEE Communications Magazine, June 1997.
• 9: Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 10: Hyunseok Chang , Ramesh Govindan , Sugih Jamin , Scott J. Shenker , Walter Willinger, Towards capturing representative AS-level Internet topologies, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 11: Ludmila Cherkasova and Jangwon Lee. FastReplica: Efficient Large File Distribution within Content Delivery Networks. In 4th USENIX Symposium on Internet Technologies and Systems, March 2003.
• 12: Reuven Cohen and Gideon Kaempfer. A Unicast-based Approach for Streaming Multicast. In INFOCOM, pages 440--448, 2001.
• 13: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 14: Patrick Th. Eugster , Rachid Guerraoui , S. B. Handurukande , Petr Kouznetsov , Anne-Marie Kermarrec, Lightweight Probabilistic Broadcast, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.443-452, July 01-04, 2001
• 15: Sally Floyd , Mark Handley , Jitendra Padhye , Jörg Widmer, Equation-based congestion control for unicast applications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.43-56, August 28-September 01, 2000, Stockholm, Sweden
• 16: 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]
• 17: Vivek K Goyal. Multiple Description Coding: Compression Meets the Network. IEEE Signal Processing Mag., pages 74--93, May 2001.
• 18: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 19: Yang Chu , Sanjay Rao , Srinivasan Seshan , Hui Zhang, Enabling conferencing applications on the internet using an overlay muilticast architecture, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.55-67, August 2001, San Diego, California, United States
• 20: Manish Jain , Constantinos Dovrolis, End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughput, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 21: John Jannotti, David K. Gifford, Kirk L. Johnson, M. Frans Kaashoek, and Jr. James W. O'Toole. Overcast: Reliable Multicasting with an Overlay Network. In Proceedings of Operating Systems Design and Implementation (OSDI), October 2000.
• 22: Kazaa media desktop. http://www.kazaa.com.
• 23: Min Sik Kim, Simon S. Lam, and Dong-Young Lee. Optimal Distribution Tree for Internet Streaming Media. Technical Report TR-02-48, Department of Computer Sciences, University of Texas at Austin, September 2002.
• 24: Dejan Kostić, Adolfo Rodriguez, Jeannie Albrecht, Abhijeet Bhirud, and Amin Vahdat. Using Random Subsets to Build Scalable Network Services. In Proceedings of the USENIX Symposium on Internet Technologies and Systems, March 2003.
• 25: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 26: Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi , Daniel A. Spielman , Volker Stemann, Practical loss-resilient codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.150-159, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258573]
• 27: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 28: Venkata N. Padmanabhan, Lili Qiu, and Helen J. Wang. Server-based Inference of Internet Link Lossiness. In Proceedings of the IEEE Infocom, San Francisco, CA, USA, 2003.
• 29: Venkata N. Padmanabhan , Helen J. Wang , Philip A. Chou, Resilient Peer-to-Peer Streaming, Proceedings of the 11th IEEE International Conference on Network Protocols, p.16, November 04-07, 2003
• 30: Venkata N. Padmanabhan , Helen J. Wang , Philip A. Chou , Kunwadee Sripanidkulchai, Distributing streaming media content using cooperative networking, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507695]
• 31: Larry Peterson, Tom Anderson, David Culler, and Timothy Roscoe. A Blueprint for Introducing Disruptive Technology into the Internet. In Proceedings of ACM HotNets-I, October 2002.
• 32: R. C. Prim. Shortest Connection Networks and Some Generalizations. In Bell Systems Technical Journal, pages 1389--1401, November 1957.
• 33: Adolfo Rodriguez, Sooraj Bhat, Charles Killian, Dejan Kostić, and Amin Vahdat. MACEDON: Methodology for Automatically Creating, Evaluating, and Designing Overlay Networks. Technical Report CS-2003-09, Duke University, July 2003.
• 34: Antony I. T. Rowstron , Anne-Marie Kermarrec , Miguel Castro , Peter Druschel, SCRIBE: The Design of a Large-Scale Event Notification Infrastructure, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.30-43, November 07-09, 2001
• 35: Stefan Savage. Sting: A TCP-based Network Measurement Tool. In Proceedings of the 2nd USENIX Symposium on Internet Technologies and Systems (USITS-99), pages 71--80, Berkeley, CA, October 11--14 1999. USENIX Association.
• 36: Alex C. Snoeren , Kenneth Conley , David K. Gifford, Mesh-based content routing using XML, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 37: Amin Vahdat , Ken Yocum , Kevin Walsh , Priya Mahadevan , Dejan Kostić , Jeff Chase , David Becker, Scalability and accuracy in a large-scale network emulator, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060315]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications

General Terms:
Experimentation, Management, Performance

Keywords:
bandwidth, overlays, peer-to-peer