SplitStream: high-bandwidth multicast in cooperative environments

ABSTRACT

In tree-based multicast systems, a relatively small number of interior nodes carry the load of forwarding multicast messages. This works well when the interior nodes are highly-available, dedicated infrastructure routers but it poses a problem for application-level multicast in peer-to-peer systems. SplitStream addresses this problem by striping the content across a forest of interior-node-disjoint multicast trees that distributes the forwarding load among all participating peers. For example, it is possible to construct efficient SplitStream forests in which each peer contributes only as much forwarding bandwidth as it receives. Furthermore, with appropriate content encodings, SplitStream is highly robust to failures because a node failure causes the loss of a single stripe on average. We present the design and implementation of SplitStream and show experimental results obtained on an Internet testbed and via large-scale network simulation. The results show that SplitStream distributes the forwarding load among all peers and can accommodate peers with different bandwidth capacities while imposing low overhead for forest construction and maintenance.

REFERENCES

• 1: Planetlab. http://www.planet-lab.org.
• 2: E. Adar and B. Huberman. Free riding on Gnutella. First Monday, 5(10), Oct. 2000. http://firstmonday.org/issues/issue5_10/adar/index.html.
• 3: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 4: J. G. Apostolopoulos. Reliable video communication over lossy packet networks using multiple state encoding and path diversity. In Visual Communications and Image Processing, Jan. 2001.
• 5: J. G. Apostolopoulos and S. J. Wee. Unbalanced multiple description video communication using path diversity. In IEEE International Conference on Image Processing, Oct. 2001.
• 6: 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
• 7: M. Bawa, H. Deshpande, and H. Garcia-Molina. Transience of peers and streaming media. In HotNets-I, New Jersey, USA, Oct. 2002.
• 8: 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]
• 9: R. Blahut. Theory and Practice of Error Control Codes. Addison Wesley, MA, 1994.
• 10: 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
• 11: M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Exploiting network proximity in peer-to-peer overlay networks. Technical Report MSR-TR-2002-82, Microsoft Research, 2002.
• 12: M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Proximity neighbor selection in tree-based structured peer-to-peer overlays. Technical Report MSR-TR-2003-52, Microsoft Research, Aug. 2003.
• 13: M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. SCRIBE: A large-scale and decentralized application-level multicast infrastructure. IEEE JSAC, 20(8), Oct. 2002.
• 14: M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. Scalable application-level anycast for highly dynamic groups. In Networked Group Communications, Oct. 2003.
• 15: M. Castro, M. Jones, A.-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman. An evaluation of scalable application-level multicast built using peer-to-peer overlay networks. In INFOCOM'03, 2003.
• 16: 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
• 17: Yogen K. Dalal , Robert M. Metcalfe, Reverse path forwarding of broadcast packets, Communications of the ACM, v.21 n.12, p.1040-1048, Dec. 1978 [doi>10.1145/359657.359665]
• 18: Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
• 19: 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
• 20: J. Gemmell, E. Schooler, and J. Gray. Fcast multicast file distribution. IEEE Network, 14(1):58--68, Jan 2000.
• 21: R. Govindan and H. Tangmunarunkit. Heuristics for internet map discovery. In Proc. 19th IEEE INFOCOM, pages 1371--1380, Tel Aviv, Israel, March 2000. IEEE.
• 22: J. Jannotti, D. Gifford, K. Johnson, M. Kaashoek, and J. O'Toole. Overcast: Reliable multicasting with an overlay network. In Proc. OSDI 2000, San Diego, CA, 2000.
• 23: D. Kostic, A. Rodriguez, J. Albrecht, A. Bhirud, and A. Vahdat. Using random subsets to build scalable network services. In USITS'03, Mar. 2003.
• 24: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 25: R. Mahajan, M. Castro, and A. Rowstron. Controlling the cost of reliability in peer-to-peer overlays. In IPTPS'03, Feb. 2003.
• 26: P. Maymounkov and D. Mazieres. Rateless Codes and Big Downloads. In IPTPS'03, Feb. 2003.
• 27: A. Mohr, E. Riskin, and R. Ladner. Unequal loss protection: Graceful degredation of image quality over packet erasure channels through forward error correction. IEEE JSAC, 18(6):819--828, June 2000.
• 28: T. Ngan, P. Druschel, and D. S. Wallach. Enforcing fair sharing of peer-to-peer resources. In IPTPS '03, Berkeley, CA, Feb. 2003.
• 29: T. Nguyen and A. Zakhor. Distributed video streaming with forward error correction. In Packet Video Workshop, Pittsburgh, USA., 2002.
• 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: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 32: Sylvia Ratnasamy , Mark Handley , Richard M. Karp , Scott Shenker, Application-Level Multicast Using Content-Addressable Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.14-29, November 07-09, 2001
• 33: 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
• 34: S. Saroiu, P. K. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proceedings of the Multimedia Computing and Networking (MMCN), San Jose, CA, Jan. 2002.
• 35: 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
• 36: 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
• 37: H. Tangmunarunkit, R. Govindan, D. Estrin, and S. Shenker. The impact of routing policy on internet paths. In Proc. 20th IEEE INFOCOM, Alaska, USA, Apr. 2001.
• 38: E. Zegura, K. Calvert, and S. Bhattacharjee. How to model an internetwork. In INFOCOM'96, San Francisco, CA, 1996.
• 39: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001
• 40: Shelley Q. Zhuang , Ben Y. Zhao , Anthony D. Joseph , Randy H. Katz , John D. Kubiatowicz, Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.11-20, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378347]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.); Routing protocols

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.8 Performance

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

Keywords:
application-level multicast, content distribution, end-system multicast, peer-to-peer, video streaming