Search party: using randomcast for reliable multicast with local recovery

Abstract

IP multicast is an efficient means of sending to a group, but the packets are sent unreliably. Some applications, like distributed whiteboard and news articles, require detection and retransmission of lost packets. In order to scale to large groups, local recovery is necessary to avoid involving the entire group in the repair process for packet losses affecting small regions of the distribution tree. While many current research efforts have attempted to devise local recovery schemes that rely only on the existing service model, we believe that extending the multicast forwarding service could enable viable and highly scalable local recovery mechanisms. To investigate this open issue, we propose a new randomized forwarding service called randomcast, and build upon it a loss recovery protocol called search party. Starting with the local recovery structure of the very scalable lightweight multicast services (LMS) scheme, we use randomized forwarding to greatly improve robustness at a modest cost in overhead and/or retransmission delay (the trade off between the two costs is fine-tunable). Analysis predicts that as the group size N increases, overhead will increase by at most log N and retransmission delay will be unaffected. Simulation experiments show that both increase very little as N grows from 8 to 64, and confirm the tunability of the trade-off.