C.C. Cipriano and T.F. Gonzalez (USA)
Heuristics, n-cube, sp-multicasting trees, multicasting,Steiner Trees.
Given a source node s and a set of destinations D in the n-cube we study the problem of constructing near-optimal sp-multicast trees. In other words, construct a near-optimal Steiner tree for {s} ∪ D in which all paths from s to the destination nodes are shortest paths in the n-cube. We discuss known algorithms (Greedy, NGrouping, and Clustering) for the sp-multicast tree problem and identify problem instances for which they perform poorly. We introduce three new algorithms (MOverlap, BEstimate and BUp) that identify structural similarities between the message destinations and avoid the pitfalls of the previously known algorithms. We present an experimental evaluation of all the algorithms over a wide range of problem instances. Our experimentation shows that the new algorithm BUp outperforms all the other methods.
Important Links:
Go Back
