Using transactions to compute and propagate network forwarding state

The present invention relates to the use of transactions to minimize churn in distributed network control systems.

Many of today's enterprises have large advanced networks that include switches, hubs, routers, servers, workstations and other network equipment that support a variety of connections, applications and systems. With the increasing sophistication of computer networking, including virtual machine movement, dynamic workload, multi-tenancy, and customer-specific quality of service and security configurations, network control systems are needed to accommodate this. Distributed network control systems are provided to distribute and process these large-scale advanced networks. However, in many cases, network state changes made by one component of a distributed network control system spill back and forth through the rest of the system, resulting in churn in the distributed network control system.

Some embodiments of the present invention provide a particular network controller that receives input from a first controller and a second controller in an upper layer of a hierarchy formed by a plurality of network controllers. The particular controller should be identical to the output produced by processing the inputs from the first and second controls and only the inputs from the first controller. Produce output.

In particular, certain controls of some embodiments receive a first set of inputs from a first controller and a second set of inputs from a second controller. The particular control then begins the calculation of the output set using the first input set. After the failure of the first controller, the particular controller receives a third set of inputs from the second controller. The third input set and the first input set or the second input set form an input group that is processed together and is processed separately from another input group.

The particular control then receives an indicator from the second control that all inputs in the input group have arrived at the particular control. A particular control sends the output set to a fourth controller or managed transfer element after receiving the indicator and fully calculating the output set. The fourth controller then processes the output set from the particular controller and sends the processed output to the managed transfer element.

Some embodiments of the present invention further provide network controls in the middle layer of the hierarchy that receive input from each of a plurality of different controls in the upper layer of the hierarchy. Inputs from higher layer controls are served as multiple different transactions. In some embodiments, lower layer controls generate output from inputs received from different controls and output the generated output as a single transaction to a set of lower layer controls in the hierarchy. To do.

Specifically, the intermediate layer network controls receive multiple input groups from a set of higher layer network controls. Each input group is processed together and separately from another input group. If an input group meets certain conditions, the intermediate layer network control processes two or more of the input groups together to produce an output set. If the input groups do not meet certain conditions, the network control processes the input groups and produces an output set by processing each input group together. The network controller then sends out the output set generated in the lower layer set of controls.

The outline of the invention described above is intended to be a brief description of some embodiments of the invention. This is not intended to be an explanation or summary of the subject matter of all inventions disclosed herein. The embodiments described in the outline of the invention and other embodiments will be further described with reference to the following embodiments for carrying out the invention and the drawings referenced therein. Therefore, in order to understand all the embodiments described herein, it is necessary to read all the outlines of the invention, the embodiments and drawings for carrying out the invention. Furthermore, the claims are not limited by the outline of the invention, the forms for carrying out the invention and the exemplary details in the drawings, as they can be realized in other particular forms without departing from the gist of the subject matter of the invention. , Defined by the appended claims.

The novel features of the present invention are described in the appended claims. However, for illustration purposes, a plurality of embodiments of the present invention are described in the drawings below.<figref num="1">FIG. 1 is a diagram showing an example of a hierarchy of network controls.</figref><figref num="2">FIG. 2 is a diagram showing the architecture of the network controller of some embodiments.</figref><figref num="3">FIG. 3 is a diagram conceptually showing a physical control that receives an input from a logical control.</figref><figref num="4">FIG. 4 is a diagram conceptually showing the processing performed by some embodiments to process the failover of the source control existing in the upper layer in the network control hierarchy.</figref><figref num="5">FIG. 5 is a diagram conceptually showing a physical control that receives an input from a logical control.</figref><figref num="6">FIG. 6 is a diagram conceptually showing a physical control that receives input changes from a plurality of logical controls.</figref><figref num="7">FIG. 7 is a diagram conceptually showing the processing performed by some embodiments to generate a set of transaction output changes from input changes that form a plurality of transactions.</figref><figref num="8">FIG. 8 is a diagram showing a network control system in which a network control distributes a request from a user to managed transfer elements and returns a response to the request to the user.</figref><figref num="9">FIG. 9 is a diagram showing logical controllers of some embodiments that aggregate general-purpose responses received from a set of physical controllers.</figref><figref num="10">FIG. 10 shows several embodiments performed to aggregate a set of responses from lower layers of lower layers in a hierarchy of controls to generate a single response to be passed to higher layers of higher layers in the hierarchy. It is a figure which shows the process to perform conceptually.</figref><figref num="11">FIG. 11 is a diagram conceptually showing an electronic system in which some embodiments of the present invention are realized.</figref>

In the following detailed description of the invention, many details, examples and embodiments of the invention will be described and described. However, it will be apparent to those skilled in the art that the invention is not limited to the embodiments described and may be practiced without some of the specific details and examples described.

Some embodiments provide a network control system that computes transfer state information that a network controller pushes to a set of managed transfer elements to define the transfer behavior of the set of managed transfer elements. In some embodiments, the network controls form a hierarchy with multiple control layers. The set of logical controls is located at the top layer of the hierarchy and generates general-purpose physical control plane data from the input logical control plane data. The sublayer of the set of logical controls is the set of physical controls, which, in some embodiments, customizes the general purpose physical control plane data to the physical control plane data specific to the managed transfer element.

In some embodiments, the physical control relays general purpose physical control plane data to a set of chassis controls that actually perform customizations to the managed transfer element. In these embodiments, the chassis controller resides in the lowest layer of the hierarchy formed by the controller. The physical control or chassis control interfaces with the managed transfer element and supplies the managed transfer element with customized physical control plane data. The managed transfer element uses the data received from the control to transfer the data over the network.

A particular control in the upper layer of the hierarchy supplies its output data to another control in the lower layer of the hierarchy. In some embodiments, the particular control acts as a hot standby or redundant control for the particular control (eg, providing the same output data to the lower layer controls in the hierarchy). Are on the same layer. In some embodiments, the lower layer controls generate their own output from the output data received from a particular control.

In the event of a failure of a particular control, the lower layer controls should (1) ensure that the output data does not change by processing the same output data from the backup control. Generates its own output data from the output data received up to that point and (2) the output data from the backup control. That is, after the failure of the specific control occurs, the lower layer control receives and processes the output data including the same data as the data received from the specific control before the failure occurs from the backup control. However, the lower layer control is from the backup control so that the output data of the lower layer control is the same as the output data when it is generated by processing only the output data from a particular control. Process the output data of.

The controls in the lower layers of the hierarchy receive output data from each of a plurality of different controls in the upper layer. The output data from the upper layer controls is supplied as a number of different transactions. In some embodiments, lower layer controls generate their own output data from output data received from different controls, with their output data as a single transaction and a set of lower layer controls. Send to.

More detailed embodiments will be described in the following sections. In detail, Section I first describes some embodiments of network control systems that control logical and physical networks. Next, in Section II, the minimum update speed will be explained. Section III describes an electronic system in which some embodiments of the present invention are realized.

I. Network control system FIG. 1 shows a network control system 100 that computes transfer state information that a network controller pushes to a set of managed transfer elements to define the transfer behavior of the set of managed transfer elements. The network control system 100 includes a logical control 110, two physical controls 115 and 120, and three managed transfer elements 125-135. Network control system 100 represents a simplified example in which two physical controllers 115 and 120 push state to three managed transfer elements. Often, the network control system of some embodiments comprises a large number of controls and hundreds or thousands of managed transfer elements.

In some embodiments, network controllers 110-120 perform a transfer state calculation and push that state to the managed transfer element in the form of a flow entry. The network controller of some embodiments receives the logical control plane (LCP) data that defines the logical network and converts the LCP data into physical control plane (PCP) data to the managed transfer elements 125-135. Send out. In some embodiments, the logical control plane of a logical network defines one or more logical transfer elements (eg, logical switches, logical routers) that connect end machines (eg, virtual machines) in a logical address space. The logical transfer element defines how packets from the source machine are forwarded to the destination machine in logical space (eg, the association between the logical port and the MAC address of the virtual machine). Further, in some embodiments, the LCP defines a logical policy (eg, an access control list) implemented by a logical transfer element. The LCP and its structure are unknown to the physical network in which the LCP and its structure are realized.

