Single and Multi Destinations Trees for Routing Applications

Tree topologies are widely used by routing applications as they do not have loops. In this paper we focus on generation algorithms of single and multi destination trees from mesh networks. They represent the paths from a network node, called source, to one or more other nodes called destinations. Starting from an existing generation algorithm of single destination trees we propose an extension of it to generate multi destination trees and study the computational complexity of both the algorithms. The focus of the computational complexity study is on the effect of the dead end paths. They are paths ending up in loops which cannot be discarded a priori during tree generation. The number of dead end paths generated decreases with the number of destinations and it becomes null when all the network nodes, excepting the source, are destinations. Moreover, we propose a cut-tree strategy to generate single or multi destination trees to different sets of destinations from a tree which includes all of them. This strategy allows to reduce the computational cost if a Multicast routing application requires multiple trees from the same source and a given network topology.