Recursive Peer-to-Group Routing on a Network Hierarchy for Stable Overlay Multicast

This paper presents a new application-layer multicast technique, {\em recursive peer-to-group routing}, in which data delivery paths are not fixed but change dynamically and frequently even when no failures occur at receiver hosts. The advantages of our technique include (1) well-distributed and well-balanced network-relaying traffic for all hosts over the delivery system, (2) automatic and rapid adaptation of delivery routes to the non-uniformity and temporary fluctuations in host performance, and (3) stability of the whole system even with frequent joins and departures of receiver hosts. We exploit a network hierarchy for system scalability just as in the conventional fixed path approaches, but we also introduce layered destinations without assigning any fixed hierarchical roles to the host nodes. In addition, the determination of the multicast paths is decentralized and distributed to the end nodes. Link stresses for uplinks and downlinks are almost the same as for the original data rate at any hierarchical level, which localizes and reduces network traffic. We give an analysis of latency and loss rates with concatenated queuing systems and show how to control the final loss rate by determining such system parameters as data rate, network performance, and recovery rate of erasure code words. We also present and discuss some simulation
results with a blocking system, in which the data rate is maximized at the point of the highest system utilization.