The network controller of some embodiments performs a number of different transformations of the LCP data in order to reach the PCP data pushed to the managed transfer element. In some embodiments, the controller transforms the LCP data into logical transfer plane (LFP) data and then the LFP data into PCP data. LFP data defines a forwarding entry for forwarding a packet in logical space. That is, the LFP data contains an entry indicating that the packet is forwarded to the logical port if the addresses match, rather than simply associating the logical port with the address.

The conversion of LFP data to PCP data incorporates a logical transfer entry into the physical network. The PCP entry contains information for performing a transfer in the logical address space within the physical network (eg, mapping a logical port to a physical port).

In some embodiments, the calculation of PCP to push to the managed transfer element is distributed among different control layers within the hierarchy formed by the controls. For example, in some embodiments, the logical controller 110 manages at least one logical transfer element. The logical controller 110 executes the conversion from LCP to LFP and the subsequent conversion from LFP to general-purpose PCP (UPCP), as shown in the right half of FIG. UPCP data includes flow entries. These flow entries are not customized to contain data specific to any managed transfer element, only abstract concepts (eg, port numbers, tunnel identifiers, etc.) for data specific to a particular physical implementation. Including.

In some embodiments, the logical controller that manages a particular logical transfer element sends UPCP data to one or more physical controllers. For example, the logical controller 110 sends UPCP data to the two physical controllers 115 and 120. Each of the managed transfer elements is managed by the master physical controller. Therefore, UPCP data for a logical transfer element realized across a plurality of managed transfer elements may be sent to a plurality of different master physical controls that manage those transfer elements. As shown, the physical controller 115 is a master controller that manages two managed transfer elements 125 and 130. The physical controller 120 is a master controller that manages the managed transfer element 135.

UPCP data is converted to customized PCP (CPCP) data in either the physical control or the chassis control in the same physical machine as the managed transfer element (not shown in Figure 1). CPCP data is physical control plane data in which customized data specific to a specific managed transfer element is entered. As mentioned, in some embodiments, the physical controller uses the information received from the managed transfer element to perform the transformation. In another embodiment, the physical control acts as a waypoint to send UPCP data to the host machine where the managed transfer element resides, in which case the logic of the control (chassis control) goes from UPCP to CPCP. Perform the conversion.

The managed transfer elements 125 to 135 are software or hardware transfer elements managed by a network control (for example, receiving transfer status information from the network control). In some embodiments, the managed transfer element is a software transfer element that runs on the host machine (eg, in the host machine's user space and / or kernel). These managed transfer elements receive packets from end machines 140-160, perform logical processing on the packets, and are connected to different destinations (eg, different managed transfer elements as well) over the physical network. Send a packet to the end machine).

The end machines 140 to 160 may be physical machines or virtual machines. In some embodiments, the virtual machine end machines operate within the same host that has a managed forwarding element that forwards packets to them. Virtual machines belonging to multiple physical networks may be located within a single host machine (for example, end machines 140 and 145 may be located within the same host machine where the managed transfer element 125 is located. Good), each of the managed transfer elements may implement a plurality of different logical transfer elements. Moreover, as mentioned above, a single logical transfer element is generally implemented across many managed transfer elements.

In addition to managed transfer elements located at the network edge on hosts with virtual machines, some embodiments also include second level unedge managed transfer elements (sometimes referred to as pool nodes or service nodes). .. If the edge-managed forwarding element cannot perform all of the processing on the packet (for example, because it does not have a flow entry that links the destination MAC address to the logical port), the pool node can process the packet and send it to the destination. , The edge managed transfer element sends a packet to the pool node.

FIG. 2 conceptually shows an example of the architecture of the network controller 200 of some embodiments. The network controller 200 can function as a logical controller, a physical controller, or a chassis controller, depending on the type of data it processes.

If it is a logical control, the network control 200 receives LCP data as an input. In some embodiments, the network controller 200 converts the LCP data into LFP data and then into UPCP data. The network controller 200 pushes UPCP data to a set of physical controls that are masters of managed transfer elements that implement the logical transfer elements managed by the network controller 200, which is a logical control.

In the case of the physical controller of some embodiments, the network controller 200 receives the UPCP data as an input and converts the UPCP data into CPCP data. The network controller then pushes CPCP data to a set of managed transfer elements for which the network controller 200 is the master. In another embodiment, the network controller 200, which is a physical controller, relays UPCP data to a set of chassis controllers operating on a host on which the set of managed transfer elements operates. In these embodiments, the network controller 200 is the master of this set of managed transfer elements.

If it is a chassis controller, network controller 200 receives UPCP data from a set of physical controllers as input. The network controller 200 converts the UPCP data into CPCP data for the managed transfer element managed by the chassis controller, and sends the CPCP data to the managed transfer element.

As shown in FIG. 2, the network controller 200 includes a rule engine input table set 210, a function table and constant table set 215, an importer 220, a rule engine 225, a rule engine output table set 245, a converter 250, and an exporter. Includes 255, non-temporary transaction database (PTD) 260 and compiler 235. Compiler 235 is one component of a control that operates at a different time than the other components of the control. The compiler works when the developer needs to specify a rule engine for a particular network control and / or virtual environment, and the remaining modules of the control allow the control to be another control or a managed transfer element. Works at runtime when interfacing with.

In some embodiments, the compiler 235 receives a relatively small set (eg, hundreds of lines) of declarative instructions 240 specified in the declarative language and performs a table mapping of the controls. Convert these into a large set (eg, thousands of lines) of code (ie, object code) that specifies the behavior of. In this way, the compiler greatly simplifies the process of defining and updating a network control by the developer of the network control. It allows developers to use an advanced programming language that allows developers to compactly define complex mapping behaviors for network controls, and is subsequently supported by any number of changes (eg, network controls). This is because the mapping operation can be updated in response to a change in the logical networking function, a change to the desired behavior of the network controller, etc.). In addition, the compiler eliminates the need for developers to consider the order in which events arrive at network controls when defining mapping behavior. The developer also programs the network controller 200 with a different set of rules so that the network controller 200 functions as a logical controller, a physical controller, or a chassis controller.

In some embodiments, the rules engine (RE) input table 210 includes a table that has different types of data based on what type of network control the network controller 200 operates as. When the network controller 200 operates as a logical control, the input table 210 contains LFP data that needs to be mapped to LFP data and LFP data that needs to be mapped to UPCP data. When the network controller 200 operates as a physical controller or chassis controller, the input table 210 contains UPCP data that needs to be mapped to CPCP data.

In addition to the RE input table 210, the network controller 200 includes various other tables 215 that the rules engine 225 uses to collect inputs for table mapping operations. These tables 215 include constant tables that store constant values for the constants that the rules engine 225 needs to perform table mapping operations. For example, the constant table 215 sets the constant "zero" defined as the value 0, the constant "dispatch_port_no" defined as the value 4000, and the constant "broadcast_MAC_addr" defined as the value 0xFF: FF: FF: FF: FF: FF. Including.

When the rule engine 225 references a constant, the corresponding value defined for the constant is actually searched and used. In addition, the values defined for the constants in the constant table 215 may be changed and / or updated. In this way, the constant table 215 provides the ability to change the values defined for the constants referenced by the rule engine 225 without having to rewrite or recompile the code that specifies the behavior of the rule engine 225. Table 215 further includes a function table that contains the functions required by the rules engine 225 to be used to calculate the values needed to populate output table 245.

Rule engine 225 performs a table mapping operation that specifies one way to convert input data to output data. Every time one of the Rule Engine (RE) input tables is modified, the Rule Engine performs a set of table mapping operations, resulting in one or more data tuples in one or more RE output tables being modified. To. In some embodiments, the network control system uses a variant of the datalog database language called nLog to create the rules engine 225. Like data logs, nLog provides a small number of declarative rules and operators that allow developers to specify different actions to be taken when different events occur. In some embodiments, nLog provides a limited subset of the operators provided by datalog to speed up the operation of nLog. For example, in some embodiments, nLog only allows the use of the AND operator in any of the declarative rules.

As shown in FIG. 2, the rule engine 225 includes an event processor 222, a plurality of query plans 227, and a table processor 230. Each query plan is a set of rules that specifies a set of join actions to be performed when a change occurs in one of the RE input tables. Hereinafter, such a change is referred to as an input table event. Each query plan is generated by compiler 235 from one declarative rule in declarative set 240. In some embodiments, two or more query plans are generated from one declarative rule. For example, a query plan is created for each of the tables joined by one declarative rule. That is, if the declarative rule specifies that four tables should be joined, four different query plans are created from this one declaration. In some embodiments, the query plan is defined by using the declarative language of nLog.

