Patent Description:
A computer network is a collection of interconnected computing devices that can exchange data and share resources. A variety of devices operate to facilitate communication between the computing devices. For example, a computer network may include routers, switches, gateways, firewalls, and a variety of other devices to provide and facilitate network communication.

These network devices typically include mechanisms, such as management interfaces, for locally or remotely configuring the devices. By interacting with the management interface, a client can perform configuration tasks as well as perform operational commands to collect and view operational data of the managed devices. For example, the clients may configure interface cards of the device, adjust parameters for supported network protocols, specify physical components within the device, modify routing information maintained by a router, access software modules and other resources residing on the device, and perform other configuration tasks. In addition, the clients may allow a user to view current operating parameters, system logs, information related to network connectivity, network activity or other status information from the devices as well as view and react to event information received from the devices.

Network configuration services may be performed by multiple distinct devices, such as routers with service cards and/or dedicated service devices. Such services include connectivity services such as Layer Three Virtual Private Network (L3VPN), Virtual Private Local Area Network Service (VPLS), and Peer to Peer (P2P) services. Other services include network configuration services, such as Dotlq VLAN Service. Network management systems (NMSs) and NMS devices, also referred to as controllers or controller devices, may support these services such that an administrator can easily create and manage these high-level network configuration services.

In particular, user configuration of devices may be referred to as "intents. " An intent-based networking system lets administrators describe the intended network/compute/storage state. User intents can be categorized as business policies or stateless intents. Business policies, or stateful intents, may be resolved based on the current state of a network. Stateless intents may be fully declarative ways of describing an intended network/compute/storage state, without concern for a current network state.

Intents may be represented as intent data models, which may be modeled using unified graphs. Intent data models may be represented as connected graphs, so that business policies can be implemented across intent data models. For example, data models may be represented using connected graphs having vertices connected with has-edges and reference (ref) edges. Controller devices may model intent data models as unified graphs, so that the intend models can be represented as connected. In this manner, business policies can be implemented across intent data models. When Intents are modeled using a unified graph model, extending new intent support needs to extend the graph model and compilation logic.

In order to configure devices to perform the intents, a user (such as an administrator) may write translation programs that translate high-level configuration instructions (e.g., instructions according to an intent data model, which may be expressed as a unified graph model) to low-level configuration instructions (e.g., instructions according to a device configuration model). As part of configuration service support, the user/administrator may provide the intent data model and a mapping between the intent data model to a device configuration model.

In order to simplify the mapping definition for the user, controller devices may be designed to provide the capability to define the mappings in a simple way. For example, some controller devices provide the use of Velocity Templates and/or Extensible Stylesheet Language Transformations (XSLT). Such translators contain the translation or mapping logic from the intent data model to the low-level device configuration model. Typically, a relatively small number of changes in the intent data model impact a relatively large number of properties across device configurations. Different translators may be used when services are created, updated, and deleted from the intent data model.

<CIT> relates to an entity e.g. web server, inventory storage system for e.g. firewall, having child/terminal nodes linked to a parent node by relation so that entity versions and group of versions of child or terminal nodes form part of parent node version group.

<CIT> relates to a configuration representation and modeling using configuration spaces.

In general, this disclosure describes techniques for managing network devices. A network management system (NMS) device, also referred to herein as a controller device, may configure network devices using low-level (that is, device-level) configuration data, e.g., expressed in Yet Another Next Generation (YANG) data modeling language. Moreover, the controller device may manage the network devices based on the configuration data for the network devices. According to the techniques of this disclosure, the controller device may maintain a graph data structure including a trie node to represent deviations in device level configuration models for a common model of network device (e.g., two different versions of configuration schemas for the same model of network device). That is, each trie node may represent the model for a path in the configuration schema. The trie node may indicate whether, for example, certain configuration parameters are not applicable to a particular version of the model of network device and/or whether additional schema properties are added for the particular version of the model of network device.

In one example, a method of managing a plurality of network devices includes maintaining, by a controller device that manages a plurality of network devices, a graph data structure representing device level configuration schemas for the plurality of network devices, the graph data structure including trie nodes for every first device level configuration schema element for a first model of a version of a network device of the plurality of network devices; obtaining, by the controller device, a corresponding second device level configuration schema element for a second model of the version of the network device, where obtaining the second device level configuration schema element comprises: loading, by the controller device, the second device level configuration schema element, and/or compiling, by the controller device, an intent model including data for the second model of the version of the network device to produce the second device level configuration schema element; determining, by the controller device, a deviation between the second device level configuration schema element and a first device level configuration schema element of the first device level configuration schema elements; updating, by the controller device, the trie node to add a branch to a node representing the second device level configuration schema element; and managing network devices of the plurality of network devices matching the particular version of the network device using the trie node of the graph data structure, where managing the network devices comprises: managing network devices that correspond to the first model of the version of the network device using the first device level configuration schema element; and managing network devices that correspond to the second model of the version of the network device using the second device level configuration schema element.

In another example, a controller device manages a plurality of network devices. The controller device includes one or more processing units implemented in circuitry and configured to maintain, by a controller device that manages a plurality of network devices, a graph data structure representing device level configuration schemas for the plurality of network devices, the graph data structure including trie nodes for every first device level configuration schema element for a first model of a version of a network device of the plurality of network devices; obtain, by the controller device, a corresponding second device level configuration schema element for a second model of the version of the network device, wherein obtaining the second device level configuration schema element comprises: loading, by the controller device, the second device level configuration schema element, and/or compiling, by the controller device, an intent model including data for the second model of the version of the network device to produce the second device level configuration schema element; determine, by the controller device, a deviation between the second device level configuration schema element and a first device level configuration schema element of the first device level configuration schema elements; update, by the controller device, the trie node to add a branch to a node representing the second device level configuration schema element; and manage network devices of the plurality of network devices matching the particular version of the network device using the trie node of the graph data structure, wherein managing the network devices comprises: managing network devices that correspond to the first model of the version of the network device using the first device level configuration schema element; and managing network devices that correspond to the second model of the version of the network device using the second device level configuration schema element.

