Using transactions to compute and propagate network forwarding state

Within the network, the network transfer state (forwarding state) is a packet that incoming transports from the mouth point to the exit point. The forwarding state causes the network element to forward the packet to the element approaching its destination on a hop-by-hop basis. It is clear that the calculation of the transfer status according to the set network policy is extremely important for the operation of the network. Without a legitimate forwarding condition, the network would not deliver the packet to its destination, nor would it forward according to the configured policy.

Some embodiments of the present invention provide a controller cluster that updates the forwarding state to specify a new network policy. The controller group sends the updated transfer state to the transfer element set in a way that the transfer element set consistently applies the new network policy to the packet and does not mix old and new policies.

In some embodiments, the controller group uses the first hop managed forwarding element, which is present at the beginning of the packet path, for all of the logical forwarding decisions to forward the packet (eg, the logical exit port (logical)). Set to search for egress ports) and identify the physical exit port for the logical exit port). Other unmanaged forwarding elements in the packet path element) makes no logical transfer decisions about the packet and therefore does not require or receive a transfer state. These other forwarding elements are merely used as a configuration (fabric) for sending a packet to a destination based on the source and destination information of the packet. The packet need not have any version information to indicate that it must be forwarded with the updated forwarding state. This is because all logical transfer decisions for that packet are made by the first hop management transfer element, and the other hop transfer elements do not receive the updated transfer state. Packets are forwarded only by the new policy because they are forwarded by the first hop management forwarding element, which makes all logical forwarding decisions based on the new policy.

In some embodiments, the controller set the management transfer element in such a way that the logical transfer decision is executed not only in the first hop but also in other hop transfer elements. In these embodiments, the controller group first transmits the updated transfer state to a transfer element other than the first hop in the packet path. Only after transmitting the updated transfer state to a transfer element other than the first hop, the controller group transmits the updated transfer state to the first hop transfer element of the packet. The controller group then instructs the first hop transfer element to use the updated transfer state to transfer the packet. In some embodiments, the packet forwarded to the first hop forwarding element has version information indicating that the packet must be forwarded using the updated forwarding state. In this way, packets forwarded by the first hop forwarding element to other hop forwarding elements are guaranteed to be forwarded based on the new network policy.

Some embodiments of the present invention are managed transfer elements that are configured to enable transactions across several network controllers in a group of network controllers and an established channel set. provide. Specifically, the managed transfer element according to some embodiments does not commit the transfer state received through those channels until it receives the barrier through those channels. Barriers that the management transfer element may receive through other channels do not commit the transfer state received by the management transfer element. That is, the management transfer element commits the transfer state only after the barrier is received through a particular channel. In this way, the management transfer combines transaction inputs coming in through other channels with transaction inputs coming in through a particular channel.

The above overview is provided as a brief introduction to some embodiments of the present invention. This does not mean that it is an introduction or summary of all the subject matter of the invention disclosed herein. The following detailed description column and the drawings referred to in the detailed description will further describe embodiments and other embodiments described in the section of abstract of the invention. Therefore, an overview of the invention, a detailed description, and a thorough review of the drawings are required to understand all the embodiments described herein. Further, since the technical idea of the present invention can be implemented in other forms within the scope thereof, it should not be limited by the outline of the invention, the detailed description, and the specific details in the drawings, and the description of the scope of claims. Should be specified by.

The novel features of the present invention are described in the appended claims. However, for purposes of illustration, some embodiments of the present invention are described in the drawings below.

<figref num="1">It is a figure which shows the example hierarchical structure of a network controller.</figref><figref num="2">It is a figure which shows the architecture of the network controller which concerns on some embodiments.</figref><figref num="3">It is a figure which shows the example of the plurality of logical switching elements implemented over the management transfer element set.</figref><figref num="4">It is a figure which shows some logical transfer elements implemented in a physical infrastructure.</figref><figref num="5">It is a figure which shows the transmission of the updated transfer state information to the management transfer element set.</figref><figref num="6">Some embodiments are diagrams conceptually showing the steps to be taken to send updated transfer status information to the management transfer element set.</figref><figref num="7">Some embodiments are diagrams conceptually showing the steps to be taken to receive the updated transfer status information on the management transfer element.</figref><figref num="8">It is a figure which shows the transmission of the updated transfer state information to the management transfer element set.</figref><figref num="9">Some embodiments are diagrams conceptually showing the steps to be taken to send updated transfer status information to the management transfer element set.</figref><figref num="10">Some embodiments are diagrams conceptually showing the steps to be taken to receive the updated transfer status information on the management transfer element.</figref><figref num="11">FIG. 5 is a diagram conceptually showing a procedure to be executed in order to calculate transfer status information transactionally and send it to a management transfer element set in some embodiments.</figref><figref num="12">It is a figure which shows the management transfer element which some controller of a group of controllers establishes some communication channels for sending an update.</figref><figref num="13">It is a diagram conceptually showing how some embodiments are executed to combine a transaction received through a primary channel with a plurality of transactions received through a secondary channel set.</figref><figref num="14">It is a figure which conceptually shows an electronic system which can be used for carrying out a part of Embodiment of this invention.</figref>

In the following detailed description of the invention, various details, examples, and embodiments of the invention will be described and described. However, as will be apparent to those skilled in the art, the invention is not limited to the embodiments described, and the invention does not use any of the specific details and examples described. Can be implemented in.

Some embodiments provide a network control system in which the network controller calculates transfer status information to push to the managed transfer element set in order to specify the transfer operation of the managed transfer element set. The controller also updates the transfer status information to change the behavior of the management transfer element. When updating the transfer status information, the network controller manages and transfers the updated transfer status information so that the management transfer element transfers the data (eg, in the form of a data packet) within the network according to the updated transfer status information. Push to the element.

In some embodiments, the controller pushes the updated transfer status information to the managed transfer element in such a way that all managed transfer elements in the path of the packet apply the updated transfer status information. For example, in some embodiments, the controller makes all logical forwarding decisions by the first hop forwarding element of the packet path so that the other forwarding elements in the path simply act as a fabric to forward the packet to the destination. To set. In these embodiments, the controller transmits the updated transfer status information only to the first hop transfer element. In this way, the packet needs to include version information to indicate to the forwarding element other than the first hop forwarding element that the packet must be processed with the updated forwarding information in order to forward the packet to its destination. Is gone.

In some embodiments, the controller configures the forwarding element to make a logical forwarding decision not only by the first hop forwarding element but also by other forwarding elements of the packet path. In some of these embodiments, the controller first transfers the updated transfer state information to one management transfer element (ie, the first with respect to the packet) in the packet path (ie, the path between the entry and exit points of the packet). Send to all management transfer elements except hop transfer element). The first hop transfer element for the packet receives the packet directly from the source device. That is, the first hop forwarding element for that packet is located at the beginning of the route.

Then, the controller transmits the updated transfer status information to the first hop management transfer element. In some embodiments, the first hop management forwarding element includes version information in the packet when forwarding the packet to the forwarding element of the next hop. This version information indicates that the packet must be forwarded based on the updated forwarding state information, not the old forwarding state information. In this way, the packet received and forwarded by the first hop management forwarding element that uses the updated forwarding status information is another hop in the packet path that is ready to use the updated forwarding status information. Further transferred by the management transfer element.

Further detailed embodiments will be described in the following sections. Specifically, Section I first describes a network control system according to some embodiments for controlling logical and physical networks. Section II then describes a network controller that generates, updates, and pushes transfer state information according to some embodiments of the invention. Section III describes a management transfer element that uses several communication channels to receive transfer status information from the controller. Finally, Section IV describes an electronic system in which some embodiments of the present invention can be implemented.

I. Network control system FIG. 1 shows a network control system 100 in which a network controller calculates transfer status information for pushing to a managed transfer element set in order to specify a transfer operation of the managed transfer element set. The network control system 100 has a controller group 105 and three management transfer elements 125-135. The network controller group 105 has three network controllers (one logical controller 110 and two physical controllers 115 and 120). The network control system 100 represents a simple example having one controller group 105 that pushes state to three management transfer elements. In many cases, the network control system according to some embodiments will have a large number of controllers, each group containing a large number of controllers, and hundreds or thousands of management transfer elements.

In some embodiments, the network controller group 105 performs a transfer state calculation and pushes the calculated transfer state to the management transfer element in the form of a flow entry. The network controller group according to some embodiments receives the logical control plane (LCP) data that defines the logical network, and the physical control plane (PCP) data for transmitting this LCP data to the management transfer elements 125-135. Convert to. 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 the logical network. The logical transfer element specifies how packets from the source device should be forwarded to the destination device in logical space (eg, the association between the virtual machine MAC address and the logical port). Further, in some embodiments, the LCP defines a logical policy (eg, an access control list) that is implemented in the logical transfer element. LCP and its structure are independent of the physical network in which it is implemented.

The network controller group according to some embodiments performs a unique transformation to make the LCP data into PCP data pushed to the management transfer element. In some embodiments, the controller group transforms the LCP data into logical transfer plane (LFP) data and then the LFP data into PCP data. LFP data specifies a forwarding entry for forwarding a packet in logical space. That is, rather than simply associating an address with a logical port, the LFP data contains an entry that describes forwarding the packet to the logical port if the addresses match.

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

