A rtt-based partitioning algorithm for a multi-rate reliable multicast protocol

Abstract. Various Internet applications involve multiple parties and usually adopt a one-to-many communication paradigm (multicast). The presence of multiple receivers in a multicast session rises the problem of inter-receiver fairness. Transmitting with a rate which matches the slowest receiver will limit the throughput of other receivers and thus their satisfaction. A multi-rate mechanism where the receivers are distributed into subgroups with similar capacities, can improve the inter-receiver fairness for multicast sessions. In this paper, we deal with the problem of receivers partitioning and propose a simple algorithm based on the receivers RTT variations where an explicit estimation of the receivers capacities is avoided. Our partitioning algorithm, although simple, performs an on-the-fly partitioning depending on the receivers ’ feedback. We show that our partitioning algorithm approximates and in many cases, achieves the optimal solution with a minimum computation effort.