Topology partition detection

Abstract

Techniques described herein relate to a method for topology partition detection. Network devices within a network topology often share information to achieve desired network functionality. However, when a network topology becomes partitioned such that not all network devices are directly or indirectly connected to the other network devices, the information sharing may fail. Techniques described herein detect such network topology partitioning by analyzing information that represents the network topology, and the connections therein (e.g., a set of paths).

What is claimed is: 
     
         1 . A method for topology partition detection, the method comprising:
 making a first determination, by a network device of a network, that a topology of the network has changed;   obtaining, based on the first determination, a set of paths from a current topology for the network;   assigning a first node of a first path of the set of paths to a first partition;   making a second determination, using the first path, that a second node should be connected to the first node;   making a third determination, using connectivity information of the network device, that the first node and the second node are neighbors; and   assigning, based on the third determination, the second node to the first partition.   
     
     
         2 . The method of  claim 1 , further comprising:
 making a fourth determination, using the first path, that a third node in the first path should be connected to the second node;   making a fifth determination, using the connectivity information, that the second node and the third node are not neighbors; and   assigning, based on the fifth determination, the third node to a second partition;   making a sixth determination, using a second path of the set of paths and the connectivity information that the second node and the third node are neighbors and should be connected; and   merging, based on the sixth determination, the first partition and the second partition into a third partition comprising the first node, the second node, and the third node.   
     
     
         3 . The method of  claim 2 , further comprising:
 making a seventh determination that a fourth node of a third path of the set of paths is not in the first partition;   assigning, based on the seventh determination, the fourth node to a fourth partition;   making an eighth determination that the third path does not include any nodes that should be connected to the first node, the second node, or the third node;   making a ninth determination, based on the eighth determination, that the current topology is partitioned into the third partition and the fourth partition; and   performing, based on the ninth determination, a topology repair action set.   
     
     
         4 . The method of  claim 3 , wherein performing the topology repair action set comprises:
 performing an analysis on the connectivity information to determine that the fourth node and the first node are neighbors; and   repairing, based on the analysis, the current topology by updating the current technology to add a link between the fourth node and the first node, wherein adding the link allows for transmitting link state information between the first node and the fourth node.   
     
     
         5 . A method for topology partition detection, the method comprising:
 making a first determination, by a network device in a network, that a topology of the network has changed;   obtaining, by the network device and based on the first determination, a set of paths from a current topology for the network; and   performing, by the network device, a partition detection action set using the set of paths and a link state database of the network device,   wherein the partition detection action set determines whether the current topology is partitioned.   
     
     
         6 . The method of  claim 5 , wherein performing the partition detection action set comprises:
 assigning a first node of a first path of the set of paths to a first partition;   making a second determination, using the first path, that a second node should be connected to the first node;   making a third determination, using the link state database, that the first node is a neighbor of the second node; and   assigning, based on the second determination and the third determination, the second node to the first partition with the first node.   
     
     
         7 . The method of  claim 5 , wherein performing the partition detection action set comprises:
 making a second determination, using a first path of the set of paths, that a first node should be connected to a second node;   making a third determination, using the link state database, that the first node is not a neighbor of the second node; and   assigning, based on the second determination and the third determination, the second node in a second partition.   
     
     
         8 . The method of  claim 5 , wherein performing the partition detection action set comprises detecting that the current topology is partitioned into a first partition and a second partition, and the method further comprises:
 performing, in response to detecting that the current topology is partitioned, a topology repair action set.   
     
     
         9 . The method of  claim 8 , wherein performing the topology repair action set comprises:
 making a fourth determination, using the set of paths, that a first node in the first partition and a second node in the second partition are not connected in the current topology;   performing an analysis, using the link state database, to determine that the first node is a neighbor of the second node; and   repairing, based on the analysis, the current topology by transmitting link state information between the first node and the second node.   
     
     
         10 . The method of  claim 5 , wherein performing the partition detection action set comprises detecting that the current topology is partitioned into a first partition and a second partition, and the method further comprises:
 making a second determination, using the set of paths, that a first node of the first partition and a second node of the second partition are connected in the current topology   making a third determination, using the link state database that the first node and the second node are neighbors; and   merging, based on the second determination and the third determination, the first partition and the second partition into a third partition.   
     
     
         11 . The method of  claim 5 , wherein performing the partition detection action set determines that all nodes of the current topology are in a single partition. 
     
     
         12 . The method of  claim 5  further comprising:
 performing, by the network device in response to the first determination, an analysis to determine routes to each of a plurality of other network devices in the network. 
 
     
     
         13 . The method of  claim 5 , wherein making the first determination comprises receiving a link state update from a second device of the network. 
     
     
         14 . The method of  claim 5 , wherein making the first determination comprises receiving an updated topology. 
     
     
         15 . The method of  claim 5 , wherein the link state database comprises link state information indicating whether nodes of the current topology are neighbors. 
     
     
         16 . A non-transitory computer readable medium comprising instructions that, when executed by a processor, perform a method for topology partition detection, the method comprising:
 making a first determination, by a network device in a network, that a topology of the network has changed;   obtaining, by the network device and based on the first determination, a set of paths from a current topology for the network; and   performing, by the network device, a partition detection action set using the set of paths and a link state database of the network device,   wherein the partition detection action set determines whether the current topology is partitioned.   
     
     
         17 . The non-transitory computer readable medium of  claim 16 , wherein performing the partition detection action set comprises:
 assigning a first node of a first path of the set of paths to a first partition;   making a second determination, using the first path, that a second node should be connected to the first node;   making a third determination, using the link state database, that the first node is a neighbor of the second node; and   assigning, based on the second determination and the third determination, the second node to the first partition with the first node.   
     
     
         18 . The non-transitory computer readable medium of  claim 16 , wherein performing the partition detection action set comprises:
 making a second determination, using a first path of the set of paths, that a first node should be connected to a second node;   making a third determination, using the link state database, that the first node is not a neighbor of the second node; and   assigning, based on the second determination and the third determination, the second node in a second partition.   
     
     
         19 . The non-transitory computer readable medium of  claim 16 , wherein performing the partition detection action set comprises detecting that the current topology is partitioned into a first partition and a second partition, and the method further comprises:
 performing, in response to detecting that the current topology is partitioned, a topology repair action set.   
     
     
         20 . The non-transitory computer readable medium of  claim 19 , wherein performing the topology repair action set comprises:
 making a fourth determination, using the set of paths, that a first node in the first partition and a second node in the second partition are not connected in the current topology;   performing an analysis, using the link state database, to determine that the first node is a neighbor of the second node; and   repairing, based on the analysis, the current topology by transmitting link state information between the first node and the second node.