The event processor 222 of the rule engine 225 detects the occurrence of each input table event. Event processors of different embodiments detect the occurrence of input table events in different ways. In some embodiments, the event processor registers in a callback with the RE input table for notification of changes to the records in the RE input table. In such an embodiment, the event processor 222 detects an input table event when it receives a notification from the RE input table that one of the records has changed.

In response to the detected input table event, the event processor 222 (1) selects the appropriate query plan for the detected table event and (2) instructs the table processor 230 to execute the query plan. In some embodiments, in order to execute the query plan, the table processor 230 performs the join operation specified by the query plan and one or more data from one or more input tables 210 and various tables 215. Generate one or more records that represent the value set. The table processor 230 of some embodiments then performs (1) a selection operation that selects a subset of data values from the records generated by the join operation, and (2) is selected for one or more RE output tables 245. Write a subset of the data values.

In some embodiments, the RE output table 245 stores the data attributes of both the logical and physical network elements. If table 245 stores the output of the rule engine 225 table mapping operation, then table 245 is called the RE output table. In some embodiments, the RE output table is grouped into a number of different categories. For example, in some embodiments, these tables may be RE input tables and / or control output tables. If a change in the table causes the rules engine to detect an input vent that requires execution of the query plan, then the table is an RE input table. The RE output table 245 may also be the RE input table 210 that generates an event that causes the rules engine to execute another query plan. Such an event is called an internal input event, which is contrasted with an external input event, which is an event caused by a change in the RE input table generated by the importer 220.

If a change in a table causes exporter 255 to export the change to another control or managed transfer element, the table is a control output table. The table in the RE output table 245 may be an RE input table, a control output table, or both an RE input table and a control output table. In some embodiments, the RE input table and the RE output table are relational database management system (RDBMS) tables. These tables are stored as the data structure of the relational database, which is the primary data storage structure of the network control.

Exporter 255 detects changes to the control output table in RE output table 245. Exporters of different embodiments detect the occurrence of control output table events in different ways. In some embodiments, the exporter registers in a callback with the control output table for notification of changes to the records in the control output table. In such an embodiment, exporter 255 detects an output table event when it receives a notification from the control output table that one of the records has changed.

In response to the detected output table event, exporter 255 gets some or all of the modified data tuples in the modified control output table and uses the modified data tuples with other controls or Propagate to the managed transfer element. Specifically, when the network control 200 acts as a logical control, the exporter 255 is physically via a set of communication channels established with the physical control (eg, a remote procedure call (RPC) channel). Propagate UPCP data to a set of controls. When the network control 200 operates as a physical control, the exporter 255 of some embodiments propagates UPCP data to a set of chassis controls through a set of communication channels established with the chassis controls. To do. The exporter 255 of another embodiment propagates CPCP data to a set of managed transfer elements via a pair of communication channels established with each managed transfer element (eg, OpenFlow channels and configuration channels). When the network controller 200 operates as a chassis controller, the exporter 255 of some embodiments is managed via a pair of communication channels (eg, OpenFlow and configuration channels) to and from each managed transfer element. Propagate CPCP data to a set of transfer elements.

In some embodiments, the network control does not hold data in the output table 245 that it is not responsible for managing. However, such data is converted by the converter 250 into a format that can be stored in the PTD and stored in the PTD 260. PTD is the secondary storage structure of the network controller. The PTD of the network controller 200 propagates the data to one or more other network controllers, thereby allowing some network controllers responsible for managing the data within those network controllers to manage the data. Can be processed.

In some embodiments, the network control further stores the data stored in the output table 245 (ie, the data that the network control is responsible for managing) in the PTD for data recovery. Such data is similarly transformed by the transducer 250, stored in the PTD, and propagated to other PTDs in other control instances. Therefore, in these embodiments, the PTD of the control instance has all the configuration data for all the data managed by the network control system. That is, in some embodiments, each PTD contains an overview of the configuration of logical and physical networks.

The importer 220 interfaces with many different input data sources and uses the input data to modify or create the input table 210. The importer 220 of some embodiments is an input conversion controller that converts user input (eg, in the form of an application programming interface (API) call) into LCP data when the network controller 200 operates as a logical control. Receive input data from the user (tenant) via (not shown). In some embodiments, the importer 220 receives LCP data over a communication channel. The importer 220 further interfaces with the PTD 260 so that the data received from other control instances via the PTD can be used as input data to modify or create the input table 210. In addition, the importer 220 also detects changes in the RE input table and control output table of the RE output table 245. The LFP data generated and stored in the output table 245 is fed back to the rule engine 225 by the importer 220 for the rule engine 225 to generate UPCP data.

When the network control 200 operates as a physical control, the importer 220 acquires UPCP data from the set of logical controls via a set of communication channels established with the set of logical controls. When the network controller 200 operates as a chassis controller, the importer acquires UPCP data from the set of physical controls via a set of communication channels established with the set of physical controls.

Up to this point in FIG. 2, the input table 210 contains inputs from the controls in the upper layer of the controller hierarchy, and the output table 245 outputs to the controls or the set of managed transfer elements in the lower layers of the controller hierarchy. Explained that it includes. Inputs and outputs may be transmitted and received in opposite directions. That is, in such a case, the network controller takes the input from the lower layer controller or the managed transfer element and sends the output to the upper layer controller. For example, the network controller 200 may receive a request sent by a user and distribute the request to a set of lower layer controls or a set of managed transfer elements. These distributed requests reach the managed transfer element, which creates the response. The response returns to network control 200 as input via the importer. The rule engine 255 performs a table mapping operation to combine the responses and generate a response to send to the control that sent the request to the network control 200. Further details regarding the processing of requests and responses will be described later with reference to FIGS. 9 and 10.

Having described a network control system in which network controls form a hierarchy, Section II below describes how to combine transactions to minimize churn in a network control system.

II. Minimize update speed A. Sorting of external inputs In a network control system, a network controller manages the network state in order to realize a logical network across a physical network. The network state is not immutable, and if the state changes, state updates need to be distributed across the network to managed transfer elements. These network state updates occur for at least three reasons. First, when the logical policy changes because the network policy implemented by the logical pipeline is reconfigured (for example, the administrator of the logical network updates the access control list), the network state changes. Second, the network state changes as a result of changes in workload behavior. For example, if you move a virtual machine from a first node to a second node, the logical perspective does not change. However, because the physical location of the logical port to which the VM connects is different, this move requires the network state to be updated. Third, network conditions can change as a result of physical reconfiguration events such as device additions, removals, upgrades, and reconfigurations.

A typical user-driven policy configuration change causes a small gradual change, and the gradual change to the transfer state can be calculated efficiently, but the input to the nLog calculation engine changes significantly due to failover conditions. There is. Consider a receiver controller that is configured to receive input from a sender controller and the sender controller fails and the new controller includes the task of the sender controller. .. Since the new control is a backup control, the state was pre-computed, but the receiving control still needs to fail over from the old source to the new source.

In some embodiments, the receiving control simply deletes all inputs received from the failed control (cancels the effects of the inputs), almost even if the old and new inputs are not exactly the same. It feeds the nLog compute engine with new inputs from the new controller, even if it can be expected to be very likely to be the same. The transactionality of a calculation prevents the transfer state change from being exposed before a new source is launched and the calculation reaches a fixed point (eg, when the calculation is performed on a given input data). However, the calculation overhead is enormous. The entire transfer state is calculated twice, first calculated to eliminate the state and then to reestablish the state.

In some embodiments, the receiving controller identifies the difference between the input from the old source and the input from the new source and calculates the transfer state change only for the changed input. This completely eliminates the overhead. However, when using the transaction calculation and fixed point arrival functions, the receiving control of some embodiments can obtain the same result without distinguishing the differences. In order to gradually and efficiently transition from one source of input to another without identifying differences, network control systems do not simply start by removing the input from the old source, but rather old. Supply the input from the new source to the compute engine while still using the input from the source. The network control system then waits for the new source to reach a fixed point for the input from the new source, then deletes the input from the old source after the new source reaches such a fixed point. ..

