Thursday, November 20, 2008

Scalable application layer multicast

This paper adopts an application overlay approach to multicast. The main focus of the paper is in building a suitable hierarchical structure of nodes such that the average case control overhead is O(1) and worst case is O(log N), where N is the number of nodes. (There is also a parameter to control the size of each cluster that can creep into those numbers). Care is taken to ensure that the parent of a set of nodes is about equally "far" away from them, and that when nodes join or leave, this is maintained, along with the size of a cluster of nodes (a cluster is like a set of nodes for which its parent is responsible for distributing data to), and that a tree structure is maintained (to avoid loops/data duplication).

The host joining algorithm reminds me of a tree VQ - a node finds the "right" cluster by going down the tree, and at each layer, selecting the cluster with the "closest" cluster head. However, it is not clear how the cluster leader is selected when there either changes in membership or in network conditions. It probably cannot be the cluster leader that determines when to relinquish, since it has an incentive to cheat in return for lower latency. Do the nodes do some form of voting based on the heartbeat messages? The adoption of allowing a node to immediately receive data from the current layer at which its querying is a nice touch to reduce latency of when data first starts flowing.

So this seems to be more of a framework that describes "best practices" for building a multicast tree, rather than a protocol that can be used off the shelf. What would be the best way to implement the ideas here such that a content provider can use it with minimal fuss?

I would be concerned with overhead traffic, since building and maintaing the tree require a fair amount of control coordination. The simulation results, does not quite agree with the theory that the average control overhead is constant with number of nodes. The standard deviation grows, but that is to be expected due to the worst case - in fact that should be the number to be reported. The other comparison I would have made is with an "ideal topology" for each set of conditions - i.e. when nodes leave/join, the "ideal topology" is one in which a tree builder, given central control, would have built. This would be more meaningful than IP Multicast to judge how good NICE is at maintaining good hierarchies.

No comments: