Break before make forwarding information base (fib) population for multicast

Abstract

A method of installing forwarding state in a link state protocol controlled network node having a topology database representing a known topology of the network, and at least two ports for communication with corresponding peers of the network node. A unicast path is computed from the node to a second node in the network, using the topology database, and unicast forwarding state associated with the computed unicast path installed in a filtering database (FDB) of the node. Multicast forwarding state is removed for multicast trees originating at the second node if an unsafe condition is detected. Subsequently, a “safe” indication signal is advertised to each of the peers of the network node. The “safe” indication signal comprises a digest of the topology database. A multicast path is then computed from the network node to at least one destination node of a multicast tree originating at the second node. Finally, multicast forwarding state associated with the computed multicast path is installed in the filtering database (FDB) of the network node, when predetermined safe condition is satisfied.

1 - 11 . (canceled) 
     
     
         12 . A link state protocol controlled network, comprising a plurality of nodes interconnected by links, wherein each node is configured to:
 detect whether an “unsafe” condition exists at that node; and   responsive to detecting an “unsafe” condition at that node:
 remove forwarding state for multicast paths originating at other network nodes and subsequently advertise a “safe” indication to each neighbour node of the node, the “safe” indication comprising a digest of a topology database of the node; and 
 conditional on the node achieving a “go” condition, install, in a respective filtering database (FDB) of the node, forwarding state associated with multicast paths, the “go” condition comprising receiving at least one respective “safe” indication from at least one neighbour node. 
   
     
     
         13 . The network of  claim 12 , wherein, responsive to a detected topology change, each node is configured to compute respective information characterizing shortest unicast paths from that node to at least one other node before detecting whether an “unsafe” condition exists at that node. 
     
     
         14 . The network of  claim 13 , wherein each node has a respective topology database for storing a representation of a topology of the network and is configured to detect network topology changes. 
     
     
         15 . The network of  claim 12 , wherein each node achieving a “go” condition is configured to forward packets based on the installed forwarding state. 
     
     
         16 . The network of  claim 13 , wherein each node is configured to compute the respective information characterizing shortest unicast paths by computing a respective distance of the shortest unicast path from that node to another node. 
     
     
         17 . The network of  claim 13 , wherein each node is configured to compute the respective information characterizing shortest unicast paths from that node to at least one other node using the topology database. 
     
     
         18 . The network of  claim 17 , wherein each node is configured to detect whether an “unsafe” condition exists by detecting at least one difference in a characteristic of a unicast path to another node relative to that characteristic of a previous unicast path to that other node. 
     
     
         19 . The network of  claim 18 , wherein the characteristic of the unicast path is a distance to the other node. 
     
     
         20 . The network of  claim 18 , wherein the characteristic of the unicast path is a route traversed by each of the computed and previous unicast paths to the other node. 
     
     
         21 . The network of  claim 17 , wherein each node is configured to detect whether an “unsafe” condition exists by detecting whether at least one computed unicast path would not have been a valid path in the previous topology. 
     
     
         22 . The network of  claim 12 , wherein the digest of the topology database advertised by each node comprises information reflecting the detected network topology change. 
     
     
         23 . The network of  claim 12 , wherein achieving the “go” condition at a node comprises receiving a respective “safe” indication from each neighbour node of the node. 
     
     
         24 . The network of  claim 12 , wherein achieving the “go” condition at a node comprises receiving a “safe” indication signal from each neighbour node of the node on the multicast path. 
     
     
         25 . The network of  claim 19 , wherein each node is configured to detect whether an “unsafe” condition exists by, when the computed unicast path would have been a valid path in the previous topology, further determining whether a first neighbour node that is one hop from the node towards the other node along the computed unicast path in the current topology database is further from the other node than a second neighbour node was in the previous topology database. 
     
     
         26 . The network of  claim 17 , wherein the “go” condition comprises:
 when the distance to the other node is less than a previous distance to the other node,
 receiving a “safe” indication signal from a neighbour node of the node that is one hop from the node towards the other node along the computed multicast path; and 
 
 when the distance to the other node is greater than a previous distance to the other node,
 receiving a respective “safe” indication signal from each neighbour node of the node that is one hop from the node away from the other node along the computed multicast path. 
 
 
     
     
         27 . The network of  claim 12 , wherein each node is configured to detect whether an “unsafe” condition exists by receiving a respective “safe” indication from at least one neighbour node containing a respective topology database digest that does not match the topology database digest of the “safe” indication advertised by the node.