By reordering the external inputs / events in this way, the nLog computing engine of some embodiments can detect duplicates and avoid the overhead of completely removing the old state. The receiving control does not commit the transaction until the new source reaches a fixed point because there is no need to remove the state from the old source. When the new source reaches a fixed point, the receiving control pushes changes to the transfer state (ie, output state) due to the changed input to the consumer transfer element. If the changes are significant, this technique comes at the cost of increased temporary memory usage. In some embodiments, when the source controller reaches a fixed point, the source controller sends out a barrier. When the barrier is received by the receiving controller, the receiving controller recognizes that the sending controller has reached a fixed point.

FIG. 3 conceptually shows the physical controller 305 that receives input from the logical controller 310. In particular, FIG. 3 shows four different stages of input processing for the physical control 305 when the logical control 310 fails and the logical control 335 calculates the update and takes over the task to send to the physical control 305. It is indicated by 301 to 304. The logical controller 335 is a hot standby logical controller for the logical controller 310.

The physical controller 305 is similar to the network controller 200 described above with reference to FIG. 2 in that it includes an importer 315, a rule engine 320, an input table 325 and an output table 330 similar to the corresponding components of the controller 200. Is. For the sake of brevity, not all components of physical control 305 are shown in FIG.

In the first step 301, the logical controller 310 sends the input changes 1 and 2 indicated by the white parallelogram to the physical controller 305. Input changes are changes to one or more records in the control's input table. In some embodiments, the input modification is in the form of a data tuple. The logical controller 335 similarly sends the same changes 1 and 2 to the physical controller 305. Changes 1 and 2 sent from backup logical control 335 are shown by gray parallelograms to visually distinguish them from changes 1 and 2 from logical control 310.

In the second stage 302, the physical controller 305 received changes 1 and 2 from the logical controller 310 and changes 1 and 2 from the logical controller 335. However, the importer 315 updates the input table 325 using only changes 1 and 2 from the logical controller 310, and holds the changes 1 and 2 from the backup logical controller 335 in a storage structure (not shown). ..

In some embodiments, physical controller 305 does not recognize that logical controller 335 is a backup controller for logical controller 310. That is, when viewed from the physical controller 305, the logical controllers 310 and 335 are two controllers that supply the same input change. Physical control 305 locally determines to use the change from one of the controls and switches to the other control if the control that was using the change fails. At step 302, physical controller 305 uses modifications from logical controller 310.

Step 302 further indicates that the logical controller 310 has failed and that the logical controller 335 has sent changes 3 and 4 after the logical controller 310 has failed. Change 4 is shown with a bold frame to indicate that change 4 is the last change in the transaction from logical control 335. In other words, changes 3 and 4 form a transaction, and change 4 (or separate data after change 4) has a barrier that marks the end of the input set for a transaction. The rule engine 320 has not yet processed changes 1 and 2, for example, because it has not yet finished processing other changes (not shown).

The third stage 303 indicates that the rule engine 320 has performed a table mapping operation to generate a set of output changes from changes 1 and 2. An output change is a change made to one or more records in the control's output table as a result of performing a table mapping operation on the input table that is changed by the input change. In some embodiments, the output modification is in the form of a data tuple. To show that these output changes are the result of processing changes 1 and 2 from logical controller 310, the output changes are shown as a dashed frame containing changes 1 and 2. Also, in the third stage 303, the importer 315 updated the input table 325 with changes 1 and 2 from the logical controller 335 held in the storage structure. Also, because the logical controller 310 fails, the logical controller 335 is switched to the logical controller 335, and the changes are received from the logical controller 335, the importer 315 has changes 1 and 2 from the logical controller 310. Was removed. In addition, physical controller 305 received changes 3 and 4 from logical controller 335. The importer 315 updates the input table 325 with changes 3 and 4.

The fourth stage 304 indicates that the rule engine 320 has performed a table mapping operation and generated output changes from changes 1-4 received via backup logical controller 335. Output changes shown as dashed frames containing changes 1 to 4 did not cause the importer to update the input table twice with changes 1 and 2 (the first using changes 1 and 2 from logical controller 310). , The second time uses changes 1 and 2 from the logical controller 335) to show that it is the same as the output change generated. This is because the rules engine of some embodiments does not generate duplicate output changes by performing table mapping operations on duplicate input changes.

The logical control 335 has reached its own fixed point because the physical control has processed all the input changes that form a transaction from the upper layer controls. The physical controller 335 then sends this set of output changes to a set of managed transfer elements or a set of chassis controls. Figure 3 shows the process of failover of a logical control by a physical control. However, those skilled in the art will recognize that the chassis controller may handle failover of the physical controller as well.

FIG. 4 conceptually illustrates process 400 performed by some embodiments to handle failover of the source control in the upper layer in the network control hierarchy. Process 400 is performed by a receiving control that receives the input change from two or more source controls that generate the input change. In some embodiments, the receiving controller is a physical controller that receives an input change from a set of logical controls that generate an input change that includes UPCP data. The receiving controller may also be a chassis controller that receives input changes from a set of physical controllers that relay UPCP data. The receiving controller of some embodiments is similar to the physical controller 305 described above with reference to FIG.

Process 400 is started by receiving an input change (405) from the master source controller and the backup source controller. A backup control is a standby or redundant control that sends the same input changes that the master control sends to the receiving control. In some embodiments, the receiving controller does not know which of the two source controllers is the master controller. The receiving control selects one of them and uses the changes in the input from the selected source control to generate changes in the output of the receiving control itself. For convenience of explanation, the master source controller is the controller first selected by the receiver controller.

Next, in process 400, the output change is calculated using only the input from the master control (410). In process 400 of some embodiments, a storage structure for duplicate input changes from the backup control until a transaction (eg, a set of input changes between barriers) is fully received from the master source control. Hold in. In process 400 of some embodiments, changes in the inputs held in the storage structure are not used. In process 400 of some embodiments, changes in the input received from the master control are not removed from the input table.

In process 400, it is determined whether or not a failure has occurred in the master sender control (415). In some embodiments, the sender controller periodically transmits its own state or heartbeat, and the receiver controller uses the state to determine if the sender control is operating. In some embodiments, the receiving controller polls the sending controller to determine if the sending controller is operating. If it is determined in process 400 that a failure has occurred in the master sender controller (415), process 400 proceeds to 430. 430 will be described later.

In process 400, when it is determined that the master sending source control has not failed (415), it is determined whether a barrier has been received from the master control (420). That is, it is determined whether the received input changes form a complete transaction. If it is determined in process 400 that a complete transaction has not been received from the master source control (420), process 400 returns to 405 and changes the inputs from the master source control and backup source control. Continues to receive.

In process 400, when it is determined that a barrier has been received from the master sender controller (420), it is determined whether process 400 has reached its own fixed point (425). In the process 400 of some embodiments, when all the processes of the input changes of the transaction received from the master sender control are completed and the output changes are generated, the process 400 is determined to have reached the fixed point. To. In that case, process 400 proceeds to 450. 450 will be described later.

In process 400, when it is determined that a failure has occurred in the master sending source control (415), the switch is switched to the backup sending source control and the input change is received from the backup control (430). Then, in process 400, the output change is calculated based on the input received from the backup control (435). In some embodiments, in process 400, the retained (410) changes are further used to calculate the output changes. The retained changes are duplicate changes of the input changes from the master source control used to generate the output changes. However, in process 400, the output changes generated by processing the same input changes received from the master source controller are not deleted. At process 400, the retained duplicate input changes are still processed, but the rules engine of the receiving control that performs process 400 produces duplicate output changes by processing the duplicate input changes. do not do. In process 400 of some embodiments, changes received from the failed control are removed from the input table when switching to the backup source control.

Next, in process 400, it is determined that the barrier has been received from the backup source control (440). That is, it is determined whether the received input changes form a complete transaction. Input changes that form a complete transaction include retained duplicate input changes and input changes received from the backup control after a master control failure.

If it is determined in process 400 that the barrier has not been received (440), process 400 returns to 430 and continues to receive input changes from the backup source control. When it is determined that the barrier has been received in the process 400 (440), it is determined whether the process 400 has reached its own fixed point (425).