In another example, a computer-readable medium has stored thereon instructions that, when executed, cause a processor of a controller device that manages a plurality of network devices to maintain, by a controller device that manages a plurality of network devices, a graph data structure representing device level configuration schemas for the plurality of network devices, the graph data structure including trie nodes for every first device level configuration schema element for a first model of a version of a network device of the plurality of network devices; obtain, by the controller device, a corresponding second device level configuration schema element for a second model of the version of the network device, wherein obtaining the second device level configuration schema element comprises: loading, by the controller device, the second device level configuration schema element, and/or compiling, by the controller device, an intent model including data for the second model of the version of the network device to produce the second device level configuration schema element; determine, by the controller device, a deviation between the second device level configuration schema element and a first device level configuration schema element of the first device level configuration schema elements; update, by the controller device, the trie node to add a branch to a node representing the second device level configuration schema element; and manage network devices of the plurality of network devices matching the particular version of the network device using the trie node of the graph data structure, wherein managing the network devices comprises: managing network devices that correspond to the first model of the version of the network device using the first device level configuration schema element; and managing network devices that correspond to the second model of the version of the network device using the second device level configuration schema element.

<FIG> is a block diagram illustrating an example including elements of an enterprise network <NUM> that are managed using a controller device <NUM>. Managed elements 14A-<NUM> (collectively, "elements <NUM>") of enterprise network <NUM> include network devices interconnected via communication links to form a communication topology in order to exchange resources and information. Elements <NUM> (also generally referred to as network devices or remote network devices) may include, for example, routers, switches, gateways, bridges, hubs, servers, firewalls or other intrusion detection systems (IDS) or intrusion prevention systems (IDP), computing devices, computing terminals, printers, other network devices, or a combination of such devices. While described in this disclosure as transmitting, conveying, or otherwise supporting packets, enterprise network <NUM> may transmit data according to any other discrete data unit defined by any other protocol, such as a cell defined by the Asynchronous Transfer Mode (ATM) protocol, or a datagram defined by the User Datagram Protocol (UDP). Communication links interconnecting elements <NUM> may be physical links (e.g., optical, copper, and the like), wireless, or any combination thereof.

Enterprise network <NUM> is shown coupled to public network <NUM> (e.g., the Internet) via a communication link. Public network <NUM> may include, for example, one or more client computing devices. Public network <NUM> may provide access to web servers, application servers, public databases, media servers, end-user devices, and other types of network resource devices and content.

Controller device <NUM> is communicatively coupled to elements <NUM> via enterprise network <NUM>. Controller device <NUM>, in some examples, forms part of a device management system, although only one device of the device management system is illustrated for purpose of example in <FIG>. Controller device <NUM> may be coupled either directly or indirectly to the various elements <NUM>. Once elements <NUM> are deployed and activated, administrators <NUM> uses controller device <NUM> (or multiple such management devices) to manage the network devices using a device management protocol. One example device protocol is the Simple Network Management Protocol (SNMP) that allows controller device <NUM> to traverse and modify management information bases (MIBs) that store configuration data within each of managed elements <NUM>. Further details of the SNMP protocol can be found in <NPL>. As another example, Network Configuration Protocol (NETCONF) provides mechanisms for configuring network devices and uses an Extensible Markup Language (XML)-based data encoding for configuration data, which may include policy data. NETCONF is described in <NPL>.

In common practice, controller device <NUM>, also referred to as a network management system (NMS) or NMS device, and elements <NUM> are centrally maintained by an IT group of the enterprise. Administrators <NUM> interacts with controller device <NUM> to remotely monitor and configure elements <NUM>. For example, administrators <NUM> may receive alerts from controller device <NUM> regarding any of elements <NUM>, view configuration data of elements <NUM>, modify the configurations data of elements <NUM>, add new network devices to enterprise network <NUM>, remove existing network devices from enterprise network <NUM>, or otherwise manipulate the enterprise network <NUM> and network devices therein. Although described with respect to an enterprise network, the techniques of this disclosure are applicable to other network types, public and private, including LANs, VLANs, VPNs, and the like.

In some examples, administrators <NUM> uses controller device <NUM> or a local workstation to interact directly with elements <NUM>, e.g., through telnet, secure shell (SSH), or other such communication sessions. That is, elements <NUM> generally provide interfaces for direct interaction, such as command line interfaces (CLIs), web-based interfaces, graphical user interfaces (GUIs), or the like, by which a user can interact with the devices to directly issue text-based commands. For example, these interfaces typically allow a user to interact directly with the device, e.g., through a telnet, secure shell (SSH), hypertext transfer protocol (HTTP), or other network session, to enter text in accordance with a defined syntax to submit commands to the managed element. In some examples, the user initiates an SSH session <NUM> with one of elements <NUM>, e.g., element 14F, using controller device <NUM>, to directly configure element 14F. In this manner, a user can provide commands in a format for execution directly to elements <NUM>.

