Graph construction for computed spring multicast

Patent metadata

Field	Value
Publication number	US-2017201451-A1
Application number	US-201615076546-A
Country	US
Kind code	A1
Filing date	Mar 21, 2016
Priority date	Jan 8, 2016
Publication date	Jul 13, 2017
Grant date	—

Abstract

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.

First claim

What is claimed is:

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.

2 . The method of claim 1 , wherein a failure to resolve the multicast distribution tree using the first set of pruning processes results in application of a second set of pruning processes that are not authoritative, combined with verification of the fully resolved multicast distribution tree.

3 . The method of claim 1 , wherein the first set of pruning processes includes any one or more of eliminating ( 113 ) non-leaf non-candidate replication points in the (S, G) graph, eliminating ( 115 ) triangles in the (S, G) graph, or selecting ( 117 ) upstream links to replication points from leaves that have a lowest metric.

4 . The method of claim 1 , further comprising:
checking ( 111 ) whether the network device is in the (S,G) graph; and exiting ( 131 ) computation of the method in response to the network device not being in the (S,G) graph.

5 . The method of claim 1 , further comprising:
installing ( 130 ) state in the network device based on the fully resolved multicast distribution tree generated.

6 . The method of claim 1 , wherein the metric is a potentially served leaf metric.

7 . A network device configured to execute a method 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 network device comprising:
a non-transitory machine readable storage medium ( 1918 ) having stored therein a graph simplification element ( 1931 A); and a processor ( 1912 ) coupled to the non-transitory machine readable storage medium, the processor configured to execute the graph simplification element, the graph simplification element configured to compute a shortest path to all nodes of the topology graph rooted at a source node S, to determine a metric for each adjacency on each shortest path of the topology graph for a multicast group G, to construct an (S, G) graph with only source node S, leaves and candidate replication points, and to prune 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.

8 . The network device of claim 7 , wherein a failure to resolve the multicast distribution tree using the first set of pruning processes results in application of a second set of pruning processes that are not authoritative combined with verification of the fully resolved multicast distribution tree.

9 . The network device of claim 7 , wherein the first set of pruning processes includes any one or more of eliminating non-leaf non-candidate replication points in the (S, G) graph, eliminating triangles in the (S, G) graph, or selecting upstream links to replication points from leaves that have a lowest metric.

10 . The network device of claim 7 , wherein the graph simplification element is further configured to check whether the network device is in the (S, G) graph, and to exit computation of the method in response to the network device not being in the (S, G) graph.

11 . The network device of claim 7 , wherein the graph simplification element is further configured to install state in the network device based on the fully resolved multicast distribution tree generated.

12 . The network device of claim 7 , wherein the metric is a potentially served leaf metric.

13 . A computing device configured to execute a plurality of virtual machines, the plurality of virtual machines implementing network function virtualization (NFV), the computing device in communication with a network device, a virtual machine from the plurality of virtual machines configured to execute a method 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 network device comprising:
a non-transitory machine readable storage medium ( 1948 ) having stored therein a graph simplification element ( 1965 A); and a processor ( 1942 ) coupled to the non-transitory machine readable storage medium, the processor configured to execute the virtual machine, the virtual machine configured to execute the graph simplification element, the graph simplification element configured to compute a shortest path to all nodes of the topology graph rooted at a source node S, to determine a metric for each adjacency on each shortest path of the topology graph for a multicast group G, to construct an (S, G) graph with only source node S, leaves and candidate replication points, and to prune 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.

14 . The computing device of claim 13 , wherein a failure to resolve the multicast distribution tree using the first set of pruning processes results in application of a second set of pruning processes that are not authoritative combined with verification of the fully resolved multicast distribution tree.

15 . The computing device of claim 13 , wherein the first set of pruning processes includes any one or more of eliminating non-leaf non-candidate replication points in the (S, G) graph, eliminating triangles in the (S, G) graph, or selecting upstream links to replication points from leaves that have a lowest metric.

16 . The computing device of claim 13 , wherein the graph simplification element is further configured to check whether the network device is in the (S, G) graph, and to exit computation of the method in response to the network device not being in the (S, G) graph.

17 . The computing device of claim 13 , wherein the graph simplification element is further configured to install state in the network device based on the fully resolved multicast distribution tree generated.

18 . The computing device of claim 13 , wherein the metric is a potentially served leaf metric.

19 . A control plane device is configured to implement a control plane of a software defined networking (SDN) network including a network device, the control plane device configured to execute a method 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 t

Assignees

• ERICSSON TELEFON AB L M (publ)

Inventors

• Allan David Ian

Classifications

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/16

  Multipoint routing · CPC title

• H04L65/4076

  Electricity · mapped topic

• H04L45/12 Primary

  Shortest path evaluation · CPC title

• H04L12/185 Primary

  with management of multicast group membership · CPC title