Then, in process 400, the calculated output change is sent to a set of controlled transfer elements that transfer data based on a set of controls or a set of outputs in a lower layer in the control hierarchy (450). In process 400 of some embodiments, a barrier is inserted at the end of the output change, or information indicating a complete transaction is added to the last change of the output change. After that, the process ends.

B. Transactions in hierarchical transfer state calculation In some embodiments, network controls form a hierarchy with two or more layers of network controls that supply updates to forwarding elements that receive updates for receiving transaction from multiple controls. In these embodiments, the top-level control computes updates in transactions, but lower-layer controls may receive updates from multiple top-level controls, as well as multiple transfer elements. Updates may be received from second level controls.

The transaction goes down unchanged at the boundary. That is, the top-level transaction processed by the second-level control is a transaction that is fed to the transfer element containing only the changes obtained as a result of the transaction received from the top-level control. However, policy consistency is maintained even if transactions are aggregated on the way to the transfer element. In some embodiments, the second level control aggregates the received transactions (which may be received from different top-level controls) and feeds the transfer element a single. Make it a transaction. It is a local decision to determine the appropriate aggregation level (if such a level exists). For example, the system does not aggregate transactions at all by default, but in an overloaded state where the number of transactions in the queue increases, it expects transactions (from the same source) to have duplicate changes that cancel each other out. A method of aggregation may be implemented. For wider networks, this technique is considered to be a type of root flap damping.

FIG. 5 conceptually shows a physical controller 505 that receives an input from the logical controller 510. In particular, FIG. 5 shows four different stages 501 through which the physical control 505 aggregates the input changes that form multiple complete transactions from the logical control 510 that supplies the physical control 505 with the input changes. Shown by 504. The physical controller 505 is similar to the network controller 200 described above with reference to FIG. 2 in that it includes an importer 515, a rule engine 520, an input table 525 and an output table 530 similar to the corresponding components of the controller 200. Is. For the sake of brevity, not all components of physical control 505 are shown in FIG.

In the first stage 501, the logical controller 510 sends input changes 1 to 3 to the physical controller 505. Changes 1 to 3 are shown with a bold frame to show that they form a complete transaction. That is, change 3 includes or involves a barrier. In step 501, the input table 525 and the output table 530 are empty because the physical controller 505 previously calculated and sent out a set of transaction output changes.

In the second stage 502, the physical controller 505 received changes 1-3 from the logical controller 510. Importer 515 updated input table 525 with changes 1-3. The second stage 502 further indicates that the logical control is sending out the next set of input changes 4 and 5 that form a transaction.

In the third stage 503, physical control 505 receives from logical control 530 the next set of input changes 4 and 5 that form a transaction. Importer 515 updates input table 525 with changes 4 and 5. The third step 503 further indicates that the rule engine 520 performed a table mapping operation to generate a set of output changes from the changes 1-3 entered in the input table 525 in the previous step 502. To show that these output changes are the result of processing changes 1-3, the output changes are shown as a dashed frame containing changes 1-3.

Also, in step 503, physical control 505 generated output changes by (1) processing a set of input changes that form a complete transaction, so the output currently present in output table 530. Determine whether to send the changes in or (2) wait for further input changes to be supplied. In some embodiments, the physical controller makes the determination based on certain criteria. For example, a physical control waits for further input changes to be supplied if a period of time has not passed since sending the last set of output changes or receiving the last transaction. In some of these embodiments, after a period of time, physical control 505 aggregates all of the input changes that form a complete transaction into a single set of transaction output changes. Generate.

Alternatively or additionally, the physical controller 505 of some embodiments considers the amount of data it has in the input table 525. In some of these embodiments, if the input table 525 has data above a threshold amount, physical control 505 aggregates all of the input changes that make up the complete transaction and outputs the transaction. Generate a single set of changes. Instead of or in addition to considering the amount of data, the physical control 505 of some embodiments considers the number of complete transactions that the input table 525 has. In some such embodiments, if the input table 525 has a complete transaction above a threshold number, the physical control aggregates the input changes that form the complete transaction and simply changes the output of the transaction. Generate a set.

In a fourth stage, 504, physical control 505 determines that an additional transaction needs to be used to generate a single set of changes in the output of the transaction. Therefore, the physical controller 505 does not send out the output changes calculated from the changes 1-3. The rules engine 520 performed table mapping operations on changes 4 and 5 to generate output changes. As shown, the output changes generated from changes 4 and 5 are grouped together with the output changes generated from changes 1-3. The physical controller 505 then sends this group of output changes to a set of managed transfer elements or a set of chassis controls.

A single set of changes in the output of a transaction forms a transaction sent to another control or managed transfer element. The transaction contains a set of changes that apply to the transfer state of the receiver managed transfer element. Thus, some embodiments of the controller combine change sets by aggregating multiple transactions on the input side and generating a single transaction to send to the output side, whereby all of those changes Applies to both managed transfer elements.

FIG. 6 conceptually shows a physical controller 610 that receives input changes from a plurality of logical controllers 635 to 645. In particular, FIG. 6 shows the behavior of the physical control 610 summarizing the input changes that form multiple transactions from multiple different logical controls into a single set of transaction output changes 601 ~ Shown by 605. The physical controller 610 is similar to the network controller 200 described above with reference to FIG. 2 in that it includes an importer 615, a rules engine 620, an input table 625 and an output table 630 similar to the corresponding components of the controller 200. Is. For the sake of brevity, not all components of the physical controller 610 are shown in FIG.

In the first step 601 the logical controller 635 sends an input change 1 to the physical controller 610. Logical control 640 sends input changes 2-4 that form a complete transaction. In step 601 the input table 625 and the output table 630 are empty because the physical control 610 previously calculated and sent out a set of transaction output changes.

In the second stage 602, physical controller 610 received changes 1-4 from logical controllers 635 and 640. The importer 615 updated the input table 625 with changes 1-4. The second stage 602 further indicates that the logical controller 645 is sending changes 5 and 6 that form a complete transaction.

In the third stage 603, the physical control 610 receives the input changes 5 and 6 forming the transaction from the logical control 645. The importer 615 updates the input table 625 with changes 5 and 6. At this point, the input table 625 has changes 1-6. The third stage 603 further indicates that the rule engine 620 performed a table mapping operation to generate output changes from the changes 1-4 entered in the input table 625 in the previous stage 602. Two sets of output changes were generated. As shown, the first set contains changes to the output generated by processing change 1. The second set contains changes to the output generated by processing changes 2-4.

Also, in step 603, physical control 610 should process changes 2-4 because (1) the physical control generated output changes by processing all input changes that form a complete transaction. Determine whether to send out these output changes generated by (2) wait for further input changes to be supplied. In some embodiments, the physical control sends out a set of specific criteria, ie, changes in the output of a transaction, or receives a complete transaction, as described above with reference to FIG. The determination is made based on the elapsed time period, the amount of data in the input table 625, and / or the number of complete transactions in the input table 625.

In step 604, physical control 610 determines that an additional transaction needs to be used to generate a single set of changes in the output of the transaction. Therefore, the physical controller 610 does not send out the output changes calculated from the input changes 2-4. The rules engine 620 performed table mapping operations on changes 5 and 6 to generate the corresponding output changes. However, as shown, in this case, the output changes calculated from the input changes 5 and 6 are grouped together with the output changes calculated from the input changes 2-4. Therefore, the physical controller 610 modifies the output by aggregating the output obtained by processing the set of input mods 2-4 and the set of input mods 5 and 6 that form two transactions. Generated a single set of.

In step 605, physical controller 610 sent a change in the output calculated from changes 2-6 to a set of chassis controllers or a set of managed transfer elements. The physical control removed changes to the output output from the output table 630. The physical control further removed input changes 2-6 from the input table 625. Step 605 indicates that the input change 1 remains in the input table 625 and the output changes calculated from the input change 1 remain in the output table 630. This is because change 1 of the input does not form a complete transaction, that is, the physical control has not received a barrier indicating that the complete transaction containing change 1 has been received in physical control 610. ..

FIG. 7 conceptually illustrates the process 700 performed by some embodiments to generate a set of transaction output changes from input changes that form multiple transactions. Process 700 is executed by the receiving control that receives the input change from two or more source controls that generate the input change. In some embodiments, the receiving controller is a physical controller that receives an input change from a set of logical controls that generate an input change that includes UPCP data. The receiving controller may also be a chassis controller that receives input changes from a set of physical controllers that relay UPCP data. The receiving side controller is the same as the physical controllers 505 and 605 of FIGS. 5 and 6.

