Heterogeneous gossip

ABSTRACT

Gossip-based information dissemination protocols are considered easy to deploy, scalable and resilient to network dynamics. Load-balancing is inherent in these protocols as the dissemination work is evenly spread among all nodes. Yet, large-scale distributed systems are usually heterogeneous with respect to network capabilities such as bandwidth. In practice, a blind load-balancing strategy might significantly hamper the performance of the gossip dissemination.

This paper presents HEAP, HEterogeneity-Aware gossip Protocol, where nodes dynamically adapt their contribution to the gossip dissemination according to their bandwidth capabilities. Using a continuous, itself gossip-based, approximation of relative bandwidth capabilities, HEAP dynamically leverages the most capable nodes by increasing their fanout, while decreasing by the same proportion that of less capable nodes. HEAP preserves the simple and proactive (churn adaptation) nature of gossip, while significantly improving its effectiveness. We extensively evaluate HEAP in the context of a video streaming application on a testbed of 270 PlanetLab nodes. Our results show that HEAP significantly improves the quality of the streaming over standard homogeneous gossip protocols, especially when the stream rate is close to the average available bandwidth.

References

1. K. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky. Bimodal Multicast. TOCS, 17(2):41--88, 1999.
2. M. Bishop, S. Rao, and K. Sripanidulchai. Considering Priority in Overlay Multicast Protocols under Heterogeneous Environments. In Proc. of INFOCOM, 2006.
3. T. Bonald, L. Massoulié, F. Mathieu, D. Perino, and A. Twigg. Epidemic Live Streaming: Optimal Performance Trade-Offs. In Proc. of SIGMETRICS, 2008.
4. M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. SplitStream: High-Bandwidth Multicast in Cooperative Environments. In Proc. of SOSP, 2003.
5. Y.-H. Chu, S. Rao, and H. Zhang. A Case for End System Multicast. JSAC, 20(8):1456--1471, 2000.
6. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic Algorithms for Replicated Database Maintenance. In Proc. of PODC, 1987.
7. M. Deshpande, B. Xing, I. Lazardis, B. Hore, N. Venkatasubramanian, and S. Mehrotra. CREW: A Gossip-based Flash-Dissemination System. In Proc. of ICDCS, 2006.
8. P. Eugster, R. Guerraoui, S. Handurukande, A.-M. Kermarrec, and P. Kouznetsov. Lightweight Probabilistic Broadcast. TOCS, 21(4):341--374, 2003.
9. D. Frey, R. Guerraoui, A.-M. Kermarrec, M. Monod, and V. Quéma. Stretching Gossip with Live Streaming. In Proc. of DSN, 2009.
10. B. Garbinato, F. Pedone, and R. Schmidt. An Adaptive Algorithm for Efficient Message Diffusion in Unreliable Environments. In Proc. of DSN, 2004.
11. R. Guerraoui, K. Huguenin, A.-M. Kermarrec, and M. Monod. On Tracking Freeriders in Gossip Protocols. In Proc. of P2P (to appear), 2009.
12. X. Hei, C. Liang, J. Liang, Y. Liu, and K. Ross. A Measurement Study of a Large-Scale P2P IPTV System. TMM, 9(8):1672--1687, 2007.
13. M. Jelasity, A. Montresor, and O. Babaoglu. Gossip-Based Aggregation in Large Dynamic Networks. TOCS, 23(3):219--252, 2005.
14. K. Jenkins, K. Hopkinson, and K. Birman. A Gossip Protocol for Subgroup Multicast. In Proc. of ICDCS Workshops, 2001.
15. A.-M. Kermarrec, L. Massoulié, and A. Ganesh. Probabilistic Reliable Dissemination in Large-Scale Systems. TPDS, 14(3):248--258, 2003.
16. P. Kyasanur, R. R. Choudhury, and I. Gupta. Smart Gossip: An Adaptive Gossip-based Broadcasting Service for Sensor Networks. In Proc. of MASS, 2006.
17. B. Li, Y. Qu, Y. Keung, S. Xie, C. Lin, J. Liu, and X. Zhang. Inside the New Coolstreaming: Principles, Measurements and Performance Implications. In Proc. of INFOCOM, 2008.
18. H. Li, A. Clement, M. Marchetti, M. Kapritsos, L. Robinson, L. Alvisi, and M. Dahlin. FlightPath: Obedience vs Choice in Cooperative Services. In Proc. of OSDI, 2008.
19. H. Li, A. Clement, E. Wong, J. Napper, I. Roy, L. Alvisi, and M. Dahlin. BAR Gossip. In Proc. of OSDI, 2006.
20. C. Liang, Y. Guo, and Y. Liu. Is Random Scheduling Sufficient in P2P Video Streaming? In Proc. of ICDCS, 2008.
21. L. Ma and W. Ooi. Congestion Control in Distributed Media Streaming. In Proc. of INFOCOM, 2007.
22. N. Magharei and R. Rejaie. PRIME: Peer-to-Peer Receiver-drIven MEsh-based Streaming. In Proc. of INFOCOM, 2007.
23. V. Pai, K. Kumar, K. Tamilmani, V. Sambamurthy, and A. Mohr. Chainsaw: Eliminating Trees from Overlay Multicast. In Proc. of IPTPS, 2005.
24. F. Picconi and L. Massoulié. Is There a Future for Mesh-Based live Video Streaming? In Proc. of P2P, 2008.
25. PPLive. http://www.pplive.com.
26. N. Spring, L. Peterson, A. Bavier, and V. Pai. Using Planetlab for Network Research: Myths, Realities, and Best Practices. OSR, 40(1):17--24, 2006.
27. Y.-W. Sung, M. Bishop, and S. Rao. Enabling Contribution Awareness in an Overlay Broadcasting System. CCR, 36(4):411--422, 2006.
28. R. van Renesse, K. Birman, and W. Vogels. Astrolabe: A Robust and Scalable Technology for Distributed System Monitoring, Management, and Data Mining. TOCS, 21(2):164--206, 2003.
29. V. Venkataraman, K. Yoshida, and P. Francis. Chunkyspread: Heterogeneous Unstructured Tree-Based Peer to Peer Multicast. In Proc. of ICNP, 2006.
30. V. Vishnumurthy and P. Francis. On Heterogeneous Overlay Construction and Random Node Selection in Unstructured P2P Networks. In Proc. of INFOCOM, 2006.
31. W. Wang, C. Jin, and S. Jamin. Network Overlay Construction under Limited End-to-End Reachability. In Proc. of INFOCOM, 2005.
32. J. Widmer and M. Handley. Extending Equation-based Congestion Control to Multicast Applications. In Proc. of SIGCOMM, 2001.
33. Zattoo. http://www.zattoo.com.
34. B. Zhang, W. Wang, S. Jamin, D. Massey, and L. Zhang. Universal IP multicast delivery. Computer Networks, 50(6):781--806, 2006.
35. M. Zhang, Q. Zhang, L. Sun, and S. Yang. Understanding the Power of Pull-Based Streaming Protocol: Can We Do Better? JSAC, 25(9):1678--1694, 2007.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network protocols

    • Network layer protocols

      • Routing protocols

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications