Self-healing algorithm for real-time multicast tree

Abstract

This dissertation addresses the problem of dynamic rerouting in a real-time multicast tree. Real-time multicast routing had been studied in depth and a number of multicast tree building algorithms had been proposed that take into consideration network cost and performance guarantee services like end-to-end delay constraint. However, these algorithms are not resilient to link failures and would require intensive computation and expensive restructuring of the routing tree. Increase in network delay and packet loss is inevitable during the transition to the new multicast tree. While other algorithms that require less restructuring exist, they are not suitable for real-time communications. The presence of these performance guaranteed services prompted the study of fault recovery techniques and we investigate one aspect of fault recovery, the rerouting of guaranteed performance connections, which are affected by the link faults in the network. Recovery is achieved by rerouting the affected connection in order to bypass the failed link and yet ensuring that performance guarantees are met. The objective is to attempt to retain the original structure of the multicast tree. This is to reduce the transition time to the new multicast tree and reduce packet loss in the network. We proposed an algorithm that will attempt to reconnect the broken tree while meeting the delay constraint. Extensive simulations with different configurations were conducted and the results and analysis are presented.