Process 700 is started by receiving an input change (705) from the source controller. In some embodiments, changing inputs from different source controls relates to different sets of logical transfer elements. In process 700, the input changes received so far are used to calculate the output changes (710).

Then, in process 700, it is determined whether at least one complete transaction has been received from the source control (715). As mentioned above, a complete transaction involves changing the input received from a source control between receiving a barrier from one source control and receiving another barrier. If process 700 determines that it has not received at least one complete transaction (715), process 700 returns to 705 and receives further input changes from the source control.

If process 700 determines that at least one complete transaction has been received (715), process 700 proceeds to 720 to determine if a particular aggregation criterion is met. Different embodiments have different aggregation criteria. For example, in some embodiments, a particular criterion includes the time elapsed since sending the last set of output changes or receiving the last complete transaction. When this period expires, certain criteria are met. Alternatively or additionally, in some embodiments, a particular aggregation criterion includes the amount of data it has in the input table (of the receiving control performing process 700). In these embodiments, certain criteria are met if the input table has data above a threshold amount. In some of these embodiments, instead of or in addition to the amount of data, a particular criterion includes the number of complete transactions that the input table has. In these embodiments, certain criteria are met if the input table has more complete transactions than the threshold number.

The process 700 then aggregates the output changes calculated from the input changes that make up all of the complete transaction (725). In some embodiments, processing 700 excludes output changes that are calculated from input changes that do not form a complete transaction. In other words, these excluded output changes are calculated from the input changes for which the barrier has not been received.

In process 700, send out output changes aggregated in a set of controlled transfer elements that transfer data based on a set of controls or output changes that exist in a lower layer of the control hierarchy (730). In process 700 of some embodiments, a barrier is inserted at the end of the output change or information indicating the complete transaction is added to the last change of the output change. It also removes the transmitted output changes from the receiving control's output table, forming a complete transaction and using the input changes used to calculate the transmitted output changes to the receiving control's inputs. Remove from table. After that, the process ends.

C. Use case 1. API Inputs that define logical transfer elements, which are forms of application programming interface (API) calls, are sent to input conversion controls that support the API. The network control system of some embodiments renders API updates atomically. That is, a configuration change atomically shifts the system from the old state to the new state. Specifically, after receiving an API call, the API receive code in the system updates the state to the nLog engine, and after supplying all the updates, the API receive code in the system reaches a fixed point (converges the calculation). Wait and signal the transaction that is terminated by making changes to nLog. After this, all transfer state updates are sent to lower controls in the cluster hierarchy or towards the transfer element, all in a single transactional update. Updates are applied in transactions by the receiving element.

In some embodiments, API updates are transmitted across a distributed storage system (eg, a PTD in a control) as long as the updates arrive at the receiver as updates for a single transaction. That is, as long as the update is written to storage as a single transaction update and the nLog processing controller receives the update as a single transaction, the process of pushing state updates continues as described above, so nLog Updates to computational processing can be written as updates for a single transaction.

2. Control failover Consider a master logical controller that manages a set of logical transfer elements. In some embodiments, the control has a hot backup that calculates the same state and pushes that state in a manner similar to the master. One difference between the master and the hot backup is that the stream from the backup is ignored until failover begins. In the event of a master failure, the receiving control / transfer element switches to backup by gradually transitioning from the old state to the new state as follows:

Instead of removing / blocking the stream of state updates from the old master and converging the calculation towards the state where the active stream of updates is received from the higher control, simply switch to the new master and converge the calculation. , Effectively combine old and new streams. That is, it is based on the assumption that both sources produce the same or nearly identical streams. After performing this operation, the controller waits for the computation to converge by waiting for the fixed point to be reached, and then completely removes the old stream after it reaches the fixed point. Again, by waiting for the fixed point to be reached, the controller converges the calculation for use with the new source only. After this, the control completes the transition from the old source to the new source by committing the transaction. This signals the execution time of nLog to effectively pass the barrier from the underlying control / transfer element as a signal that the state update needs to be processed.

D. Processing on-demand requests Processing of API requests may be achieved using the nLog engine. In that case, the request is translated into a set of tuples that trigger the calculation of the API response by nLog and fed to the nLog engine. API responses are also represented as tuples. It is easy to wait for a response because the request and response that are tuples have a one-to-one mapping with the request and response tuples. The processing of an API request is simply to wait for a response that matches the request. When a response that matches the request arrives, it is ready to perform calculations on the response.

However, if the request / response does not have a one-to-one mapping, it is difficult to know that the request has been processed. In that case, the processing of the API request may ask for a fixed point of calculation after supplying the request. Upon reaching the fixed point, the request has all the responses generated. As long as the request and response tuples have some common identifier, it is easy to identify the response tuples, regardless of the number of response tuples. Therefore, this use case does not require the use of such commits, but the primitive that allows computation is to wait for a fixed point.

FIG. 8 shows a network control system 800 in which a network control distributes a request from a user to managed transfer elements and returns a response to the request to the user. The network control system 800 similarly calculates the transfer state information that the controller in the network control system 800 pushes to the managed transfer element to define the transfer behavior of the managed transfer element. Similar to 100. The network control system 800 includes an input conversion control 805, a logical control 810, two physical controls 815 and 820, and three managed transfer elements 825 to 835. The network control system 800 represents a simplified example in which two physical controllers 815 and 820 distribute requests to three managed transfer elements. In many cases, the network control system of some embodiments includes a large number of controls and hundreds or thousands of managed transfer elements.

The input conversion controller 805 of some embodiments receives an input from the user. These inputs include a logical network designation, which the input conversion controller converts to LCP data that the logical control later processes. In addition, the input may further include a request for information about the logical network. For example, a request from a user may ask for statistical information (for example, the amount of traffic to a logical port of a logical transfer element for a certain period of time). The input conversion controller 805 converts the request into a logical request in the form of a data tuple that the logical control later processes.

In some embodiments, the input conversion controller 805 receives input from the user in the form of an API call. The input conversion controller 805 supports APIs, and network management applications (eg, web applications or command line interface (CLI) applications) can be built on top of the APIs. The user uses a network application to get the input to the input conversion control.

In some embodiments, network controllers 810-820 perform request transformations and distribute the requests to managed transfer elements in the form of data tuples. The network controller of some embodiments performs a number of different request transformations before distributing the requests to the managed transfer elements. Specifically, the logical controller 810 receives a logical request from the input conversion controller 805. In some embodiments, the logical request is specified using the logical attributes of the logical network. An example of a logical request is a request for information about a particular logical port of a particular logical transfer element. This request is made using the name or address of the logical port and the name or address of the logical transfer element.

The logical controller 810 converts this logical request into a general-purpose request. In some embodiments, the generic request is specified using the attributes of the managed transfer element that implements the logical network. However, these attributes are expressed in abstract terms that are not specific to a particular physical implementation (eg, port number, tunnel identifier, etc.). For example, a generic request is created using the name of the physical port of one of the managed transfer elements instead of using the actual port number of the physical port.

In some embodiments, the logical controller 810 sends the general-purpose request to any number of physical controllers. For example, the logical controller 810 sends a general-purpose request to the two physical controllers 815 and 820. In some embodiments, the generic request has an identifier to identify the request. This identifier is used to match the request with the corresponding response. The response will be described later.

Each managed transfer element is managed by the master physical controller. Therefore, a logical request for a logical transfer element realized over a plurality of managed transfer elements may be sent to a plurality of different master physical controls that manage these transfer elements. As shown, physical controller 815 is a master controller that manages two managed transfer elements 825 and 830. The physical controller 820 is a master controller that manages the managed transfer element 835.

A general-purpose request is converted into a customized request in either the physical control or the chassis control in the same physical machine as the managed transfer element (not shown in FIG. 8). In some embodiments, the customized request is specified using the managed transfer element's attributes that are specific to the managed transfer element. For example, a customized request for a managed transfer element is made with the actual port number used locally for the physical port of the managed transfer element. In an embodiment where the physical controller is a transit point that sends UPCP data to the chassis controller, the physical controller is a transit point that sends general-purpose requests to the chassis controller.