Further, administrators <NUM> can also create scripts that can be submitted by controller device <NUM> to any or all of elements <NUM>. For example, in addition to a CLI interface, elements <NUM> also provide interfaces for receiving scripts that specify the commands in accordance with a scripting language. In a sense, the scripts may be output by controller device <NUM> to automatically invoke corresponding remote procedure calls (RPCs) on the managed elements <NUM>. The scripts may conform to, e.g., extensible markup language (XML) or another data description language.

Administrators <NUM> uses controller device <NUM> to configure elements <NUM> to specify certain operational characteristics that further the objectives of administrators <NUM>. For example, administrators <NUM> may specify for an element <NUM> a particular operational policy regarding security, device accessibility, traffic engineering, quality of service (QoS), network address translation (NAT), packet filtering, packet forwarding, rate limiting, or other policies. Controller device <NUM> uses one or more network management protocols designed for management of configuration data within managed network elements <NUM>, such as the SNMP protocol, NETCONF protocol, or a derivative thereof, such as the Juniper Device Management Interface, to perform the configuration. Controller device <NUM> may establish NETCONF sessions with one or more of elements <NUM>.

Controller device <NUM> may be configured to compare a new intent data model to an existing (or old) intent data model, determine differences between the new and existing intent data models, and apply the reactive mappers to the differences between the new and old intent data models. In particular, controller device <NUM> determines whether the new data model includes any additional configuration parameters relative to the old intent data model, as well as whether the new data model modifies or omits any configuration parameters that were included in the old intent data model.

The intent data model may be a unified graph model, while the low-level configuration data may be expressed in YANG, which is described in Bjorklund, "YANG-A Data Modeling Language for the Network Configuration Protocol (NETCONF)," Internet Engineering Task Force, RFC <NUM>, Oct. <NUM>, available at tools. org/html/rfc6020. In some examples, the intent data model may be expressed in YAML Ain't Markup Language (YAML). Controller device <NUM> may include various reactive mappers for translating the intent data model differences. These functions are configured accept the intent data model (which may be expressed as structured input parameters, e.g., according to YANG or YAML). The functions are also configured to output respective sets of low-level device configuration data model changes, e.g., device configuration additions and removals. That is, y1 = f1(x), y2 = f2(x),. yN = fN(x).