In some embodiments, the calculation of the PCP to push to the management transfer element is distributed among the different controller layers of the controller group. For example, in some embodiments, the logical controller 110 manages at least one logical transfer element. As shown in the right half of FIG. 1, the logical controller 110 executes the conversion from LFP to universal PCP (UPCP) following the conversion from LCP to LFP. The flow entries that UPCP data has are not customized to contain data that is specific to any management transfer element, but instead for data that is specific to a particular physical implementation (eg port number, tunnel identifier, etc.). Contains only the abstraction of.

In some embodiments, the logical controller that manages a particular logical transfer element sends UPCP data to any number of physical controllers. For example, the logical controller 110 transmits UPCP data to the two physical controllers 115 and 120. Each of the management transfer elements is managed by the master physical controller.

Therefore, UPCP data about a logical transfer element performed across several management transfer elements may be sent to several different master physical controllers that manage the few transfer elements. As shown in the figure, the physical controller 115 is a master controller that manages two management transfer elements 125 and 135. The physical controller 120 is a master controller that manages the management transfer element 135.

UPCP data is converted to customized PCP (CPCP) data on either the physical controller or the chassis controller (not shown) in the same physical machine as the management transfer element. CPCP data is physical control plane data that contains customized data specific to a particular management transfer element. As mentioned above, in some embodiments, the physical controller uses the information received from the management transfer element to perform this transformation. In other embodiments, the physical controller acts as a passthrough to send UPCP data to the host machine where the management transfer element resides, and the controller logic (chassis controller) performs the UPCP to CPCP conversion.

Management Transfer elements 125-135 are software or hardware transfer elements managed by a network controller (eg, by receiving transfer status information from the network). In some embodiments, the management transfer element is a software transfer element that runs on the host machine (eg, in user space and / or in the kernel of the host machine). These managed forwarding elements receive packets from end machines 140-160, apply logical processing to those packets, and send the packets to their destinations across the physical network (eg, different end machines). It may be connected to a management transfer element.)

The end machines 140-160 may be physical machines or virtual machines. In some embodiments, the end machines as virtual machines run within the same host as the host that has the management forwarding element that forwards packets to them. Virtual machines belonging to multiple physical networks may be located in one host machine (for example, the end machines 140 and 145 may be located in the same host machine as the host machine in which the management transfer element 125 is located), so that they are managed. Each of the transfer elements can realize a plurality of different logical transfer elements. Further, as described above, one logical transfer element will generally be implemented across a number of managed transfer elements.

In addition to the management transfer element located at the edge of the network, in some embodiments a second level non-edge management transfer element (pool node) on the host having the virtual machine. Or it may be called a service node). If the edge-managed forwarding element cannot perform any processing on a packet (for example, by not having a flow entry to associate the destination MAC address with the logical port), the edge-managed forwarding element pools the packet. Send the packet to the pool node for the node to process and send to the destination.

FIG. 2 conceptually illustrates an exemplary architecture of the network controller 200 according to 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 to be handled.

The network controller 200 as a logical controller acquires 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 physical controller set that is a master of a management transfer element that realizes a logical transfer element managed by the network controller 200 as a logical controller.

As a physical controller according to some embodiments, the network controller 200 takes UPCP data as input and converts the UPCP data into CPCP data. Then, the network controller 200 pushes the CPCP data to the management transfer element set which is the master itself. In another embodiment, the network controller 200 as a physical controller relays UPCP data to a chassis controller set running on a host running the management transfer element set. The network controller 200 is, in these embodiments, the master of this management transfer element set.

The network controller 200 as a chassis controller takes UPCP data from the physical controller set as input. The network controller 200 converts the UPCP data into CPCP data for the management transfer element managed by the chassis controller, and transmits the CPCP data to the management transfer element.

As shown in FIG. 2, the network controller 200 includes a rule engine input table set 210, a function and constant table set 215, an importer 220, a rule engine 225, a rule engine output table set 245, a converter 250, an exporter 255, and a persistent transaction database. It has (PTD) 260, and a compiler 235. The compiler 235 is one component of the controller and operates in an instance that is temporally different from the other components of the controller. The compiler works when the developer needs to specify a rules engine for a particular network controller and / or virtualized environment, while the remaining modules of the controller allow the controller to interact with other controllers or management transfer elements ( It works at runtime when interface).

In some embodiments, the compiler 235 is a relatively small (eg, hundreds of lines) declarative statement specified in a declarative language. Obtain instructions) 240 and convert them into a large (eg, thousands of lines) set of code (ie, object code) that specifies the behavior of the rule engine 225 that performs the controller's table mapping. Therefore, the compiler greatly simplifies the process of network controller developers to specify and update network controllers. That's because the compiler allows developers to use high-level programming languages. High-level programming languages compactly define complex mappings for network controllers, and then any number (eg, changes in the logical networking capabilities supported by the network controller, changes in the desired behavior of the network controller, etc.). Allows you to update this mapping in response to changes in. In addition, the compiler reduces the effort of developers to consider the order in which events will occur on a network controller when defining mapping behavior. Developers also program the network controller 200 with different rule sets to allow the network controller 200 to function as a logical controller, physical controller, or chassis controller.

In some embodiments, the rule engine (RE) input table 210 has a plurality of tables with different types of data based on the type of network controller in which the network controller 200 operates. When the network controller 200 operates as a logical controller, the input table 210 includes LCP data required to be mapped to LFP data and LFP data required 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 required to be mapped to CPCP data.

In addition to the RE input table 210, the network controller 200 has various other tables 215 that the rule engine 225 uses to organize inputs related to its table mapping operation. These tables 215 include constant tables that store constant values of constants required for the rule engine 225 to perform table mapping operations. For example, in the constant table 215, the constant "zero" specified as the value 0, the constant "dispatch_port_no" specified as the value 4000, and the constant "broadcast" specified as the value 0xFF: FF: FF: FF: FF: FF. May include "MAC addr".

When the rule engine 225 refers to a constant, the corresponding value specified for that constant is actually read and used. In addition, the values specified for the constants in the constant table 215 may be changed and / or updated. In this way, the constant table 215 has the ability to change the values specified for the constants referenced by the rule engine 225 without having to rewrite or recompile the code that defines the behavior of the rule engine 225. provide. Table 215 further includes a function table that stores the functions required by the rule engine 225 to calculate the values needed to populate the output table 245.

The rule engine 225 performs a table mapping operation that specifies one method for converting input data into output data. Each time one of the rule engine (RE) input tables is modified, the rule engine performs a series of table mapping operations, which can modify one or more data tuples in one or more RE output tables. In some embodiments, the network control system uses a derivative of the datalog database language called nLog to create the rule engine 225. Like datalog, nLog provides a few declarative rules and operators that allow developers to specify different actions to be taken in response to different events. In some embodiments, nLog provides a limited subset of the operators provided by the data log to improve execution speed. For example, in some embodiments, nLog limits the operators that can be used in declarative rules to AND.

As shown in FIG. 2, the rule engine 225 has an event processor 222, some query plan 227, and a table processor 230. Each query execution plan is a set of rules that defines a set of join actions that should be executed when a change to one of the RE input tables occurs. In the following description, such changes are referred to as input table events. Each query execution plan is generated by compiler 235 from one declarative rule in declaration set 240. In some embodiments, one declarative rule generates multiple query execution plans. For example, one query execution plan is generated for each of a plurality of tables joined by one declarative rule. That is, if a declarative rule specifies a join of four tables, then four different query execution plans will be generated from one declaration. In some embodiments, the query execution plan is specified using the nLog declarative language.

The event processor 222 of the rule engine 225 detects the occurrence of each of the input table events. The event processor in another embodiment detects the occurrence of another input table event. In some embodiments, the event processor registers a callback with the RE input table to notify 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 its records has changed.

In response to the detected input table event, the event processor 222 (1) selects an appropriate query execution plan for the detected table event, and (2) causes the table processor 230 to execute the query execution plan. To order. To execute a query execution plan, in some embodiments, the table processor 230 generates one or more records that represent one or more of the data value sets from at least one of the input table 210 and the miscellaneous table 215. , Performs the join operation specified by the query execution plan. The table processor 230 according to some embodiments then performs a selection operation to select a subset of the data values from one or more records generated by the join operation, and (2) the selected data. Write a subset of the values to one or more RE output tables 245.

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

If a change in one table causes the exporter 255 to export the change to another one or more controllers or one or more management transfer elements, that table is the controller output table. The table in the RE output table 245 may be an RE input table, a controller output table, or an RE input table and a controller output table. In some embodiments, the RE input and RE output tables are relational database management system (RDBMS) tables. These tables are stored as a relational data structure, which is the main data storage structure of the network controller.

The exporter 255 detects changes to the controller output table of the RE output table 245. The exporter in another embodiment detects the occurrence of another controller output table event. In some embodiments, the exporter registers a callback with the controller output table to notify changes to the records in the controller output table. In such an embodiment, the exporter 255 detects an output table event when it receives a notification from the controller output table that one of its records has changed.

