network-programmingroutesspanning-tree

Minimum cost broadcast routing

Is there any method where we can get a minimum cost broadcast routing scheme without using the spanning tree algorithm?

Any references to guide me on this will be of great use to me.

Solution

  • Any algorithm for implementing a minimum cost broadcast (or multicast) routing scheme in the end boils down to constructing a least-cost spanning tree (rooted at the multicast source) of the full graph which represents the network.

    There are various algorithms for computing the least-cost spanning tree.

    IP multicast routing protocols such as PIM rely on least-cost spanning tree which is computed by the IGP (OSPF or ISIS) using the Dijkstra algorithm.

    Older protocols, such as DVMRP, rely on a distance-vector protocol to compute the spanning tree.

    One could theoretically use other algorithms to compute the least-cost spanning tree (e.g. Bellman-Ford) although I know of no implementation that does so in practice.