Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Search Party: Using Randomcast for Reliable Multicast with Local Recovery

Adam M. Costello and Steven McCanne

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-98-1011
August 1998

http://www.eecs.berkeley.edu/Pubs/TechRpts/1998/CSD-98-1011.pdf

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 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.


BibTeX citation:

@techreport{Costello:CSD-98-1011,
    Author = {Costello, Adam M. and McCanne, Steven},
    Title = {Search Party: Using Randomcast for Reliable Multicast with Local Recovery},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1998},
    Month = {Aug},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1998/5242.html},
    Number = {UCB/CSD-98-1011},
    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 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 <i>N</i> increases, overhead will increase by at most log <i>N</i> and retransmission delay will be unaffected. Simulation experiments show that both increase very little as <i>N</i> grows from 8 to 64, and confirm the tunability of the trade-off.}
}

EndNote citation:

%0 Report
%A Costello, Adam M.
%A McCanne, Steven
%T Search Party: Using Randomcast for Reliable Multicast with Local Recovery
%I EECS Department, University of California, Berkeley
%D 1998
%@ UCB/CSD-98-1011
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1998/5242.html
%F Costello:CSD-98-1011