ASAP – As Scalable As Possible

Group Scalability in Distributed Systems

We address shortcomings of two important group communication paradigms, IP Multicast and gossip based message dissemination, both of which have scalability issues when the number of groups grows.

First, we propose a transparent and backward-compatible layer called Dr. Multicast to allow data center administrators to enable IPMC for large numbers of groups without causing scalability issues. Dr.Multicast optimizes IPMC resources by grouping together similar groups in terms of membership to minimize redundant transmissions as well as the cost of filtering unwanted messages.

Second, we argue that when nodes belong to multiple groups, gossip based communication loses its appealing property of using a fixed amount of bandwidth. We propose a platform called GO (Gossip Objects) that bounds each node’s bandwidth use to a customizable limit, prohibiting applications from joining groups that would cause the limit to be exceeded. We make the observation that gossip rumors tend to be small, and propose a utility-based heuristic to stack rumors into packets to optimize delivery speed, with rumors sometimes travelling through indirect paths.

Features joint work with Hussam Abu-Libdeh, Mahesh Balakrishnan, Ken Birman, Robert Burgess, Gregory Chockler, Qi Huang, Jure Leskovec, Haoyuan Li, Deepak Nataraj and Yoav Tock.

Seminar Ymir VIGFUSSON (IBM Research, Haifa) – Thursday 19 November, 2pm
INRIA Rennes – Bretagne Atlantique, Salle Sardaigne

Tags: Gossip

Gossip-Based Video Streaming: Managing Heterogeneous Bandwidth

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. As such, gossip’s blind load balancing may significantly hamper the performance of the data dissemination. This talk presents HEAP, an  HEterogeneity-Aware gossip Protocol, where nodes dynamically adapt their contribution to the gossip dissemination according to their bandwidth capabilities. HEAP dynamically leverages the most capable nodes by increasing their fanouts, while decreasing by the same proportion those of less capable nodes. This preserves the simple and proactive nature of gossip, while significantly improving its effectiveness. Experiments in the context of a video streaming application on a PlanetLab testbed show that HEAP significantly improves the perceived quality over standard homogeneous gossip protocols, especially when the stream rate is close to the average available bandwidth.

Seminar by Davide Frey – Tuesday 10 November, 3pm
ENS Cachan, Antenne de Bretagne, Salle du conseil

Tags: Gossip