SRM

This paper essentially describes an implementation of a reliability layer on top of a multicast protocol. The authors state that they will implement reliability by avoiding ACKs (and the ACK implosion problem), as well as sender-based reliability protocols (since this would mean the sender would have to track participation).

In the model that they use for multicast, participants in a multicast group can leave and join at will. All messages are deliverd to all participants, and all participants are both senders and receivers. The actual multicast is achieved using some sort of structure for message propagation; this structure can be a chain, a star, a tree, or anything else.

The first part of this paper is loss detection and recovery - each participant has a unique ID, and their messages are sent out with their ID as well as a sequential number. These numbers apply to distinct application-level messages, rather than packets. Whenever a node receives two non-sequential numbers, it assumes that there has been a loss, and prepares to request a recovery. It waits a random amount of time that is also dependent upon its "distance" from the sender.

By randomizing the amount of time that they wait, these nodes help avoid the synchronization problem. When a node sends a request for missing data, it is multicast like all other messages. This means that other nodes who want the same data can now back off (reset and double the timers on their requests) so as to have a minimal number of requests for each piece of missing data. Any node that hears a recovery request and has the requested data can respond to the request, thereby (hopefully) improving the response time for these requests. Not pictured here: RTT estimator (that doesn't require synchronized clocks), race condition avoidance (wait 3*RTT estimate).

They then do a couple of simulations of the algorithm's performance on various different topologies. They conclude that the number of retransmissions per lost data message is low, the amount of time to recover a lost message (divided by the RTT time) is low, and so forth. However, as they said in the paper, "We do not claim to be presenting realistic topologies or typical patterns of packet loss.". So in other words, this is all pretty suspect.

Lastly, they present a theoretical improvement where the wait time is adjusted based on the number of duplicate requests that a node sees, as well as the average request delay that it has. They then consider using TTL values to localize recovery requests and retransmissions (under the assumption that a loss implies a single failure somewhere in the topology rather than general network unreliability).

In general, I liked the first part of this paper a lot more than the rest of it. It presented an algorithm and implementation that was actually in use, and served a very specific purpose. As they state in the paper, it is unlikely that anyone will create a multicast application that satisfies everyone's needs, so it is better to have a more application-specific framework for multicast.