In response to a detected output table event, exporter 255 gets some or all of the modified data tuples in the modified controller output table and uses this modified data tuple as another controller or management transfer element. Communicate to. Specifically, when the network controller 200 operates as a logical controller, the exporter 255 transfers UPCP data to the physical controller set through a set of communication channels established with the physical controller (eg, a remote procedure call (RPC) channel). Communicate to. When the network controller 200 operates as a physical controller, the exporter 255 according to some embodiments transmits UPCP data to the chassis controller set through a communication channel set established with the chassis controller. The exporter 255 according to another embodiment transmits CPCP data to the management transfer element set through a communication channel pair (for example, one OpenFlow channel and one configuration channel) established with each of the management transfer elements. When the network controller 200 operates as a chassis controller, the exporter 255 according to some embodiments is a communication channel pair established with each of the management transfer elements (eg, one OpenFlow channel and one configuration channel). Transfer CPCP data to the management transfer element set through.

In some embodiments, the network controller does not hold data in the output table 245 that it does not need to manage. 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 transmits the data to one or more other network controllers so that the other network controller responsible for managing the data can manage the data.

In some embodiments, the network controller also stores the data stored in the output table 245 (ie, the data it manages) in the PTD to improve data fault tolerance. You may. Such data is also transformed by the transducer 250, stored in the PTD and transmitted to other PTDs in other controller instances. Therefore, in these embodiments, the PTD of the controller instance has all the configuration data for all the data managed by the network control system. That is, in some embodiments, each PTD stores a global view of the configuration of logical and physical networks.

The importer 220 interacts with a plurality of input data sources and uses the input data to modify or generate the input table 210. The importer 220 according to some embodiments converts input data to a user (tenant) through an input conversion controller (not shown) that converts user input into LCP data when the network controller 200 operates as a logical controller. Receive from. In some embodiments, the importer 220 receives LCP data through a communication channel.

The importer 220 also interacts with the PTD 260 so that data received from other controller instances through the PTD can be used to modify or generate the input table 210. Further, the importer 220 detects changes in the controller output table of the RE input table and 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 UPCP data generation by the rule engine 225.

When the network controller 200 operates as a physical controller, the importer 220 acquires UPCP data from the logical controller set through the communication channel set established with the logical controller set. When the network controller 200 operates as a chassis controller, the importer 220 acquires UPCP data from the physical controller set through the communication channel set established with the physical controller set.

FIG. 3 conceptually illustrates the logical transfer elements 380 and 390 implemented across the management transfer elements 310-330. The upper half of the figure shows three management transfer elements 310-330 and end machines 340-365. As shown, machines 340, 350 and 360 belong to user A and machines 345, 355 and 365 belong to user B. For simplicity of illustration and description, this figure shows a configuration in which logical transfer elements are connected to a small number of end machines and implemented with a small number of managed transfer elements. As described above, the logical transfer element may be connected to a large number of end machines and implemented by a large number of management transfer elements.

Management transfer elements 310-330 according to some embodiments transfer network data (eg, packets, frames, etc.) between network elements within the network connected to management transfer elements 310-330. As shown, the management transfer element 310 transfers network data between the machines 340 and 345 and the transfer element 320. Similarly, the transfer element 320 transfers network data between the machine 350 and the management transfer elements 310, 330, and the transfer element 330 transfers network data between the machines 355-365 and the transfer element 320.

In addition, each of the management transfer elements 310-330 transfers network data based on the transfer logic of the transfer element, which in some embodiments has the form of a table. In some embodiments, the forwarding table determines where to forward network data (eg, a port on a forwarding element) according to forwarding conditions. For example, the forwarding table of the Layer 2 forwarding element may determine where to forward network data based on the MAC address (eg, source MAC address and / or destination MAC address). As another example, the forwarding table of the Layer 3 forwarding element may determine where to forward the network data based on the IP address (eg, source IP address and / or destination IP address). Many other transfer conditions are possible.

As shown, the transfer table in each of the management transfer elements 310-330 has several records. In some embodiments, each record defines a transfer operation of network data based on transfer conditions. Records may be referred to as flow entries in some embodiments because they control the "flow" of data through management transfer elements 310-330.

The lower half of FIG. 3 shows a conceptual representation of the user's logical network. As shown in the figure, the logical network 380 of the user A has a logical transfer element 385 to which the machines 340, 350 and 360 of the user A are connected. User B's logical network 390 has a logical transfer element 395 to which User B's machines 345, 355 and 365 are connected. Therefore, from the viewpoint of user A, user A has a transfer element to which only the machine of user A is connected, and from the viewpoint of user B, user B has a transfer element to which only the machine of user B is connected. doing. In other words, each user has his own network with only his own machines.

Hereinafter, a conceptual flow entry for realizing the flow of the network data transmitted from the machine 340 to the machine 350 and the network data transmitted from the machine 340 to the machine 360 will be described. First, the flow entry for transferring the network data transmitted from the machine 340 to the machine 350 will be described, and then the flow entry for transferring the network data transmitted from the machine 340 to the machine 360 will be described. ..

The flow entry "A1 to A2" in the transfer table of the management transfer element 310 instructs the management transfer element 310 to transfer the network data addressed to the machine 350 originating from the machine 310 to the transfer element 320. The flow entry "A1 to A2" in the transfer table of the management transfer element 320 instructs the management transfer element 320 to transfer the network data destined for the machine 350 originating from the machine 310 to the machine 350.

The flow entry "A1 to A2" in the transfer table of the management transfer element 310 instructs the management transfer element 310 to transfer the network data addressed to the machine 350 originating from the machine 310 to the transfer element 320. The flow entry "A1 to A3" in the transfer table of the management transfer element 320 instructs the management transfer element 320 to transfer the network data destined for the machine 360 originating from the machine 340 to the transfer element 330. The flow entry "A1 to A3" in the transfer table of the management transfer element 330 instructs the management transfer element 330 to transfer the network data addressed to the machine 360 originating from the machine 340 to the machine 360.

The conceptual flow entry for transferring the network data destined for machine 350 originating from machine 340 and the network data destined for machine 360 originating from machine 340 has been described, but within user A's logical network 380. Similar flow entries will be included in the transfer table for management transfer elements 310-330 to transfer network data between other machines. In addition, a similar flow entry will be included in the transfer table of management transfer elements 310-330 to transfer network data between machines within User B's logical network 390.

The conceptual flow entry shown in FIG. 3 contains both source and destination information so that the management forwarding element can figure out which next hop forwarding element to send the packet to. However, since the management transfer element according to some embodiments can clarify the transfer element of the next hop using only the destination information (for example, the destination address), the source information is not included in the flow entry. Good.

In some embodiments, tunneling protocols (eg, CAPWAP (control and provisioning of wireless access points), GRE (generic forward encapsulation)," to facilitate the implementation of logical transfer elements 385 and 395 across management transfer elements 310-330. IPsec (GRE Internet Protocol) The tunnel provided by Security) etc. may be used. Tunneling causes a packet to be transmitted as a payload of another packet through a forwarding element. That is, the tunneled packet is forwarded based on the address contained in the header of the outer packet that encapsulates it, so there is no need to expose its own address (eg, source and destination MAC addresses). Thus, tunneling can have a meaningful address in the logical address space while the outer packet is forwarded based on an address in the physical address space, thus tunneling between the logical address space and the physical address space. Allows separation. In this way, the tunnel can be seen as a "logical wiring" connecting the management transfer elements to implement the logical transfer elements 385 and 395.

By configuring the transfer element in the various ways described above to achieve multiple logical transfer elements across the transfer element set, multiple users can actually connect between the same transfer element set and / or transfer element set (eg, transfer element set). While sharing tunnels, physical wiring), it is possible for each to have an independent network and / or forwarding element from the perspective of the individual user.

FIG. 3 shows an example of implementing a logical transfer element with a management transfer element set, but it is more complicated (for example, including some logical L3 transfer elements) by setting a transfer table of the management transfer element. It is also possible to realize a logical network. FIG. 4 conceptually shows an example of a more complex logical network. FIG. 4 shows a network architecture 400 according to some embodiments that implements three logical transfer elements, a logical router 425 and logical switches 420, 430. Specifically, the network architecture 400 represents a physical network that realizes a logical network in which data packets are transferred by the logical router 425 and the logical switches 420, 430. The upper half of the figure shows the logical router 425 and the logical switches 420 and 430. The lower half of the figure shows the management transfer elements 455 and 460. In addition, both the upper and lower halves show end machines (eg, virtual machines (VMs)) 1-4.

In this example, the logical switch element 420 forwards data packets between the logical router 425, the end machine 1, and the end machine 2. The logical switch element 430 forwards data packets between the logical router 425, the end machine 3, and the end machine 4. As described above, the logical router 425 routes data packets between the logical switches 420, 430 and other logical routers and switches (not shown). The logical switches 420, 430 and the logical router 425 are logically connected through a logical port (not shown) and exchange data packets through the logical port. These logical ports are mapped or attached to the physical ports of management transfer elements 455 and 460.

In some embodiments, the logical router is implemented at each management switch element within the management network. When the management switch element receives a packet from a machine attached to it, the management switch element performs logical routing. That is, in these embodiments, the management switch element, which is the first hop switch element for a packet, performs logical routing.

In this example, the management transfer elements 455 and 460 are software switches running on hosts 465 and 470, respectively. Management transfer elements 455 and 460 have flow entries that implement logical switches 420 and 430 for forwarding and routing packets they receive from end machines 1-4. This flow entry also implements the logical router 425. Using these flow entries, managed forwarding elements 455 and 460 are network elements within the network that can forward and route packets between network elements connected to them.

