GRAPH CONSTRUCTION FOR COMPUTED SPRING MULTICAST

A method is provided that is implemented by a network device to simplify a topology graph of a network to generate a multicast distribution tree, the method to reduce the complexity of the topology graph while enabling a creation of the multicast distribution tree such that the computational complexity of generating the multicast distribution tree is reduced, the method including computing a shortest path to all nodes of the topology graph rooted at a source node S, determining a metric for each adjacency on each shortest path of the topology graph for the multicast group G, construct an (S, G) graph with only source node S, leaves and candidate replication points, and prune the (S, G) graph using a set of pruning processes to fully resolve the multicast distribution tree, where full resolution can be determined, and the first set of pruning processes if successful are known to produce a minimum cost tree.