MULTICAST TREE GENERATION IN NETWORKS WITH ASYMMETRIC LINKS

We formulate the problem of multicast tree generation as one of comput ing a directed Steiner tree of minimal cost, In this context, we prese nt a polynomial-time algorithm that provides for trade-off selection, using a single parameter kappa, between the tree-cost (Steiner cost) a nd the run time efficiency. Further, the same algorithm may be used fo r delay optimization or tree cost minimization simply by configuring t he value of kappa appropriately, We present theoretical and experiment al analysis characterizing the problem and the performance of our algo rithm, Theoretically, we show that it is highly unlikely that there ex ists a polynomial-time algorithm with a performance guarantee of const ant times optimum cost, introduce metrics for measuring the asymmetry of graphs, and show that the worst-case cost of the tree produced by o ur algorithm is, at most, twice the optimum cost times the asymmetry, for two of these asymmetry metrics, For graphs with bounded asymmetry, this gives constant times optimum performance guarantee, We also show that three well-known algorithms for (undirected) Steiner trees are b ut particular cases of our algorithm, Our experimental study shows tha t operating at a low kappa gives nearly best possible expected tree co st while maintaining acceptable runtime efficiency.