As shown, each of the management transfer elements 455 and 460 has three ports (eg, a virtual interface (VIF)) for exchanging data packets with network elements connected to it. Data packets in these embodiments are exchanged through a tunnel established between the management transfer elements 455 and 460 (for example, a tunnel ending at port 3 of the management switch element 455 and port 6 of the management switch element 460). It may be done. This tunnel makes it possible to separate addresses in logical space from addresses in physical space.

In this example, hosts 465 and 470 have one management switch element and several end machines. A network address set (for example, MAC address for L2, IP address for L3, etc.) is assigned to each of the end machines 1-4, and network data can be sent and received to and from other network elements. .. The end machine is managed by a hypervisor (not shown) running on hosts 465 and 470. End machines 1 and 2 are associated with logical ports 1 and 2 of the same logical switch 420, respectively. However, machine 1 is associated with port 4 of management switch element 455, and machine 2 is associated with port 7 of management switch element 460. Therefore, logical ports 1 and 2 are mapped to ports 4 and 7, respectively, but this mapping need not be disclosed to any network element (not shown) in the network. This is because the packet containing this mapping information is exchanged between the end machines 1 and 2 through the tunnel based on the outer header of the outer packet carrying the packet as a payload.

We have described the realization of logical networks in network control systems and physical infrastructure. Section II below describes the transactional transmission of updated transfer state to the management transfer element.

II. Use of transactionality After the network configuration changes, there are some issues to be solved in order to update the transfer state (that is, shift from the previously calculated state to the newly calculated state). Some solutions are described below. These solutions look at the problem in terms of two dimensions: accuracy and efficiency. That is, these solutions are examining how to guarantee that the state existing in the network at that time complies with the network policy correctly, not only before and after the update but also during the update. In terms of efficiency, these solutions are looking at how the cost of potentially large state updates can be minimized.

In the discussion below, the network control system has a centralized set of controllers that calculate the transfer state for the transfer element in order to manage the network transfer element. Furthermore, in the following discussion, "network policy" is not limited to security policy, but includes any viewpoint related to configuration and configuration such as policy regarding how to route network traffic and physical (or logical) network configuration. Therefore, in this discussion, "policy" is used for everything related to user-configured inputs.

A. Transaction requirements The forwarding state acts on the packet. It is essential that one packet is not a mixture of old and new policies, but is forwarded according to one consistent policy. As long as the transition from the old version to the new version occurs so that one packet is not handled by both the old and new policies, subsequent packets can be processed by another version of the policy.

The requirement for atomic transitions to new policies implies that updates to the transfer state must be made transactionally. However, as mentioned above, it does not mean that all network transfer states must be updated atomically at the same time. In particular, the network control system according to some embodiments relaxes this requirement from two perspectives. First, for packet streams from a source to one or more destinations, it is not very important to specify when the old policy changes to the new policy. It is only essential that no packets are forwarded according to both the old and new policies. Each packet must be forwarded according to either the old policy or the new policy. Second, the network control system according to some embodiments allows different policies to be applied transiently to different packet streams entering the network from different locations. Again, in these embodiments, only one policy is applied to a packet, only the old and new policies are required not to be applied.

B. Realization of transactional updates Consider the realization of transactional updates under these requirements and mitigation conditions. M. Reitblatt et al. Consistent Updates for Software -Defined Networks: Change You Can Believe in! Proceedings of the 10th ACM Workshop on Hot Topics in Networks, p.1-6, November 14-15, 2011, Cambridge, Massachusetts (hereinafter referred to as the Reitblatt literature) proposes to tag packets at the entrance of a network using the version of the forwarding state used there. Therefore, as the packet travels through the network, subsequent network elements will know which version is being used. This makes it possible to efficiently update the network transfer state over the entire network in a transactional manner.

However, there are some realization challenges with this approach. First, if network slicing is not assumed, the network needs to be updated in several steps (serialize). That is, the entire network must be prepared for a particular version, and then only after updating the entry point to use the ready version can the preparation for the next version begin.

Second, since the packet must have an explicit version tag, there must be enough bits somewhere in the packet header to assign the tag. If the network needs to operate using traditional tunneling protocols, it will be difficult to find free bits for such tags in the header.

Therefore, while transactional updates across the network as described in the Reitblatt literature are powerful, they have practical challenges that should ideally be avoided. Therefore, instead of this approach described in the Reitblatt literature, network control systems according to some embodiments utilize the placement of managed transfer elements at the network edge. As described in Section I, the network control system according to some embodiments makes a logical transfer decision (ie, which one or more logical ports should receive the packet) in the first hop. Subsequent steps simply forward the packet to the selected destination based on this forwarding decision.

FIG. 5 conceptually shows a network controller group 505 of a network control system that makes a logical transfer decision in the first hop. Specifically, this figure shows that the network controller group 505 sends transfer state updates only to the first hop management transfer element in four different stages 501-504. The network controller group 105 described with reference to FIG. 1 in that the network controller group 505 has a logical controller and a physical controller (not shown) that generate, update, and transmit the transfer state to the management transfer element (MFE) 510. Is similar to. The management transfer element 510 is a first hop transfer element for data originating from the end machine 540. That is, the management transfer element 510 directly interacts with the end machine 540 and transfers the data from the end machine 540 toward its destination. Transfer elements 515-535 transfer data between a set of end machines 540-550.

In the first stage 501, the management transfer element 510 transfers network data (not shown) from the end machine 540 based on the current transfer state (old state) of the transfer element. Specifically, the route defined by the controller group for the packet transmitted from the end machine 540 to the end machine 545 spans the transfer elements (FE) 510, 515, and 520, as shown by the solid line in the figure. Also, in step 501, controller group 505 receives updates to the transfer state from the user (eg, through an input transaction controller not shown). This update represents a new network policy, such as a new QoS policy that specifies different allowed bandwidths, or a new route from one virtual machine (VM) to another newly offered virtual machine.

In the second stage 502, the controller group 505 calculates the transfer state update (eg, by converting the input LCP data into UPCP or CPCP data). In some embodiments, controller group 505 identifies all management transfer elements that implement logical transfer elements. Specifically, the controller group 505 is the first regarding the route of the packet to be transferred from the first physical port mapped to the logical inlet port and the logical exit port of the logical transfer element to the second physical port. A transfer element having a physical port (eg, a first hop transfer element) and a transfer element having a second physical port (eg, a last hop transfer element) are identified.

In step 502, the updated forwarding state has a new path for packets destined for end machine 550 transmitted from end machine 540. Here, the end machine 550 is an end machine added to the network after the old transfer state is calculated and transmitted to the network transfer element. For this new route, the management transfer element 510 is the first hop management transfer element and the transfer element 520 is the final hop transfer element. The forwarding element 515 is one of a plurality of "intermediate" managed or unmanaged forwarding elements that forward the packet towards the final hop managed forwarding element 535.

The controller group 505 calculates the updated transfer status information for all the routes affected by the update by the user, and identifies the first hop management transfer element for each of the routes. In step 502, controller group 505 transmits to the management transfer element updated transfer state information about the first hop management transfer element of the route. For simplification of the figure, step 502 shows the old and new transfer states for the route starting from the management transfer element 510. The management transfer element 510 has old and new transfer states for those routes. The management transfer element 510 does not yet use the new transfer state and forwards the packet based on the old transfer state.

In some embodiments, the management transfer element, which is the first hop transfer element, begins to use the new transfer state when it receives the new transfer state. However, in some embodiments, the controller group 505 sends a command to the management transfer element to use the updated transfer state to transfer the packet as the first hop transfer element. In the third stage 503, the controller group 505 sends such a command to the management transfer element 510. The management transfer element 510 uses a new transfer state as the first hop transfer element for the route originating from itself. For a new route to a packet transmitted from the end machine 540 to the end machine 550, the management transfer element 510 will be able to transfer the packet based on the new transfer state. Since the non-first hop transfer element does not require and does not acquire a new transfer state, the packets in these embodiments provide version information to notify that the non-first hop transfer element must use the new transfer state. No need to transport.

In the fourth stage 504, the management transfer element 510-535 deletes the old transfer state. In some embodiments, the controller group 505 sets the management transfer element to delete the old transfer state after a lapse of a predetermined time after receiving the new transfer state. In another embodiment, controller group 505 sends a command to the management transfer element to delete the old transfer state.

FIG. 6 is a diagram conceptually illustrating a procedure 600 that some embodiments perform to update the transfer state and transmit it to the management transfer element. Specifically, procedure 600 relates to an embodiment in which all logical transfer decisions are made in the first hop management transfer element. In some embodiments, procedure 600 is performed by controller groups (not shown) such as controller groups 105 and 505 of FIGS. 1 and 5.

Step 600 begins by receiving an input (at 605) that updates the transfer state of the management transfer element managed by the controller group. These updates to the transfer state can occur for at least three reasons. First, the transfer state changes when the logical policy changes as the network policy executed by the logical pipeline is reconfigured by the user (eg, by updating the access control list). Secondly, the transfer state changes due to the operation change of the processing load. For example, if the virtual machine moves from the first node to the second node, the logical view remains immutable. However, because the physical location of the logical port to which the virtual machine is attached changes, this transfer requires the transfer state to be updated. Third, physical reconfiguration events such as the addition, removal, upgrade and reconfiguration of managed transfer elements can change the transfer state.