The managed transfer elements 825 to 835 are the same as the managed transfer elements 125 to 135 of FIG. The end machines 840 to 860 are the same as the end machines 140 to 160 in FIG. Managed transfer elements 825-835 collect the information queried by the customized request. Each of the managed transfer elements 825 to 835 generates a customized response containing the collected information in response to the receipt of the customized request.

The managed transfer element passes a customized response to the physical control (or chassis control) on which the managed transfer element receives the customized request. In either the physical control or the chassis control, the customized response is aggregated as needed and converted into a generic response. The general-purpose response is then passed to the logical control that the physical control receives the general-purpose request.

For example, the physical controller 815 receives the customized response from the managed transfer elements 825 and 830, aggregates the customized response, and converts it into a general-purpose response. In some embodiments, physical control 820 does not need to aggregate customized responses. The physical control 820 only converts the customized response received from the managed transfer element 825, and passes the general-purpose response to the logical control 810.

The logical controller 810 receives a general-purpose response from the physical control to which the logical controller 810 has sent a general-purpose request. The logical control 810 aggregates the general-purpose response, converts the aggregated general-purpose response into a logical response, and passes the logical response to the input conversion control 805. In some embodiments, the input conversion controller 805 transforms the logical response into output that the user views through the management application.

In some embodiments, the customized response, the generic response, and the logical response are specified with the same attributes that were used to specify the customized request, the generic request, and the logical request, respectively. In some embodiments, these requests and responses are in the form of data tuples.

The controller in the hierarchy of the controller may not receive a plurality of responses from the control lower in the hierarchy. For example, if the request is to get information about a particular logical port that maps to a particular physical port on a particular managed transfer element, the logical controller sends the generic request to two or more physical controls. Get one generic response from the physical control because it does not need to be distributed.

When a control passes a response to another controller above it in the hierarchy of the control that sent the request to it, the control sends the response in a transaction. FIG. 9 shows a logical controller 910 of some embodiments that aggregates general-purpose responses received from a set of physical controllers 935, 940, and 945. In particular, Figure 9 aggregates the output changes by processing the input changes that the logical control 910 forms multiple transactions from different physical controls into a single set of transaction output changes. The operation to be performed is shown in five stages 901 to 905. In this case, the logical controller 910 passes the aggregated output changes to an input conversion controller (not shown). The aggregated output changes include a logical response containing information queried by the logical request received by the logical controller 910 from the input conversion controller.

The logical controller 910 is equivalent to the network controller 200 described above with reference to FIG. 2 in that it includes an importer 915, a rule engine 920, an input table 925 and an output table 930 similar to the corresponding components of the controller 200. Is. For the sake of brevity, not all components of logical controller 910 are shown in FIG.

In the first stage 901, the physical controller 935 sends input changes 1 to 3 to the logical controller 910. Input changes 1-3 include a general-purpose response created by the physical control 935 in response to receiving a general-purpose request from the logical control 910. In some embodiments, input changes 1-3 include a generic request identifier. The logical control 910 uses an identifier to match the response with the request.

In some embodiments, the physical controller 935 aggregates (1) a set of customized responses that the physical controller 935 receives from a set of managed transfer elements and (2) generically aggregates the aggregated customized responses. Create a generic response by converting it into a response. In another embodiment, the physical controller 935 creates a generic response by aggregating a set of generic responses that the physical controller 935 receives from a set of chassis controls (not shown). The chassis controller creates a generic response to pass to physical control 935 by aggregating a set of customized responses from a set of managed transfer elements that operate on the same host on which the chassis controller operates.

In step 901, the input table 925 and the output table 930 may include records for transfer states, requests and / or responses. For the sake of brevity, these other records are not shown in Figure 9.

In the second stage 902, the logical controller 910 received changes 1-3 from the physical controller 935. Importer 915 updated input table 925 with changes 1-3. The second stage 902 further indicates that physical control 940 is sending changes 4-6 that form a complete transaction. Control 945 is sending changes 7 and 8 that form a complete transaction. Modifications 4-6 and 7-8 include general purpose responses created by physical controllers 940 and 945 in response to receiving general purpose requests from logical control 910, respectively. In some embodiments, modifications 4-8 further include a generic request identifier.

In the third stage 903, the logical control 910 receives a set of transaction input changes 4 to 6 from the physical control 940 and a transaction input changes 7 and 8 from the physical control 945. .. The importer 915 updates the input table 925 with changes 4-8. At this point, the input table 925 has changes 1-8. The third stage 903 further indicates that the rule engine 920 performed a table mapping operation to generate output changes from the changes 1-3 entered in the input table 925 in the previous stage 902.

Also, in step 903, the logical controller 910 (1) generated an output change by processing an input change that forms a complete transaction, and thus by processing changes 1-3. Determine whether to send these generated output changes or (2) wait for further input changes, including general-purpose responses, to be delivered. The physical controller makes this determination based on certain criteria. For example, in some embodiments, the logical controller 910 waits for all of the physical controls that have received the generic request from the logical controller 910 to pass a generic response. In these embodiments, the logical controller 910 aggregates the output changes generated by processing all general purpose responses to generate a logical response. Alternatively or additionally, the logical controller 910 aggregates the output changes generated by processing the generic response received during a predetermined period of time after the generic request was sent to the physical controller. The logical control generates a logical response from changes in the aggregated output over a predetermined period of time.

In a fourth stage, 904, logical control 910 determines that an additional transaction containing a generic response needs to be used to generate a single set of output changes for the transaction containing the logical response. Therefore, the logical controller 910 does not send out the output changes calculated from the input changes 1 to 3 calculated in the previous step 903. The rules engine 920 performed table mapping operations on changes 4-8 to generate the corresponding output changes. However, as shown, in this case, the output changes calculated from the input changes 4-8 are grouped together with the output changes calculated from the input changes 1-3. Therefore, logical controller 910 produces a single set of changes in this output, including logical responses, by aggregating input changes 1-3, 4-6, and 7-8 that form three complete transactions. did.

In the fifth stage 905, the logical controller 910 sent the output changes calculated from the changes 1 to 8 to the input conversion controller (not shown). The physical control removed input changes 1-8 from input table 925 and output changes from output table 930.

Figure 9 shows the aggregation of general-purpose responses by a logical controller. Those skilled in the art will recognize that the logical and physical controls shown in FIG. 9 can be replaced with physical and chassis controls, respectively, to show the aggregation of customized responses by the physical controls.

FIG. 10 shows several embodiments for aggregating response sets from a set of lower layers of lower layers in a hierarchy of controls to generate a single response to be passed to higher layers of higher layers in the hierarchy. The process 1000 to be executed is conceptually shown. In some embodiments, process 1000 is performed by an intermediate controller similar to the logical controllers 810 and 910 of FIGS. 8 and 9. That is, the intermediate controller (1) receives the request from the upper controller, (2) distributes the request to a set of lower controllers, and (3) aggregates the responses to the requests from the lower controller into a single unit. Generates the response of and passes it to the host controller. In some embodiments, the requests and responses received or generated by the intermediate control are in the form of changes (eg, data tuples) that form a complete transaction.

In some embodiments, the receiving controller receives a logical request from the input conversion controller, sends a general purpose request to a set of physical controls, receives a general purpose response from the physical control, and is an input conversion controller. It is a logical controller that sends a logical response to. The process 1000 when executed by the logical controller will be described below. However, the receiving controller of some embodiments receives a generic request from the logical controller and either sends a customized request to a set of managed transfer elements or relays the generic request to a set of chassis controls. , It may be a physical controller that receives a customized response from a managed transfer element or a general purpose response from a chassis controller and sends a general purpose response to a logical controller.

Process 1000 starts from receiving a logical request from the input conversion controller (1005). The input conversion controller generates a logical request from the input data provided by the user of the network control system of some embodiments. The logical request queries the specific information of the logical transfer element managed by the user through the input conversion control. In process 1000, the general-purpose request is calculated by converting the logical request into a general-purpose request (1010).

Next, in process 1000, the set of physical controls to which the general-purpose request is sent is identified (1015). In order to identify the set of physical controls, in process 1000, the set of managed transfer elements that realizes the logical transfer element is first identified, and then the master physical control of the set of managed transfer elements is identified. In some embodiments, these master physical controllers need to receive generic requests. In process 1000, a general-purpose request is sent to each identified physical control (1015). In some embodiments, in process 1000, the identifier of the logical request is retained and the identifier is added to the generic request. In process 1000, the identifier is used to match the generic response with the generic request and the logical request.

