Scalable Application Layer Multicast

S. Banerjee, B. Bhattacharjee, C. Kommareddy, "Scalable Application Layer Multicast," ACM SIGCOMM Conference, (August 2002).

One line summary: This paper describes NICE, a new application-layer multicast protocol intended primarily for low-bandwidth, data streaming applications with large receiver sets.

Summary

This paper describes a new application-layer multicast protocol for low-bandwidth, data streaming applications with large receiver called NICE. The problem with network-layer multicast, as opposed to application-layer multicast, is that it has not been widely adopted by most ISPs, so much of the Internet is incapable of native multicast. In application-layer multicast, network infrastructure is left unchanged, while the multicast forwarding functionality is implemented at end-hosts. Application-layer multicast protocols are less efficient than network-layer multicast protocols because they must send the same packet over the same link. Thus, two good metrics by which to judge application-layer multicast protocols are stress and stretch. Stress is defined per link and is the count of the number of identical packets sent by a protocol over each underlying link in the network. Stretch is defined per multicast group member and is the ratio of the path length from the source to the member along the overlay used by the multicast protocol to the length of the direct unicast path.

The way the NICE protocol works is by logically arranging the multicast group members into a hierarchy. Each host in the hierarchy belongs to a layer, and the hosts in each layer are partitioned into a set of clusters, where each cluster has a cluster leader that is the graph-theoretic center the cluster. The size of each cluster is bounded between k and 3k-1 and clusters consist of hosts that are close to each other. Hosts are organized into layers according to the rule that all hosts are part of the lowest layer, L(0), then all the cluster leaders of all the clusters in layer L(i) join layer L(i+1). A host is allowed to belong to only a single cluster at any layer. If a host is present in layer L(i) it must be a cluster leader in each of layers L(0), ..., L(i-1). If a host is not present in a layer L(i) it cannot be present in any layer L(j) where j > i. Lastly, there are allowed to be at most logkN layers, and the highest layer has only a single member. The supercluster of any host x is defined as the cluster in the next highest layer to which x’s cluster leader y belongs.

The hierarchy is then used to define different overlay structures for control messages and data delivery paths. In NICE, the control topology is a clique and the data topology is a star, but it is possible to choose other topologies. The NICE protocol assumes the existence of a special host that all hosts know of called the Rendezvous Point (RP), and the RP is always the leader in the cluster at the highest layer of the hierarchy. The NICE protocol consists of three main components: (1) initial cluster assignment when a new host joins, (2) periodic cluster maintenance and refinement, and (3) recovery from leader failures. In initial cluster assignment, the joining hosts contacts all the members in the highest layer to identify the member closest to it, then contacts the lower-level cluster of that closest member to find the closest member there, and so on until the hosts finds its L(0) cluster. This process involves O(k log N) query-response pairs. In this process, some the center of some clusters may change, so a new cluster leader must be chosen. To aid in cluster maintenance and refinement, each member of a cluster sends periodic heartbeat messages to the other members of its cluster. There is also a method for cluster splitting and merging when to keep clusters within the size bound, as well as a method for refining attachments in case a host is not able to locate the closest cluster in a layer when joining. Leader failures are dealt with using a remove message if the leader is able to do a graceful-leave, or by detecting failures using the heartbeat messages and selecting a new leader.

To evaluate NICE, the authors first simulated their protocol and compared it to three other schemes: multi-unicast, native IP multicast (CBT), and the Narada application-layer multicast protocol. Their main findings are that NICE data paths have stretch comparable to Narada, the stress on links and routers is lower in NICE, especially as the multicast group size increases, the failure recovery of both schemes are comparable, and this performance is achievable with orders of magnitude lower control overhead for group sizes greater than 32. The authors also implemented the NICE protocol and tested their implementation in a wide-area testbed over a period of a month. They observe a maximum packet loss of 1% as members join and leave the group at random and an average control overhead of less than 1 Kbps for groups of size 100.

Critique

I liked this paper and it was informative to read about application-layer multicast as opposed to network-layer multicast. Even though the performance at the application-layer is, from what I can see, pretty much unavoidably worse than at the network-layer, if the authors are right that ISPs do not tend to support native multicast then that is a good enough reason to use the application-layer multicast despite the performance hit. I thought this paper did a nice job of describing how the NICE hierarchy is built but the authors could have done a better job explaining the control path and data paths used. Overall, as it appears that there are many application-layer multicast protocols that have been developed, this one seemed like as fine a choice as any to read about, though it’s hard to say without having read most of the other application-layer multicast protocol papers. It might be nice to read a survey paper like we did for DHT-based lookup protocols that summarizes the different kinds of multicast protocols and their differences.