Topology partition detection
AssigneeArista Networks, Inc.
InventorAnthony Joseph Li
Life of this patent
Estimating the term…
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).
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.