Method and apparatus for multicast implementation in a routed ethernet mesh network
Interest in multicast group membership may be advertised via a routing system on an Ethernet network along with an indication of an algorithm to be used by the nodes on the network to calculate the distribution tree or trees for the multicast. Each node, upon receipt of the advertisement, will determine the algorithm that is to be used to produce the multicast tree and will use the algorithm to calculate whether it is on a path between nodes advertising common interest in the multicast. Example algorithms may include shortest path algorithms and spanning tree algorithms. This allows multicast membership to be managed via the routing control plane, while enabling spanning tree processes to be used to forward multicast traffic. Since spanning tree is able to install multicast state per service rather than per source per service, this reduces the amount of forwarding state required to implement multicasts on the routed Ethernet mesh network.
1. A method of implementing multicast on a routed Ethernet mesh network, the method comprising:
receiving, by a node on the routed Ethernet mesh network, a plurality of link state advertisements each specifying an end-point of a multicast tree to be implemented on the routed Ethernet mesh network, at least one of the link state advertisements further specifying an algorithm being used to calculate the multicast tree;
determining whether there is agreement between the specified algorithm and an algorithm to be used by the node on the routed Ethernet mesh network, and when there is agreement, using the specified algorithm, by the node on the routed Ethernet mesh network, to calculate the multicast tree; and
selectively installing forwarding state for the multicast tree if the node on the routed Ethernet mesh network is on the path of the multicast tree between two nodes each advertising an end-point of the multicast tree.
2. The method of claim 1 , wherein the algorithm is one of a plurality of possible multicast tree creation algorithms.
3. The method of claim 1 , wherein the at least one of the link state advertisements further specifies a VLAN ID associated with the multicast tree to enable multicast trees to be created using different multicast tree creation algorithms on a per VLAN basis.
4. The method of claim 1 , wherein the algorithm calculates a shortest path tree.
5. The method of claim 1 , wherein the algorithm is a spanning tree algorithm.
6. The method of claim 5 , wherein the spanning tree algorithm further specifies a root selection process for the spanning tree.
7. The method of claim 5 , wherein the link state advertisement specifies the root for the spanning tree.
8. The method of claim 1 , wherein the multicast tree is a minimum spanning tree.
9. The method of claim 8 , further comprising calculating the minimum spanning tree by tie-breaking between links of equal weight by using a secondary metric algorithmically derived from unique end-point identifiers.
10. The method of claim 8 , further comprising calculating the minimum spanning tree by adjusting link weights on the network where multiple links have equal weights.
11. The method of claim 10 , wherein the adjusting the link weights comprises modifying each link's weight based on a unique identifier of network nodes connected by the link.
12. The method of claim 10 , wherein the adjusting the link weights comprises calculating a fractional weight for at least one of the links that have equal weights, and either adding or subtracting the fractional weight to the original link weight.
13. The method of claim 12 , wherein the fractional weight is strictly less than an integer unit of the original link metric.
14. The method of claim 8 , further comprising using a minimum spanning tree algorithm to determine the minimum spanning tree, and using node identifiers during the step of using the minimum spanning tree algorithm to adjust link weights to prevent multiple links from having equal weights.
15. The method of claim 1 , further comprising removing forwarding state for the multicast tree upon occurrence of a change in network topology.
16. The method of claim 15 , wherein the removing the forwarding state for the multicast tree comprises removing source specific multicast forwarding state for all multicast trees associated with a source that is farther from or closer to the node based on the change in network topology.
17. A computer program product stored on a non-transitory computer readable medium, the computer program product containing data and instructions which, when loaded into one or more processors of a node on a routed Ethernet mesh network, cause the one or more processors to perform a method of implementing multicast on the routed Ethernet mesh network, the method comprising the steps of:
receiving, by the node on the routed Ethernet mesh network, a plurality of link state advertisements each specifying an end-point of a multicast tree to be implemented on the routed Ethernet mesh network, at least one of the link state advertisements further specifying an algorithm being used to calculate the multicast tree;
determining whether there is agreement between the specified algorithm and an algorithm to be used by the node on the routed Ethernet mesh network, and when there is agreement, using the specified algorithm, by the node on the routed Ethernet mesh network, to calculate the multicast tree; and
selectively installing forwarding state for the multicast tree if the node on the routed Ethernet mesh network is on the path of the multicast tree between two nodes each advertising an end-point of the multicast tree.
18. The computer program product of claim 17 , wherein the algorithm is one of a plurality of possible multicast tree creation algorithms, and wherein the at least one of the link state advertisements further specifies a VLAN ID associated with the multicast tree to enable multicast trees to be created using different multicast tree creation algorithms on a per VLAN basis.
19. The computer program product of claim 17 , wherein the multicast tree is a minimum spanning tree, and wherein the method further comprises the step of calculating the minimum spanning tree by adjusting link weights on the network where multiple links have equal weights.
20. The computer program product of claim 19 , wherein the step of adjusting link weights comprises modifying each link's weight based on a unique identifier of network nodes connected by the link.
21. The computer program product of claim 20 , wherein the step of adjusting link weights comprises calculating a fractional weight for at least one of the links that have equal weights, and either adding or subtracting the fractional weight to the original link weight.