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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Birman, K., Hayden, M., Ozkasap, O., Xiao, Z., Budiu, M., Minsky, Y.: Bimodal Multicast. TOCS 17(2), 41–88 (1999)
Bishop, M., Rao, S., Sripanidulchai, K.: Considering Priority in Overlay Multicast Protocols under Heterogeneous Environments. In: Proc. of INFOCOM (2006)
Bonald, T., Massoulié, L., Mathieu, F., Perino, D., Twigg, A.: Epidemic Live Streaming: Optimal Performance Trade-Offs. In: Proc. of SIGMETRICS (2008)
Castro, M., Druschel, P., Kermarrec, A.-M., Nandi, A., Rowstron, A., Singh, A.: SplitStream: High-Bandwidth Multicast in Cooperative Environments. In: Proc. of SOSP (2003)
Chu, Y.-H., Rao, S., Zhang, H.: A Case for End System Multicast. JSAC 20(8), 1456–1471 (2000)
Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic Algorithms for Replicated Database Maintenance. In: Proc. of PODC (1987)
Deshpande, M., Xing, B., Lazardis, I., Hore, B., Venkatasubramanian, N., Mehrotra, S.: CREW: A Gossip-based Flash-Dissemination System. In: Proc. of ICDCS (2006)
Eugster, P., Guerraoui, R., Handurukande, S., Kermarrec, A.-M., Kouznetsov, P.: Lightweight Probabilistic Broadcast. TOCS 21(4), 341–374 (2003)
Frey, D., Guerraoui, R., Kermarrec, A.-M., Monod, M., Quéma, V.: Stretching Gossip with Live Streaming. In: Proc. of DSN (2009)
Garbinato, B., Pedone, F., Schmidt, R.: An Adaptive Algorithm for Efficient Message Diffusion in Unreliable Environments. In: Proc. of DSN (2004)
Guerraoui, R., Huguenin, K., Kermarrec, A.-M., Monod, M.: On Tracking Freeriders in Gossip Protocols. In: Proc. of P2P (2009)
Hei, X., Liang, C., Liang, J., Liu, Y., Ross, K.: A Measurement Study of a Large-Scale P2P IPTV System. TMM 9(8), 1672–1687 (2007)
Jelasity, M., Montresor, A., Babaoglu, O.: Gossip-Based Aggregation in Large Dynamic Networks. TOCS 23(3), 219–252 (2005)
Jenkins, K., Hopkinson, K., Birman, K.: A Gossip Protocol for Subgroup Multicast. In: Proc. of ICDCS Workshops (2001)
Kermarrec, A.-M., Massoulié, L., Ganesh, A.: Probabilistic Reliable Dissemination in Large-Scale Systems. TPDS 14(3), 248–258 (2003)
Kyasanur, P., Choudhury, R.R., Gupta, I.: Smart Gossip: An Adaptive Gossip-based Broadcasting Service for Sensor Networks. In: Proc. of MASS (2006)
Li, B., Qu, Y., Keung, Y., Xie, S., Lin, C., Liu, J., Zhang, X.: Inside the New Coolstreaming: Principles, Measurements and Performance Implications. In: Proc. of INFOCOM (2008)
Li, H., Clement, A., Marchetti, M., Kapritsos, M., Robinson, L., Alvisi, L., Dahlin, M.: FlightPath: Obedience vs Choice in Cooperative Services. In: Proc. of OSDI (2008)
Li, H., Clement, A., Wong, E., Napper, J., Roy, I., Alvisi, L., Dahlin, M.: BAR Gossip. In: Proc. of OSDI (2006)
Liang, C., Guo, Y., Liu, Y.: Is Random Scheduling Sufficient in P2P Video Streaming? In: Proc. of ICDCS (2008)
Ma, L., Ooi, W.: Congestion Control in Distributed Media Streaming. In: Proc. of INFOCOM (2007)
Magharei, N., Rejaie, R.: PRIME: Peer-to-Peer Receiver-drIven MEsh-based Streaming. In: Proc. of INFOCOM (2007)
Pai, V., Kumar, K., Tamilmani, K., Sambamurthy, V., Mohr, A.: Chainsaw: Eliminating Trees from Overlay Multicast. In: Castro, M., van Renesse, R. (eds.) IPTPS 2005. LNCS, vol. 3640, pp. 127–140. Springer, Heidelberg (2005)
Picconi, F., Massoulié, L.: Is There a Future for Mesh-Based live Video Streaming? In: Proc. of P2P (2008)
PPLive, http://www.pplive.com
Spring, N., Peterson, L., Bavier, A., Pai, V.: Using Planetlab for Network Research: Myths, Realities, and Best Practices. OSR 40(1), 17–24 (2006)
Sung, Y.-W., Bishop, M., Rao, S.: Enabling Contribution Awareness in an Overlay Broadcasting System. CCR 36(4), 411–422 (2006)
van Renesse, R., Birman, K., Vogels, W.: Astrolabe: A Robust and Scalable Technology for Distributed System Monitoring, Management, and Data Mining. TOCS 21(2), 164–206 (2003)
Venkataraman, V., Yoshida, K., Francis, P.: Chunkyspread: Heterogeneous Unstructured Tree-Based Peer to Peer Multicast. In: Proc. of ICNP (2006)
Vishnumurthy, V., Francis, P.: On Heterogeneous Overlay Construction and Random Node Selection in Unstructured P2P Networks. In: Proc. of INFOCOM (2006)
Wang, W., Jin, C., Jamin, S.: Network Overlay Construction under Limited End-to-End Reachability. In: Proc. of INFOCOM (2005)
Widmer, J., Handley, M.: Extending Equation-based Congestion Control to Multicast Applications. In: Proc. of SIGCOMM (2001)
Zattoo, http://www.zattoo.com
Zhang, B., Wang, W., Jamin, S., Massey, D., Zhang, L.: Universal IP multicast delivery. Computer Networks 50(6), 781–806 (2006)
Zhang, M., Zhang, Q., Sun, L., Yang, S.: Understanding the Power of Pull-Based Streaming Protocol: Can We Do Better? JSAC 25(9), 1678–1694 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 IFIP International Federation for Information Processing
About this paper
Cite this paper
Frey, D. et al. (2009). Heterogeneous Gossip. In: Bacon, J.M., Cooper, B.F. (eds) Middleware 2009. Middleware 2009. Lecture Notes in Computer Science, vol 5896. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10445-9_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-10445-9_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10444-2
Online ISBN: 978-3-642-10445-9
eBook Packages: Computer ScienceComputer Science (R0)