MOB: zero-configuration high-throughput multicasting for grid applications

ABSTRACT

Grid applications often need to distribute large amounts of data efficiently from one cluster to multiple others (multicast). Existing methods usually arrange nodes in optimized tree structures, based on external network monitoring data. This dependence on monitoring data, however, severely impacts both ease of deployment and adaptivity to dynamically changing network conditions.

In this paper, we present Multicast Optimizing Bandwidth (MOB), a high-throughput multicast approach, inspired by the BitTorrent protocol. With MOB, data transfers are initiated by the receivers that try to steal data from peer clusters. Instead of using potentially outdated monitoring data, MOB automatically adapts to the currently achievable bandwidth ratios.

Our experimental evaluation compares MOB to both the BitTorrent protocol and to our previous approach, Balanced Multicasting, the latter optimizing multicast trees based on external monitoring data. We show that MOB outperforms the BitTorrent protocol. MOB is competitive with Balanced Multicasting as long as the network bandwidth remains stable. With dynamically changing bandwith, MOB outperforms Balanced Multicasting by wide margins.

REFERENCES

• 1: O. Beaumont , L. Marchal , Y. Robert, Broadcast Trees for Heterogeneous Platforms, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.80.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.131]
• 2: Ruchir Bindal , Pei Cao , William Chan , Jan Medved , George Suwala , Tony Bates , Amy Zhang, Improving Traffic Locality in BitTorrent via Biased Neighbor Selection, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.66, July 04-07, 2006 [doi>10.1109/ICDCS.2006.48]
• 3: 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
• 4: B. Cohen. Incentives build robustness in BitTorrent. In Proceedings of Workshop on Economics of Peer-to-Peer Systems, Berkeley, CA, USA, May 2003. http://www.bittorrent.org/bittorrentecon.pdf.
• 5: R. Cohen and G. Kaempfer. A Unicast-based Approach for Streaming Multicast. In 20th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM 2001), pages 440--448, Anchorage, AK, USA, April 22-26 2001.
• 6: Yi Cui , Baochun Li , Klara Nahrstedt, On achieving optimized capacity utilization in application overlay networks with multiple competing sessions, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007937]
• 7: Y. Cui, Y. Xue, and K. Nahrstedt. Max-min Overlay Multicast: Rate Allocation and Tree Construction. In 12th IEEE International Workshop on Quality of Service (IwQoS '04), Montreal, Canada, June 7-9 2004.
• 8: Linux Advanced Routing and Traffic Control. http://lartc.org/.
• 9: The Distributed ASCI Supercomputer 2. http://www.cs.vu.nl/das2/, 2002.
• 10: The Distributed ASCI Supercomputer 3. http://www.cs.vu.nl/das3/, 2006.
• 11: Mathijs den Burger , Thilo Kielmann , Henri E. Bal, Balanced Multicasting: High-throughput Communication for Grid Applications, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.46, November 12-18, 2005 [doi>10.1109/SC.2005.15]
• 12: M. Devera. HTB Linux queuing discipline manual - user guide. http://luxik.cdi.cz/~devik/qos/htb/userg.pdf.
• 13: C. Dovrolis, P. Ramanathan, and D. Moore. What Do Packet Dispersion Techniques Measure? In 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), Anchorage, AK, USA, April 22--26 2001.
• 14: Antonio Plaza , David Valencia , Javier Plaza , Pablo Martinez, Commodity cluster-based parallel processing of hyperspectral imagery, Journal of Parallel and Distributed Computing, v.66 n.3, p.345-358, March 2006 [doi>10.1016/j.jpdc.2005.10.001]
• 15: T. Gross, B. Lowekamp, R. Karrer, N. Miller, and P. Steenkiste. Design, Implementation and Evaluation of the Remos Network. Journal of Grid Computing, 1(1):75--93, May 2003.
• 16: S. Hemminger. Network Emulation with NetEm. Linux Conf Au, April 2005.
• 17: R. Izmailov, S. Ganguly, and N. Tu. Fast Parallel File Replication in Data Grid. In Future of Grid Data Environments workshop (GGF-10), Berlin, Germany, March 2004.
• 18: Exploiting Hierarchy in Parallel Computer Networks to Optimize Collective Operation Performance, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.377, May 01-05, 2000
• 19: Thilo Kielmann , Henri E. Bal , Sergei Gorlatch , Kees Verstoep , Rutger F.H. Hofman, Network performance-aware collective communication for clustered wide-area systems, Parallel Computing, v.27 n.11, p.1431-1456, October 2001 [doi>10.1016/S0167-8191(01)00098-9]
• 20: Thilo Kielmann , Rutger F. H. Hofman , Henri E. Bal , Aske Plaat , Raoul A. F. Bhoedjang, MagPIe: MPI's collective communication operations for clustered wide area systems, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.131-140, May 04-06, 1999, Atlanta, Georgia, United States
• 21: Min Sik Kim , Simon S. Lam , Dong-Young Lee, Optimal Distribution Tree for Internet Streaming Media, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.116, May 19-22, 2003
• 22: B. Lowekamp, B. Tierney, L. Cottrell, R. Hughes-Jones, T. Kielmann, and M. Swany. A Hierarchy of Network Performance Characteristics for Grid Applications and Services. Proposed Recommendation GFD-R-P.023, Global Grid Forum, 2004.
• 23: Jason Maassen , Henri E. Bal, Smartsockets: solving the connectivity problems in grid computing, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA [doi>10.1145/1272366.1272368]
• 24: J. Maassen, R. V. Nieuwpoort, T. Kielmann, and K. Verstoep. Middleware Adaptation with the Delphoi Service. In AGridM 2004, Workshop on Adaptive Grid Middleware, Antibes Juan-les-Pins, France, September 2004.
• 25: J. A. Pouwelse, P. Garbacki, J. Wangand, A. Bakker, J. Yang, A. Iosup, D. Epema, M.Reinders, M. R. van Steen, and H. J. Sips. Tribler: A social-based based peer to peer system. In 5th Int'l Workshop on Peer-to-Peer Systems (IPTPS), Santa Barbara, CA, USA, February 27--28 2006.
• 26: V. Ribeiro, R. Reidi, R. Baraniuk, J. Navratil, and L. Cottrel. PathChirp: Efficient Available Bandwidth Estimation for Network Paths. In Passive and Active Measurement workshop (PAM 2003), La Jolla, CA, USA, April 6--8 2003.
• 27: F. J. Seinstra, J. M. Geusebroek, D. Koelma, C. G. M. Snoek, M. Worring, and A. W. M. Smeulders. High-Performance Distributed Image and Video Content Analysis with Parallel-Horus.IEEE Multimedia, 2007. to appear.
• 28: Rob V. van Nieuwpoort , Jason Maassen , Gosia Wrzesińska , Rutger F. H. Hofman , Ceriel J. H. Jacobs , Thilo Kielmann , Henri E. Bal, Ibis: a flexible and efficient Java-based Grid programming environment: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.7-8, p.1079-1107, June 2005 [doi>10.1002/cpe.v17:7/8]
• 29: (R) Efficient Reliable Multicast on MYRINET, Proceedings of the Proceedings of the 1996 International Conference on Parallel Processing, p.156, August 12-16, 1996
• 30: Rich Wolski, Experiences with predicting resource performance on-line in computational grid settings, ACM SIGMETRICS Performance Evaluation Review, v.30 n.4, March 2003 [doi>10.1145/773056.773064]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bandwidth adaptation, cluster computing, peer-to-peer