After sending a generic request to the identified set of physical controls, in process 1000 it receives a generic response from the physical controls (1020). Also at 1020, process 1000 processes input changes, including generic responses (eg, performs a table mapping operation) to generate output changes.

Then, in process 1000, it is determined whether at least one complete transaction has been received from the physical control (1025). A complete transaction involves changing the input received from a physical control between receiving a barrier and receiving another barrier. A complete transaction from a physical control includes a generic response.

If process 1000 determines that it has not received at least one complete transaction (eg, at least one complete generic response) from the physical control (1025), process 1000 returns to 1020 and from the physical control. Receive further input changes.

If process 1000 determines that at least one complete transaction has been received (1025), process 1000 proceeds to 1030 to determine if a particular aggregation criterion is met. Different embodiments include different aggregation criteria. For example, in some embodiments, a particular criterion includes a period of time (1015) after sending a generic request or (1005) after receiving a logical request. When this period expires, certain criteria are met. Alternatively or additionally, in some embodiments, a particular criterion includes whether a generic response is received from all of the physical controls that have received the generic request. In these embodiments, certain criteria are met if a general purpose response is received from all of the physical controls that have received the general purpose request.

If it is determined in process 1000 that a specific criterion is not met (1030), the process returns to 1020, continues receiving the general-purpose response, and processes the general-purpose response. In process 1000, if it is determined that a particular criterion is met (1030), the output changes calculated from the received generic response (ie, the input modification of the complete transaction containing the generic response) are aggregated (1035). ). Also, at 1035, process 1000 produces a single logical response from the aggregated output changes.

After that, in process 1000, a logical response is sent to the input conversion controller that sent the logical request to the logical controller (1040). In process 1000 of some embodiments, a barrier is inserted at the end of the output change or information indicating the complete transaction is added to the last change of the output change. It also removes the transmitted output changes from the logical control output table and removes the input changes that form the complete transaction used to calculate the logical response from the logical control input table. After that, the process ends.

III. Electronic system Many of the above features and applications are implemented as software processes designated as instruction sets recorded on a computer-readable storage medium (also called a computer-readable medium). When executed by one or more processors (eg, one or more processors, processor cores or other processors), these instructions cause the processor to perform the operation indicated in the instruction. Examples of computer-readable media include, but are not limited to, CD-ROMs, flash drives, RAM chips, hard drives, EPROMs, and the like. Computer-readable media do not include carrier and electronic signals over wireless or wired connections.

As used herein, the term "software" is intended to include firmware or applications stored in magnetic storage that reside in read-only memory that is readable in memory for processing by a processor. Also, in some embodiments, the plurality of software inventions can be realized as part of a large program, the rest of which are different software inventions. In some embodiments, the plurality of software inventions can also be realized as separate programs. Finally, any combination of separate programs that together implement the software inventions described herein is within the scope of the invention. In some embodiments, a software program, when installed to operate in one or more electronic systems, defines the implementation of one or more specific machines that perform the operation of the software program.

FIG. 11 conceptually illustrates an electronic system 1100 in which some embodiments of the present invention are realized. The electronic system 1100 can be used to execute any of the controls, virtualization or operating system applications described above. The electronic system 1100 may be a computer (eg, desktop computer, personal computer, tablet computer, server computer, large computer, blade computer, etc.), telephone, PDA or some other type of electronic device. Such electronic systems include various computer-readable media and interfaces to various other computer-readable media. The electronic system 1100 includes a bus 1105, a processing device 1110, a system memory 1125, a read-only memory 1130, a fixed storage device 1135, an input device 1140, and an output device 1145.

Bus 1105 collectively represents all system buses, peripheral buses, and chipset buses that are communicably connected to many internal devices of the electronic system 1100. For example, the bus 1105 communicatively connects the processing device 1110 with the read-only memory 1130, the system memory 1125, and the fixed storage device 1135.

The processing device 1110 searches these various storage devices for instructions to be executed and data to be processed in order to execute the processing of the present invention. In different embodiments, the processor may be a single processor or a multi-core processor.

Read-only memory (ROM) 1130 stores static data and instructions required by processing equipment 1110 and other modules of the electronic system. On the other hand, the fixed storage device 1135 is a read / write storage device. The device is a non-volatile storage device that stores instructions and data even when the electronic system 1100 is powered off. Some embodiments of the present invention use a large capacity storage device (magnetic disk or optical disk and corresponding disk drive, etc.) as the fixed storage device 1135.

Another embodiment uses a removable storage device (floppy disk, flash drive, etc.) as the fixed storage device. Like the fixed storage device 1135, the system memory 1125 is a read / write storage device. However, unlike the storage device 1135, the system memory is a volatile read / write memory such as a random access memory. System memory stores some of the instructions and data that the processor needs at run time. In some embodiments, the processing of the present invention is stored in system memory 1125, fixed storage 1135 and / or read-only memory 1130. The processing device 1110 searches these various storage devices for instructions to be executed and data to be processed in order to perform the processing of some embodiments.

Bus 1105 further connects to input device 1140 and output device 1145. The input device allows the user to communicate information to the electronic system and select commands. The input device 1140 includes an alphanumeric keyboard and a pointing device (also referred to as a "cursor control device"). Output device 1145 displays an image produced by the electronic system. Output devices include printers and display devices such as cathode ray tubes (CRTs) or liquid crystal displays (LCDs). Some embodiments include devices such as touch screens that function as both input and output devices.

Finally, as shown in FIG. 11, bus 1105 further couples the electronic system 1100 to network 1165 via a network adapter (not shown). Thus, the computer may be part of a computer network (local area network (LAN), wide area network (WAN) or intranet, etc.) or one of the networks of networks such as the Internet. It may be a department. Any or all components of electronic system 1100 may be used in connection with the present invention.

In some embodiments, electronic devices such as microprocessors, storage devices and memory that store computer program instructions on a machine-readable or computer-readable medium (also referred to as a computer-readable medium, machine-readable medium or machine-readable storage medium). Includes components. Some examples of such computer-readable media include RAM, ROM, read-only compact discs (CD-ROMs), recordable compact discs (CD-R), rewritable compact discs (CD-RW), and read-only digital discs. General-purpose discs (eg DVD-ROM, dual-layer DVD-ROM), various recordable / rewritable DVDs (eg DVD-RAM, DVD-RW, DVD + RW, etc.), flash memory (eg SD card, Mini SD card, micro SD card, etc.), magnetic hard drive and / or solid hard drive, read-only Blu-Ray (r) disc and recordable Blu-Ray (r) disc, ultra-high density optical disc, some other optical medium Alternatively, it includes a magnetic medium and a floppy disk. A computer-readable medium may contain a computer program that is executable by at least one processing device and contains an instruction set for performing various operations. Examples of computer programs or computer code include machine code as generated by a compiler, as well as files containing high-level code executed by a computer, electronic component or microprocessor that uses an interpreter.

Although the above description primarily refers to microprocessors or multi-core processors running software, some embodiments include one or more integrated circuits (ASICs) or field programmable gate arrays (FPGAs) such as application specific integrated circuits (ASICs). Performed by the circuit. In some embodiments, such an integrated circuit executes instructions stored in the circuit itself.

As used herein, the terms "computer," "server," "processor," and "memory" all refer to electronic devices or other technical devices. These terms do not include humans or groups of humans. For convenience of the present specification, the term "display" means to display on an electronic device. As used herein, the terms "computer-readable medium" and "machine-readable medium" are all limited to tangible physical objects that store information in a computer-readable form. These terms do not include radio signals, wired download signals and any other temporary signals.

Although the present invention has been described with reference to many specific details, one of ordinary skill in the art will recognize that the present invention is feasible in other particular embodiments without departing from the spirit of the invention. In addition, many drawings (including FIGS. 4, 7 and 10) conceptually illustrate the process. Certain actions of these processes do not have to be performed in the exact order shown and described. The particular action does not have to be performed in a series of successive actions, and different specific actions may be performed in different embodiments. Further, the processing may be realized using a plurality of sub-processing, or may be realized as a part of a large macro processing.