# US 12,184,501 B2 · Topology partition detection > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,184,501 B2 - Document ID: US12184501B2 - Status: Granted - Kind: B2 - Application number: 18/343,996 - Filed: 2023-06-29 - Published: 2023-11-09 - Granted: 2024-12-31 - Earliest claimed: 2020-01-09 - Assignees: Arista Networks, Inc. - Applicants: Arista Networks, Inc. - Inventors: Anthony Joseph Li - Web page: https://patentgrep.com/patent/US12184501B2 ## CPC - H04L 41/12: Discovery or management of network topologies - H04L 41/14: Network analysis or design - H04L 43/0811: by checking connectivity - H04L 41/0893: Assignment of logical groups to network elements - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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). ## Claims ### Claim 1 A method for managing a sub-topology of a network, the method comprising: receiving notification at a network device that connectivity of nodes in an existing sub-topology has changed, the existing sub-topology comprising a set of paths, each path comprising two or more of the nodes; performing, by the network device, a partition detection action set based on a link state database of the network device for each node in a path, the link state database reflecting a current state of nodes in the sub-topology of the network; determining that a number of partitions of the existing sub-topology is greater than one based on the partition detection action set performed based on the link state database reflecting the current state of nodes in the sub-topology of the network, wherein at least one node in each of the number of partitions of the sub-topology of the network is not operatively connected to at least one node in another partition of the sub-topology of the network; performing, in response to determining that the number of partitions is greater than one, a topology repair action set; and updating the existing sub-topology based on the topology repair action set. ### Claim 2 (depends on 1) The method of claim 1, wherein the performing the partition detection action set, the performing the topology repair action set and the updating the existing sub-topology are performed for each path in the set of paths. ### Claim 3 (depends on 1) The method of claim 1, wherein performing the partition detection action set for each node in the path comprises: determining the connectivity of the node to a next node in the path; and adding the next node to a partition. ### Claim 4 (depends on 3) The method of claim 3, wherein performing the partition detection action set for each node in the path further comprises: determining a greatest union partition associated with the node and the next node based on the connectivity and a previously determined partition, wherein the greatest union partition is one of the number of partitions. ### Claim 5 (depends on 1) The method of claim 1, wherein updating the existing topology is achieved by performing the partition detection action set for each node in each path only once. ### Claim 6 (depends on 1) The method of claim 1, wherein performing the topology repair action set comprises: performing an analysis on the connectivity information using the link state database to determine that a first node from a first partition is connected to a second node from a second partition; and updating the existing topology to add a link between the first node and the second node, wherein adding the link allows for transmission of link state information between the first node and the second node. ### Claim 7 (depends on 6) The method of claim 6, wherein the first node and second node are neighbors. ### Claim 8 (depends on 1) The method of claim 1, wherein receiving the notification at the network device that the topology of the network has changed comprises receiving a link state update from a second network device of the network. ### Claim 9 (depends on 1) The method of claim 1, wherein receiving the notification at the network device that the topology of the network has changed comprises receiving an updated topology. ### Claim 10 (depends on 1) The method of claim 1, further comprising: performing, by the network device in response to receiving the notification that the topology of the network has changed, an analysis to determine routes to each of a plurality of other network devices in the network. ### Claim 11 (depends on 1) The method of claim 1, wherein the link state database comprises link state information indicating whether nodes of the current topology are neighbors. ### Claim 12 A method for detecting a partition in a network sub-topology that forms a portion of a network topology, the method comprising: receiving notification at a network device that a link of the network sub-topology has broken, the network sub-topology comprising a set of paths, each path comprising two or more nodes and connecting links; for each path of the set of paths, performing a partition detection process based on a current state of the portion of the network topology, comprising: iteratively determining for each node in a path whether a partition of the node is connected by an unbroken link to another partition based on the current state of the portion of the network topology, if the partition of the node is connected by an unbroken link to another partition, forming a union of the partition of the node and said another partition, and if the partition of the node is not connected by an unbroken link to another partition, maintaining the partition of the node as a separate partition, wherein the node in the separate partition is not operatively connected to the another partition by virtue not being connected by the unbroken link; and determining whether, after completing the partition detection process, there exists more than one remaining partition. ### Claim 13 (depends on 12) The method of claim 12, further comprising, in response to determining that there exist more than one remaining partitions after completing the partition detection process: (i) for at least one pair of the remaining partitions, identifying a first unbroken link between a first node of a first partition of the pair of partitions and a second node of a second partition of the pair of partitions, wherein the first unbroken link is included in the network topology but is not included in the network sub-topology; and (ii) adding the first unbroken link to the network sub-topology to form a union of the pair of partitions. ### Claim 14 (depends on 13) The method of claim 13, further comprising repeating steps (i) and (ii) until there is only one remaining partition. ### Claim 15 (depends on 12) The method of claim 12, wherein determining whether the partition of the node is connected by an unbroken link to another partition comprises examining a link state database that stores the state of links between devices in the network topology. ### Claim 16 (depends on 12) The method of claim 12, wherein forming the union of the partition of the node and said another partition comprises updating a link state database that stores the state of links between devices in the network topology. ### Claim 17 (depends on 12) The method of claim 12, wherein receiving the notification that the link of the network sub-topology has broken comprises receiving a link state update from a link state database that stores the state of links between devices in the network topology, the link state update sent by a network device when a change to the link state database occurs. ### Claim 18 A non-transitory computer readable medium comprising instructions that, when executed by a processor, perform a method for detecting a partition in a network sub-topology that forms a portion of a network topology, the method comprising: receiving notification at a network device that a link of the network sub-topology has broken, the network sub-topology comprising a set of paths, each path comprising two or more nodes and connecting links; for each path of the set of paths, performing a partition detection process comprising: iteratively determining for each node in a path whether a partition of the node is connected by an unbroken link to another partition based on the current state of the portion of the network topology, if the partition of the node is connected by an unbroken link to another partition, forming a union of the partition of the node and said another partition, and if the partition of the node is not connected by an unbroken link to another partition, maintaining the partition of the node as a separate partition, wherein the node in the separate partition is not operatively connected to the another partition by virtue not being connected by the unbroken link; and determining whether, after completing the partition detection process, there exists more than one remaining partition. ### Claim 19 (depends on 18) The non-transitory computer readable medium of claim 18, the method further comprising, in response to determining that there exist more than one remaining partitions after completing the partition detection process: (i) for at least one pair of the remaining partitions, identifying a first unbroken link between a first node of a first partition of the pair of partitions and a second node of a second partition of the pair of partitions, wherein the first unbroken link is included in the network topology but is not included in the network sub-topology; and (ii) adding the first unbroken link to the network sub-topology to form a union of the pair of partitions. ### Claim 20 (depends on 19) The non-transitory computer readable medium of claim 19, the method further comprising repeating steps (i) and (ii) until there is only one remaining partition.