NICE

Note: I lost internet in between starting and finishing this post. I've had internet for a minute or two right now.

This paper essentially presents a protocol for accomplishing multicast in which there is a designated sender, and all other nodes are receivers; in other words, they are subscribing to the data being sent.

To accomplish this in an efficient manner, the authors suggest a dynamically constructed tree of bounded degree. Given a constant k, they wish to bound the degree by k and 3k-1. This means that it is always possible to split a node that is too large, and it is always possible to merge two nodes if one has become too small (if their sum exceeds 3k-1, split the large one, and then merge with either of the resulting halves). This is essentially a concept stolen from B-trees.

The basic concept behind multicast in this setup is that messages propagate from the root to their leaves. Each new node joins at the lowest level of the tree. Each group of nodes in the tree has a leader, which is not only a member of the lowest level, but also a member of the level one above. This continues recursively until there is only 1 root. The leader of a group is its geographic center; this enables a new node to find a group in O(log(n)) time by querying nodes that are successively lower in the hierarchy for their list of children. With each query, the new node chooses the child closest to itself, and eventually ends up in the lowest level of the structure with the leader that is closest to itself.

Nodes in the same group send eachother heartbeat messages. When a node goes silent for long enough, it is considered dead. When the leader goes silent, a new leader is elected through a distributed algorithm that was not entirely clear to me.

They run some simulations, and find that NICE performs slightly better than Narada in all metrics, including stress and path length, and does significantly better in terms of control overhead. But all simulations run with 128 nodes, and this seems kind of small for the kind of multicast that they're discussing (news feeds, stock ticker, etc.).

The one thing that I think could be seriously improved is the criteria for leader selection. Certainly, it is important to have a leader who is geographically close to all nodes in the group. However, it also seems important to have a leader who has a reliable internet connection. After all, if packets don't get to the leader, they will not get to the leaves; but if the leader is simply unreliable and not dead, then that particular node will continue to be the leader and to do a disservice to the rest of the nodes in his group. Some kind of redundant leadership might be nice in this situation.