Next, the procedure 600 calculates (610) the updated transfer state based on the received input. This calculation includes the conversion of LCP data to LFP data and the conversion of LFP data to UPCP or CPCP data. The updated LCP data can affect some logical transfer factors. That is, when logical paths (ie, many logical paths between many pairs of logical ports of the affected logical transfer element) are deleted, added, or modified, they are affected logically. Physical routes to realize the routes are also removed, added, or modified.

In some embodiments, the logical transfer operation of these affected logical transfer elements is performed only by the first hop management transfer element. For example, to execute the logical L2 transfer operation of the first logical switch, the logical L3 routing of the logical router, and the logical L2 transfer operation of the second logical switch that acquires the packet routed by the logical router. The controller group sets the first hop management transfer element. Therefore, the transfer state calculated by the procedure 600 in these embodiments is only related to the first hop transfer element. The intermediate and final hop forwarding elements for these routes are used as configurations to forward the packet to the destination machine. Therefore, the transfer state does not cause the managed transfer element to add version information to the packet.

Next, step 600 calculates (610) an updated transfer state for the management transfer element to operate as the first hop transfer element. Then, step 600 transmits (615) the updated transfer status to the management transfer element. This causes the managed transfer element to have both an old transfer state and an updated transfer state.

If necessary, step 600 sends a command (625) to the management transfer element to remove the old transfer state from the management transfer element. In some embodiments, instead of sending an explicit command to switch to the new transfer state, the controller group replaces the old transfer state with the new transfer state as soon as the management transfer element receives the new transfer state. , Set the management transfer element to delete the old transfer state. Alternatively, or in combination with it, the controller group configures the management transfer element to delete the old transfer state after a predetermined time has elapsed after receiving the new transfer state, instead of sending a command to the management transfer element. Then, the procedure ends.

FIG. 6 shows a procedure 600 executed by the network controller group according to some embodiments, while FIG. 7 shows a procedure executed by the management transfer element according to some embodiments. FIG. 7 conceptually illustrates a procedure 700 that some embodiments perform to transfer data. Step 700 is performed by a management transfer element that uses a transfer state to operate as the first hop transfer element.

The procedure is initiated by forwarding an incoming packet (705) using the current forwarding state (old forwarding state). Incoming packets are from the end machine with which the management forwarding elements interact directly. The transfer status is received by transmitting the transfer status to the management transfer element from the controller group or the chassis controller that manages the management transfer element.

Next, the procedure 700 receives the updated transfer state from the controller group (710). This transfer state has been updated by the controllers and contains the CPCP data converted from the LCP data. In some embodiments, the controller transmits the updated transfer state to the first hop management transfer element after the management transfer element acting as the non-first hop transfer element receives the updated transfer state. This causes the managed transfer element to have both an old transfer state and an updated transfer state.

Then, the procedure 700 receives a command (715) from the controller group to start using the updated transfer state for the transfer of incoming data. Upon receiving the command, the first hop management transfer element according to some embodiments switches the old transfer state to the updated transfer state. In some embodiments, this command may be implicit. That is, the first hop management transfer element uses the new transfer state as soon as the new transfer state is installed on the first hop management transfer element without receiving an explicit command to switch to the new transfer state. ..

Then, the procedure 700 forwards (720) the incoming packet using the updated forwarding state. The non-first hop management transfer element that obtained the packets from the first hop management transfer element will use the updated transfer state to transfer those packets. In some embodiments, step 700 adds version information to the packet so that the non-first hop management transfer element can select a new transfer state to transfer the packet from the first hop management transfer element.

At 725, step 700 receives a command from the controller group to delete the old transfer state as needed. In some embodiments, the managed transfer element does not receive an explicit command to delete the old transfer state. Instead, the management transfer element is set by the controller group to delete the old transfer state after a predetermined time has elapsed after receiving the updated transfer state. Then, step 700 deletes (730) the old transfer state. Then, the procedure ends.

As described in Section I, the network control system according to some embodiments makes logical forwarding decisions (ie, which one or more logical ports should receive packets) in the first hop as well as in the non-first hop. Run with hops. In some of these embodiments, the transactional updates across the network are (1) transactional updates of the first hop management transfer element and (2) from the first hop management transfer element to the last hop management transfer element. It is divided into transactional updates of routes through the network. If these two can be realized, the entire transaction can be provided. That is, by preparing a new required route before updating the first hop with a new policy, the overall state update becomes atomic. After these two steps, network routes that are not needed for the new first hop state setting can be removed.

FIG. 8 conceptually shows a group of network controllers in a network control system that employs this two-step method. Specifically, this figure shows that the network controller group 805 transmits transfer state updates to two groups of management transfer elements in two parts in four different stages 801-804. The network controller group 105 described with reference to FIG. 1 in that the network controller group 805 has a logical controller and a physical controller (not shown) that generate, update, and transmit the transfer state to the management transfer element set 810-835. Is similar to. The management transfer element 810-835 transfers network data (not shown) between the end machine sets 840-850 based on the transfer status received from the network controller group 805.

In the first stage 801 the management transfer element 810-835 transfers network data (not shown) based on the current transfer state (old state) of the management transfer element. Specifically, the route defined by the controller group for the packet transmitted from the end machine 840 to the end machine 845 spans the management transfer elements (MFE) 810, 815, and 820, as shown by the solid line in the figure. .. Also, in step 801 the controller group 805 receives updates to the transfer state from the user (eg, through an input transaction controller not shown). This update represents a new network policy, such as a new QoS policy that specifies different allowed bandwidths, or a new route from one virtual machine (VM) to another newly offered virtual machine.

In the second stage 802, the controller group 805 calculates the transfer state update (eg, by converting the input LCP data into UPCP or CPCP data). In some embodiments, the controller group 805 identifies all management transfer elements that implement the logical transfer element. Specifically, the controller group 805 is the first regarding the route of the packet to be transferred from the first physical port mapped to the logical inlet port and the logical exit port of the logical transfer element to the second physical port. A transfer element having a physical port (eg, a first hop transfer element) and a transfer element having a second physical port (eg, a last hop transfer element) are identified. Then, the controller group 805 classifies the first hop management transfer element into one group and the final hop management transfer element and other management transfer elements existing in the packet route into another group for this route.

For example, the updated forwarding state has a new path for packets destined for end machine 850 sent from end machine 840. Here, the end machine 550 is an end machine added to the network after the old transfer state is calculated and transmitted to the network transfer element. With respect to this new route, the management transfer element 810 is the first hop management transfer element and the management transfer element 820 is the final hop transfer element. The management transfer element 815 is one of a plurality of "intermediate" management or unmanaged transfer elements (not shown) that forward the packet towards the final hop management transfer element 835.

The controller group 805 calculates the updated transfer status information for all the routes affected by the update by the user, and identifies the first hop management transfer element and the non-first hop management transfer element for each of the routes. In step 802, controller group 805 transmits the updated transfer state to the non-first hop management transfer element. For simplification of the figure, step 802 shows the old and new transfer states for the route starting from the management transfer element 810. Therefore, for these routes, the management transfer element 810 has only the old transfer state, and the other management transfer elements have both the old transfer state and the new transfer state. The management transfer element 820 does not have a transfer state for forwarding packets toward the destination machine 850 (that is, the mapping between the logical exit port and the physical port of the management transfer element 850 is the first hop transfer element. Since it does not exist in 810), the first hop management transfer element 820 still cannot correctly transfer the packet for a new route regarding the packet transmitted from the end machine 840 to the end machine 850.

In the third stage 803, the controller group 805 transmits the update calculated for the first hop transfer element for all routes. As a result, the management transfer element 810 has a new transfer state for functioning as a first hop transfer element for the route based on itself. Then, with respect to the new route for the packet transmitted from the end machine 840 to the end machine 850, the management transfer element 810 can correctly transfer the packet based on the new transfer state.

In some embodiments, the management transfer element, which is the first hop transfer element, begins to use the new transfer state when it receives the new transfer state. However, in some embodiments, the controller group 805 sends a command to the management transfer element to use the updated transfer state to transfer the packet as the first hop transfer element.

In some embodiments, the management transfer element, which acts as the first hop transfer element for packets received directly from the source machine, adds version information to those packets. In some embodiments, the management transfer element uses a particular binary bit of the packet as a version indicator or adds two or more bits to each packet to store version information. In some of these embodiments, this version bit swaps its value each time the managed transfer element switches to a new version of the transfer state update. Then, the non-first hop management transfer element uses the old transfer state or the new transfer state based on the version information carried by the packet. In this way, a particular packet is forwarded based on one of the old and new forwarding states, not based on both the old and new forwarding states.

In the fourth stage 804, the management transfer element 810-835 deletes the old transfer state. In some embodiments, the controller group 805 sets the management transfer element to delete the old transfer state after a lapse of a predetermined time after receiving the new transfer state. In another embodiment, the controller group 805 sends a command to the management transfer element to delete the old transfer state.

The four steps 801-804 in FIG. 8 show the update of one old route and one new route. Since many other routes can be defined to implement the logical transfer element, the controller group 805 and the management transfer element 810-835 perform the two-step process described for the four steps 801-804 with the effect of user updates. Execute for all received routes. FIG. 9, which is the next figure, is a diagram conceptually showing a procedure 900 that some embodiments perform to send an update to a management transfer element for all routes that have been updated or generated. In some embodiments, procedure 900 is performed by controller groups (not shown) such as controller groups 105 and 805 of FIGS. 1 and 8.

