Fast rearrangement of multicast trees for applications with bandwidth and delay QoS requirements

Many real-time applications rely on the provision of a multicast service capable of supporting their quality of service (QoS) requirements. Most of the current approaches to the multicast issue involve the maintenance of a multicast tree, through which data propagate to reach the end users. Such a constraint on the topology of the multicast network introduces several difficult issues when the multicast tree has to be rearranged. We address the problem of efficiently rearranging a multicast tree at the effect of node faults. We provide a theoretical formulation of the problem and prove that it is NP-hard. Since we cannot opt for exact solutions, we present two heuristics for efficient rearrangement. Both heuristics aim at re-admitting the maximum number of disrupted users to the multicast group, while observing the tree-property of the multicast network