Stability of a multicast tree

Most of the currently deployed multicast protocols (e.g. DVMRP, PIM, MOSPF) build one shortest path multicast tree per sender, the tree being rooted at the sender's subnetwork. This paper examines the stability of such a tree, specifically, how the number of links change as the number of multicast users in a group changes. We make two modelling assumptions: (a) packets are delivered along the shortest path tree; (b) the m multicast group member nodes are chosen uniformly out of the total number of nodes N. The probability density function for the number of changed edges, /spl Delta//sub N/(m), when one multicast user joins or leaves the group is studied. For random graphs of the class G/sub p/(N) with N nodes, link density p and with uniformly (or exponentially) distributed link weights, the probability density function, Pr[/spl Delta//sub N/(m)=k], is proved to tend to a Poisson distribution for large N. The proof of this theorem enables a generalization to an arbitrary topology. Simulations, mainly conducted to quantify the validity of the asymptotic regime, reveal that the Poisson law seems more widely valid than just in the asymptotic regime where N/spl rarr//spl infin/. In addition, the effect of the link weight distribution on the stability of the multicast tree is investigated. Finally, via simulations, the stability of a Steiner tree connecting m multicast users is compared to the shortest path tree.