How Bad is Na'ive Multicast Routing?

Abstract

When the problem of routing multicast connections in networks has been previously considered, the emphasis has been on the source transmitting to a fixed set of destinations (the multicast group). There are some applications where destinations will join and leave the multicast group. Under these conditions, computing an “optimal” spanning tree after each modification may not be the best way to proceed. An alternative is to make modest alterations to an existing spanning tree to derive a new one. An extreme, though non-optimal, variation of this is to use minimal cost source to destination routing for each destination, effectively ignoring the existing multicast tree. We examine just how non-optimal these trees are in random general topology networks and conclude that they are worse by only a small factor. The factor is reduced still further if a hierarchy is imposed upon the random network to give a more realistic model.