Patent Document ID: 20170201451
Application ID: 15076546
Patent Status: 0

Claim One:
1. A method implemented by a network device to simplify a topology graph of a network and to generate a multicast distribution tree, the method to reduce complexity of the topology graph such that a computational complexity of generating the multicast distribution tree is reduced, the method comprising: computing ( 103 ) a shortest path to all nodes of the topology graph rooted at a source node S; determining ( 107 ) a metric for each adjacency on each shortest path of the topology graph for a multicast group G; constructing ( 109 ) an (S, G) graph with only source node S, leaves and candidate replication points; and pruning ( 112 ) the (S, G) graph using a first set of pruning processes to attempt 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.