Controller device <NUM> may use YANG modeling for intent data model and low-level device configuration models. This data may contain relations across YANG entities, such as list items and containers. As discussed in greater detail below, controller device <NUM> may convert a YANG data model into a graph data model, and convert YANG validations into data validations. Techniques for managing network devices using a graph model for high level configuration data is described in "CONFIGURING AND MANAGING NETWORK DEVICES USING PROGRAM OVERLAY ON YANG-BASED GRAPH DATABASE," <CIT> (<CIT>.

Controller device <NUM> may receive data from one of administrators <NUM> representing any or all of create, update, and/or delete actions with respect to the unified intent data model. Controller device <NUM> may be configured to use the same compilation logic for each of create, update, and delete as applied to the graph model.

In general, controllers, like controller device <NUM>, use a hierarchical data model for intents, low-level data models, and resources. The hierarchical data model can be based on YANG or YAML. The hierarchical data model can be represented as a graph, as discussed above. Modern systems have supported intents to ease the management of networks. Intents are declarative. To realize intents, controller device <NUM> attempts to select optimal resources. Customer environments may be configured to allow customers (e.g., administrators <NUM>) to control intent realization and assure programmed intents.

YANG may be used as a data modeling language to manage configuration and state for managed network devices, such as elements <NUM>. Elements <NUM> may support YANG as a data modeling language, while controller device <NUM> may use YANG modeling for a vendor agnostic configuration model. Elements <NUM> of enterprise network <NUM> may include various vendor devices, models, and software versions (e.g., operating system versions).

Network management systems may use a device model schema to check whether an intent change (abstract configuration) is valid for particular network devices of elements <NUM>, to merge configuration, to generate data representing differences between configuration (configuration delta), and configlets. In general, configlets allow users, such as administrators <NUM>, to manage configuration of any configurable parameter in profiles for elements <NUM>. Thus, controller device <NUM> may provide data representing each of the available configurable parameters for each of elements <NUM>, which may depend on software versions installed on elements <NUM>. Elements <NUM> themselves may use translators to convert from an abstract data model to a native data model. That is, elements <NUM> may support open configuration YANG data models natively.

Controller device <NUM> may further compile intents to form low-level (i.e., device level) configuration, as noted above. In some instances, two or more device-level configuration schemas may be produced for a model of network device. For example, there may be multiple different configuration schemas for a particular model of a switch or router, e.g., because different instances of the switch or router may have different versions of an operating system (such as JUNOS) installed. Thus, compilation of intents or other high-level configuration data may result in two or more device-level configuration for network devices of the same model (e.g., different versions of the same model of network device).

In accordance with the techniques of this disclosure, controller device <NUM> may maintain a graph data structure (e.g., modeled in YANG) to include device level configuration schemas. In particular, when two or more device level configuration schemas are available for a model of network device, controller device <NUM> may store a trie-type node including branches for each element of respective device level configuration schema. These techniques are discussed in greater detail below.

Using a trie-type node in this manner provides an efficient way of loading and maintaining a hierarchical schema in memory. For example, these techniques may provide an efficient way of keeping both a "device model" schema and one or more "version" schemas in memory, without having multiple copies of the schemas. There may be many models (m) of network devices and versions (n) of each model, and thus, these techniques may be used to avoid maintaining m*n variations of the schemas. Thus, these techniques may be used to address memory constraint issues of previous techniques for managing network devices using multiple schemas. These techniques also support on demand loading of schemas for new models and device versions.

Elements <NUM> may support open configuration modules, although such modules are not yet mature. RFC <NUM> indicates that YANG versions are to be backward compatible. As open configuration/IETF modules are still being developed, it is not yet possible to maintain a YANG version standard. Opencofig (described at www. openconfig. net/docs/semver) follows the Semantic version. When the Semantic version is followed, there should be an efficient way to load schemas into memory.

In distributed architectures, functionality may spread across microservices. These microservices may need to access the schema of certain fields. In these applications, there should be a way to load the schema to microservices and load the required properties alone. A data structure may be provided to support on demand loading of schema properties. Suppose, for example, a configuration manager requires a data type, list, and key properties from a schema. A configlet designer microservice may require all of the properties, such as enumeration (enum) values, description, leaf default type, extensions, and the like. A system should be able to load a few properties alone, and later the data structure should support loading the additional properties. This disclosure describes techniques to support such on demand loading of schema properties.

In general, according to the techniques of this disclosure, controller device <NUM> may be configured to use a variant of a trie data structure (generally referred to herein simply as a "trie data structure") within a graph data structure to maintain deviations alone between multiple schema element versions. That is, the trie data structure may include separate branches for each version of a schema element. Using a trie data structure in this way may improve memory usage and access speed. While loading schemas into the trie data structure, the trie data structure expands. Controller device <NUM> may be configured with a threshold value and, once the trie data structure exceeds the threshold value, controller device <NUM> may adjust nodes in the trie data structure to shrink the trie data structure. This may further improve memory usage and access speed. Use of the trie data structure to store schema elements may reduce the memory footprint of the graph data structure. The trie data structure of this disclosure may be used in many scenarios where values with deviations are to be populated. Although generally described with respect to storing a device-level configuration model for network devices, the trie data structure may be used when storing a model representing hardware inventory, the meanings of words in a dictionary for various sublanguages, or other uses.

<FIG> is a block diagram illustrating an example set of components for controller device <NUM> of <FIG>. In this example, controller device <NUM> includes control unit <NUM>, network interface <NUM>, and user interface <NUM>. Network interface <NUM> represents an example interface that can communicatively couple network device <NUM> to an external device, e.g., one of elements <NUM> of <FIG>. Network interface <NUM> may represent a wireless and/or wired interface, e.g., an Ethernet interface or a wireless radio configured to communicate according to a wireless standard, such as one or more of the IEEE <NUM> wireless networking protocols (such as <NUM> a/b/g/n or other such wireless protocols). Controller device <NUM> may include multiple network interfaces in various examples, although only one network interface is illustrated for purposes of example.

Control unit <NUM> represents any combination of hardware, software, and/or firmware for implementing the functionality attributed to control unit <NUM> and its constituent modules and elements. When control unit <NUM> includes software or firmware, control unit <NUM> further includes any necessary hardware for storing and executing the software or firmware, such as one or more processors or processing units. In general, a processing unit may include one or more microprocessors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or any other equivalent integrated or discrete logic circuitry, as well as any combinations of such components. Furthermore, a processing unit is generally implemented using fixed and/or programmable logic circuitry.

User interface <NUM> represents one or more interfaces by which a user, such as administrators <NUM> (<FIG>) interacts with controller device <NUM>, e.g., to provide input and receive output. For example, user interface <NUM> may represent one or more of a monitor, keyboard, mouse, touchscreen, touchpad, trackpad, speakers, camera, microphone, or the like. Furthermore, although in this example controller device <NUM> includes a user interface, administrators <NUM> need not directly interact with controller device <NUM>, but instead may access controller device <NUM> remotely, e.g., via network interface <NUM>.

In this example, control unit <NUM> includes user interface module <NUM>, network interface module <NUM>, and management module <NUM>. Control unit <NUM> executes user interface module <NUM> to receive input from and/or provide output to user interface <NUM>. Control unit <NUM> also executes network interface module <NUM> to send and receive data (e.g., packets) via network interface <NUM>. User interface module <NUM>, network interface module <NUM>, and management module <NUM> may again be implemented as respective hardware units, or in software or firmware, or a combination thereof.

Functionality of control unit <NUM> may be implemented as one or more processing units in fixed or programmable digital logic circuitry. Such digital logic circuitry may include one or more microprocessors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or any other equivalent integrated or discrete logic circuitry, as well as any combination of such components. When implemented as programmable logic circuitry, control unit <NUM> may further include one or more computer readable storage media storing hardware or firmware instructions to be executed by processing unit(s) of control unit <NUM>.

Control unit <NUM> executes management module <NUM> to manage various network devices, e.g., elements <NUM> of <FIG>. Management includes, for example, configuring the network devices according to instructions received from a user (e.g., administrators <NUM> of <FIG>) and providing the user with the ability to submit instructions to configure the network devices. In this example, management module <NUM> further includes configuration module <NUM> and translation module <NUM>.

Management module <NUM> is configured to receive intent unified-graph-modeled configuration data for a set of managed network devices from a user, such as administrators <NUM>. Such intent unified-graph-modeled configuration data may be referred to as an "intent data model. " Over time, the user may update the configuration data, e.g., to add new services, remove existing services, or modify existing services performed by the managed devices. The unified intent data model may be structured according to, e.g., YANG or YAML. The graph model may include a plurality of vertices connected by edges in a hierarchical fashion. In YANG, edges of graph models are represented though "leafref' elements. In the case of YAML, such edges may be represented with a "ref' edge. Similarly, parent to child vertex relations can be represented with a "has" edge. For example, a vertex for Element A refers to a vertex for Element B using a has-edge can be understood to mean, "Element A has Element B. " In some examples, management module <NUM> also provides the user with the ability to submit reactive mappers that translation module <NUM> executes to transform the intent data model to device-specific, low-level configuration instructions.

Controller device <NUM> also includes configuration database <NUM>. Configuration database <NUM> generally includes information describing managed network devices, e.g., elements <NUM>. Configuration database <NUM> may act as an intent data store, which may be used to persist and manage collections of intent data models. For example, configuration database <NUM> may include information indicating device identifiers (such as MAC and/or IP addresses), device type, device vendor, devices species (e.g., router, switch, bridge, hub, etc.), or the like. Configuration database <NUM> also stores current configuration information (e.g., intent data model, or in some cases, both intent data model and low-level configuration information) for the managed devices (e.g., elements <NUM>).

Translation module <NUM> determines which of reactive mappers <NUM> to execute on the intent data model based on the information of configuration database <NUM>, e.g., which of the devices are to receive the low-level configuration instructions. Translation module <NUM> then executes each of the determined reactive mappers of reactive mappers <NUM>, providing the intent data model to the reactive mappers as input and receiving low-level configuration instructions. Translation module <NUM> may also be referred to as an intent compiler, which is a service containing a set of mappers, such as reactive mappers <NUM>.

Configuration module <NUM> may first determine an existing intent data model for each service performed by the devices for which configuration is to be updated, e.g., by retrieving the intent data model for each of the services from configuration database <NUM>. Configuration module <NUM> may then compare the existing intent data model (also referred to herein as a deployed graph model) to the newly received intent data model, and determine differences between the existing and newly received intent data models (also referred to as an undeployed graph model). Configuration module <NUM> may then add these changes to the compiler stream, and reactive mappers <NUM> may then translate these changes to low-level configuration information. The changes may be included in a change set, which may be a list containing intent graph vertices and corresponding version identifiers. Management module <NUM> may use the change set to track the list of vertices changed in an intent update. After the intent has been committed, management module <NUM> may use the change set to update vertex states in the intent graph model. Configuration module <NUM> also updates the existing intent data model recorded in configuration database <NUM> based on the newly received intent data model.

In some examples, reactive mappers <NUM> that perform update translations (that is, translating changes in the unified intent data model that results in updates to values of low-level configuration information, without creation or deletion of elements in the low-level configuration data) may operate as follows. In one example, the reactive mappers <NUM> that perform updates may override single elements. That is, performance of these reactive mappers may result in deletion of an element value, e.g., by replacing an old element value with a new value. Sometimes, a single value in a configuration service model can be mapped to a list in a device configuration. In these cases, translation module <NUM> may send the old value as well as the new value.

Translation module <NUM> (which may be configured according to reactive mappers <NUM>) may use the same reactive mapper for creation, updates, and deletion of intent data model vertices. Because each vertex has its own corresponding reactive mapper, compilation can be performed in parallel. That is, the reactive mappers of each of the vertices of the graph model representing the unified intent data model can be executed in parallel, thereby achieving parallel compilation. Translation module <NUM> may be configured to allow processing of only impacted intent data model data changes (i.e., those elements in the intent data model that are impacted by the changes). Based on reactive mappers <NUM>, translation module <NUM> may infer dependencies across vertices in the intent data model. When the intent data model is changed, translation module <NUM> may publish messages in the compiler stream based on a dependency graph, as discussed above.

When a "create" template is uploaded (that is, a reactive mapper of reactive mappers <NUM> that processes new data in intent data model configuration information, relative to existing intent data model configuration information), translation module <NUM> may determine the dependencies using the dependency graph. When the service is changed, translation module <NUM> may generate a difference between the existing intent data model configuration information and the new intent data model configuration information, based on the dependencies. Translation module <NUM> may then use the reactive mapper of reactive mappers <NUM> to process the difference, and thereby translate the intent data model configuration information to low-level configuration instructions. Translation module <NUM> may then provide the low-level configuration instructions to configuration module <NUM>.

After receiving the low-level configuration instructions from translation module <NUM>, configuration module <NUM> sends the low-level configuration instructions to respective managed network devices for which configuration is to be updated via network interface module <NUM>. Network interface module <NUM> passes the low-level configuration instructions to network interface <NUM>. Network interface <NUM> forwards the low-level configuration instructions to the respective network devices.

Although user interface <NUM> is described for purposes of example as allowing administrators <NUM> (<FIG>) to interact with controller device <NUM>, other interfaces may be used in other examples. For example, controller device <NUM> may include a representational state transfer (REST) client (not shown) that may act as an interface to another device, by which administrators <NUM> may configure controller device <NUM>. Likewise, administrators <NUM> may configure elements <NUM> by interacting with controller device <NUM> through the REST client.

Management module <NUM> may model configuration database <NUM> as a graph data structure (or graph database) representing YANG configuration data elements. YANG specifies various types of data structures, including lists, leaflists, containers, containers with presence, and features. Management module <NUM> may model each of lists, containers, containers with presence, and features, as well as a top-level container, as vertices in a graph data structure. Alternatively, configuration database <NUM> may represent YAML configuration data elements.

In some cases, management module <NUM> may manage multiple different models of devices of the same version of network device. For example, a particular version of a router or switch may have multiple different models, each having its own sets of particular configuration parameters, while also sharing a common set of configuration parameters for the version generally. In accordance with techniques of this disclosure, management module <NUM> may maintain graph data structures including trie data structures for each configuration element. The trie data structures may represent the common set of configuration parameters and deviations from the common set of configuration parameters for the various models of the version of the network device.

The trie data structure may include branches for each model of the version of the network device having a deviation in a corresponding device-level configuration data schema element. Thus, when managing (e.g., configuring) a model of the network device, management module <NUM> may determine appropriate configuration parameters using a corresponding branch of the trie data structure.

After constructing the graph data structure, management module <NUM> may perform operations on data of the graph data structure. For example, management module <NUM> may map Netconf-based operations, such as get-config, get-config with filters, and edit-config, to graph query language queries, such as Gremlin queries. Gremlin is described in GremlinDocs at gremlindocs. spmallette. documentup. com and in github. com/tinkerpop/gremlin/wiki. Management module <NUM> may execute conditions mapped to vertices and edges of the graph data structure if the condition attributes are changed. In response to the conditions, management module <NUM> may process additional changes, handled as functions as discussed in greater detail below. Management module <NUM> may further update all changes in transaction semantics.

In this manner, controller device <NUM> represents an example of a controller device that manages a plurality of network devices and includes one or more processors implemented in circuitry and configured to maintain a graph data structure representing device level configuration schemas for the plurality of network devices, the graph data structure including trie nodes for every first device level configuration schema element for a first model of a version of network device of the plurality of network devices; obtain a second device level configuration schema elements based on a path for a second model of the version of the network device; determine a deviation between the second device level configuration schema element and the first device level configuration schema; and update the trie node to add a branch to a node representing the second device level configuration schema element.

<FIG> is a graph illustrating an example hash map data structure <NUM>. Hash map data structure <NUM> includes a root configuration (config) node <NUM>, virtual local area networks (VLANS) node <NUM>, interfaces (IFs) node <NUM>, filters node <NUM>, VLAN node <NUM>, identifier (ID) node <NUM>, name node <NUM>, and filter name node <NUM>. In this example, there are edges from config node <NUM> to each of VLANS node <NUM>, IFs node <NUM>, and filters node <NUM>. VLANS node <NUM> has an edge to VLAN node <NUM>, and VLAN node <NUM> has edges to each of ID node <NUM>, name node <NUM>, and filter name node <NUM>.

Hash map data structure <NUM> is one example of a data model that is hierarchical in nature. Nodes of hash map data structure <NUM> may be identified by schema paths, where child nodes of a common parent node share a common prefix for the schema path. Controller device <NUM> may maintain a schema for each path. The paths include, for example:.

Conventionally, a controller device such as controller device <NUM> would maintain such a hash map with a path as key and a schema as a value for the key. However, this can lead to a large amount of memory consumption when many different models of a common version of network device are managed. Thus, according to the techniques of this disclosure, controller device <NUM> may represent deviations among configuration elements for various models of a common version of network device using a trie data structure.

<FIG> is a graph illustrating an example graph data structure <NUM> including a trie data structure <NUM> according to the techniques of this disclosure. In this example, graph data structure <NUM> includes family node <NUM>. Family node <NUM> represents a family of devices, e.g., a family of routers or a family of switches. Family node <NUM> includes edges to child version nodes 84A-84D (version nodes <NUM>). For example, version node 84A may represent version <NUM> of a switch, version node 84B may represent version <NUM> of the switch, version node 84C may represent version <NUM> of the switch, and version node 84D may represent version <NUM> of the switch.

In this example, version node 84A is the root of trie data structure <NUM>. A conventional trie data structure has branches for each character in a string. The trie data structure of this disclosure is a variant of the conventional trie data structure, in that multiple characters of the string may be used in each node to describe a path for reaching the node. For example, model node 86A may represent model "<NUM>" of version <NUM> of the switch, model node 88A may represent model "<NUM>-24T" of version <NUM> of the switch, and model node 88B may represent model "<NUM>-48T" of version <NUM> of the switch. Model node 86B may represent model "<NUM>" of version <NUM> of the switch.

Each of model nodes 86A, 86B, 88A, and 88B may correspond to deviations of schemas for version <NUM> of the switch (i.e., the version represented by version node 84A). Schema nodes 90A-90D of <FIG> may generally represent variations for a schema element. For example, schema node 90A may represent deviations for a schema element for model node 86A relative to version node 84A, schema node 90B may represent deviations for a schema element for model node 86B relative to version node 84A, schema node 90C may represent deviations for a schema element for model node 88A relative to model node 86A, and schema node 90A may represent a deviations for a schema element for model node 88B relative to model node 86A.

In this manner, graph data structure <NUM> represents a pattern in device configuration management. In general, there are fewer variations in schemas within a device family for a given version of a device in the device family. There may be no schema changes in a patch and various releases. There may be deviations on a model starting from a device version, and a new schema element may be supported starting from a particular version of a device. Using the techniques of this disclosure represented in <FIG> may represent deviations in schema elements alone, rather than full schemas for each of the models corresponding to model nodes 86A, 86B, 88A, and 88B. Thus, memory storage and access speed may be improved using the techniques of this disclosure. The trie according to the techniques of this disclosure may take the value of the hierarchical schema trie node. That is, the nodes of trie data structure <NUM> may take values of the corresponding models for model nodes 86A, 86B, 88A, 88B.

<FIG> is a conceptual diagram illustrating a graph <NUM> representing correspondence between a node and a value represented in a trie data structure for the node. In this example, graph <NUM> includes filter name node <NUM> corresponding to value represented in trie <NUM>. As noted above, a trie may include a value for a hierarchical schema trie node.

<FIG> are graphs illustrating example graph data structures following loading of various example schemas according to the techniques of this disclosure. Assume, for example, that IEEE <NUM> X is supported on all switch platforms of version <NUM>, except for model <NUM>, and that IEEE <NUM> X is not supported in security devices and routers. An example loading order of schemas for family names, models, and versions of devices is shown below:.

<FIG> includes root node <NUM>, which may represent the entire graph data structure following steps A-C above. That is, no deviations are included among configuration for the various devices in the security and switch families of devices for version <NUM> and <NUM> for IEEE <NUM> X under the assumptions stated above, and thus, no additional nodes are needed.

<FIG> includes root node <NUM> with an edge to family node <NUM> (representing the switch family of devices), family node <NUM> having an edge to version node <NUM> (representing version <NUM> of a switch), and version node <NUM> having edges to model nodes 116A, 116B, and 116C. <FIG> represents a state of the graph data structure following steps C, D, an E discussed above. Under the assumptions stated above, there is a deviation between model <NUM> and model <NUM> of switch version <NUM>, because model <NUM> supports IEEE <NUM> X, whereas model <NUM> does not. Thus, controller device <NUM> may construct the graph data structure to add model nodes 116A, 116B, and 116C to indicate support for IEEE <NUM> X and set configuration information accordingly, whereas version node 114A may indicate that IEEE <NUM> X is not supported for other models generally.

As noted above, in some examples, controller device <NUM> may be configured with a threshold value for a number of deviations for a schema element. In this example, the threshold value may be <NUM>. After the threshold value is met or exceeded, controller device <NUM> may reconfigure the graph data structure to switch what is considered a deviation and what is considered standard across the version. Thus, after step G, in which yet another switch model (model <NUM>) has support for IEEE <NUM> X, controller device <NUM> may reconfigure the graph data structure to indicate support for IEEE <NUM> X for version <NUM> of a switch, with a deviation for model <NUM>. Accordingly, <FIG> represents the state of the graph data structure following step G above with the reconfigured graph data structure. In particular, <FIG> illustrates root node <NUM> with an edge to family node <NUM>. Family node <NUM> in this example has an edge to version node <NUM> (representing version <NUM> of the switch), and version node <NUM> has an edge to model node <NUM>. In this example, version node <NUM> may indicate support for IEEE <NUM> X generally, and model node <NUM> may indicate that for model <NUM>, IEEE <NUM> X is not supported. There is no change to the graph data structure after step H.

After having constructed the graph data structure of <FIG>, retrieval of a schema element for a security device of version <NUM>, <NUM>, <NUM>, or <NUM> would take only one lookup (being root node <NUM>). Retrieval of the schema element for a switch of version <NUM> generally would take two lookups, corresponding to version node <NUM>.

Controller device <NUM> may be configured to perform a graph data structure insertion algorithm according to the techniques of this disclosure. The graph data structure insertion algorithm may be as follows:
insertSchema(Trie, path[],Element) {
Path [] = =[Family, Version, Model]
Element= SchemaElement
If the Trie is empty, Create Root Tree node with Element and add to Trie
If the Trie is not empty:
Call UpdateElement(root, paths, Element)
}.

Controller device <NUM> may also be configured to perform a graph data structure element update algorithm, as follows:
UpdateElement (TrieNode,keyPath[] Value) {
Check TrieNode have children with key path[<NUM>]
If children not found, and the value is same as TrieNode value
Append the path to Non deviated elements (This step is optional, this can
be maintained globally for schemas)
Break;
If children are found, and the value is same as matched children value,
Append the path to Non deviated elements (This step is optional, this can
be maintained globally for schemas). Break;
If children is found, and the value is not same as matched children value
If the keyPath. length is <NUM>
Create/update ChildTrieNode with value and attach to TrieNode
If the number of Children matches the threshold
Call AdjustDeviations(TrieNode)
else
Call UpdateElement(matchedChildNode,
ReaminingKeyPath, Value).

Controller device <NUM> may also be configured to perform a graph data structure adjust deviations algorithm, as follows:.

Controller device <NUM> may also be configured to perform a graph data structure lookup schema algorithm, as follows:.

<FIG> are graphs illustrating example graph data structures following further loading of various example schemas according to the techniques of this disclosure. <FIG> represents the state of the graph data structure of <FIG> following step H (which as noted above, does not change the graph data structure). In this example, suppose the schema element needs to be expanded with additional properties for models <NUM>, <NUM>, and <NUM> of version <NUM> of a switch. As noted above, in these examples, version node <NUM> represents version <NUM> of the switch.

Controller device <NUM> may expand the graph data structure of <FIG> to form the graph data structure of <FIG>, which further includes model nodes 122A, 122B, for models <NUM> and <NUM>, respectively. Model nodes 122A, 122B indicate support for the additional schema properties discussed above.

Upon loading additional schema properties for model <NUM>, controller device <NUM> may determine that the threshold value (of <NUM>, continuing the examples discussed above) has been exceed, and therefore, may form the graph data structure of <FIG>. The graph data structure of <FIG> includes root node <NUM>, family node <NUM>, version node <NUM>, and model node <NUM>. In this example, version node <NUM> includes data representing support for the additional schema properties discussed above, whereas model node <NUM> indicates that this schema element is not supported, as discussed above.

Controller device <NUM> may be configured to perform the insertion algorithm discussed above. When updating the trie node, controller device <NUM> may determine whether the trie node already exists, and updates the trie node accordingly. Controller device <NUM> may use the graph data structure to ensure deviations are set properly, while updating the trie nodes. In some examples, controller device <NUM> may further assign digital numbers for all model and version combinations, so that each schema element trie consumes less memory.

In this manner, the techniques of this disclosure include the following:.

<FIG> is a flowchart illustrating an example method for performing techniques of this disclosure, e.g., for managing network devices. The method of <FIG> is explained with respect to controller device <NUM>, although other devices may be configured to perform this or a similar method.

Initially, controller device <NUM> loads a schema for a first model of a version of a device in a graph data structure (<NUM>). Controller device <NUM> may then construct trie data structures for each schema element (<NUM>). For example, as shown in <FIG>, the trie data structure may initially start with root node <NUM>. Controller device <NUM> then loads a schema for a second model of the version of the device (<NUM>). In this example, it is assumed that the schema for the second model has at least one schema element that is a deviation relative to the first schema. Accordingly, controller device <NUM> adds a branch to the node for the second model to the trie data structure (<NUM>). Controller device <NUM> also stores the deviated schema element in the branch node of the trie data structure (<NUM>). For example, as shown in <FIG>, controller device <NUM> may add family node <NUM>, version node <NUM>, and model node 116A for the second model of the version of the network device to store a deviated schema element for the second model.

Additionally, controller device <NUM> may determine whether a number of deviated schema elements from branches of the node of the trie data structure exceeds a threshold (<NUM>). If the number of deviated elements exceeds the threshold ("YES" branch of <NUM>), controller device <NUM> may swap the property of the deviated elements (that is, the branch node(s)) with the corresponding property of the node (<NUM>). For example, as shown in <FIG>, controller device <NUM> may replace version node <NUM> with version node <NUM>, and remove the branch nodes for models 116A, 116B, 116C (and add model <NUM> as a branch node from version node <NUM>). On the other hand, if the number of deviated elements does not exceed the threshold ("NO" branch of <NUM>), or after performing the swap of <NUM>, controller device <NUM> may configure managed network devices using the graph data structure (<NUM>).

In this manner, the method of <FIG> represents an example of a method including maintaining, by a controller device that manages a plurality of network devices, a graph data structure representing device level configuration schemas for the plurality of network devices, the graph data structure including trie nodes for every first device level configuration schema element for a first model of a version of network device of the plurality of network devices; obtaining, by the controller device, a second device level configuration schema elements based on a path for a second model of the version of the network device; determining, by the controller device, a deviation between the second device level configuration schema element and the first device level configuration schema element; and updating, by the controller device, the trie node to add a branch to a node representing the second device level configuration schema element.

Therefore, from one perspective there has been described a controller device that can manage a plurality of network devices. The controller device includes one or more processing units implemented in circuitry and configured to maintain a graph data structure representing device level configuration schemas for the plurality of network devices, the graph data structure including trie nodes for every first device level configuration schema element for a first model of a version of network device of the plurality of network devices; obtain corresponding second device level configuration schema elements based on a path for a second model of the version of the network device; determine a deviation between the second device level configuration schema element and the first device level configuration schema; and update the trie node to add a branch to a node representing the second device level configuration schema element.

For example, various aspects of the described techniques may be implemented within one or more processors, including one or more microprocessors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or any other equivalent integrated or discrete logic circuitry, as well as any combination of such components.

The techniques described in this disclosure may also be embodied or encoded in a computer-readable medium, such as a computer-readable storage medium, containing instructions. Instructions embedded or encoded in a computer-readable medium may cause a programmable processor, or other processor, to perform the method, e.g., when the instructions are executed. Computer-readable media may include non-transitory computer-readable storage media and transient communication media. Computer readable storage media, which is tangible and non-transitory, may include random access memory (RAM), read only memory (ROM), programmable read only memory (PROM), erasable programmable read only memory (EPROM), electronically erasable programmable read only memory (EEPROM), flash memory, a hard disk, a CD-ROM, a floppy disk, a cassette, magnetic media, optical media, or other computer-readable storage media. The term "computer-readable storage media" refers to physical storage media, and not signals, carrier waves, or other transient media. As noted above, computer readable media may include transient communication media. Such communication media may occur within a single computer system or between multiple computer systems, and may take the form of transient signal-conveying media such as carrier waves and transmission signals.

Claim 1:
A method of managing a plurality of network devices, the method comprising:
maintaining (<NUM>, <NUM>), by a controller device that manages a plurality of network devices, a graph data structure representing device level configuration schemas for the plurality of network devices, the graph data structure including trie nodes for every first device level configuration schema element for a first model of a version of a network device of the plurality of network devices;
obtaining (<NUM>), by the controller device, a corresponding second device level configuration schema element for a second model of the version of the network device, wherein obtaining the second device level configuration schema element comprises:
loading, by the controller device, the second device level configuration schema element, and/or
compiling, by the controller device, an intent model including data for the second model of the version of the network device to produce the second device level configuration schema element;
determining, by the controller device, a deviation between the second device level configuration schema element and a first device level configuration schema element of the first device level configuration schema elements;
updating (<NUM>, <NUM>), by the controller device, the trie node to add a branch to a node representing the second device level configuration schema element; and
managing network devices of the plurality of network devices matching the particular version of the network device using the trie node of the graph data structure, wherein managing the network devices comprises:
managing network devices that correspond to the first model of the version of the network device using the first device level configuration schema element; and
managing network devices that correspond to the second model of the version of the network device using the second device level configuration schema element.