Step 900 starts by receiving (905) an input that updates the transfer state of the management transfer element managed by the controller group. These updates to the transfer state can occur for the three reasons mentioned above.

Next, step 900 calculates (910) the updated transfer state based on the received input. This calculation includes the conversion of LCP data to LFP data and the conversion of LFP data to UPCP or CPCP data. The updated LCP data can affect several logical forwarding elements, including logical L2 switches and logical L3 routers. That is, when logical paths (ie, many logical paths between many pairs of logical ports of the affected logical transfer element) are deleted, added, or modified, they are affected logically. Physical routes to realize the routes are also removed, added, or modified. Therefore, the updated transfer state is for both the first hop transfer element and the non-first hop management transfer element for all affected physical routes.

Step 900 then identifies (915) a new transfer state for the management transfer element to operate as a non-first hop management transfer element. This transfer state is for a management transfer element that exists in the path affected by the input but is not the first hop management transfer element for that route.

In some embodiments, only the first hop management transfer element and the last hop management transfer element require a transfer state update. In some of these embodiments, the logical transfer element affected by the input is realized only by the first hop management transfer element and the final hop management transfer element. For example, the logical L2 transfer operation of the first logical switch (for example, the packet is logically transferred based on its MAC address) and the logical L3 routing of the logical router (for example, the packet is logically transferred based on its IP address). The controller group sets the first hop management transfer element to execute (routing). The controller group sets the final hop management transfer element to perform the logical L2 transfer operation of the second logical switch that acquires the packet routed by the logical router. In these embodiments, the new transfer state identified (in 915) is for the final hop management transfer element of the affected route. The transfer element existing in the middle of these routes is used in a configuration that connects the first hop management transfer element and the final hop management transfer element. At 915, step 900 further transmits the transfer state identified for the non-first hop management transfer element to the non-first hop management transfer element.

Step 900 then identifies (920) a new transfer state for the management transfer element to operate as the first hop management transfer element. This transfer state is for the management transfer element, which is the first hop management transfer element in the path affected by the input. At 920, step 900 further transmits the transfer state identified for the first hop management transfer element to the first hop management transfer element.

In some embodiments, the transfer state updates do not have to be generally ordered. It is only necessary that the updates for each first hop element be performed sequentially. That is, when there are a plurality of first hop elements that require the update of the transfer state, those updates can proceed in parallel and independently. Only the calculation needs to be done transactionally.

In some embodiments, the network control system is the state of the entire network when the transfer state for the non-first hop transfer element of the route changes so much that the old and new routes may be mixed. Use the techniques described in the Reitblatt literature to update. This can happen, for example, if the routing label addressing method varies between software versions (of the network controller). For this type of situation, the controllers reserve the first bit (or a few bits) of the route label / address as the network-wide version bit so that the route addressing structure can be changed as needed. .. However, as long as the label / address structure does not change, the entire network can be updated by the above procedure by adding a new route and migrating the first hop management transfer element after the rest of the route is ready. Please note that there is.

After transmitting the updated transfer status for the first hop management transfer and the non-first hop transfer element to the management transfer element, step 900 confirms from all the management transfer elements that have transmitted the updated transfer status. It is determined (925) whether or not confirmation) has been received. The acknowledgment indicates that the management transfer element has received the updated transfer status from the controllers. In some embodiments, step 900 transfers for the first hop transfer element only after each of the management transfer elements that received the updated transfer state for the non-first hop transfer element returns an acknowledgment. Send the status to the management transfer element. Then, procedure 900 of these embodiments waits for an acknowledgment from each of the management transfer elements that has received the updated transfer state for the non-first hop management transfer element.

If it is determined (925) that some of the management transfer elements that have received the updated transfer status have not returned the confirmation response, the procedure 900 returns to 925 and waits for the confirmation response. However, in some embodiments, step 900 may proceed to 930 after a predetermined time has elapsed since the updated transfer state was transmitted to the management transfer element.

If the procedure 900 determines (925) that all of the management transfer elements that have received the updated transfer status have returned an acknowledgment, the procedure 900 according to some embodiments is updated for the first hop transfer element. A command is sent (930) to the management transfer element to apply the transfer state. In some embodiments, when the management transfer element forwards packets using the updated transfer state, the management transfer element uses the transfer state in which the non-first hop management transfer element updates those packets. Include version information (eg, version bits) in the packet to forward.

If necessary, step 900 sends a command (935) to the management transfer element to remove the old transfer state from the management transfer element. In some embodiments, the controller group configures the management transfer element to delete the old transfer state after a predetermined time has elapsed after receiving the new transfer state, instead of sending a command to the management transfer element. Then, the procedure ends.

FIG. 9 shows a procedure 900 executed by the network controller group according to some embodiments, but FIG. 7 shown in the next figure shows a procedure executed by the management transfer element according to some embodiments. .. FIG. 10 conceptually illustrates a procedure 1000 that some embodiments perform to transfer data. Step 1000 is performed by a managed transfer element that uses a transfer state to act as a non-first hop transfer element.

Step 1000 is initiated by forwarding an incoming packet (1005) using the current forwarding state (old forwarding state). Incoming packets are not from the end machine with which the management forwarding elements interact directly. That is, the management transfer element exists in the path of these packets, but is not the first hop transfer element for those packets. The transfer status is received by transmitting the transfer status to the management transfer element from the controller group or the chassis controller that manages the management transfer element.

Next, the procedure 1000 receives the updated transfer state from the controller group (1010). This transfer state is updated by the controller group and, in some embodiments, includes CPCP data converted from LCP data. This causes the managed transfer element to have both an old transfer state and an updated transfer state.

Step 1000 then forwards (1015) the incoming packet using the updated forwarding state. In some embodiments, step 1000 selects an old or new forwarding state to forward the incoming packet, based on the version information carried by the incoming packet. That is, this version information is used to collate the version information of the old transfer state and the updated transfer state installed in the managed transfer element.

In 1025, step 1000 receives a command from the controller group to delete the old transfer state as needed. In some embodiments, the managed transfer element does not receive an explicit command to delete the old transfer state. Instead, the management transfer element is set by the controller group to delete the old transfer state after a predetermined time has elapsed after receiving the updated transfer state. Then, step 1000 deletes (1025) the old transfer state. Then, the procedure ends.

C. External dependency modeling In the above discussion, we considered the requirements that apply to transactionality in network control systems and the realization of transaction updates across networks (eg, by separating first hop processing updates and non-first hop processing updates). .. The network control system also calculates the update of the network transfer state transactionally.

Obviously, if the policy changes, the network control system will converge the calculation before updating anything transactionally. As described above, the network control system according to some embodiments uses an nLog table mapping engine to implement the network controller of the system. The nLog engine in some embodiments causes the calculation to reach its fixed point. That is, the nLog engine calculates all changes to the transfer state based on the input changes received so far.

At high levels, reaching a local definite point is easy, and it is sufficient to stop supplying new updates to the compute engine (ie, the nLog engine) and wait until the engine has nothing to process. However, in a network environment, the definition of a fixed point is understood a little more broadly. The calculation can reach a definite point, but it does not mean that it has reached a result that can be pushed to the management transfer element. For example, if you change the destination port of a tunnel, the UPCP data will only have placeholders for the physical port to which the destination port is mapped.

After all, it turns out that the calculation can depend on external changes that must be applied before it is possible to complete the calculation and reach a fixed point corresponding to the available and pushable transfer state. Continuing with the same example, placeholders for port numbers in flow entries will only be filled after the tunnel port that will result in the port number has been configured. In this case, the UPCP calculation cannot be considered complete until the dependency on some new external state (eg, the port number due to the tunnel being created) is resolved.

Therefore, it is necessary to consider these external dependencies in the calculation and include them in the judgment of the definite point. That is, the definite point has not been reached until the calculation is completed locally and the unresolved external dependencies disappear. In some embodiments, the nLog calculation consists of addition and removal of intermediate results, and any change in configuration or external state leads to addition and removal of the calculated state.

The nLog calculation engine must meet the following requirements to take into account external dependencies in UPCP calculation.

(1) If the result of the change should be added before the new UPCP data is pushable (for example, if a tunnel must be created to complete the UPCP flow entry), apply the change immediately. .. The nLog calculation engine must consider the definite point unreachable until the result of the change (eg, a new port number) is returned to the nLog calculation engine.

(2) The result of the change may affect the current UPCP data (eg, delete the old tunnel), but complete the update before the transaction is committed (ie, a new network forwarding state is enforced). If not, the change must be applied only after the transaction has been committed. Otherwise, network transfers may change before the transaction is committed. Atomic changes to external resources cannot be supported if the above rules are applied. Fortunately, most resource changes can be modeled as additions / removals. For example, if you change the configuration of a port that represents a tunnel to a particular destination, you can consider the new configuration as a new port that temporarily coexists with the old port.

So, at a high level, the above technique consists of the ability to add a new setting next to an old one. This is typically the case for network management resources residing in the route. If constraints exist (eg, if for some reason two tunnels to the same IP cannot exist), this technique will not work and therefore cannot provide the atomicity of such changes.

