The round trip network delay times between pairs of nodes in a multicast session is a key parameter; it is used in suppressing the implosion of request and repair packets, in detecting congestion, etc. This paper presents a protocol to estimate the delays between every pair of nodes in a multicast group. While existing protocols use O(n) multicast messages with O(n) size each (total of O(n/sup 2/) bits), our protocol requires O(n) multicasts with only O(1) size each (total of O(n) bits); here, n is the session size. It does not require clocks to be synchronized, or any knowledge of network topology and the session size. We incorporate our protocol into the SRM (scalable reliable multicast) protocol (Rhee et al., 1999) and show by our simulations that, (i) our delay estimation protocol is reasonably accurate, (ii) it is just as effective as existing delay estimation protocols in suppressing repair and request traffic in SRM, and (iii) it has significantly lower overhead than the existing delay estimation protocols. Furthermore, our protocol can be extended to run within a hierarchically structured multicast protocol such as RMTP (reliable multicast transport protocol) (Paul et al., 1996). Here the goal is to estimate round trip delays from a sender to each receiver. Our protocol ensures that only the immediate children of the sender send feedback messages directly to the sender, thereby avoiding feedback implosion. Our delay estimation protocols therefore significantly enhance the scalability of unstructured multicast protocols such as SRM, as well as tree-structured multicast protocols such as RMTP.

We study the problem of localizing repair packets when packets are lost during multicasts. When repair packets are multicast, a highly lossy receiver may swamp the entire multicast "group" with duplicate repair packets thereby wasting bandwidth; thus, the protocols need repair locality. We present a multicast layering scheme where the sender proactively distributes FEC repair packets among multiple multicast groups. Each receiver can selectively tune in to a subset of these multicast groups to obtain packets close in number to what it needs. We develop an efficient algorithm that dynamically determines the optimal distribution of FEC repair packets to a given (small constant) number of multicast groups. The running time of this algorithm is independent of the number of receivers in the multicast session, and is hence highly scalable. However, the optimal algorithm requires the knowledge of the FEC repair requirements of all the receivers in the multicast group, and hence is subject to the implosion problem. To handle the implosion problem, we develop an heuristic algorithm that achieves repair locality very similar to that of the optimal algorithm, but does not require as much global knowledge. Our multicast layering scheme can be integrated into known reliable multicast protocols to make them more scalable. For concreteness, we focus on: (i) singly scoped SRM, (ii) hierarchically scoped SRM, and (iii) a tree-based reliable multicasting protocol RMTP, and present combined protocols incorporating our solutions into each of them. Simulation experiments show that our solutions can substantially enhance the scalability of these reliable multicast protocols.