Search

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. [ABSTRACT FROM AUTHOR]

The search of routes with multiple Quality of Service (QoS) constraints from sources to destinations connected by networks is a Non Polynomial (NP) problem, which can be approached using Genetic Algorithms (GAs). These are heuristic algorithms that simulate the natural evolution process to solve optimization problems. In this paper we elaborate on tree-based GAs which represent the set of paths from source to destination as a tree. While existing GA applications use m-ary or binary encoding representing single paths and classes of paths in chromosomes, respectively, we propose a GA application with hybrid encoding which uses both of them. This application uses binary encoding from the first iteration until good classes of paths are found and later encodes the best paths of these classes with m-ary encoding. Its objective is taking advantage of the fast convergence due to the per class-processing of binary chromosomes and the lower computational cost of the single path processing of m-ary chromosomes. Simulation results show the performance, in terms of convergence speed, of the proposed GA application with hybrid encoding. [ABSTRACT FROM AUTHOR]