FIG. 11 is a diagram conceptually illustrating a procedure 1100 that some embodiments perform to transactionally calculate a transfer state and send it to a managed transfer element set. In some embodiments, step 1100 is performed by a physical controller or a chassis controller that receives UPCP data and converts it into CPCP data. The procedure begins with receiving (1105) a transfer state change set (eg, a data tuple) containing UPCP data from the logical or physical controller.

Then, the procedure 1100 determines (1105) whether or not the received change has an external dependency. In some embodiments, the controller processing the change does not have complete information to process the change and the missing information must be obtained from another controller or management transfer element. , The change has an external dependency. For example, in order to translate an UPCP change that specifies that a managed forwarding element must establish a tunnel from its own port into a CPCP change, the actual port number of the port is required in that CPCP change. That is, CPCP changes cannot be generated until the actual port number is received from the management forwarding element.

If the procedure 1100 determines (1105) that the received change does not have an external dependency, the procedure 1100 proceeds to 1115, which will be described later. If step 1100 determines (1105) that the change has an external dependency, step 1100 calculates a set of output changes based on the received change, which has an external dependency, and uses the calculated change as a management transfer element. Send. This output change set requests the management transfer element for the missing information. Step 1100 then returns to 1105 to receive further changes from a logical or physical controller, or from a management transfer element that may return missing information to resolve external dependencies.

If step 1100 determines (1105) that the received change has no external dependency, step 1100 calculates the output change set (1110) (eg, by converting the UPCP change to a CPCP change) and step 1100. Determines (1115) whether it has reached a definite point that would mean the end of the transactional calculation of output changes. In other words, step 1100 determines if the received changes have been completely processed and step 1100 does not currently have input changes to process.

If the procedure 1100 determines (1115) that the procedure has not yet reached the definite point, the procedure 1100 returns to 1115 to continue calculating the output change based on the input change. Otherwise, step 1125 sends an output change to the management transfer element. Then, the procedure ends.

D. Communication requirements for transactional updates The above discussion shows that it is sufficient to calculate the updates in a transactional way and push them to the first hop edge transfer element. Therefore, one or more additional requirements are imposed on the system in addition to the calculation. It is a transactional communication channel.

Thus, in some embodiments, the communication channels to the transfer element (eg, from the input conversion controller to the logical controller, from the logical controller to the physical controller, from the physical controller to the chassis controller or management transfer element, and / or from the chassis controller). The communication channel to the transfer element) supports batch changes to the unit, which may or may not be fully applied. In some of these embodiments, the communication channel only supports the concept of a "barrier" (ie, start and end tags) that notifies the receiver about the end of a transaction. As mentioned above, the receive controller or management transfer element simply queues updates until it receives the barrier. The channel must also maintain the order of the updates sent, or at least ensure that updates sent before the barrier do not arrive after the barrier.

In this way, the transmit controller can continue to send updates to the state as the calculation progresses, and once determined to reach a fixed point, it notifies the first receive hop transfer element about the end of the transaction. .. Communication channels in some embodiments are synchronized so that the transmit controller knows when a transaction has been processed (calculated until it reaches a fixed point) and pushes further (if necessary), as further described below. Supports commits. It should be noted that in the case of nested transactions, synchronous commits can result in additional synchronous commits internally at the lower layers of the network control system, as described below.

We have described the realization of transactions for the entire network. Section III below describes the realization of transactions on several channels towards the management transfer element.

III. Transaction nesting As described above with reference to FIGS. 5-10, by separating the beginning of the network from the rest with respect to updating the transfer state, the network control system according to some embodiments has a nested transaction structure. Generate efficiently. One global transaction can be thought of as containing two sub-transactions, one for the first hop port and one for the non-first hop port. Either the solution manages the non-first hop port with the finest particle size (by knowing all the physical hops in the middle of the network and establishing the required state), or the solution manages the network in a transactional way. This approach remains the same regardless of whether it is assumed that traversal connectivity can be established.

In some embodiments, this is generalized to a principle that allows a basic distributed transaction to be created from a finer set of transactions. Specifically, consider a management transfer element that has multiple communication channels to the controller, where each channel provides transactionality but does not support transactions that span multiple channels. That is, these channels do not support distributed transactions. Even in such a situation, the method of exactly the same configuration works. As long as one of the channels can be considered to be the main channel to which the transaction applies, the state of any of the other channels will not be used. With this type of configuration, the main channel commits a transaction (just as a non-first hop management transfer element is prepared before the first hop management transfer element commits its own transaction). Before, the secondary channel can be "prepared" again. In this way, the end result is a single global transaction that is committed when the transaction on the first hop management transfer element is committed.

FIG. 12 shows a state in which the controller 1210 establishes a management transfer element 1205 and two channels 1215, 1220 to transmit updates to the management transfer element 1205. Specifically, this figure shows at four different stages 1201-1204 that the management transfer element 1205 does not use updates received through multiple channels until updates from channel 1215 arrive.

The controller 1210 is the same as the controller 200 of FIG. In some embodiments, the controller 1210 is a physical controller that converts UPCP data into CPCP data. In another embodiment, the controller 1210 is a chassis controller that converts UPCP data received from the physical controller into CPCP data.

In some embodiments, the controller 1210 establishes a management transfer element 1205 and two channels 1215, 1220. Channel 1215 is established using a communication protocol for controlling the transfer plane (eg, transfer table) of management transfer element 1205. For example, the OpenFlow protocol adds a flow entry to a flow entry in a managed transfer element 1205, removes a flow entry from a flow entry in a managed transfer element 1205, or modifies a flow entry in a managed transfer element 1205. Provides a command to do. Channel 1220 is established using the configuration protocol. The management transfer element 1205 receives the setting information through the channel 1220. In some embodiments, the management transfer element 1205 stores the setting information in a setting database (not shown). In some embodiments, the configuration information includes information for configuring the management transfer element 1205, such as information regarding QoS settings for inlet ports, exit port ports, and the like. For simplicity of illustration and description, flow entry and configuration information is illustrated as transfer information.

The management transfer element 1205 interacts directly with some end machines (not shown) and sends and receives data to and from the end machines using the transfer state received from the controller 1205 through the two channels. Neither of these two channels supports distributed transactions, but management transfer element 1205 spans these two channels by nesting transactions from channel 1220 into transactions to channel 1215. Achieve distributed transactions. For example, in some embodiments, the management transfer element 1205 has channel 1215 as the primary channel and channel 1220 as the secondary channel. The management transfer element 1205 suspends the application of the transfer state received through the plurality of channels until the management transfer element 1205 receives a transaction from the main channel.

In the first stage 1201, the management transfer element 1205 has just received a change set (eg, a data tuple) from the controller 1210 through channels 1215 and 1220. These changes received through channel 1215 include flow entries. Changes received through channel 1220 include configuration information.

At step 1201, changes 1-1 are received through the main channel 1215. Modifications 2-1 and 2-2 are received through subchannel 1220. The management transfer element stores these changes in the storage structure 1230, but the management transfer element 1205 has not yet received all of the transactions through the main channel 1215, so it can be used to transfer incoming packets (not shown). I haven't started using these changes yet. The management forwarding element uses the current forwarding state to forward incoming packets.

The first stage 1201 also indicates that changes 1-2 have arrived through the main channel 1215 and changes 2-3 have arrived at the management transfer element 1220 through the secondary channel 1220. Modifications 2-3 are illustrated as parallelograms with a bold frame indicating that they are the last modification in a transaction involving modifications 2-1, 2, 2, and 2-3 received through subchannel 1220.

In the second stage 1202, the management transfer element 1205 receives modifications 1-2 and 2-3 through the main channel 125 and the sub-channel 1220, respectively. The management transfer element 1205 stores the changes 1-2 and 2-3 in the storage structure 1230, but has not yet received all of the transactions from the main channel 1215, so the incoming packet transfer and management transfer element 1205 These changes are not used in the setting of.

The second stage 1202 further indicates that changes 1-3 have arrived at the management transfer element 1205 through the main channel 1215. Changes 1-3 are illustrated as parallelograms with a thick frame indicating that they are the last changes received through the main channel 1215 in a transaction involving changes 1-1, 1-2, 1-3.

In the third stage 1203, the management transfer element 1205 has received the changes 1-3 through the main channel 1215, and therefore has received all the transactions from the main channel 1215. Therefore, the management transfer element 1205 updates the transfer state with the changes received through channels 1215 and 1220 in two transactions.

The fourth stage 1204 shows the state in which the changes have been committed by the management transfer element 1205. That is, the management transfer element 1205 uses the updated transfer state for the transfer of incoming packets and the setting of the management transfer element 1205. In this way, the management transfer element 1205 nests the transaction received through the secondary channel to the transaction received through the primary channel in order to realize the global transaction between the two channels.

FIG. 13 is a diagram conceptually illustrating a procedure 1300 that some embodiments perform to combine a transaction received through the primary channel with a plurality of transactions received through the secondary channel. Procedure 1300 according to some embodiments is performed by a management transfer element (eg, management transfer element 1205 in FIG. 12) that receives transfer status from the controller through some channels established with the controller. The controller may be a physical controller that is the master of the management transfer element, or may be a chassis controller that operates on the same host as the host on which the management transfer element operates. In some embodiments, one of the plurality of channels is designated as the primary channel and the other channel is designated as the secondary channel.

