BUILDING A MULTICASTING TREE IN A HIGH-SPEED NETWORK

To build a multicasting tree in a multicomputer network, the authors p ropose three strategies based on voting, constructing a minimum spanni ng tree, and repeatedly constructing multiple minimum spanning trees. Typically, performance metrics to evaluate a multicast solution includ e time and traffic. Simultaneously optimizing both metrics is computat ionally intractable because the problem is NP-complete. The first sche me always guarantees the use of the shortest path from the source node to each destination, which makes it time-optimal. The other hva schem es do not guarantee this but try to reduce the traffic as much as poss ible. To demonstrate these strategies' effectiveness, the authors appl y them to hypercubes, star graphs, and star graphs with some faults. T hey report experimental results to evaluate the performance of these s olutions.