A Comparison of Known Classes of Reliable Multicast Protocols

This thesis addresses the question of whether a reliable multicast protocol can be designed that enjoys all the scaling properties of receiver-initiated protocols while still being able to operate correctly with finite memory. To answer this question, we analyze the maximum throughput of the known classes of reliable multicast protocols that have been proposed to solve the acknowledgment ACK implosion problem of sender-initiated reliable multicast protocols. We introduce a new taxonomy of reliable multicast protocols, based on the premise that the mechanisms used to release data at the source after correct delivery should be decoupled from the mechanisms used to pace the transmission of data and to effect error recovery. Receiver- initiated protocols, which are based entirely on negative acknowledgments NAKs sent from the receivers to the sender are shown to require infinite buffers in order to prevent deadlocks. Two other solutions to the ACK-implosion problem are tree-based protocols and ring-based protocols. The first organize the receivers in a tree and send ACKs along the tree the latter send ACKs to the sender along a ring of receivers. These two classes of protocols are shown to operate correctly with finite buffers. We show that the tree-based protocols constitute the most scalable class of all reliable multicast protocols proposed to date.