Procedure 1300 begins with receiving the transfer state (1305) through the primary and secondary channels. In some embodiments, the transfer state received from the controller through multiple channels includes CPCP data. Specifically, the transfer state arriving through the main channel contains control data sent to the control plane of the management transfer element. The forwarding state coming in and out through the secondary channel contains configuration data (eg, data for configuring entry ports, exit ports, QoS settings for ports, middlebox instances, etc.). However, in some embodiments, as long as one of the plurality of channels is designated as the primary channel and the other channel is designated as the secondary channel, the primary and secondary channel designations are the types of data received through those channels. You don't have to rely on.

The procedure 1300 then determines (1310) whether or not the procedure 1300 has received the barrier through the main channel. As mentioned above, the barrier indicates that one transaction of the input has been completely received by the receiving device when received by the receiving device. In some embodiments, the barrier is the information added to the change. The barrier according to the other embodiment is the change itself, indicating that the sender of the change has completely transmitted the transaction input set.

If the procedure 1300 determines (1310) that the barrier has not been received through the main channel, the procedure stores the previously received transfer state in the storage structure (1320). The transfer state stored in the storage structure is not used by the management transfer element. Step 1300 returns to 1305 to receive further transfer status from the controller group through the plurality of channels.

If the procedure 1300 determines (1310) that the barrier is being received through the main channel, the procedure updates the transfer table and configuration database of the management transfer element with the transfer status it has received so far. The management transfer element then sets itself using the configuration data and initiates the transfer of incoming packets based on the updated flow entry in the transfer table. Then, the procedure 1300 ends.

Note that this generalization allows transactions to be nested to any depth if desired. Specifically, a transactional system can build its own transactionality from nested transactions. The ability to build transactionality from nested transactions is not only useful in a hierarchical structure that can be formed by multiple controllers, but these transfer elements also provide a transactional interface to multiple controllers that manage multiple transfer elements. It is also useful when considering how it can be provided.

The network control system according to some embodiments, again using the same nesting principles, introduces transactionality into the communication channel without explicit support for transactionality in the underlying management resources. Consider a route using an easily expandable table pipeline. Even if the flow table update doesn't support transactions, it's easy to add a stage in front of an existing pipeline and let one flow entry decide which version of state to use. Therefore, the entire flow table can be updated transactionally by then updating one flow entry (which is transactional). The details of this technique need not be shown to the upper controller. However, in effect, there are multiple transaction hierarchies.

As a use case for the above embodiments, migrating from one controller version to another (ie, software version) will benefit from in-system transaction and deterministic support. In this use case, the external upgrade driver performs the entire upgrade process from one controller version to another. It is the driver's responsibility to coordinate the upgrade in a way that does not cause packet loss.

The overall steps performed by the driver to construct a single global transaction consisting of multiple smaller sub-transactions are as follows:

(1) When an upgrade of the transfer state is required, the driver requests the start of calculation of a new state for the network middle (fabric). This is done for all controllers that manage the state of the network middle state, and the new middle state is expected to coexist with the old middle state.

(2) Then, the driver waits for each controller to reach the fixed point, and commits the transaction in synchronization with the receiving controller / switching element in the downward direction. The driver performs the commit in a synchronous manner because it is after the commit that the driver knows that the state is active on the switching element and is available in the packet.

(3) The driver then requests the controller to update to a new edge transfer state that will also be used for the new route established in (1) for the middle part of the network.

(4) Again, the driver requires all controllers to reach a fixed point, and when the fixed point is reached, commits the update synchronously.

(5) When the driver requests the removal of the old network middle state, the update is completed. You don't have to wait for a definite point to commit here. The removal will be pushed along with any other changes that the controller will eventually push.

IV. Electronic system Many of the functions and applications described above are implemented as software processes defined as instruction sets recorded on a computer-readable storage medium (also called a computer-readable medium). When these instructions are executed by one or more processing units (eg, one or more of processors, processor cores, or other processing units), the operations indicated in the instructions to one or more processing units. Let it run. Examples of computer-readable media include, but are not limited to, CD-ROMs, flash drives, RAM chips, hard disk drives, EPROMs, and the like. Computer-readable media do not include carrier or electronic signals that pass over a wireless or wired connection.

As used herein, the term "soft meaning of ware" includes firmware and present in read only memory, what can be read into memory for processing by the processor, such as a stored application in the magnetic storage device .. Also, in some embodiments, the plurality of software inventions may be implemented as multiple subparts of one larger program while preserving the identifiable software invention. In some embodiments, multiple software inventions may be implemented as separate programs. Finally, any combination of individual programs that jointly implement the software inventions described herein is also within the scope of the invention. In some embodiments, those software programs specify one or more specific hardware implementations that, when installed to run on one or more electronic systems, perform the actions of those software programs. To do.

FIG. 14 is a diagram conceptually showing an electronic system 1400 that can be used to carry out some embodiments of the present invention. Electronic system 1400 can be used to execute any of the controls, virtualization, or operating system applications described above. The electronic system 1400 may be a computer (eg, desktop computer, personal computer, tablet computer, server computer, mainframe, blade computer, etc.), telephone, PDA, or any other type of electronic device. Such electronic systems include interfaces for various types of computer-readable media and various other types of computer-readable media. The electronic system 1400 includes bus 1405, one or more processing units 1410, system memory 1425, read-only memory 1430, permanent storage device 1435, input device 1440, and output device 1445.

Bus 1405 collectively represents a system bus, a peripheral device bus, and a chipset bus that communicatively connect a large number of internal devices of the electronic system 1400. For example, bus 1405 connects one or more processing units 1410 communicably with read-only memory 1430, system memory 1425, and permanent storage device 1435.

From these various memory units, one or more processing units 1410 read instructions to be executed and data to be processed in order to execute the processing of the present invention. The one or more processing units may be a single processor or a multi-core processor, depending on the embodiment.

Read-only memory (ROM) 1430 stores static data and instructions required by one or more processing units 1410 and other modules of the electronic system. On the other hand, the permanent storage device 1435 is a readable and writable storage device. This device is a non-volatile storage device that stores instructions and data even when the electronic system 1400 is off. Some embodiments of the present invention use a mass storage device (eg, a magnetic or optical disk and a corresponding disk drive) as the permanent storage device 1435.

Other embodiments use removable storage devices (eg, flexible disks, flash drives, etc.) as permanent storage devices. Like the permanent storage device 1435, the system memory 1425 is a readable and writable storage device. However, unlike the storage device 1435, the system memory is a volatile readable and writable 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 procedures of the invention are stored in system memory 1425, permanent storage 1435, and / or read-only memory 1430. From these various memory units, one or more processing units 1410 read instructions to be executed and data to be processed in order to execute the processing according to some embodiments.

Bus 1405 also connects input and output devices 1440 and 1445. Input devices allow users to convey information to electronic systems and select commands. The input device 1440 includes an alphanumeric keyboard and a pointing device (also referred to as a "cursor control device"). The output device 1445 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 act as both input and output devices.

Finally, as shown in FIG. 14, bus 1405 also connects the electronic system 1400 to network 1465 through a network adapter (not shown). Thus, a computer may be part of a computer network (such as a local area network (LAN), a wide area network (WAN), or an intranet, or a network of multiple networks, such as the Internet. .. Any or all components of electronic system 1400 can be used in connection with the present invention.

In some embodiments, a microprocessor and storage in which computer program instructions are stored on a device-readable or computer-readable medium (also referred to as a computer-readable storage medium, machine-readable medium, or device-readable storage medium). Includes electronic components such as devices and memory. Some examples of such computer-readable media are RAM, ROM, read-only compact discs (CD-ROMs), write-once compact discs (CD-R), rewritable compact discs (CD-RW), and read-only digital discs. Versatile discs (eg DVD-ROM, dual layer DVD-ROM), various write-once / rewritable DVDs (eg DVD-RAM, DVD-RW, DVD + RW, etc.), flash memory (eg SD card, Includes mini SD cards, micro SD cards, etc.), magnetic and / or semiconductor hard drives, read-only and recordable Blu-ray® discs, ultra-high density optical discs, any other optical or magnetic recording medium, and flexible discs. .. A computer-readable medium can be executed by at least one processing unit and can store a computer program containing an instruction set for performing various operations. Examples of computer programs or computer code include machine code as generated by a compiler, and files containing high-level code executed by a computer, electronic component, or microprocessor using an interpreter.

The discussion above primarily refers to microprocessors or multi-core processors running software, but in some embodiments, for example, application-specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs). It is executed by one or more integrated circuits. In some embodiments, these integrated circuits execute instructions stored in the circuit itself.

The terms "computer," "server," "processor," and "memory," as used herein, include all electronic or other technical equipment. These terms exclude humans and their groups. For explicit purposes, the term "display" means display on an electronic device. As used herein, the terms "computer-readable medium," "computer-readable medium," and "machine-readable medium" are completely restricted to tangible and physical objects that store information in a computer-readable format. To. These terms exclude any radio signal, wired download signal, and other temporary signals.

Having described the invention with reference to a number of specific details, one of ordinary skill in the art will recognize that the invention can be practiced in other particular embodiments without departing from its spirit. Also, some drawings (including FIGS. 9, 6, 10, 7, 11, and 13) conceptually show the procedure. The specific operations of these procedures do not have to be performed in the order shown and described. The specific operation does not have to be executed as one continuous operation, and another specific operation may be executed in another embodiment. In addition, the procedure may be performed using several subprocesses or as part of a larger macro process.