Synchronizing device resources for element management systems

Patent metadata

Field	Value
Publication number	US-11153228-B1
Application number	US-201916711423-A
Country	US
Kind code	B1
Filing date	Dec 11, 2019
Priority date	Dec 11, 2019
Publication date	Oct 19, 2021
Grant date	Oct 19, 2021

Abstract

An example controller device that manages a plurality of network devices includes one or more processors implemented in circuitry and configured to: determine that configuration of one or more network devices of the plurality of network devices is to be updated; determine dependencies between types of resources provided by the network devices; construct a directed acyclic graph (DAG) representing the dependencies, the DAG having nodes representing the corresponding types of resources of the network devices of the plurality of network devices; sort the nodes of the DAG according to a grouped topological sort into a plurality of hierarchical levels according to the dependencies; and submit queries for two or more resources of the network devices at a common level of the plurality of hierarchical levels in parallel to determine resources of the determined types of resources of the two or more resources to configure the two or more network devices.

First claim

What is claimed is:

1. A method of managing a plurality of network devices, the method comprising:
determining that configuration of one or more network devices of the plurality of network devices is to be updated;
determining dependencies between types of resources provided by network devices;
constructing a directed acyclic graph (DAG) representing the dependencies, the DAG having nodes representing the corresponding types of resources of the network devices of the plurality of network devices;
sorting the nodes of the DAG according to a grouped topological sort into a plurality of hierarchical levels according to the dependencies; and
submitting queries for two or more resources of the network devices at a common level of the plurality of hierarchical levels in parallel to determine resources of the determined types of resources of the two or more resources to configure the two or more network devices.

2. The method of claim 1 , wherein determining the dependencies comprises determining that a first type of resource depends on a second type of resource when configuration information for the first type of resource refers to configuration information for the second type of resource.

3. The method of claim 1 , wherein constructing the DAG comprises creating a graph edge from a first node of the DAG to a second node of the DAG when a first type of resource of a first network device corresponding to the first node depends on a second type of resource of a second network device corresponding to the second node.

4. The method of claim 1 , wherein constructing the DAG comprises, for all pairs of nodes of the DAG having a dependency between the nodes, creating an edge between the nodes.

5. The method of claim 1 , wherein sorting the nodes comprises:
marking levels for all nodes of the DAG as level 0;
initializing a set of nodes of the DAG to include nodes of the DAG having zero outgoing edges;
while the set of nodes is non-empty:
removing a node from the set of nodes;
determining a current level value as the level of the node; and
for each predecessor node of the node, inserting the predecessor node into the set of nodes and, if the predecessor node has a level less than the current level, incrementing the current level value.

6. The method of claim 5 , further comprising constructing a reverse topological sort order dictionary having, for each of the hierarchical levels of the DAG, data representing node groups including nodes at the hierarchical level and numbers of outgoing edges of the nodes.

7. The method of claim 6 , wherein querying the two or more network devices comprises, for each node group of the reverse topological sort order dictionary:
sending request for synchronizing resources of the node in parallel;
for each of the resources for which a response is received, determining nodes of the sorted DAG from which there is an edge to the resource and reducing data representing the number of outgoing edges by one; and
proceeding to a next node of the node group having a value of zero for the data representing the number of outgoing edges or, if there are no next nodes of the node group, a next node group of the node groups of the reverse topological sort order dictionary.

8. A controller device that manages a plurality of network devices, the controller device comprising one or more processors implemented in circuitry and configured to:
determine that configuration of one or more network devices of the plurality of network devices is to be updated;
determine dependencies between types of resources provided by the network devices;
construct a directed acyclic graph (DAG) representing the dependencies, the DAG having nodes representing the corresponding types of resources of the network devices of the plurality of network devices;
sort the nodes of the DAG according to a grouped topological sort into a plurality of hierarchical levels according to the dependencies; and
submit queries for two or more resources of the network devices at a common level of the plurality of hierarchical levels in parallel to determine resources of the determined types of resources of the two or more resources to configure the two or more network devices.

9. The controller device of claim 8 , wherein the one or more processors are configured to determine that a first type of resource depends on a second type of resource when configuration information for the first type of resource refers to configuration information for the second type of resource.

10. The controller device of claim 8 , wherein to construct the DAG, the one or more processors are configured to create a graph edge from a first node of the DAG to a second node of the DAG when a first type of resource of a first network device corresponding to the first node depends on a second type of resource of a second network device corresponding to the second node.

11. The controller device of claim 8 , wherein to construct the DAG, the one or more processors are configured to, for all pairs of nodes of the DAG having a dependency between the nodes, create an edge between the nodes.

12. The controller device of claim 8 , wherein to sort the nodes, the one or more processors are configured to:
mark levels for all nodes of the DAG as level 0;
initialize a set of nodes of the DAG to include nodes of the DAG having zero outgoing edges;
while the set of nodes is non-empty:
remove a node from the set of nodes;
determine a current level value as the level of the node; and
for each predecessor node of the node, insert the predecessor node into the set of nodes and, if the predecessor node has a level less than the current level, increment the current level value.

13. The controller device of claim 12 , wherein the one or more processors are further configured to construct a reverse topological sort order dictionary having, for each of the hierarchical levels of the DAG, data representing node groups including nodes at the hierarchical level and numbers of outgoing edges of the nodes.

14. The controller device of claim 13 , wherein to query the two or more network devices, the one or more processors are configured to, for each node group of the reverse topological sort order dictionary:
send request for synchronizing resources of the node in parallel;
for each of the resources for which a response is received, determine nodes of the sorted DAG from which there is an edge to the resource and reducing data representing the number of outgoing edges by one; and
proceed to a next node of the node group having a value of zero for the data representing the number of outgoing edges or, if there are no next nodes of the node group, a next node group of the node groups of the reverse topological sort order dictionary.

15. A computer-readable storage medium having stored thereon instructions that, when executed, cause a processor of a controller device that manages a plurality of network devices to:
determining that configuration of one or more network devices of the plurality of network devices is to be updated;
determining dependencies between types of resources provided by the network devices;
constructing a directed acyclic graph (DAG) representing the dependencies, the DAG having nodes representing the corresponding types of resources of the network devices of the plurality of network devices;
sorting the nodes of the DAG according to a grouped topological sort into a plurality of hierarchical levels according to the dependencies; and
submitting queries for two or more resources of the network devices at a common level of the plurality of hierarchical levels in

Assignees

• Juniper Networks Inc

Inventors

• Hosamani Vijaya Kumar
• Kathireddy Vinaya Kumar
• Seerapu Adithya Shasa Sai

Classifications

• H04L41/0894

  Policy-based network configuration management · CPC title

• H04L47/782 Primary

  Hierarchical allocation of resources, e.g. involving a hierarchy of local and centralised entities · CPC title

• H04L41/082 Primary

  the condition being updates or upgrades of network functionality · CPC title

• H04L41/0806

  for initial configuration or provisioning, e.g. plug-and-play · CPC title

• H04L41/0893

  Assignment of logical groups to network elements · CPC title