Multicast tree generation in networks with asymmetric links

摘要

We formulate the problem of multicast tree generation as one of computing a directed Steiner tree of minimal cost. In this context, we present a polynomial-time algorithm that provides for trade-off selection, using a single parameter /spl kappa/, between the tree-cost (Steiner cost) and the run time efficiency. Further, the same algorithm may be used for delay optimization or tree-cost minimization simply by configuring the value of /spl kappa/ appropriately. We present theoretical and experimental analysis characterizing the problem and the performance of our algorithm. Theoretically, we show that it is highly unlikely that there exists a polynomial-time algorithm with a performance guarantee of constant times optimum cost, introduce metrics for measuring the asymmetry of graphs, and show that the worst-case cost of the tree produced by our 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 but particular cases of our algorithm. Our experimental study shows that operating at a low /spl kappa/ gives nearly best possible expected tree cost while maintaining acceptable run-time efficiency.