Network control apparatus and method with port security controls

Port security in some embodiments is a technique to apply to a particular port of a logical switching element such that the network data entering and existing the logical switching element through the particular logical port have certain addresses that the switching element has restricted the logical port to use. For instance, a logical switching element may restrict a particular logical port to one or more certain network addresses To enable a logical port of a logical switch for port security, the control application of some embodiments receives user inputs that designate a particular logical port and a logical switch to which the particular logical port belongs. The control application in some embodiments formats the user inputs into logical control plane data specifying the designation. The control application in some embodiments then converts the logical control plane data into logical forwarding data that specify port security functions.

BACKGROUND

Many current enterprises have large and sophisticated networks comprising switches, hubs, routers, servers, workstations and other networked devices, which support a variety of connections, applications and systems. The increased sophistication of computer networking, including virtual machine migration, dynamic workloads, multi-tenancy, and customer specific quality of service and security configurations require a better paradigm for network control. Networks have traditionally been managed through low-level configuration of individual components. Network configurations often depend on the underlying network: for example, blocking a user's access with an access control list (“ACL”) entry requires knowing the user's current IP address. More complicated tasks require more extensive network knowledge: forcing guest users' port 80 traffic to traverse an HTTP proxy requires knowing the current network topology and the location of each guest. This process is of increased difficulty where the network switching elements are shared across multiple users.

In response, there is a growing movement, driven by both industry and academia, towards a new network control paradigm called Software-Defined Networking (SDN). In the SDN paradigm, a network controller, running on one or more servers in a network, controls, maintains, and implements control logic that governs the forwarding behavior of shared network switching elements on a per user basis. Making network management decisions often requires knowledge of the network state. To facilitate management decision making, the network controller creates and maintains a view of the network state and provides an application programming interface upon which management applications may access a view of the network state.

Three of the many challenges of large networks (including datacenters and the enterprise) are scalability, mobility, and multi-tenancy and often the approaches taken to address one hamper the other. For instance, one can easily provide network mobility for virtual machines (VMs) within an L2 domain, but L2 domains cannot scale to large sizes. Also, retaining tenant isolation greatly complicates mobility. Despite the high-level interest in SDN, no existing products have been able to satisfy all of these requirements.

BRIEF SUMMARY

Some embodiments of the invention provide a system that allows several different logical data path sets to be specified for several different users through one or more shared network infrastructure switching elements (referred to as “switching elements” below). In some embodiments, the system includes a set of software tools that allows the system to accept logical data path sets from users and to configure the switching elements to implement these logical data path sets. These software tools allow the system to virtualize control of the shared switching elements and the network that is defined by the connections between these shared switching elements, in a manner that prevents the different users from viewing or controlling each other's logical data path sets (i.e., each other's switching logic) while sharing the same switching elements.

In some embodiments, one of the software tools that allows the system to virtualize control of a set of switching elements (i.e., to allow several users to share the same switching elements without viewing or controlling each other's logical data path sets) is an intermediate data storage structure that (1) stores the state of the network, (2) receives and records modifications to different parts of the network from different users, and (3), in some embodiments, provides different views of the state of the network to different users. For instance, in some embodiments, the intermediate data storage structure is a network information base (NIB) data structure that stores the state of the network that is defined by one or more switching elements. The system uses this NIB data structure as an intermediate storage structure for reading the state of the network and writing modifications to the state of the network. In some embodiments, the NIB also stores the logical configuration and the logical state for each user specified logical data path set. In these embodiments, the information in the NIB that represents the state of the actual switching elements accounts for only a subset of the total information stored in the NIB.

In some embodiments, the system has (1) a network operating system (NOS) to create and maintain the NIB storage structure, and (2) one or more applications that run on top of the NOS to specify logic for reading values from and writing values to the NIB. When the NIB is modified in order to effectuate a change in the switching logic of a switching element, the NOS of some embodiments also propagates the modification to the switching element.

The system of different embodiments uses the NIB differently to virtualize access to the shared switching elements and network. In some embodiments, the system provides different views of the NIB to different users in order to ensure that different users do not have direct view and control over each other's switching logic. For instance, in some embodiments, the NIB is a hierarchical data structure that represents different attributes of different switching elements as elements (e.g., different nodes) in a hierarchy. The NIB in some of these embodiments is a multi-layer hierarchical data structure, with each layer having a hierarchical structure and one or more elements (e.g., nodes) on each layer linked to one or more elements (e.g., nodes) on another layer. In some embodiments, the lowest layer elements correspond to the actual switching elements and their attributes, while each of the higher layer elements serves as abstractions of the actual switching elements and their attributes. As further described below, some of these higher layer elements are used in some embodiments to show different abstract switching elements and/or switching element attributes to different users in a virtualized control system.

In some embodiments, the definition of different NIB elements at different hierarchical levels in the NIB and the definition of the links between these elements are used by the developers of the applications that run on top of the NOS in order to define the operations of these applications. For instance, in some embodiments, the developer of an application running on top of the NOS uses these definitions to enumerate how the application is to map the logical data path sets of the user to the physical switching elements of the control system. Under this approach, the developer would have to enumerate all different scenarios that the control system may encounter and the mapping operation of the application for each scenario. This type of network virtualization (in which different views of the NIB are provided to different users) is referred to below as Type I network virtualization.

Another type of network virtualization, which is referred to below as Type II network virtualization, does not require the application developers to have intimate knowledge of the NIB elements and the links (if any) in the NIB between these elements. Instead, this type of virtualization allows the application to simply provide user specified, logical switching element attributes in the form of one or more tables, which are then mapped to NIB records by a table mapping engine. In other words, the Type II virtualized system of some embodiments accepts the logical switching element configurations (e.g., access control list table configurations, L2 table configurations, L3 table configurations, etc.) that the user defines without referencing any operational state of the switching elements in a particular network configuration. It then maps the logical switching element configurations to the switching element configurations stored in the NIB.

To perform this mapping, the system of some embodiments uses a database table mapping engine to map input tables, which are created from (1) logical switching configuration attributes, and (2) a set of properties associated with switching elements used by the system, to output tables. The content of these output tables are then transferred to the NIB elements. In some embodiments, the system uses a variation of the datalog database language, called nLog, to create the table mapping engine that maps input tables containing logical data path data and switching element attributes to the output tables. Like datalog, nLog provides a few declaratory rules and operators that allow a developer to specify different operations that are to be performed upon the occurrence of different events. In some embodiments, nLog provides a limited subset of the operators that are provided by datalog in order to increase the operational speed of nLog. For instance, in some embodiments, nLog only allows the AND operator to be used in any of the declaratory rules.

The declaratory rules and operations that are specified through nLog are then compiled into a much larger set of rules by an nLog compiler. In some embodiments, this compiler translates each rule that is meant to address an event into several sets of database join operations. Collectively the larger set of rules forms the table mapping, rules engine that is referred to below as the nLog engine. In some embodiments, the nLog virtualization engine also provides feedback (e.g., from one or more of the output tables or from NIB records that are updated to reflect values stored in the output tables) to the user in order to provide the user with state information about the logical data path set that he or she created. In this manner, the updates that the user gets are expressed in terms of the logical space that the user understands and not in terms of the underlying switching element states, which the user does not understand.

The use of nLog serves as a significant distinction between Type I virtualized control systems and Type II virtualized control systems, even for Type II systems that store user specified logical data path sets in the NIB. This is because nLog provides a machine-generated rules engine that addresses the mapping between the logical and physical domains in a more robust, comprehensive manner than the hand-coded approach used for Type I virtualized control systems. In the Type I control systems, the application developers need to have a detailed understanding of the NIB structure and need to use this detailed understanding to write code that addresses all possible conditions that the control system would encounter at runtime. On the other hand, in Type II control systems, the application developers only need to produce applications that express the user-specified logical data path sets in terms of one or more tables, which are then mapped in an automated manner to output tables and later transferred from the output tables to the NIB. This approach allows the Type II virtualized systems not to maintain the data regarding the logical data path sets in the NIB. However, some embodiments maintain this data in the NIB in order to distribute this data among other NOS instances, as further described below.

As apparent from the above discussion, the applications that run on top of a NOS instance can perform several different sets of operations in several different embodiments of the invention. Examples of such operations include providing an interface to a user to access NIB data regarding the user's switching configuration, providing different layered NIB views to different users, providing control logic for modifying the provided NIB data, providing logic for propagating received modifications to the NIB, etc.

In some embodiments, the system embeds some or all such operations in the NOS instead of including them in an application operating on top of the NOS. Alternatively, in other embodiments, the system separates some or all of these operations into different subsets of operations and then has two or more applications that operate above the NOS perform the different subsets of operations. One such system runs two applications on top of the NOS, a control application and a virtualization application. In some embodiments, the control application allows a user to specify and populate logical data path sets, while the virtualization application implements the specified logical data path sets by mapping the logical data path set to the physical switching infrastructure. In some embodiments, the virtualization application translates control application input into records that are written into the NIB, and from the NIB these records are then subsequently transferred to the switching infrastructure through the operation of the NOS. In some embodiments, the NIB stores both the logical data path set input received through the control application and the NIB records that are produced by the virtualization application.

In some embodiments, the control application can receive switching infrastructure data from the NIB. In response to this data, the control application may modify record(s) associated with one or more logical data path sets (LDPS). Any such modified LDPS record would then be translated to one or more physical switching infrastructure records by the virtualization application, which might then be transferred to the physical switching infrastructure by the NOS.

In some embodiments, the NIB stores data regarding each switching element within the network infrastructure of a system, while in other embodiments, the NIB stores state information about only switching elements at the edge of a network infrastructure. In some embodiments, edge switching elements are switching elements that have direct connections with the computing devices of the users, while non-edge switching elements only connect to edge switching elements and other non-edge switch elements.

The system of some embodiments only controls edge switches (i.e., only maintains data in the NIB regarding edge switches) for several reasons. Controlling edge switches provides the system with a sufficient mechanism for maintaining isolation between computing devices, which is needed, as opposed to maintaining isolation between all switch elements, which is not needed. The interior switches forward between switching elements. The edge switches forward between computing devices and other network elements. Thus, the system can maintain user isolation simply by controlling the edge switching elements because the edge switching elements are the last switches in line to forward packets to hosts.

Controlling only edge switches also allows the system to be deployed independent of concerns about the hardware vendor of the non-edge switches. Deploying at the edge allows the edge switches to treat the internal nodes of the network as simply a collection of elements that moves packets without considering the hardware makeup of these internal nodes. Also, controlling only edge switches makes distributing switching logic computationally easier. Controlling only edge switches also enables non-disruptive deployment of the system. Edge switching solutions can be added as top of rack switches without disrupting the configuration of the non-edge switches.

In addition to controlling edge switches, the network control system of some embodiments also utilizes and controls non-edge switches that are inserted in the switch network hierarchy to simplify and/or facilitate the operation of the controlled edge switches. For instance, in some embodiments, the control system requires the switches that it controls to be interconnected in a hierarchical switching architecture that has several edge switches as the leaf nodes in this switching architecture and one or more non-edge switches as the non-leaf nodes in this architecture. In some such embodiments, each edge switch connects to one or more of the non-leaf switches, and uses such non-leaf switches to facilitate its communication with other edge switches. Examples of functions that such non-leaf switches provide to facilitate such communications between edge switches in some embodiments include (1) routing of a packet with an unknown destination address (e.g., unknown MAC address) to the non-leaf switch so that this switch can route this packet to the appropriate edge switch, (2) routing a multicast or broadcast packet to the non-leaf switch so that this switch can convert this packet to a series of unicast packets to the desired destinations, (3) bridging remote managed networks that are separated by one or more networks, and (4) bridging a managed network with an unmanaged network.

Some embodiments employ one level of non-leaf (non-edge) switches that connect to edge switches and in some cases to other non-leaf switches. Other embodiments, on the other hand, employ multiple levels of non-leaf switches, with each level of non-leaf switch after the first level serving as a mechanism to facilitate communication between lower level non-leaf switches and leaf switches. In some embodiments, the non-leaf switches are software switches that are implemented by storing the switching tables in the memory of a standalone computer instead of an off the shelf switch. In some embodiments, the standalone computer may also be executing in some cases a hypervisor and one or more virtual machines on top of that hypervisor. Irrespective of the manner by which the leaf and non-leaf switches are implemented, the NIB of the control system of some embodiments stores switching state information regarding the leaf and non-leaf switches.

The above discussion relates to the control of edge switches and non-edge switches by a network control system of some embodiments. In some embodiments, edge switches and non-edge switches (leaf and non-leaf nodes) may be referred to as managed switches. This is because these switches are managed by the network control system (as opposed to unmanaged switches, which are not managed by the network control system, in the network) in order to implement logical data path sets through the managed switches.

In addition to using the NIB to store switching-element data, the virtualized network-control system of some embodiments also stores other storage structures to store data regarding the switching elements of the network. These other storage structures are secondary storage structures that supplement the storage functions of the NIB, which is the primary storage structure of the system while the system operates. In some embodiments, the primary purpose for one or more of the secondary storage structures is to back up the data in the NIB. In these or other embodiments, one or more of the secondary storage structures serve a purpose other than backing up the data in the NIB (e.g., for storing data that are not in the NIB).

In some embodiments, the NIB is stored in system memory (e.g., RAM) while the system operates. This allows for fast access of the NIB records. In some embodiments, one or more of the secondary storage structures, on the other hand, are stored on disks, or other non-volatile memories, which can be slower to access. Such non-volatile disks or other non-volatile memories, however, improve the resiliency of the system as they allow the data to be stored in a persistent manner.

The system of some embodiments uses multiple types of storages in its pool of secondary storage structures. These different types of structures store different types of data, store data in different manners, and provide different query interfaces that handle different types of queries. For instance, in some embodiments, the system uses a persistent transactional database (PTD) and a hash table structure. The PTD in some embodiments is a database that is stored on disk or other non-volatile memory. In some embodiments, the PTD is a commonly available database, such as MySQL or SQLite. The PTD of some embodiments can handle complex transactional queries. As a transactional database, the PTD can undo a series of earlier query operations that it has performed as part of a transaction when one of the subsequent query operations of the transaction fails.

Moreover, some embodiments define a transactional guard processing (TGP) layer before the PTD in order to allow the PTD to execute conditional sets of database transactions. The TGP layer allows the PTD to avoid unnecessary later database operations when conditions of earlier operations are not met. The PTD in some embodiments stores the exact replica of the data that is stored in the NIB, while in other embodiments it stores only a subset of the data that is stored in the NIB. In some embodiments, some or all of the data in the NIB is stored in the PTD in order to ensure that the NIB data will not be lost in the event of a crash of the NOS or the NIB.

While the system is running, the hash table in some embodiments is not stored on a disk or other non-volatile memory. Instead, it is a storage structure that is stored in volatile system memory when the system is running. When the system is powered down, the content of the hash table is stored on disk. The hash table uses hashed indices that allow it to retrieve records in response to queries. This structure combined with the hash table's placement in the system's volatile memory allows the table to be accessed very quickly. To facilitate this quick access, a simplified query interface is used in some embodiments. For instance, in some embodiments, the hash table has just two queries, a Put query for writing values to the table and a Get query for retrieving values from the table. The system of some embodiments uses the hash table to store data that the NOS needs to retrieve very quickly. Examples of such data include network entity status, statistics, state, uptime, link arrangement, and packet handling information. Furthermore, in some embodiments, the NOS uses the hash tables as a cache to store information that is repeatedly queried, such as flow entries that will be written to multiple nodes.

Using a single NOS instance to control a network can lead to scaling and reliability issues. As the number of network elements increases, the processing power and/or memory capacity that are required by those elements will saturate a single node. Some embodiments further improve the resiliency of the control system by having multiple instances of NOS running on one or more computers, with each instance of NOS containing one or more of the secondary storage structures described above. Each instance in some embodiments not only includes a NOS instance, but also includes a virtualization application instance and/or a control application instance. In some of these embodiments, the control and/or virtualization applications partition the workload between the different instances in order to reduce each instance's control and/or virtualization workload. Also, in some embodiments, the multiple instances of NOS communicate the information stored in their secondary storage layers to enable each instance of NOS to cover for the others in the event of a NOS instance failing. Moreover, some embodiments use the secondary storage layer (i.e., one or more of the secondary storages) as a channel for communicating between the different instances.

The distributed, multi-instance control system of some embodiments maintains the same switch element data records in the NIB of each instance, while in other embodiments, the system allows NIBs of different instances to store different sets of switch element data records. Some embodiments that allow different instances to store different portions of the NIB, divide the NIB into N mutually exclusive portions and store each NIB portion in one NIB of one of N controller instances, where N is an integer value greater than 1. Other embodiments divide the NIB into N portions and store different NIB portions in different controller instances, but allow some or all of the portions to partially (but not completely) overlap with the other NIB portions.

The hash tables in the distributed control system of some embodiments form a distributed hash table (DHT), with each hash table serving as a DHT instance. In some embodiments, the DHT instances of all controller instances collectively store one set of records that is indexed based on hashed indices for quick access. These records are distributed across the different controller instances to minimize the size of the records within each instance and to allow for the size of the DHT to be increased by adding other DHT instances. According to this scheme, each DHT record is not stored in each controller instance. In fact, in some embodiments, each DHT record is stored in at most one controller instance. To improve the system's resiliency, some embodiments, however, allow one DHT record to be stored in more than one controller instance, so that in case one instance fails, the DHT records of that failed instance can be accessed from other instances. Some embodiments do not allow for replication of records across different DHT instances or allow only a small amount of such records to be replicated because these embodiments store in the DHT only the type of data that can be quickly re-generated.

The distributed control system of some embodiments replicates each NIB record in the secondary storage layer (e.g., in each PTD instance and/or in the DHT) in order to maintain the records in the NIB in a persistent manner. For instance, in some embodiments, all the NIB records are stored in the PTD storage layer. In other embodiments, only a portion of the NIB data is replicated in the PTD storage layer. For instance, some embodiments store a subset of the NIB records in another one of the secondary storage records, such as the DHT.

By allowing different NOS instances to store the same or overlapping NIB records, and/or secondary storage structure records, the system improves its overall resiliency by guarding against the loss of data due to the failure of any NOS or secondary storage structure instance. For instance, in some embodiments, the portion of NIB data that is replicated in the PTD (which is all of the NIB data in some embodiments or part of the NIB data in other embodiments) is replicated in the NIBs and PTDs of all controller instances, in order to protect against failures of individual controller instances (e.g., of an entire controller instance or a portion of the controller instance).

In some embodiments, each of the storages of the secondary storage layer uses a different distribution technique to improve the resiliency of a multiple NOS instance system. For instance, as mentioned above, the system of some embodiments replicates the PTD across NOS instances so that every NOS has a full copy of the PTD to enable a failed NOS instance to quickly reload its PTD from another instance. In some embodiments, the system distributes the DHT fully or with minimal overlap across multiple controller instances in order to maintain the DHT instance within each instance small. This approach also allows the size of the DHT to be increased by adding additional DHT instances, and this in turn allows the system to be more scalable.

For some or all of the communications between the distributed instances, the distributed system of some embodiments uses coordination managers (CM) in the controller instances to coordinate activities between the different controllers. Examples of such activities include writing to the NIB, writing to the PTD, writing to the DHT, controlling the switching elements, facilitating intra-controller communication related to fault tolerance of controller instances, etc.

To distribute the workload and to avoid conflicting operations from different controller instances, the distributed control system of some embodiments designates one controller instance within the system as the master of any particular NIB portion (e.g., as the master of a logical data path set) and one controller instance within the system as the master of any given switching element. Even with one master controller, a different controller instance can request changes to different NIB portions and/or to different switching elements controlled by the master. If allowed, the master instance then effectuates this change and writes to the desired NIB portion and/or switching element. Otherwise, the master rejects the request.

The control application of some embodiments converts control data records (also called data tuples below) to forwarding plane data records (e.g., logical forwarding plane data) by performing conversion operations. In some embodiments, the generated logical forwarding plane data is transmitted to the virtualization application, which subsequently generate physical control plane data from the logical forwarding plane data. The physical control plane data is propagated to the managed switching elements, which in turn will produce forwarding plane data (e.g., flow entries) for defining forwarding behaviors of the switches.

The input event data may be logical data supplied by the user in some embodiments. As will be described further below, some embodiments provide the user with an interface that the user can use to specify input event data. An example of user-supplied data could be logical control plane data including access control list data for a logical switch that the user manages. The input event data may also be logical forwarding plane data that the control application generates in some embodiments from the logical control plane data. The input event data in some embodiments may also be physical forwarding plane data or physical control plane data received from the NIB. In some embodiments, the control application receives the physical forwarding data from a NIB monitor that monitors the NIB to detect a change in the NIB that reflects a change in one or more managed switching elements.

The control application performs a filtering operation to determine whether this instance of the control application is responsible for the input event data. As described above, several instances of the control application may operate in parallel to control multiple sets of logical data paths in some embodiments. In these embodiments, each control application uses the filtering operation to filter out input data that does not relate to the control application's logical data path set. To perform this filtering operation, the control application of some embodiments includes a filter module. This module in some embodiments is a standalone module, while in other embodiments it is implemented by a table mapping engine (e.g., implemented by the join operations performed by the table mapping engine) that maps records between input tables and output tables of the virtualization application.

The filtering operation fails in some embodiments when the input event data does not fall within one of the logical data path sets that are the responsibility of the control application. When the filtering operation does not fail, a converter of the virtualization application generates one or more sets of data tuples based on the input event data. In some embodiments, the converter is a table mapping engine that performs a series of table mapping operations on the input event data to map the input event data to other data tuples. As mentioned above, this table mapping engine also performs the filtering operation in some embodiments. One example of such a table mapping engine is an nLog table-mapping engine. In some embodiments, the data tuples that the control application generates may include data (e.g., logical forwarding plane data) that the process has to push down to the NIB. The control application publishes to the NIB any data tuples that it generated if such publication is necessary.

The control application in some embodiments performs its mapping operations by using the nLog table mapping engine, which, as described above, is a custom variation of the datalog table mapping technique. Another custom design choice relates to the join operations performed by the nLog engine. Join operations are common database operations for creating association between records of different tables. In some embodiments, the nLog engine limits its join operations to inner join operations (also called as internal join operations) because performing outer join operations (also called as external join operations) can be time consuming and therefore impractical for real time operation of the engine.

Yet another custom design choice is to implement the nLog engine as a distributed table mapping engine that is executed by several different control applications. Some embodiments implement the nLog engine in a distributed manner by partitioning management of logical data path sets. Each logical data path set includes logical data paths that are specified for a single user of the control system in some embodiments. Partitioning management of the logical data path sets involves specifying for each particular logical data path set only one controller instance as the instance responsible for specifying the NIB records associated with that particular logical data path set. For instance, when the control system uses three switching elements to specify five logical data path sets for five different users with two different controller instances, one controller instance can be the master for NIB records relating to two of the logical data path sets while the other controller instance can be the master for the NIB records for the other three logical data path sets. Partitioning management of logical data path sets ensures that conflicting values for the same logical data path sets are not written to the NIB by two different controller instances, and thereby alleviates the applications running on top of NOS from guarding against the writing of such conflicting values. Some embodiments refer the partitioning management of logical data paths sets as serializing management of logical data paths.

Partitioning management of the LDPS′ also assigns in some embodiments the table mapping operations for each LDPS to the nLog engine of the controller instance responsible for the LDPS. The distribution of the nLog table mapping operations across several nLog instances reduces the load on each nLog instance and thereby increases the speed by which each nLog instance can complete its mapping operations. Also, this distribution reduces the memory size requirement on each machine that executes a controller instance. As further described below, some embodiments partition the nLog table mapping operations across the different instances by designating the first join operation that is performed by each nLog instance to be based on the LDPS parameter. This designation ensures that each nLog instance's join operations fail and terminate immediately when the instance has started a set of join operations that relate to a LDPS that is not managed by the nLog instance.

In addition to creating and managing logical switching elements, the control application of some embodiments allows the user to enable a logical port of a logical switching element for port security. Port security in some embodiments is a technique to apply to a particular port of a logical switching element such that the network data entering and existing the logical switching element through the particular logical port have certain addresses that the switching element has restricted the logical port to use. For instance, a logical switching element may restrict a particular logical port to one or more certain network addresses (e.g., a MAC address and/or an IP address). That is, any network traffic coming in or going out through the particular logical port must have the restricted addresses as source or destination addresses. The logical switching element drops particular network traffic entering or exiting the logical switching element through the particular logical port when the particular network traffic does not include the specified set of network addresses.

To enable a logical port of a logical switch for port security, the control application of some embodiments receives user inputs that designate a particular logical port and a logical switch to which the particular logical port belongs. The control application in some embodiments formats the user inputs into logical control plane data specifying the designation. The control application in some embodiments then converts the logical control plane data into logical forwarding data that specify port security functions.

In some embodiments, the control application also allows the user to enable a logical switching element for Quality of Service (QoS). QoS in some embodiments is a technique to apply to a particular logical port of a logical switching element such that the switching element can guarantee a certain level of performance to network data that a machine sends through the particular logical port. For instance, by enabling QoS for a particular port of a switching element, the switch guarantees a minimum bitrate and/or a maximum bitrate to network data sent by a machine to the network through the switching element.

The control application of some embodiments receives user inputs that specify a particular logical switch to enable for QoS. The control application may additionally receive performance constraints data (e.g., minimum/maximum bitrates, etc.). The control application in some embodiments formats the user inputs into logical control plane data. The control application in some embodiments then converts the logical control plane data into logical forwarding data that specify QoS functions. In some embodiments, the control application performs several rounds of mapping operations to create and/or modify network constructs that are necessary to enable the logical switch for QoS.

DETAILED DESCRIPTION

Some embodiments of the invention provide a method that allows several different logical data path sets to be specified for several different users through one or more shared switching elements without allowing the different users to control or even view each other's switching logic. In some embodiments, the method provides a set of software tools that allows the system to accept logical data path sets from users and to configure the switching elements to implement these logical data path sets. These software tools allow the method to virtualize control of the shared switching elements and the network that is defined by the connections between these shared switching elements, in a manner that prevents the different users from viewing or controlling each other's logical data path sets while sharing the same switching elements.

In some embodiments, one of the software tools that the method provides that allows it to virtualize control of a set of switching elements (i.e., to enable the method to allow several users to share the same switching elements without viewing or controlling each other's logical data path sets) is an intermediate data storage structure that (1) stores the state of the network, (2) receives modifications to different parts of the network from different users, and (3), in some embodiments, provide different views of the state of the network to different users. For instance, in some embodiments, the intermediate data storage structure is a network information base (NIB) data structure that stores the state of the network that is defined by one or more switching elements. In some embodiments, the NIB also stores the logical configuration and the logical state for each user specified logical data path set. In these embodiments, the information in the NIB that represents the state of the actual switching elements accounts for only a subset of the total information stored in the NIB.

The method uses the NIB data structure to read the state of the network and to write modifications to the state of the network. When the data structure is modified in order to effectuate a change in the switching logic of a switching element, the method propagates the modification to the switching element.

In some embodiments, the method is employed by a virtualized network control system that (1) allows user to specify different logical data path sets, (2) maps these logical data path sets to a set of switching elements managed by the control system. In some embodiments, the network infrastructure switching elements includes virtual or physical network switches, routers, and/or other switching devices, as well as any other network elements (such as load balancers, etc.) that establish connections between these switches, routers, and/or other switching devices. Such switching elements (e.g., physical switching elements, such as physical switches or routers) are implemented as software switches in some embodiments. Software switches are switches that are implemented by storing the switching tables in the memory of a standalone computer instead of an off the shelf switch. In some embodiments, the standalone computer may also be executing in some cases a hypervisor and one or more virtual machines on top of that hypervisor.

These switches are referred to below as managed switching elements or managed forwarding elements as they are managed by the network control system in order to implement the logical data path sets. In some embodiments described below, the control system manages these switching elements by pushing physical control plane data to them, as further described below. Switching elements generally receive data (e.g., a data packet) and perform one or more processing operations on the data, such as dropping a received data packet, passing a packet that is received from one source device to another destination device, processing the packet and then passing it a destination device, etc. In some embodiments, the physical control plane data that is pushed to a switching element is converted by the switching element (e.g., by a general purpose processor of the switching element) to physical forwarding plane data that specifies how the switching element (e.g., how a specialized switching circuit of the switching element) processes data packets that it receives.

The virtualized control system of some embodiments includes (1) a network operating system (NOS) that creates and maintains the NIB storage structure, and (2) one or more applications that run on top of the NOS to specify control logic for reading values from and writing values to the NIB. The NIB of some of these embodiments serves as a communication channel between the different controller instances and, in some embodiments, a communication channel between different processing layers of a controller instance.

Several examples of such systems are described below in Section I. Section II then describes the software architecture of a NOS instance. Section III describes the control data pipeline of some embodiments of the invention. Section IV next describes how some embodiments perform the virtualization operations that map user specified input to LDPS data tuples. Next, Section V describes several examples of use cases in which the control application performs the virtualization operations. Finally, Section VI describes an electronic system that implements some embodiments of the invention.

I. Virtualized Control System

FIG. 1illustrates a virtualized network system100of some embodiments of the invention. This system allows multiple users to create and control multiple different sets of logical data paths on a shared set of network infrastructure switching elements (e.g., switches, virtual switches, software switches, etc.). In allowing a user to create and control the user's set of logical data paths (i.e., the user's switching logic), the system does not allow the user to have direct access to another user's set of logical data paths in order to view or modify the other user's switching logic. However, the system does allow different users to pass packets through their virtualized switching logic to each other if the users desire such communication.

As shown inFIG. 1, the system100includes one or more switching elements105, a network operating system110, a network information base115, and one or more applications120. The switching elements include N switching devices (where N is a number equal to 1 or greater) that form the network infrastructure switching elements of the system100. In some embodiments, the network infrastructure switching elements includes virtual or physical network switches, software switches (e.g., Open vSwitch), routers, and/or other switching devices, as well as any other network elements (such as load balancers, etc.) that establish connections between these switches, routers, and/or other switching devices. All such network infrastructure switching elements are referred to below as switching elements or forwarding elements.

The virtual or physical switching devices105typically include control switching logic125and forwarding switching logic130. In some embodiments, a switch's control logic125specifies (1) the rules that are to be applied to incoming packets, (2) the packets that will be discarded, and (3) the packet processing methods that will be applied to incoming packets. The virtual or physical switching elements105use the control logic125to populate tables governing the forwarding logic130. The forwarding logic130performs lookup operations on incoming packets and forwards the incoming packets to destination addresses.

As further shown inFIG. 1, the system100includes one or more applications120through which switching logic (i.e., sets of logical data paths) is specified for one or more users (e.g., by one or more administrators or users). The network operating system (NOS)110serves as a communication interface between (1) the switching elements105that perform the physical switching for any one user, and (2) the applications120that are used to specify switching logic for the users. In this manner, the application logic determines the desired network behavior while the NOS merely provides the primitives needed to access the appropriate network state. In some embodiments, the NOS110provides a set of Application Programming Interfaces (API) that provides the applications120programmatic access to the network switching elements105(e.g., access to read and write the configuration of network switching elements). In some embodiments, this API set is data-centric and is designed around a view of the switching infrastructure, allowing control applications to read and write state to any element in the network.

To provide the applications120programmatic access to the switching elements, the NOS110needs to be able to control the switching elements105itself. The NOS uses different techniques in different embodiments to control the switching elements. In some embodiments, the NOS can specify both control and forwarding switching logic125and130of the switching elements. In other embodiments, the NOS110controls only the control switching logic125of the switching elements, as shown inFIG. 1. In some of these embodiments, the NOS110manages the control switching logic125of a switching element through a commonly known switch-access interface that specifies a set of APIs for allowing an external application (such as a network operating system) to control the control plane functionality of a switching element. Two examples of such known switch-access interfaces are the OpenFlow interface and the Open Virtual Switch interface, which are respectively described in the following two papers: McKeown, N. (2008).OpenFlow: Enabling Innovation in Campus Networks(which can be retrieved from http://www.openflowswitch.org//documents/openflow-wp-latest.pdf), and Pettit, J. (2010).Virtual Switching in an Era of Advanced Edges(which can be retrieved from http://openvswitch.org/papers/dccaves2010.pdf). These two papers are incorporated herein by reference.

FIG. 1conceptually illustrates the use of switch-access APIs through the depiction of halos135around the control switching logic125. Through these APIs, the NOS can read and write entries in the control plane flow tables. The NOS' connectivity to the switching elements' control plane resources (e.g., the control plane tables) is implemented in-band (i.e., with the network traffic controlled by NOS) in some embodiments, while it is implemented out-of-band (i.e., over a separate physical network) in other embodiments. There are only minimal requirements for the chosen mechanism beyond convergence on failure and basic connectivity to the NOS, and thus, when using a separate network, standard IGP protocols such as IS-IS or OSPF are sufficient.

In order to define the control switching logic125for physical switching elements, the NOS of some embodiments uses the Open Virtual Switch protocol to create one or more control tables within the control plane of a switch element. The control plane is typically created and executed by a general purpose CPU of the switching element. Once the system has created the control table(s), the system then writes flow entries to the control table(s) using the OpenFlow protocol. The general purpose CPU of the physical switching element uses its internal logic to convert entries written to the control table(s) to populate one or more forwarding tables in the forwarding plane of the switch element. The forwarding tables are created and executed typically by a specialized switching chip of the switching element. Through its execution of the flow entries within the forwarding tables, the switching chip of the switching element can process and route packets of data that it receives.

To enable the programmatic access of the applications120to the switching elements105, the NOS also creates the network information base (NIB)115. The NIB is a data structure in which the NOS stores a copy of the switch-element states tracked by NOS. The NIB of some embodiments is a graph of all physical or virtual switch elements and their interconnections within a physical network topology and their forwarding tables. For instance, in some embodiments, each switching element within the network infrastructure is represented by one or more data objects in the NIB. However, in other embodiments, the NIB stores state information about only some of the switching elements. For example, as further described below, the NIB in some embodiments only keeps track of switching elements at the edge of a network infrastructure. In yet other embodiments, the NIB stores state information about edge switching elements in a network as well as some non-edge switching elements in the network that facilitate communication between the edge switching elements. In some embodiments, the NIB also stores the logical configuration and the logical state for each user specified logical data path set. In these embodiments, the information in the NIB that represents the state of the actual switching elements accounts for only a subset of the total information stored in the NIB.

In some embodiments, the NIB115is the heart of the NOS control model in the virtualized network system100. Under one approach, applications control the network by reading from and writing to the NIB. Specifically, in some embodiments, the application control logic can (1) read the current state associated with network entity objects in the NIB, (2) alter the network state by operating on these objects, and (3) register for notifications of state changes to these objects. Under this model, when an application120needs to modify a record in a table (e.g., a control plane flow table) of a switching element105, the application120first uses the NOS' APIs to write to one or more objects in the NIB that represent the table in the NIB. The NOS then acting as the switching element's controller propagates this change to the switching element's table.

FIG. 2presents one example that illustrates this switch controller functionality of the NOS110. In particular, this figure illustrates in four stages the modification of a record (e.g., a flow table record) in a switch205by an application215and a NOS210. In this example, the switch205has two switch logic records230and235. As shown in stage one ofFIG. 2, a NIB240stores two records220and225that correspond to the two switch logic records230and235of the switch. In the second stage, the application uses the NOS' APIs to write three new values d, e, and f in the record220of the NIB to replace three previous values a, b, and c.

Next, in the third stage, the NOS uses the set of switch-access APIs to write a new set of values into the switch. In some embodiments, the NIB performs a translation operation that modifies the format of the records before writing these records into the NIB. These operations are pictorially illustrated inFIG. 2by showing the values d, e, f translated into d′, e′, f′, and the writing of these new values into the switch205. Alternatively, in some embodiments, one or more sets of values are kept identically in the NIB and the switching element, which thereby causes the NOS210to write the NIB values directly to the switch205unchanged.

In yet other embodiments, the NOS' translation operation might modify the set of values in the NIB (e.g., the values d, e, f) into a different set of values with fewer values (e.g., values x and y, where x and y might be a subset of d, e, and f, or completely different) or additional values (e.g., the w, x, y, z, where w, x, y, and z might be a super set of all or some of d, e, and f, or completely different). The NOS in these embodiments would then write this modified set of values (e.g., values x and y, or values w, x, y and z into the switching element).

The fourth stage finally shows the switch205after the old values a, b, and c have been replaced in the switch control record230with the values d′, e′, and f′. Again, in the example shown inFIG. 2, the NOS of some embodiments propagates NIB records to the switches as modified versions of the records were written to the NIB. In other embodiments, the NOS applies processing (e.g., data transformation) to the NIB records before the NOS propagates the NIB records to the switches, and such processing changes the format, content and quantity of data written to the switches.

A. Different NIB Views

In some embodiments, the virtualized system100ofFIG. 1provides different views of the NIB to different users in order (1) to ensure that different users do not have direct view and control over each other's switching logic and (2) to provide each user with a view of the switching logic at an abstraction level that is desired by the user. For instance, in some embodiments, the NIB is a hierarchical data structure that represents different attributes of different switching elements as elements (e.g., different nodes) in a hierarchy. The NIB in some of these embodiments is a multi-layer hierarchical data structure, with each layer having a hierarchical structure and one or more elements (e.g., nodes) on each layer linked to one or more elements (e.g., nodes) on another layer. In some embodiments, the lowest layer elements correspond to the actual switching elements and their attributes, while each of the higher layer elements serves as abstractions of the actual switching elements and their attributes. As further described below, some of these higher layer elements are used in some embodiments to show different abstract switching elements and/or switching element attributes to different users in a virtualized control system. In other words, the NOS of some embodiments generates the multi-layer, hierarchical NIB data structure, and the NOS or an application that runs on top of the NOS shows different users different views of different parts of the hierarchical levels and/or layers, in order to provide the different users with virtualized access to the shared switching elements and network.

FIG. 3illustrates an example of displaying different NIB views to different users. Specifically, this figure illustrates a virtualized switching system300that includes several switching elements that are shared by two users. The system300is similar to the system100ofFIG. 1, except that the system300is shown to include four switching elements105a-105dand one application120, as opposed to the more general case of N switching elements105and M (where M is a number greater than or equal to 1) applications inFIG. 1. The number of switching elements and the use of one application are purely exemplary. Other embodiments might use more or fewer switching elements and applications. For instance, instead of having the two users interface with the same application, other embodiments provide two applications to interface with the two users.

In system300, the NIB115stores sets of data records for each of the switching elements105a-105d. In some embodiments, a system administrator can access these four sets of data through an application120that interfaces with the NOS. However, other users that are not system administrators do not have access to all of the four sets of records in the NIB, because some switch logic records in the NIB might relate to the logical switching configuration of other users.

Instead, each non system-administrator user can only view and modify the switching element records in the NIB that relate to the logical switching configuration of the user.FIG. 3illustrates this limited view by showing the application120providing a first layered NIB view345to a first user355and a second layered NIB view350to a second user360. The first layered NIB view345shows the first user data records regarding the configuration of the shared switching elements105a-105dfor implementing the first user's switching logic and the state of this configuration. The second layered NIB view350shows the second user data records regarding the configuration of the shared switching elements105a-105dfor implementing the second user's switching logic and the state of this configuration. In viewing their own logical switching configuration, neither user can view the other user's logical switching configuration.

In some embodiments, each user's NIB view is a higher level NIB view that represents an abstraction of the lowest level NIB view that correlates to the actual network infrastructure that is formed by the switching elements105a-105d. For instance, as shown inFIG. 3, the first user's layered NIB view345shows two switches that implement the first user's logical switching configuration, while the second user's layered NIB view350shows one switch that implements the second user's logical switching configuration. This could be the case even if either user's switching configuration uses all four switching elements105a-105d. However, under this approach, the first user perceives that his computing devices are interconnected by two switching elements, while the second user perceives that her computing devices are interconnected by one switching element.

The first layered NIB view is a reflection of a first set of data records365that the application120allows the first user to access from the NIB, while the second layered NIB view is a representation of a second set of data records370that the application120allows the second user to access from the NIB. In some embodiments, the application120retrieves the two sets of data records365and370from the NIB and maintains these records locally, as shown inFIG. 3. In other embodiments, however, the application does not maintain these two sets of data records locally. Instead, in these other embodiments, the application simply provides the users with an interface to access the limited set of first and second data records from the NIB115. Also, in other embodiments, the system300does not provide switching element abstractions in the higher layered NIB views345and350that it provides to the users. Rather, it simply provides views to the limited first and second set of data records365and370from the NIB.

Irrespective of whether the application maintains a local copy of the first and second data records or whether the application only provides the switching element abstractions in its higher layered NIB views, the application120serves as an interface through which each user can view and modify the user's logical switching configuration, without being able to view or modify the other user's logical switching configuration. Through the set of APIs provided by the NOS110, the application120propagates to the NIB115changes that a user makes to the logical switching configuration view that the user receives from the application. The propagation of these changes entails the transferring, and in some cases of some embodiments, the transformation, of the high level data entered by a user for a higher level NIB view to lower level data that is to be written to lower level NIB data that is stored by the NOS.

In the system300ofFIG. 3, the application120can perform several different sets of operations in several different embodiments of the invention, as apparent from the discussion above. Examples of such operations include providing an interface to a user to access NIB data regarding the user's logical switching configuration, providing different layered NIB views to different users, providing control logic for modifying the provided NIB data, providing logic for propagating received modifications to the NIB structure stored by the NOS, etc.

The system of some embodiments embeds all such operations in the NOS110instead of in the application120operating on top of the NOS. Alternatively, in other embodiments the system separates these operations into several applications that operate above the NOS.FIG. 4illustrates a virtualized system that employs several such applications. Specifically, this figure illustrates a virtualized system400that is similar to the virtualized system300ofFIG. 3, except that the operations of the application120in the system400have been divided into two sets of operations, one that is performed by a control application420and one that is performed by a virtualization application425.

In some embodiments, the virtualization application425interfaces with the NOS110to provide different views of different NIB records to different users through the control application420. The control application420also provides the control logic for allowing a user to specify different operations with respect to the limited NIB records/views provided by the virtualization application. Examples of such operations can be read operations from the NIB or write operations to the NIB. The virtualization application then translates these operations into operations that access the NIB. In translating these operations, the virtualization application in some embodiments also transfers and/or transforms the data that are expressed in terms of the higher level NIB records/views to data that are expressed in terms of lower level NIB records.

Even thoughFIG. 4shows just one control application and one virtualization application being used for the two users, the system400in other embodiments employs two control applications and/or two virtualization applications for the two different users. Similarly, even though several of the above-described figures show one or more applications operating on a single NOS instance, other embodiments provide several different NOS instances on top of each of which one or more applications can execute. Several such embodiments will be further described below.

B. Type I versus Type II Virtualized System

Different embodiments of the invention use different types of virtualization applications. One type of virtualization application exposes the definition of different elements at different hierarchical levels in the NIB and the definition of the links between these elements to the control applications that run on top of the NOS and the virtualization application in order to allow the control application to define its operations by reference to these definitions. For instance, in some embodiments, the developer of the control application running on top of the virtualization application uses these definitions to enumerate how the application is to map the logical data path sets of the user to the physical switching elements of the control system. Under this approach, the developer would have to enumerate all different scenarios that the control system may encounter and the mapping operation of the application for each scenario. This type of virtualization is referred to below as Type I network virtualization.

Another type of network virtualization, which is referred to below as Type II network virtualization, does not require the application developers to have intimate knowledge of the NIB elements and the links in the NIB between these elements. Instead, this type of virtualization allows the application to simply provide user specified switching element attributes in the form of one or more tables, which are then mapped to NIB records by a table mapping engine. In other words, the Type II virtualized system of some embodiments accepts switching element configurations (e.g., access control list table configurations, L2 table configurations, L3 table configurations, etc.) that the user defines without referencing any operational state of the switching elements in a particular network configuration. It then maps the user-specified switching element configurations to the switching element configurations stored in the NIB.

FIG. 5illustrates an example of such a Type II virtualized system. Like the virtualized system300ofFIG. 3and the virtualized system400ofFIG. 4, the virtualized system500in this example is shown to include one NOS110and four switching elements105a-105d. Also, like the virtualized system400, the system500includes a control application and a virtualization application that run on top of the NOS110. In some embodiments, the control application520allows a user to specify and populate logical data path sets, while the virtualization application525implements the specified logical data path sets by mapping the logical data path set to the physical switching infrastructure.

More specifically, the control application520allows (1) a user to specify abstract switching element configurations, which the virtualization application525then maps to the data records in the NIB, and (2) the user to view the state of the abstract switching element configurations. In some embodiments, the control application520uses a network template library530to allow a user to specify a set of logical data paths by specifying one or more switch element attributes (i.e., one or more switch element configurations). In the example shown inFIG. 5, the network template library includes several types of tables that a switching element may include. In this example, the user has interfaced with the control application520to specify an L2 table535, an L3 table540, and an access control list (ACL) table545. These three tables specify a logical data path set550for the user. In some embodiments a logical data path set defines a logical switching element (also referred to as a logical switch). A logical switch in some embodiments is a simulated/conceptual switch that is defined (e.g., by a user) to conceptually describe a set of switching behaviors for a switch. The control application of some embodiments (such as the control application520illustrated inFIG. 5) implements this logical switch across one or more physical switches, which as mentioned above may be hardware switches, software switches, or virtual switches defined on top of other switches.

In specifying these tables, the user simply specifies desired switch configuration records for one or more abstract, logical switching elements. When specifying these records, the user of the system500does not have any understanding of the switching elements105a-105demployed by the system nor any data regarding these switching elements from the NIB115. The only switch-element specific data that the user of the system500receives is the data from the network template library, which specifies the types of network elements that the user can define in the abstract, which the system can then process.

While the example inFIG. 5shows the user specifying ACL table, one of ordinary skill in the art will realize that the system of some embodiments does not provide such specific switch table attributes in the library530. For instance, in some embodiments, the switch-element abstractions provided by the library530are generic switch tables and do not relate to any specific switching element table, component and/or architecture. In these embodiments, the control application520enables the user to create generic switch configurations for a generic set of one or more tables. Accordingly, the abstraction level of the switch-element attributes that the control application520allows the user to create is different in different embodiments.

Irrespective of the abstraction level of the switch-element attributes produced through the control logic application, the virtualization application525performs a mapping operation that maps the specified switch-element attributes (e.g., the specific or generic switch table records) to records in the NIB. In some embodiments, the virtualization application translates control application input into one or more NIB records585. The virtualization application then writes the resulting NIB records585to the NIB through the API set provided by NOS. From the NIB, these records are then subsequently transferred to the switching infrastructure through the operation of the NOS. In some embodiments, the NIB stores both the logical data path set input received through the control application as well as the NIB records that are produced by the virtualization application.

In some embodiments, the control application can receive switching infrastructure data from the NIB. In response to this data, the control application may modify record(s) associated with one or more logical data path sets (LDPS). Any such modified LDPS record would then be translated to one or more physical switching infrastructure records by the virtualization application, which might then be transferred to the physical switching infrastructure by the NOS.

To map the control application input to physical switching infrastructure attributes for storage in the NIB, the virtualization application of some embodiments uses a database table mapping engine to map input tables, which are created from (1) the control-application specified input tables, and (2) a set of properties associated with switching elements used by the system, to output tables. The content of these output tables are then transferred to the NIB elements.

Some embodiments use a variation of the datalog database language to allow application developers to create the table mapping engine for the virtualization application, and thereby to specify the manner by which the virtualization application maps logical data path sets to the controlled physical switching infrastructure. This variation of the datalog database language is referred to below as nLog. Like datalog, nLog provides a few declaratory rules and operators that allow a developer to specify different operations that are to be performed upon the occurrence of different events. In some embodiments, nLog provides a limited subset of the operators that are provided by datalog in order to increase the operational speed of nLog. For instance, in some embodiments, nLog only allows the AND operator to be used in any of the declaratory rules.

The declaratory rules and operations that are specified through nLog are then compiled into a much larger set of rules by an nLog compiler. In some embodiments, this compiler translates each rule that is meant to address an event into several sets of database join operations. Collectively the larger set of rules forms the table mapping, rules engine that is referred to below as the nLog engine. The nLog mapping techniques of some embodiments is further described below.

In some embodiments, the nLog virtualization engine provides feedback (e.g., from one or more of the output tables or from NIB records that are updated to reflect values stored in the output tables) to the user in order to provide the user with state information about the logical data path set that he or she created. In this manner, the updates that the user gets are expressed in terms of the logical space that the user understands and not in terms of the underlying switching element states, which the user does not understand.

The use of nLog serves as a significant distinction between Type I virtualized control systems and Type II virtualized control systems, even for Type II systems that store user specified logical data path sets in the NIB. This is because nLog provides a machine-generated rules engine that addresses the mapping between the logical and physical domains in a more robust, comprehensive manner than the hand-coded approach used for Type I virtualized control systems. In the Type I control systems, the application developers need to have a detailed understanding of the NIB structure and need to use this detailed understanding to write code that addresses all possible conditions that the control system would encounter at runtime. On the other hand, in Type II control systems, the application developers only need to produce applications that express the user-specified logical data path sets in terms of one or more tables, which are then automatically mapped to output tables whose content are in turn transferred to the NIB. This approach allows the Type II virtualized systems not to maintain the data regarding the logical data path sets in the NIB. However, some embodiments maintain this data in the NIB in order to distribute this data among other NOS instances, as further described below.

C. Edge and Non-Edge Switch Controls

As mentioned above, the NIB in some embodiments stores data regarding each switching element within the network infrastructure of a system, while in other embodiments, the NIB stores state information about only switching elements at the edge of a network infrastructure.FIGS. 6 and 7illustrate an example that differentiates the two differing approaches. Specifically,FIG. 6illustrates the switch infrastructure of a multi-tenant server hosting system. In this system, six switching elements are employed to interconnect six computing devices of two users A and B. Four of these switches605-620are edge switches that have direct connections with the computing devices635-660of the users A and B, while two of the switches625and630are interior switches (i.e., non-edge switches) that interconnect the edge switches and connect to each other.

FIG. 7illustrates a virtualized network control system700that manages the edge switches605-620. As shown in this figure, the system700includes a NOS110that creates and maintains a NIB115, which contains data records regarding only the four edge switching elements605-620. In addition, the applications705running on top of the NOS110allow the users A and B to modify their switch element configurations for the edge switches that they use. The NOS then propagates these modifications if needed to the edge switching elements. Specifically, in this example, two edge switches605and620are used by computing devices of both users A and B, while edge switch610is only used by the computing device645of the user A and edge switch615is only used by the computing device650of the user B. Accordingly,FIG. 7illustrates the NOS modifying users A and B records in switches605and620, but only updating user A records in switch element610and user B records in switch element615.

The system of some embodiments only controls edge switches (i.e., only maintains data in the NIB regarding edge switches) for several reasons. Controlling edge switches provides the system with a sufficient mechanism for maintaining isolation between computing devices, which is needed, as opposed to maintaining isolation between all switch elements, which is not needed. The interior switches forward between switching elements. The edge switches forward between computing devices and other network elements. Thus, the system can maintain user isolation simply by controlling the edge switch because the edge switch is the last switch in line to forward packets to a host.

Controlling only edge switches also allows the system to be deployed independent of concerns about the hardware vendor of the non-edge switches, because deploying at the edge allows the edge switches to treat the internal nodes of the network as simply a collection of elements that moves packets without considering the hardware makeup of these internal nodes. Also, controlling only edge switches makes distributing switching logic computationally easier. Controlling only edge switches also enables non-disruptive deployment of the system because edge-switching solutions can be added as top of rack switches without disrupting the configuration of the non-edge switches.

In addition to controlling edge switches, the network control system of some embodiments also utilizes and controls non-edge switches that are inserted in the switch network hierarchy to simplify and/or facilitate the operation of the controlled edge switches. For instance, in some embodiments, the control system requires the switches that it controls to be interconnected in a hierarchical switching architecture that has several edge switches as the leaf nodes in this switching architecture and one or more non-edge switches as the non-leaf nodes in this architecture. In some such embodiments, each edge switch connects to one or more of the non-leaf switches, and uses such non-leaf switches to facilitate its communication with other edge switches. Examples of functions that a non-leaf switch of some embodiments may provide to facilitate such communications between edge switch in some embodiments include (1) routing of a packet with an unknown destination address (e.g., unknown MAC address) to the non-leaf switch so that this switch can route this packet to the appropriate edge switch, (2) routing a multicast or broadcast packet to the non-leaf switch so that this switch can convert this packet to a series of unicast packets to the desired destinations, (3) bridging remote managed networks that are separated by one or more networks, and (4) bridging a managed network with an unmanaged network.

Some embodiments employ one level of non-leaf (non-edge) switches that connect to edge switches and in some cases to other non-leaf switches. Other embodiments, on the other hand, employ multiple levels of non-leaf switches, with each level of non-leaf switch after the first level serving as a mechanism to facilitate communication between lower level non-leaf switches and leaf switches. In some embodiments, the non-leaf switches are software switches that are implemented by storing the switching tables in the memory of a standalone computer instead of an off the shelf switch. In some embodiments, the standalone computer may also be executing in some cases a hypervisor and one or more virtual machines on top of that hypervisor. Irrespective of the manner by which the leaf and non-leaf switches are implemented, the NIB of the control system of some embodiments stores switching state information regarding the leaf and non-leaf switches.

The above discussion relates to the control of edge switches and non-edge switches by a network control system of some embodiments. In some embodiments, edge switches and non-edge switches (leaf and non-leaf nodes) may be referred to as managed switches. This is because these switches are managed by the network control system (as opposed to unmanaged switches, which are not managed by the network control system, in the network) in order to implement logical data path sets through the managed switches.

D. Secondary Storage Structure

In addition to using the NIB to store switching-element data, the virtualized network-control system of some embodiments also stores other storage structures to store data regarding the switching elements of the network. These other storage structures are secondary storage structures that supplement the storage functions of the NIB, which is the primary storage structure of the system while the system operates. In some embodiments, the primary purpose for one or more of the secondary storage structures is to back up the data in the NIB. In these or other embodiments, one or more of the secondary storage structures serves a purpose other than backing up the data in the NIB (e.g., for storing data that are not in the NIB).

In some embodiments, the NIB is stored in system memory (e.g., RAM) while the system operates. This allows for the fast access of the NIB records. In some embodiments, one or more of the secondary storage structures, on the other hand, are stored on disk or other non-volatile memories that are slower to access. Such non-volatile disk or other storages, however, improve the resiliency of the system as they allow the data to be stored in a persistent manner.

FIG. 8illustrates an example of a virtualized system800that employs secondary storage structures that supplement the NIB's storage operations. This system is similar to the systems400and500ofFIGS. 4 and 5, except that it also includes secondary storage structures805. In this example, these structures include a persistent transactional database (PTD)810, a persistent non-transactional database (PNTD)815, and a hash table820. In some embodiments, these three types of secondary storage structures store different types of data, store data in different manners, and/or provide different query interfaces that handle different types of queries.

In some embodiments, the PTD810is a database that is stored on disk or other non-volatile memory. In some embodiments, the PTD is a commonly available database, such as MySQL or SQLite. The PTD of some embodiments can handle complex transactional queries. As a transactional database, the PTD can undo a series of prior query operations that it has performed as part of a transaction when one of the subsequent query operations of the transaction fails. Moreover, some embodiments define a transactional guard processing (TGP) layer before the PTD in order to allow the PTD to execute conditional sets of database transactions. The TGP layer allows the PTD to avoid unnecessary later database operations when conditions of earlier operations are not met.

The PTD in some embodiments stores the exact replica of the data that are stored in the NIB, while in other embodiments it stores only a subset of the data that are stored in the NIB. Some or all of the data in the NIB are stored in the PTD in order to ensure that the NIB data will not be lost in the event of a crash of the NOS or the NIB.

The PNTD815is another persistent database that is stored on disk or other non-volatile memory. Some embodiments use this database to store data (e.g., statistics, computations, etc.) regarding one or more switch element attributes or operations. For instance, this database is used in some embodiment to store the number of packets routed through a particular port of a particular switching element. Other examples of types of data stored in the database815include error messages, log files, warning messages, and billing data. Also, in some embodiments, the PNTD stores the results of operations performed by the application(s)830running on top of the NOS, while the PTD and hash table store only values generated by the NOS.

The PNTD in some embodiments has a database query manager that can process database queries, but as it is not a transactional database, this query manager cannot handle complex conditional transactional queries. In some embodiments, accesses to the PNTD are faster than accesses to the PTD but slower than accesses to the hash table820.

Unlike the databases810and815, the hash table820is not a database that is stored on disk or other non-volatile memory. Instead, it is a storage structure that is stored in volatile system memory (e.g., RAM). It uses hashing techniques that use hashed indices to quickly identify records that are stored in the table. This structure combined with the hash table's placement in the system memory allows this table to be accessed very quickly. To facilitate this quick access, a simplified query interface is used in some embodiments. For instance, in some embodiments, the hash table has just two queries: a Put query for writing values to the table and a Get query for retrieving values from the table. Some embodiments use the hash table to store data that change quickly. Examples of such quick-changing data include network entity status, statistics, state, uptime, link arrangement, and packet handling information. Furthermore, in some embodiments, the NOS uses the hash tables as a cache to store information that is repeatedly queried for, such as flow entries that will be written to multiple nodes. Some embodiments employ a hash structure in the NIB in order to quickly access records in the NIB. Accordingly, in some of these embodiments, the hash table820is part of the NIB data structure.

The PTD and the PNTD improve the resiliency of the NOS system by preserving network data on hard disks. If a NOS system fails, network configuration data will be preserved on disk in the PTD and log file information will be preserved on disk in the PNTD.

Using a single NOS instance to control a network can lead to scaling and reliability issues. As the number of network elements increases, the processing power and/or memory capacity that are required by those elements will saturate a single node. Some embodiments further improve the resiliency of the control system by having multiple instances of NOS running on one or more computers, with each instance of NOS containing one or more of the secondary storage structures described above. The control applications in some embodiments partition the workload between the different instances in order to reduce each instance's workload. Also, in some embodiments, the multiple instances of NOS communicate the information stored in their storage layers to enable each instance of NOS to cover for the others in the event of a NOS instance failing.

FIG. 9illustrates a multi-instance, distributed network control system900of some embodiments. This distributed system controls multiple switching elements990with three instances905,910, and915. In some embodiments, the distributed system900allows different controller instances to control the operations of the same switch or of different switches.

As shown inFIG. 9, each instance includes a NOS925, a virtualization application930, one or more control applications935, and a coordination manager (CM)920. For the embodiments illustrated in this figure, each NOS in the system900is shown to include a NIB940and three secondary storage structures, i.e., a PTD945, a distributed hash table (DHT) instance950, and a persistent non-transaction database (PNTD)955. Other embodiments may not tightly couple the NIB and/or each of the secondary storage structures within the NOS. Also, other embodiments might not include each of the three secondary storage structures (i.e., the PTD, DHT instance, and PNTD) in each instance905,910, or915. For example, one NOS instance905may have all three data structures whereas another NOS instance may only have the DHT instance.

In some embodiments, the system900maintains the same switch element data records in the NIB of each instance, while in other embodiments, the system900allows NIBs of different instances to store different sets of switch element data records.FIGS. 10-12illustrate three different approaches that different embodiments employ to maintain the NIB records. In each of these three examples, two instances1005and1010are used to manage several switching elements having numerous attributes that are stored collectively in the NIB instances. This collection of the switch element data in the NIB instances is referred to as the global NIB data structure1015inFIGS. 10-12.

FIG. 10illustrates the approach of maintaining the entire global NIB data structure1015in each NOS instance1005and1010.FIG. 11illustrates an alternative approach of dividing the global NIB1015into two separate portions1020and1025, and storing each of these portions in a different NOS instance.FIG. 12illustrates yet another alternative approach. In this example, the global NIB1015is divided into two separate, but overlapping portions1030and1035, which are then stored separately by the two different instances (with instance1005storing portion1030and instance1010storing portion1035). In the systems of some embodiments that store different portions of the NIB in different instances, one controller instance is allowed to query another controller instance to obtain a NIB record. Other systems of such embodiments, however, do not allow one controller instance to query another controller instance for a portion of the NIB data that is not maintained by the controller itself. Still others allow such queries to be made, but allow restrictions to be specified that would restrict access to some or all portions of the NIB.

The system900of some embodiments also replicates each NIB record in each instance in the PTD945of that instance in order to maintain the records of the NIB in a persistent manner. Also, in some embodiments, the system900replicates each NIB record in the PTDs of all the controller instances905,910, or915, in order to protect against failures of individual controller instances (e.g., of an entire controller instance or a portion of the controller instance). Other embodiments, however, do not replicate each NIB record in each PTD and/or do not replicate the PTD records across all the PTDs. For instance, some embodiments only replicate only a part but not all of the NIB data records of one controller instance in the PTD storage layer of that controller instance, and then replicate only this replicated portion of the NIB in all of the NIBs and PTDs of all other controller instances. Some embodiments also store a subset of the NIB records in another one of the secondary storage records, such as the DHT instance950.

In some embodiments, the DHT instances (DHTI)950of all controller instances collectively store one set of records that are indexed based on hashed indices for quick access. These records are distributed across the different controller instances to minimize the size of the records within each instance and to allow the size of the DHT to be increased by adding additional DHT instances. According to this scheme, one DHT record is not stored in each controller instance. In fact, in some embodiments, each DHT record is stored in at most one controller instance. To improve the system's resiliency, some embodiments, however, allow one DHT record to be stored in more than one controller instance, so that in case one DHT record is no longer accessible because of one instance failure, that DHT record can be accessed from another instance. Some embodiments store in the DHT only the type of data that can be quickly re-generated, and therefore do not allow for replication of records across different DHT instances or allow only a small amount of such records to be replicated.

The PNTD955is another distributed data structure of the system900of some embodiments. For example, in some embodiments, each instance's PNTD stores the records generated by the NOS925or applications930or935of that instance or another instance. Each instance's PNTD records can be locally accessed or remotely accessed by other controller instances whenever the controller instances need these records. This distributed nature of the PNTD allows the PNTD to be scalable as additional controller instances are added to the control system900. In other words, addition of other controller instances increases the overall size of the PNTD storage layer.

The PNTD in some embodiments is replicated partially across different instances. In other embodiments, the PNTD is replicated fully across different instances. Also, in some embodiments, the PNTD955within each instance is accessible only by the application(s) that run on top of the NOS of that instance. In other embodiments, the NOS can also access (e.g., read and/or write) to the PNTD955. In yet other embodiments, the PNTD955of one instance is only accessible by the NOS of that instance.

By allowing different NOS instances to store the same or overlapping NIB records, and/or secondary storage structure records, the system improves its overall resiliency by guarding against the loss of data due to the failure of any NOS or secondary storage structure instance. In some embodiments, each of the three storages of the secondary storage layer uses a different distribution technique to improve the resiliency of a multiple NOS instance system. For instance, as mentioned above, the system900of some embodiments replicates the PTD across NOS instances so that every NOS has a full copy of the PTD to enable a failed NOS instance to quickly reload its PTD from another instance. In some embodiments, the system900distributes the PNTD with overlapping distributions of data across the NOS instances to reduce the damage of a failure. The system900in some embodiments also distributes the DHT fully or with minimal overlap across multiple controller instances in order to maintain the DHT instance within each instance small and to allow the size of the DHT to be increased by adding additional DHT instances.

For some or all of the communications between the distributed instances, the system900uses the CMs920. The CM920in each instance allows the instance to coordinate certain activities with the other instances. Different embodiments use the CM to coordinate the different sets of activities between the instances. Examples of such activities include writing to the NIB, writing to the PTD, writing to the DHT, controlling the switching elements, facilitating intra-controller communication related to fault tolerance of controller instances, etc.

As mentioned above, different controller instances of the system900can control the operations of the same switching elements or of different switching elements. By distributing the control of these operations over several instances, the system can more easily scale up to handle additional switching elements. Specifically, the system can distribute the management of different switching elements and/or different portions of the NIB to different NOS instances in order to enjoy the benefit of processing efficiencies that can be realized by using multiple NOS instances. In such a distributed system, each NOS instance can have a reduced number switches or reduce portion of the NIB under management, thereby reducing the number of computations each controller needs to perform to distribute flow entries across the switches and/or to manage the NIB. In other embodiments, the use of multiple NOS instances enables the creation of a scale-out network management system. The computation of how best to distribute network flow tables in large networks is a CPU intensive task. By splitting the processing over NOS instances, the system900can use a set of more numerous but less powerful computer systems to create a scale-out network management system capable of handling large networks.

As noted above, some embodiments use multiple NOS instance in order to scale a network control system. Different embodiments may utilize different methods to improve the scalability of a network control system. Three example of such methods include (1) partitioning, (2) aggregation, and (3) consistency and durability. For a first method, the network control system of some embodiments configures the NOS instances so that a particular controller instance maintains only a subset of the NIB in memory and up-to-date. Further, in some of these embodiments, a particular NOS instance has connections to only a subset of the network elements, and subsequently, can have less network events to process.

A second method for improving scalability of a network control system is referred to as aggregation. In some embodiments, aggregation involves the controller instances grouping NOS instances together into sets. All the NOS instances within a set have complete access to the NIB entities representing network entities connected to those NOS instances. The set of NOS instances then exports aggregated information about its subset of the NIB to other NOS instances (which are not included in the set of NOS instances)

Consistency and durability is a third method for improving scalability of a network control system. For this method, the controller instances of some embodiments are able to dictate the consistency requirements for the network state that they manage. In some embodiments, distributed locking and consistency algorithms are implemented for network state that requires strong consistency, and conflict detection and resolution algorithms are implemented for network state that does not require strong consistency (e.g., network state that is not guaranteed to be consistent). As mentioned above, the NOS of some embodiments provides two data stores that an application can use for network state with differing preferences for durability and consistency. The NOS of some embodiments provides a replicated transactional database for network state that favors durability and strong consistency, and provides a memory-based one-hop DHT for volatile network state that can sustain inconsistencies.

In some embodiments, the above methods for improving scalability can be used alone or in combination. They can also be used to manage networks too large to be controlled by a single NOS instance. These methods are described in further detail in U.S. patent application Ser. No. 13/177,538, now issued as U.S. Pat. 8,830,823, entitled “A Distributed Control Platform for Large-scale Production Networks,” filed concurrently with the present Application.

To distribute the workload and to avoid conflicting operations from different controller instances, the system900of some embodiments designates one controller instance (e.g.,905) within the system900as the master of any particular NIB portion and/or any given switching element (e.g.,990c). Even with one master controller, different controller instance (e.g.,910and915) can request changes to different NIB portions and/or to different switching elements (e.g.,990c) controlled by the master (e.g.,905). If allowed, the master instance then effectuates this change and writes to the desired NIB portion and/or switching element. Otherwise, the master rejects the request.

FIG. 13illustrates an example of specifying a master controller instance for a switch in a distributed system1300that is similar to the system900ofFIG. 9. In this example, two controllers1305and1310control three switching elements S1, S2and S3, for two different users A and B. Through two control applications1315and1320, the two users specify two different sets of logical data paths1325and1330, which are translated into numerous records that are identically stored in two NIBs1355and1360of the two controller instances1305and1310by NOS instances1345and1350of the controllers.

In the example illustrated inFIG. 13, both control applications1315and1320of both controllers1305and1310can modify records of the switching element S2for both users A and B, but only controller1305is the master of this switching element. This example illustrates two cases. The first case involves the controller1305updating the record S2b1in switching element S2for the user B. The second case involves the controller1305updating the records S2a1in switching element S2after the control application1320updates a NIB record S2a1for switching element S2and user A in NIB1360. In the example illustrated inFIG. 13, this update is routed from NIB1360of the controller1310to the NIB1355of the controller1305, and then subsequently routed to switching element S2.

Different embodiments use different techniques to propagate changes to the NIB1360of controller instance1310to NIB1355of the controller instance1305. For instance, to propagate changes, the system1300in some embodiments uses the secondary storage structures (not shown) of the controller instances1305and1310. More generally, the distributed control system of some embodiments uses the secondary storage structures as communication channels between the different controller instances. Because of the differing properties of the secondary storage structures, these structures provide the controller instances with different mechanisms for communicating with each other. For instance, in some embodiments, different DHT instances can be different, and each DHT instance is used as a bulletin board for one or more instances to store data so that they or other instances can retrieve this data later. In some of these embodiments, the PTDs are replicated across all instances, and some or all of the NIB changes are pushed from one controller instance to another through the PTD storage layer. Accordingly, in the example illustrated inFIG. 13, the change to the NIB1360could be replicated to the PTD of the controller1310, and from there it could be replicated in the PTD of the controller1305and the NIB1355.

Instead of propagating the NIB changes through the secondary storages, the system1300uses other techniques to change the record S2a1in the switch S2in response to the request from control application1320. For instance, to propagate this update, the NOS1350of the controller1310in some embodiments sends an update command to the NOS1345of the controller1305(with the requisite NIB update parameters that identify the record and one or more new values for the record) to direct the NOS1345to modify the record in the NIB1355or in the switch S2. In response, the NOS1345would make the changes to the NIB1355and the switch S2(if such a change is allowed). After this change, the controller instance1310would change the corresponding record in its NIB1360once it receives notification (from controller1305or from another notification mechanism) that the record in the NIB1355and/or switch S2has changed.

Other variations to the sequence of operations shown inFIG. 13could exist because some embodiments designate one controller instance as a master of a portion of the NIB, in addition to designating a controller instance as a master of a switching element. In some embodiments, different controller instances can be masters of a switch and a corresponding record for that switch in the NIB, while other embodiments require the controller instance to be master of the switch and all records for that switch in the NIB.

In the embodiments where the system1300allows for the designation of masters for switching elements and NIB records, the example illustrated inFIG. 13illustrates a case where the controller instance1310is the master of the NIB record S2a1, while the controller instance1305is the master for the switch S2. If a controller instance other than the controller instance1305and1310was the master of the NIB record S2a1, then the request for the NIB record modification from the control application1320would have to be propagated to this other controller instance. This other controller instance would then modify the NIB record and this modification would then cause the NIB1355, the NIB1360and the switch S2to update their records once the controller instances1305and1310are notified of this modification through any number of mechanisms that would propagate this modification to the controller instances1305and1310.

In other embodiments, the controller instance1305might be the master of the NIB record S2a1, or the controller instance might be the master of switch S2and all the records for this NIB. In these embodiments, the request for the NIB record modification from the control application1320would have to be propagated the controller instance1305, which would then modify the records in the NIB1355and the switch S2. Once this modification is made, the NIB1360would modify its record S2a1once the controller instance1310is notified of this modification through any number of mechanisms that would propagate this modification to the controller instance1310.

As mentioned above, different embodiments employ different techniques to facilitate communication between different controller instances. In addition, different embodiments implement the controller instances differently. For instance, in some embodiments, the stack of the control application(s) (e.g.,935or1315inFIGS. 9 and 13), the virtualization application (e.g.,930or1335), and the NOS (e.g.,925or1345) is installed and runs on a single computer. Also, in some embodiments, multiple controller instances can be installed and run in parallel on a single computer. In some embodiments, a controller instance can also have its stack of components divided amongst several computers. For example, within one instance, the control application (e.g.,935or1315) can be on a first physical or virtual computer, the virtualization application (e.g.,930or1335) can be on a second physical or virtual computer, and the NOS (e.g.,925or1350) can be on a third physical or virtual computer.

FIG. 14illustrates a particular distributed network control system1400of some embodiments of the invention. In several manners, this control system1400is similar to the control system900ofFIG. 9. For instance, it uses several different controller instances to control the operations of the same switching elements or of different switching elements. In the example illustrated inFIG. 14, three instances1405,1410and1415are illustrated. However, one of ordinary skill in the art will understand that the control system1400can have any number of controller instances.

Also, like the control system900, each controller instance includes a NOS1425, a virtualization application1430, one or more control applications1435, and a coordination manager (CM)1420. Each NOS in the system1400includes a NIB1440and at least two secondary storage structures, e.g., a distributed hash table (DHT)1450and a PNTD1455.

However, as illustrated inFIG. 14, the control system1400has several additional and/or different features than the control system900. These features include a NIB notification module1470, NIB transfer modules1475, a CM interface1460, PTD triggers1480, DHT triggers1485, and master/slave PTDs1445/1447.

In some embodiments, the notification module1470in each controller instance allows applications (e.g., a control application) that run on top of the NOS to register for callbacks when changes occur within the NIB. This module in some embodiments has two components, which include a notification processor and a notification registry. The notification registry stores the list of applications that need to be notified for each NIB record that the module1470tracks, while the notification processor reviews the registry and processes the notifications upon detecting a change in a NIB record that it tracks. The notification module as well as its notification registry and notification processor are a conceptual representation of the NIB-application layer notification components of some embodiments, as the system of these embodiments provides a separate notification function and registry within each NIB object that can be tracked by the application layer.

The transfer modules1475include one or more modules that allow data to be exchanged between the NIB1440on one hand, and the PTD or DHT storage layers in each controller instance on the other hand. In some embodiments, the transfer modules1475include an import module for importing changes from the PTD/DHT storage layers into the NIB, and an export module for exporting changes in the NIB to the PTD/DHT storage layers.

Unlike the control system900that has the same type of PTD in each instance, the control system1400only has PTDs in some of the NOS instances, and of these PTDs, one of them serves as master PTD1445, while the rest serve as slave PTDs1447. In some embodiments, NIB changes within a controller instance that has a slave PTD are first propagated to the master PTD1445, which then direct the controller instance's slave PTD to record the NIB change. The master PTD1445similarly receives NIB changes from controller instances that do not have either master or slave PTDs.

In the control system1400, the coordination manager1420includes the CM interface1460to facilitate communication between the NIB storage layer and the PTD storage layer. The CM interface also maintains the PTD trigger list1480, which identifies the modules of the system1400to callback whenever the CM interface1460is notified of a PTD record change. A similar trigger list1485for handling DHT callbacks is maintained by the DHT instance1450. The CM1420also has a DHT range identifier (not shown) that allows the DHT instances of different controller instances to store different DHT records in different DHT instances.

Also, in the control system1400, the PNTD is not placed underneath the NIB storage layer. This placement is to signify that the PNTD in the control system1400does not exchange data directly with the NIB storage layer, but rather is accessible solely by the application(s) (e.g., the control application) running on top of the NOS1425as well as other applications of other controller instances. This placement is in contrast to the placement of the PTD storage layer1445/1447and DHT storage layers1450, which are shown to be underneath the NIB storage layer because the PTD and DHT are not directly accessible by the application(s) running on top of the NOS1425. Rather, in the control system1400, data are exchanged between the NIB storage layer and the PTD/DHT storage layers of the same or different instances.

The control system1400uses the PTD, DHT and PNTD storage layers to facilitate communication between the different controller instances. In some embodiments, each of the three storages of the secondary storage layer uses a different storage and distribution technique to improve the resiliency of the distributed, multi-instance system1400. For instance, the system1400of some embodiments replicates the PTD across NOS instances so that every NOS has a full copy of the PTD to enable a failed NOS instance to quickly reload its PTD from another instance. On the other hand, the system1400in some embodiments distributes the PNTD with partial overlapping distributions of data across the NOS instances to reduce the damage of a failure. Similarly, the system1400in some embodiments distributes the DHT fully or with minimal overlap across multiple controller instances in order to maintain the DHT instance within each instance small. Also, using this approach, allows the system to increase the size of the DHT by adding additional DHT instances in order to make the system more scalable.

One of the advantages of this system is that it can be configured in any number of ways. In some embodiments, this system provides great flexibility to specify the configurations for the components of the system in order to customize its storage and data distribution scheme to achieve the best tradeoff of scalability and speed on one hand, and reliability and consistency on the other hand. Attributes of the storage structures that affect scalability, speed, reliability and consistency considerations include the speed of the storage (e.g., RAM versus disk access speed), the reliability of the storage (e.g., persistent non-volatile storage of disk versus volatile storage of RAM), the query interface of the storage (e.g., simple Put/Get query interface of DHT versus more robust transactional database queries of PTD in some embodiments), and the number of points of failures in the system (e.g., a single point of failure for a DHT record versus multiple points of failure for a PTD record in some embodiments).

Through the configurations of its components, the system can be configured (1) on how to distribute the data records between the NIB and the secondary storage structures within one instance (e.g., which secondary storage should store which NIB record), (2) on how to distribute the data records between the NIBs of different instances (e.g., which NIB records should be replicated across different controller instances), (3) on how to distribute the data records between the secondary storage structures within one instance (e.g., which secondary storage records contain which records), (4) on how to distribute the data records between the secondary storage structures of different instances (e.g., which secondary storage records are replicated across different controller instances), (5) on how to distribute secondary storage instances across controller instances (e.g., whether to put a PTD, a DHT, or a Stats database instances within each controller or whether to put different subset of these storages within different instances), and (6) on how to replicate data records in the distributed secondary storage structures (e.g., whether to replicated PTD fully across all instances, whether to replicate some or all DHT records across more than one instance, etc.). The system also allows the coordination between the different controller instances as to the master control over different switching elements or different portions of the NIB to be configured differently. In some embodiments, some or all of these configurations can be specified by applications (e.g., a control application or a virtualization application) that run on top of the NOS.

In some embodiments, as noted above, the CMs facilitate intra-controller communication related to fault tolerance of controller instances. For instance, the CMs implement the intra-controller communication through the secondary storage layers described above. A controller instance in the control system may fail due to any number of reasons. (e.g., hardware failure, software failure, network failure, etc.). Different embodiments may use different techniques for determining whether a controller instance has failed. In some embodiments, Paxos protocol is used to determine whether a controller instance in the control system has failed. While some of these embodiments may use Apache Zookeeper to implement the Paxos protocols, other of these embodiments may implement Paxos protocol in other ways.

Some embodiments of the CM1420may utilize defined timeouts to determine whether a controller instance has failed. For instance, if a CM of a controller instance does not respond to a communication (e.g., sent from another CM of another controller instance in the control system) within an amount of time (i.e., a defined timeout amount), the non-responsive controller instance is determined to have failed. Other techniques may be utilized to determine whether a controller instance has failed in other embodiments.

When a master controller instance fails, a new master for the logical data path sets and the switching elements needs to be determined. Some embodiments of the CM1420make such determination by performing a master election process that elects a master controller instance (e.g., for partitioning management of logical data path sets and/or partitioning management of switching elements). The CM1420of some embodiments may perform a master election process for electing a new master controller instance for both the logical data path sets and the switching elements of which the failed controller instance was a master. However, the CM1420of other embodiments may perform (1) a master election process for electing a new master controller instance for the logical data path sets of which the failed controller instance was a master and (2) another master election process for electing a new master controller instance for the switching elements of which the failed controller instance was a master. In these cases, the CM1420may determine two different controller instances as new controller instances: one for the logical data path sets of which the failed controller instance was a master and another for the switching elements of which the failed controller instance was a master.

In some embodiments, the master election process is further for partitioning management of logical data path sets and/or management of switching elements when a controller instance is added to the control system. In particular, some embodiments of the CM1420perform the master election process when the control system1400detects a change in membership of the controller instances in the control system1400. For instance, the CM1420may perform the master election process to redistribute a portion of the management of the logical data path sets and/or the management of the switching elements from the existing controller instances to the new controller instance when the control system1400detects that a new network controller has been added to the control system1400. However, in other embodiments, redistribution of a portion of the management of the logical data path sets and/or the management of the switching elements from the existing controller instances to the new controller instance does not occur when the control system1400detects that a new network controller has been added to the control system1400. Instead, the control system1400in these embodiments assigns unassigned logical data path sets and/or switching elements in these embodiments (e.g., new logical data path sets and/or switching elements or logical data path sets and/or switching elements from a failed network controller) to the new controller instance when the control system1400detects the unassigned logical data path sets and/or switching elements have been added.

II. Single NOS Instance

FIG. 15conceptually illustrates a single NOS instance1500of some embodiments. This instance can be used as a single NOS instance in the distributed control system1400that employs multiple NOS instances in multiple controller instances. Alternatively, with slight modifications, this instance can be used as a single NOS instance in a centralized control system that utilizes only a single controller instance with a single NOS instance. The NOS instance1500supports a wide range of control scenarios. For instance, in some embodiments, this instance allows an application running on top of it (e.g., a control or virtualization application) to customize the NIB data model and have control over the placement and consistency of each element of the network infrastructure.

Also, in some embodiments, the NOS instance1500provides multiple methods for applications to gain access to network entities. For instance, in some embodiments, it maintains an index of all of its entities based on the entity identifier, allowing for direct querying of a specific entity. The NOS instance of some embodiments also supports registration for notifications on state changes or the addition/deletion of an entity. In some embodiments, the applications may further extend the querying capabilities by listening for notifications of entity arrival and maintaining their own indices. In some embodiments, the control for a typical application is fairly straightforward. It can register to be notified on some state change (e.g., the addition of new switches and ports), and once notified, it can manipulate the network state by modifying the NIB data tuple(s) (e.g., key-value pairs) of the affected entities.

As shown inFIG. 15, the NOS1500includes an application interface1505, a notification processor1510, a notification registry1515, a NIB1520, a hash table1524, a NOS controller1522, a switch controller1525, transfer modules1530, a CM1535, a PTD1540, a CM interface1542, a PNTD1545, a DHT instance1550, switch interface1555, and NIB request list1560.

The application interface1505is a conceptual illustration of the interface between the NOS and the applications (e.g., control and virtualization applications) that can run on top of the NOS. The interface1505includes the NOS APIs that the applications (e.g., control or virtualization application) running on top of the NOS use to communicate with the NOS. In some embodiments, these communications include registrations for receiving notifications of certain changes in the NIB1520, queries to read certain NIB attributes, queries to write to certain NIB attributes, requests to create or destroy NIB entities, instructions for configuring the NOS instance (e.g., instructions regarding how to import or export state), requests to import or export entities on demand, and requests to synchronize NIB entities with switching elements or other NOS instances.

The switch interface1555is a conceptual illustration of the interface between the NOS and the switching elements that run below the NOS instance1500. In some embodiments, the NOS accesses the switching elements by using the OpenFlow or OVS APIs provided by the switching elements. Accordingly, in some embodiments, the switch interface1555includes the set of APIs provided by the OpenFlow and/or OVS protocols.

The NIB1520is the data storage structure that stores data regarding the switching elements that the NOS instance1500is controlling. In some embodiments, the NIB just stores data attributes regarding these switching elements, while in other embodiments, the NIB also stores data attributes for the logical data path sets defined by the user. Also, in some embodiments, the NIB is a hierarchical object data structure (such as the ones described above) in which some or all of the NIB objects not only include data attributes (e.g., data tuples regarding the switching elements) but also include functions to perform certain functionalities of the NIB. For these embodiments, one or more of the NOS functionalities that are shown in modular form inFIG. 15are conceptual representations of the functions performed by the NIB objects.

The hash table1524is a table that stores a hash value for each NIB object and a reference to each NIB object. Specifically, each time an object is created in the NIB, the object's identifier is hashed to generate a hash value, and this hash value is stored in the hash table along with a reference (e.g., a pointer) to the object. The hash table1524is used to quickly access an object in the NIB each time a data attribute or function of the object is requested (e.g., by an application or secondary storage). Upon receiving such requests, the NIB hashes the identifier of the requested object to generate a hash value, and then uses that hash value to quickly identify in the hash table a reference to the object in the NIB. In some cases, a request for a NIB object might not provide the identity of the NIB object but instead might be based on non-entity name keys (e.g., might be a request for all entities that have a particular port). For these cases, the NIB includes an iterator that iterates through all entities looking for the key specified in the request.

The notification processor1510interacts with the application interface1505to receive NIB notification registrations from applications running on top of the NOS and other modules of the NOS (e.g., such as an export module within the transfer modules1530). Upon receiving these registrations, the notification processor1510stores notification requests in the notification registry1515that identifies each requesting party and the NIB data tuple(s) that the requesting party is tracking.

As mentioned above, the system of some embodiments embeds in each NIB object a function for handling notification registrations for changes in the value(s) of that NIB object. For these embodiments, the notification processor1510is a conceptual illustration of the amalgamation of all the NIB object notification functions. Other embodiments, however, do not provide notification functions in some or all of the NIB objects. The NOS of some of these embodiments therefore provides an actual separate module to serve as the notification processor for some or all of the NIB objects.

When some or all of the NIB objects have notification functions in some embodiments, the notification registry for such NIB objects are typically kept with the objects themselves. Accordingly, for some of these embodiments, the notification registry1515is a conceptual illustration of the amalgamation of the different sets of registered requestors maintained by the NIB objects. Alternatively, when some or all of the NIB objects do not have notification functions and notification services are needed for these objects, some embodiments use a separate notification registry1515for the notification processing module1510to use to keep track of the notification requests for such objects.

The notification process serves as only one manner for accessing the data in the NIB. Other mechanisms are needed in some embodiments for accessing the NIB. For instance, the secondary storage structures (e.g., the PTD1540and the DHT instance1550) also need to be able to import data from and export data to the NIB. For these operations, the NOS1500uses the transfer modules1530to exchange data between the NIB and the secondary storage structure.

In some embodiments, the transfer modules include a NIB import module and a NIB export module. These two modules in some embodiments are configured through the NOS controller1522, which processes configuration instructions that it receives through the interfaces1505from the applications above the NOS. The NOS controller1522also performs several other operations. As with the notification processor, some or all of the operations performed by the NOS controller are performed by one or more functions of NIB objects, in some of the embodiments that implement one or more of the NOS1500operations through the NIB object functions. Accordingly, for these embodiments, the NOS controller1522is a conceptual amalgamation of several NOS operations, some of which are performed by NIB object functions.

Other than configuration requests, the NOS controller1522of some embodiments handles some of the other types of requests directed at the NOS instance1500. Examples of such other requests include queries to read certain NIB attributes, queries to write to certain NIB attributes, requests to create or destroy NIB entities, requests to import or export entities on demand, and requests to synchronize NIB entities with switching elements or other NOS instances.

In some embodiments, the NOS controller stores requests to change the NIB on the NIB request list1560. Like the notification registry, the NIB request list in some embodiments is a conceptual representation of a set of distributed requests that are stored in a distributed manner with the objects in the NIB. Alternatively, for embodiments in which some or all of the NIB objects do not maintain their modification requests locally, the request list is a separate list maintained by the NOS1500. The system of some of these embodiments that maintains the request list as a separate list, stores this list in the NIB in order to allow for its replication across the different controller instances through the PTD storage layer and/or the DHT storage layer. This replication allows the distributed controller instances to process in a uniform manner a request that is received from an application operating on one of the controller instances.

Synchronization requests are used to maintain consistency in NIB data in some embodiments that employ multiple NIB instances in a distributed control system. For instance, in some embodiments, the NIB of some embodiments provides a mechanism to request and release exclusive access to the NIB data structure of the local instance. As such, an application running on top of the NOS instance(s) is only assured that no other thread is updating the NIB within the same controller instance; the application therefore needs to implement mechanisms external to the NIB to coordinate an effort with other controller instances to control access to the NIB. In some embodiments, this coordination is static and requires control logic involvement during failure conditions.

Also, in some embodiments, all NIB operations are asynchronous, meaning that updating a network entity only guarantees that the update will eventually be pushed to the corresponding switching element and/or other NOS instances. While this has the potential to simplify the application logic and make multiple modifications more efficient, often it is useful to know when an update has successfully completed. For instance, to minimize disruption to network traffic, the application logic of some embodiments requires the updating of forwarding state on multiple switches to happen in a particular order (to minimize, for example, packet drops). For this purpose, the API of some embodiments provides the synchronization request primitive that calls back one or more applications running on top of the NOS once the state has been pushed for an entity. After receiving the callback, the control application of some embodiments will then inspect the content of the NIB and determine whether its state is still as originally intended. Alternatively, in some embodiments, the control application can simply rely on NIB notifications to react to failures in modifications as they would react to any other network state changes.

The NOS controller1522is also responsible for pushing the changes in its corresponding NIB to switching elements for which the NOS1500is the master. To facilitate writing such data to the switching element, the NOS controller1522uses the switch controller1525. It also uses the switch controller1525to read values from a switching element. To access a switching element, the switch controller1525uses the switch interface1555, which as mentioned above uses OpenFlow or OVS, or other known set of APIs in some embodiments.

Like the PTD and DHT storage structures1445and1450of the control system1400ofFIG. 14, the PTD and DHT storage structures1540and1550ofFIG. 15interface with the NIB and not the application layer. In other words, some embodiments only limit PTD and DHT layers to communicate between the NIB layer and these two storage layers, and to communicate between the PTD/DHT storages of one instance and PTD/DHT storages of other instances. Other embodiments, however, allow the application layer (e.g., the control application) within one instance to access the PTD and DHT storages directly or through the transfer modules1530. These embodiments might provide PTD and DHT access handles (e.g., APIs to DHT, PTD or CM interface) as part of the application interface1505, or might provide handles to the transfer modules that interact with the PTD layer (e.g., the CM interface1542) and DHT layers, so that the applications can directly interact with the PTD and DHT storage layers.

Also, like structures1445and1450, the PTD1540and DHT instance1550have corresponding lists of triggers that are respectively maintained in the CM interface1542and the DHT instance1550. Also, like the PNTD1455of the control system1400, the PNTD1545ofFIG. 15does not interface with the NIB1520. Instead, it interfaces with the application layer through the application interface1505. Through this interface, the applications running on top of the NOS can store data in and retrieve data from the PNTD. Also, applications of other controller instances can access the PNTD1545, as shown inFIG. 15.

III. Control Data Pipeline

FIG. 16further elaborates on the propagation of the instructions to control a managed switch through the various processing layers of the controller instances of some embodiments of the invention. This figure illustrates a control data pipeline1600that translates and propagates control plane data through three processing layers of the same or different controller instances to a managed switch1625. These three layers are the control application1605, the virtualization application1610, and the NOS1615. In some embodiments, these three layers are in the same controller instance. However, other arrangements of these layers exist in other embodiments. For instance, in other embodiments, only the control and virtualization applications1605and1610and the NIB that initially stores the output of the virtualization application1610are in the same controller instance, but the functionality to propagate the generated physical control plane data reside in a NOS of another controller instance (not shown). In these other embodiments, the physical control plane data is transferred from the initial NIB to the NIB of a NOS of the other controller instance, before this other NOS pushes the control plane data to the managed switch.

As shown inFIG. 16, the control application1605in some embodiments has two logical planes1630and1635that can be used to express the input and output to this application. In some embodiments, the first logical plane1630is a logical control plane that includes a collection of higher-level constructs that allow the control application and its users to specify one or more logical data path sets within the logical control plane for one or more users. The second logical plane1635in some embodiments is the logical forwarding plane, which represents the logical data path sets of the users in a format that can be processed by the virtualization application1610. In this manner, the two logical planes1630and1635are virtualization space analogs of the control and forwarding planes1655and1660that are typically can be found in a typical managed switch1650, as shown inFIG. 16.

In some embodiments, the control application1605defines and exposes the logical control plane constructs with which the application itself or users of the application define different logical data path sets within the logical control plane. For instance, in some embodiments, the logical control plane data1630includes logical ACL data, etc. Some of this data (e.g., logical ACL data) can be specified by the user, while other such data (e.g., the logical L2 or L3 records) are generated by the control application and may not be specified by the user. In some embodiments, the control application1605generates and/or specifies such data in response to certain changes to the NIB (which indicate changes to the managed switches and the managed data path sets) that the control application1605detects.

In some embodiments, the logical control plane data (i.e., the LDPS data that is expressed in terms of the control plane constructs) can be initially specified without consideration of current operational data from the managed switches and without consideration of the manner by which this control plane data will be translated to physical control plane data. For instance, the logical control plane data might specify control data for one logical switch that connects five computers, even though this control plane data might later be translated to physical control data for three managed switches that implement the desired switching between the five computers.

The control application includes a set of modules for converting any logical data path set within the logical control plane to a logical data path set in the logical forwarding plane1635. In some embodiments, the control application1605uses the nLog table mapping engine to perform this conversion. The control application's use of the nLog table mapping engine to perform this conversion is further described below. The control application also includes a set of modules for pushing the LDPS from the logical forwarding plane1635of the control application1605to a logical forwarding plane1640of the virtualization application1610.

The logical forwarding plane1640includes one or more logical data path sets of one or more users. The logical forwarding plane1640in some embodiments includes logical forwarding data for one or more logical data path sets of one or more users. Some of this data is pushed to the logical forwarding plane1640by the control application, while other such data are pushed to the logical forwarding plane by the virtualization application detecting events in the NIB1620as further described below for some embodiments.

In addition to the logical forwarding plane1640, the virtualization application1610includes the physical control plane1645. The physical control plane1645includes one or more physical control path sets of one or more users. The virtualization application includes a set of modules for converting any LDPS within the logical forwarding plane1640to a physical control data path set in the physical control plane1645. In some embodiments, the virtualization application1610uses the nLog table mapping engine to perform this conversion. The virtualization application also includes a set of modules (not shown) for pushing the physical control plane data from the physical control plane1645of the virtualization application1610into the NIB1620of the NOS1615.

From the NIB, the physical control plane data is later pushed into the managed switch1650, as shown inFIG. 16. As mentioned above, the physical control plane data in some instances of some embodiments is pushed to the managed switch by the NOS of the same controller instance that has the control application1605and virtualization application, but in other instance is pushed to the managed switch by the NOS of another controller instance (not shown). The managed switch1650then converts this physical control plane data to physical forwarding plane data that specifies the forwarding behavior of the managed switch.

In some embodiments, the physical control plane data that is propagated to the managed switch1650allows this switch to perform the logical data processing on data packets that it processes in order to effectuate the processing of the logical data path sets specified by the control application. In some such embodiments, physical control planes include control plane data for operating in the physical domain and control plane data for operating in the logical domain. In other words, the physical control planes of these embodiments include control plane data for processing network data (e.g., packets) through managed switches to implement physical switching and control plane data for processing network data through managed switches in order to implement the logical switching. In this manner, the physical control plane facilitates implementing logical switches across managed switches. The use of the propagated physical control plane to implement logical data processing in the managed switches is further described in U.S. patent application Ser. No. 13/177,535, now issued as U.S. Pat. 8,750,164, entitled “Hierarchical Managed Switch Architecture,” filed concurrently herewith. This patent application is incorporated by reference in this application.

In addition to pushing physical control plane data to the NIB1620, the control and virtualization applications1605and1610also store logical control plane data and logical forwarding plane data in the NIB. These embodiments store such data in the NIB for a variety of reasons. For instance, in some embodiments, the NIB1620serves as a medium for communications between different controller instances, and the storage of such data in the NOB facilitates the relaying of such data across different controller instances.

FIG. 16illustrates the control data pipeline1600through three processing layers of the same or different controller instances to a managed switch1625. However, in some embodiments, the control data pipeline1600may have two processing layers instead of three with the upper layer being a single application that performs the functionalities of both the control application1605and the virtual application1610. The dashed box encompassing the two applications indicates that a single virtualization application (also called network hypervisor) may replace these two applications1605and1610in some embodiments. In such embodiments, the control application1605would form the front end of this network hypervisor, and would create and populate the logical data path sets. The virtualization application1610in these embodiments would form the back end of the network hypervisor, and would convert the logical data path sets to physical data path sets that are defined in the physical control plane.

FIG. 17illustrates another perspective on the operation of the control, virtualization, and NOS applications of some embodiments. The perspective provided in this figure is meant to emphasize that one or more controller instances can execute these applications in a distributed manner in parallel. Specifically, this figure replaces the control application1605, the virtualization application1610, and the NOS1615, with a control layer1705, a virtualization layer1710, and a NOS layer1715. Each of these layers represents one or more applications that can be executing in parallel on one or more controller instances. Collectively these three layers represent a control system that can be operated as a single controller instance, or can be operated in a distributed manner by several controller instances.

FIG. 17illustrates another perspective on the operation of the control, virtualization, and NOS applications of some embodiments. The perspective provided in this figure is meant to emphasize that one or more controller instances can execute these applications in a distributed manner in parallel. Specifically, this figure replaces the control application1605, the virtualization application1610, and the NOS1615, with a control layer1705, a virtualization layer1710, and a NOS layer1715. Each of these layers represents one or more applications that can be executing in parallel on one or more controller instances. Collectively these three layers represent a control system that can be operated as a single controller instance, or can be operated in a distributed manner by several controller instances.

FIG. 17is also meant to provide an example of logical data path sets that are created by the control applications of some embodiments, and the mapping of the created logical data path sets to the resources of the managed switches. In this example, the logical data path sets are several logical switches1770that are specified by the control application layer1705. A logical switch in some embodiments is a simulated/conceptual switch that is defined (e.g., by a user) to conceptually describe a set of switching behaviors for a switch. The control system of some embodiments (such as the system illustrated inFIG. 17) implements this logical switch across one or more physical switches, which as mentioned above may be hardware switches, software switches, or virtual switches defined on top of other switches.

Each logical switch has two logical planes1730and1735that can be used to express the input and output to the logical switch. In some embodiments, the logical plane1730is a logical control plane (denoted by “LCP” in the figure) that includes a collection of higher-level constructs that allow the control application layer and its user to specify one or more logical data path sets within the logical control plane for the user. The second logical plane1735in some embodiments is the logical forwarding plane (denoted by “LFP” in the figure), which represents the logical data path sets of the user in a format that can be processed by the virtualization application layer1710. Because of these two logical planes1730and1735, the logical switches appear as virtualization space analogs of the control and forwarding planes1755and1760that typically can be found in managed switches, as shown inFIG. 17.

This figure then illustrates that through the virtualization application layer1710and the NOS layer1715, the logical switches1770can be implemented in three managed switches1725. The number of logical switches1770may be less or more than three. That is, the number of logical switches1770in some embodiments does not have to match to the number of managed switches that implement the logical switches. To implement the logical switches1770in the three managed switches, the virtualization application layer1710converts the logical forwarding plane data of the logical switches into physical control plane data, and the NOS layer1715pushes this data to the managed switches1725. As mentioned above, the pushed physical control plane data allows the managed switches to perform physical switching operations in both the physical and logical data processing domains.

IV. Control Application

As mentioned above, the control application of some embodiments converts control data records (also called data tuples below) to forwarding plane data records (e.g., logical forwarding plane data) by performing conversion operations. Specifically, in some embodiments, the control application populates the logical data path tables (e.g., the logical forwarding tables) that are created by the virtualization application with logical data path sets.

FIG. 18illustrates an example of such conversion operations that an instance of a control application of some embodiments performs. This figure conceptually illustrates a process1800that the control application performs to generate logical forwarding plane data based on input event data that specifies the logical control plane data. As described above, the generated logical forwarding plane data is transmitted to the virtualization application, which subsequently generate physical control plane data from the logical forwarding plane data. The physical control plane data is propagated to the managed switching elements, which in turn will produce forwarding plane data (e.g., flow entries) for defining forwarding behaviors of the switches.

As shown inFIG. 18, the process1800initially receives (1805) data regarding an input event. The input event data may be logical data supplied by the user in some embodiments. As will be described further below, some embodiments provide the user with an interface that the user can use to specify input event data. An example of user-supplied data could be logical control plane data including access control list data for a logical switch that the user manages. The input event data may also be logical forwarding plane data that the control application generates in some embodiments from the logical control plane data. The input event data in some embodiments may also be physical forwarding plane data or physical control plane data received from the NIB. In some embodiments, the process1800receives the physical forwarding data from a NIB monitor that monitors the NIB to detect a change in the NIB that reflects a change in one or more managed switching elements.

At1810, the process1800then performs a filtering operation to determine whether this instance of the control application is responsible for the input event data. As described above, several instances of the control application may operate in parallel to control multiple sets of logical data paths in some embodiments. In these embodiments, each control application uses the filtering operation to filter out input data that does not relate to the control application's logical data path set. To perform this filtering operation, the control application of some embodiments includes a filter module. This module in some embodiments is a standalone module, while in other embodiments it is implemented by a table mapping engine (e.g., implemented by the join operations performed by the table mapping engine) that maps records between input tables and output tables of the virtualization application, as further described below.

Next, at1815, the process determines whether the filtering operation has failed. The filtering operation fails in some embodiments when the input event data does not fall within one of the logical data path sets that are the responsibility of the control application. When the process determines (at1815) that the filtering operation has failed the process ends. Otherwise, the process1800transitions to1820.

At1820, a converter of the virtualization application generates one or more sets of data tuples based on the received input event data. In some embodiments, the converter is a table mapping engine that performs a series of table mapping operations on the input event data to map the input event data to other data tuples. As mentioned above, this table mapping engine also performs the filtering operation in some embodiments. One example of such a table mapping engine is an nLog table-mapping engine which will be described bellow.

In some embodiments, the data tuples that the process1800generates may include data (e.g., logical forwarding plane data) that the process has to push down to the NIB. Accordingly, at1825, the process publishes to the NIB any data tuples that it generated if such publication is necessary. After1825, the process ends.

The control application in some embodiments performs its mapping operations by using the nLog table mapping engine, which, as described above, is a variation of the datalog table mapping technique. Datalog is used in the field of database management to map one set of tables to another set of tables. Datalog is not a suitable tool for performing table mapping operations in a control application of a network control system as its current implementations are often slow. Accordingly, the nLog engine of some embodiments is custom designed to operate quickly so that it can perform the real time mapping of the user specified inputs to the LDPS data records (also called LDPS data tuples below) to the data tuples of the managed switching elements. This custom design is based on several custom design choices. For instance, some embodiments compile the nLog table mapping engine from a set of high level declaratory rules that are expressed by an application developer (e.g., by a developer of a control application). In some of these embodiments, one custom design choice that is made for the nLog engine is to allow the application developer to use only the AND operator to express the declaratory rules. By preventing the developer from using other operators (such as ORs, XORs, etc.), these embodiments ensure that the resulting rules of the nLog engine are expressed in terms of AND operations that are faster to execute at run time.

Another custom design choice relates to the join operations performed by the nLog engine. Join operations are common database operations for creating association between records of different tables. In some embodiments, the nLog engine limits its join operations to inner join operations (also called as internal join operations) because performing outer join operations (also called as external join operations) can be time consuming and therefore impractical for real time operation of the engine.

Yet another custom design choice is to implement the nLog engine as a distributed table mapping engine that is executed by several different control applications. Some embodiments implement the nLog engine in a distributed manner by partitioning management of logical data path sets. Each logical data path set includes logical data paths that are specified for a single user of the control system. Partitioning management of the logical data path sets involves specifying for each particular logical data path set only one controller instance as the instance responsible for specifying the NIB records associated with that particular logical data path set. For instance, when the control system uses three switching elements to specify five logical data path sets for five different users with two different controller instances, one controller instance can be the master for NIB records relating to two of the logical data path sets while the other controller instance can be the master for the NIB records for the other three logical data path sets. Partitioning management of logical data path sets ensures that conflicting values for the same logical data path sets are not written to the NIB by two different controller instances, and thereby alleviates the applications running on top of NOS from guarding against the writing of such conflicting values.

Partitioning management of the LDPS′ also assigns in some embodiments the table mapping operations for each LDPS to the nLog engine of the controller instance responsible for the LDPS. The distribution of the nLog table mapping operations across several nLog instances reduces the load on each nLog instance and thereby increases the speed by which each nLog instance can complete its mapping operations. Also, this distribution reduces the memory size requirement on each machine that executes a controller instance. As further described below, some embodiments partition the nLog table mapping operations across the different instances by designating the first join operation that is performed by each nLog instance to be based on the LDPS parameter. This designation ensures that each nLog instance's join operations fail and terminate immediately when the instance has started a set of join operations that relate to a LDPS that is not managed by the nLog instance.

A more detailed example of the nLog mapping engine and the virtualization application is described in sub-sections A-E below. Sub-section A initially describes the software architecture of the control application of some embodiments. Sub-section B then describes further the parallel, distributed management of the LDPS. Sub-section C next describes one manner for designing the nLog mapping engine. Lastly, Sub-section D then describes the nLog engine's table mapping operations in response to an external event from the NIB or an internal event that is generated by the nLog engine.

FIG. 19illustrates a control application1900of some embodiments of the invention. This application1900uses an nLog table mapping engine to map input tables that contain input data tuples to LDPS data tuples. This application resides on top of a virtualization application1905that receives the LDPS data tuples from the control application1900. The virtualization application1905maps the LDPS data tuples to data tuples for defining managed switching elements, attributes of the managed switching elements, and flow entries for the managed switching elements. The virtual application1905resides on top of a NOS1965that contains a NIB1960that stores the data tuples generated by the virtualization application1905.

More specifically, the control application1905allows different users to define different logical data path sets (LDPS), which specify the desired switching configurations of the users. The control application1905also reacts to changes in the NIB to modify the LDPS′. The virtualization application1905through its mapping operations converts each of the LDPS of each user into a set of data tuples to populate the NIB. The virtualization application1905then populates the NIB1960with the generated sets of data tuples. When the NOS1965subsequently propagates the NIB data tuples for a particular user to the switching element(s), the NOS completes the deployment of the user's switching configuration to one or more switching elements. In some embodiments, the control application is executed on the same machine with the control application and the NOS. However, the control application, the virtualization application, and the NOS do not have to run on the same machine in other embodiments. That is, one of these applications or each of these applications may run on a different computer.

As shown inFIG. 19, the control application1900includes a set of rule-engine input tables1910, a set of function and constant tables1915, a query manager1920, a rule engine1925, a set of rule-engine output tables1945, a NIB monitor1950, a publisher1955, and a compiler1935. The compiler1935is one component of the application that operates at a different instance in time than the application's other components. The compiler operates when a developer needs to specify the rules engine for a particular control application and/or virtualized environment, whereas the rest of the application's modules operate at run time when the application interfaces with the control application and the NOS to deploy and monitor logical data path sets specified by one or more users.

In some embodiments, the compiler1935takes a relatively small set (e.g., few hundred lines) of declarative instructions1940that are specified in a declarative language and converts these into a large set (e.g., thousands of lines) of code that specify the operation of the rules engine1925, which performs the application's table mapping as further described below. As such, the compiler greatly simplifies the control application developer's process of defining and updating the control application. This is because the compiler allows the developer to use a high level programming language that allows a compact definition of the control application's complex mapping operation and to subsequently update this mapping operation in response to any number of changes (e.g., changes in the logical networking functions supported by the control application, changes to desired behavior of the control application, etc.).

In some embodiments, the rule-engine (RE) input tables1910include tables with logical data and/or switching configurations (e.g., access control list configurations, private virtual network configurations, port security configurations, etc.) specified by the user and/or the control application. They also include in some embodiments tables that contain physical data (i.e., non-logical data) from the switching elements managed by the virtualized control system. In some embodiments, such physical data includes data regarding the managed switching elements (e.g., physical control plane data) and other data regarding network configuration employed by the virtualized control system to deploy the different LDPS′ of the different users.

The RE input tables1910are partially populated by the LDPS data (e.g., logical control plane data) provided by the user. It also generates part of the LDPS data (e.g., logical forwarding plane data) and physical (i.e., non-logical) data (e.g., physical control plane data) by monitoring the NIB to identify changes in the managed switching element infrastructure that would require modification to the LDPS data and/or the physical data.

In addition to the RE input tables1910, the control application1900includes other miscellaneous tables1915that the rules engine1925uses to gather inputs for its table mapping operations. These tables1915include constant tables that store defined values for constants that the rules engine1925needs to perform its table mapping operations. For instance, constant tables may include a constant “zero” that is defined as the value 0, a constant “dispatch_port_no” as the value 4000, a constant “broadcast_MAC_addr” as the value 0xFF:FF:FF:FF:FF:FF. (A dispatch port in some embodiments is a port that specifies that the managed switch should reprocess the packet based on another flow entry. Examples of such dispatch ports are provided in the above-mentioned U.S. patent application Ser. No. 13/177,535, now issued as U.S. Pat. No. 8,750,164, entitled “Hierarchical Managed Switch Architecture.”)

When the rules engine1925references constants, the corresponding value defined for the constants are actually retrieved and used. In addition, the values defined for constants in the constant table1915may be modified and/or updated. In this manner, the constant table1915provides the ability to modify the value defined for constants that the rules engine1925references without the need to rewrite or recompile code that specifies the operation of the rules engine1925.

The tables1915further include function tables1915that store functions that the rules engine1925needs to use to calculate values needed to populate the output tables1945. One example of such a function is a hash function that the rules engine uses to compute hash values for distributing DHT operations as well as load balancing traffic between lower level switches and higher level switches in a hierarchical switching architecture. U.S. patent application Ser. No. 13/177,529, now issued as U.S. Pat. No. 8,743,889, entitled “Method and Apparatus for Using a Network Information Base to Control a Plurality of Shared Network Infrastructure Switching Elements,” and filed concurrently with the present application, describes the use of hash tables for distributing DHT operations, while the above-identified U.S. patent application Ser. No. 13/177,535, now issued as U.S. Patent 8,750,164, entitled “Hierarchical Managed Switch Architecture,” describes the use of hash tables to load balance traffic in a hierarchical switching architecture. U.S. patent application Ser. No. 13/177,529, now issued as U.S. Pat. No. 8,743,889, entitled “Method and Apparatus for Using a Network Information Base to Control a Plurality of Shared Network Infrastructure Switching Elements,” and filed concurrently with the present application is incorporated herein by reference. U.S. patent application Ser. No. 13/177,529, now issued as U.S. Pat. No. 8,743,889, entitled “Method and Apparatus for Using a Network Information Base to Control a Plurality of Shared Network Infrastructure Switching Elements,” also described the above-mentioned request list processing, which allows one control instance to request modifications to a LDPS managed by another controller instance.

The rules engine1925performs table mapping operations that specify one manner for converting any logical data path set within the logical control plane to a logical data path set in the logical forwarding plane. Whenever one of the rule-engine (RE) input tables is modified, the rule engine performs a set of table mapping operations that may result in the modification of one or more data tuples in one or more RE output tables. The modification of the output table data tuples, in turn, through the virtualization application1905, may cause the NIB to be modified in order to establish and/or modify the implementation of a particular user's LDPS in the managed switching element infrastructure.

As shown inFIG. 19, the rules engine1925includes an event processor1922, several query plans1927, and a table processor1930. Each query plan is a set of join operations that are to be performed upon the occurrence of a modification to one of the RE input table. Such a modification is referred to below as an input table event. As further described below, each query plan is generated by the compiler1935from one declaratory rule in the set of declarations1940. In some embodiments, the query plans are defined by using the nLog declaratory language.

In some embodiments, the compiler1935does not just statically generate query plans but rather dynamically generates query plans based on performance data it gathers. The compiler1935in these embodiments generates an initial set of query plans and let the rules engine operate with the initial set of query plans. The control application gathers the performance data or receives performance feedbacks (e.g., from the rules engine). Based on this data, the compiler is modified so that the control application or a user of this application can have the modified compiler modify the query plans while the rules engine is not operating or during the operation of the rules engine.

For instance, the order of the join operations in a query plan may result in different execution times depending on the number of tables the rules engine has to select to perform each join operation. The compiler in these embodiments can be re-specified in order to re-order the join operations in a particular query plan when a certain order of the join operations in the particular query plan has resulted in a long execution time to perform the join operations.

The event processor1922of the rules engine1925detects the occurrence of each input table event. The event processor of different embodiments detects the occurrence of an input table event differently. In some embodiments, the event processor registers for callbacks with the RE input tables for notification of changes to the records of the RE input tables. In such embodiments, the event processor1922detects an input table event when it receives notification from a RE input table that one of its records has changed.

In response to a detected input table event, the event processor1922(1) selects the appropriate query plan for the detected table event, and (2) directs the table processor1930to execute the query plan. To execute the query plan, the table processor1930in some embodiments performs the join operations specified by the query plan to produce one or more records that represent one or more sets of data values from one or more input and miscellaneous tables1910and1915. The table processor1930of some embodiments then (1) performs a select operation to select a subset of the data values from the record(s) produced by the join operations, and (2) writes the selected subset of data values in one or more RE output tables1945.

In some embodiments, the RE output tables1945store both logical and physical network element data attributes. The tables1945are called RE output tables as they store the output of the table mapping operations of the rule engine1925. In some embodiments, the RE output tables can be grouped in several different categories. For instance, in some embodiments, these tables can be RE input tables and/or control-application (CA) output tables. A table is a RE input table when a change in the table causes the rule engine to detect an input event that requires the execution of a query plan. A RE output table1945can also be a RE input table1910that generates an event that causes the rules engine to perform another query plan. Such an event is referred to as an internal input event, and it is to be contrasted with an external input event, which is an event that is caused by a RE input table modification made by the control application1905or the NIB monitor1950.

A table is a control-application output table when a change in the table causes the publisher1955to publish a change to the virtual application1905and/or to the NIB1960, as further described below. As shown inFIG. 20, a table in the RE output tables1945can be a RE input table1910, a CA output table2005, or both a RE input table1910and a CA output table2005.

The publisher1955detects changes to the CA output tables2005of the RE output tables1945. The publisher of different embodiments detects the occurrence of a CA output table event differently. In some embodiments, the publisher registers for callbacks with the CA output tables for notification of changes to the records of the CA output tables. In such embodiments, the publisher1955detects an output table event when it receives notification from a CA output table that one of its records has changed.

In response to a detected output table event, the publisher1955takes some or all of modified data tuples in the modified CA output tables and propagates this modified data tuple(s) to the input tables (not shown) of the virtualization application1905. In some embodiments, instead of the publisher1955pushing the data tuples to the virtualization application, the virtualization application1905pulls the data tuples from the CA output tables1945into the input tables of the virtualization application. Alternatively, in some embodiments, the publisher2955publishes changes to the modified CA output tables to the NIB, and the virtualization application1905retrieves these changes from the NIB and based on them, modifies its input tables. In some embodiments, the CA output tables1945of the control application1900and the input tables of the virtualization1905may be identical. In yet other embodiments, the control and virtualization applications use one set of tables, so that the CA output tables are essentially VA input tables.

Moreover, the publisher1955in some embodiments takes some or all of modified data tuples in the modified CA output tables and propagates this modified data tuple into the NIB1960through the APIs provided by the NOS1965. Also, the publisher may push down logical data (e.g., logical control plane data, logical forwarding plane data, etc.) processed and maintained by the control application1900to the NIB1960. This is because, in some embodiments, the NIB1960serves as a medium for all communications between the control application, the virtualization application, and the NOS of different controller instances as described below.

As the CA output tables store both logical and physical network element data attributes in some embodiments, the NIB1960in some embodiments stores both logical and physical network element attributes that are identical or derived by the virtualization application1905from the logical and physical network element data attributes in the output tables1945. In other embodiments, however, the NIB only stores physical network element attributes that are identical or derived by the virtualization application1905from the physical network element data attributes in the output tables1945.

The NIB monitor1950interfaces with the NIB1960to receive notifications regarding changes to the NIB. The NIB monitor of different embodiments detects the occurrence of a change in the NIB differently. In some embodiments, the NIB monitor registers for callbacks with the NIB for notification of changes to one or more records in the NIB. In such embodiments, the NIB monitor1950detects NIB change event when it receives notification from the NIB that one of its records has changed. In response to a detected NIB change event, the NIB monitor1950may modify one or more RE input tables1910, which, in turn, may cause one or more RE input table event to occur that then initiates the execution of one or more query plans by the rules engine. In other words, the NIB monitor writes some or all of the information that it receives from the NIB into the input tables1910, so that the state and configuration of the managed switching elements can be accounted for while generating the NIB data tuples through the mapping operations. Each time the managed switching configuration or underlying managed switching element state changes, the NIB monitor1950may update the input table records1910so that the generated NIB data tuples can be updated to reflect the modified switching configuration or underlying switching element state.

In some embodiments, the NIB monitor1950is a collection of input objects (or functions) associated with the RE input tables. Each input object in some embodiments is associated with one RE input table and is responsible for modifying its associated RE input table in response to a change in the NIB. Each input object in some embodiments registers with one or more NIB objects for callback notifications upon the occurrence of changes to the NIB object(s). Similarly, in some embodiments, the publisher1955is a collection of output objects (or functions) associated with the CA output tables. Each output object in some embodiments is associated with one CA output table and is responsible for propagating changes in its associated output table to the virtualization application1905and/or to the NIB. As such, in some embodiments, the NIB monitor is a conceptual representation of the input and output objects that register with the NIB for callbacks.

The query manager1920interfaces with the control application1900to receive queries regarding LDPS data. As shown inFIG. 19, the manager1920of some embodiments also interfaces with the NIB1960in order to query the NIB to provide the control application state information regarding the network elements in the LDPS′ for the different user. In other embodiments, however, the query manager1920queries the output tables1945to obtain LDPS data for the control application.

B. Designing the nLog Table Mapping Engine

In some embodiments, the control application1900uses a variation of the datalog database language, called nLog, to create the table mapping engine that maps input tables containing logical data path data and switching element attributes to the output tables. Like datalog, nLog provides a few declaratory rules and operators that allow a developer to specify different operations that are to be performed upon the occurrence of different events. In some embodiments, nLog provides a smaller subset of the operators that are provided by datalog in order to increase the operational speed of nLog. For instance, in some embodiments, nLog only allows the AND operator to be used in any of the declaratory rules.

The declaratory rules and operations that are specified through nLog are then compiled into a much larger set of rules by an nLog compiler. In some embodiments, this compiler translates each rule that is meant to respond to an event into several sets of database join operations. Collectively the larger set of rules forms the table mapping, rules engine that is referred to below as the nLog engine.

FIG. 21illustrates a development process2100that some embodiments employ to develop the rules engine1925of the control application1900. As shown in this figure, this process uses a declaration toolkit2105and a compiler2110. The toolkit2105allows a developer (e.g., a developer of a control application1430that operates on top of the virtualization application1905) to specify different sets of rules to perform different operations upon occurrence of different sets of conditions.

One example2115of such a rule is illustrated inFIG. 21. This example is a multi-conditional rule that specifies that an Action X has to be taken if four conditions A, B, C, and D are true. The expression of each condition as true in this example is not meant to convey that all embodiments express each condition for each rule as True or False. For some embodiments, this expression is meant to convey the concept of the existence of a condition, which may or may not be true. For example, in some such embodiments, the condition “A=True” might be expressed as “Is variable Z=A?” In other words, A in this example is the value of a parameter Z, and the condition is true when Z has a value A.

Irrespective of how the conditions are expressed, a multi-conditional rule in some embodiments specifies the taking of an action when certain conditions in the network are met. Examples of such actions include creation or deletion of new packet flow entries, creation or deletion of new network constructs, modification to use of existing network constructs, etc. In the control application1900these actions are often implemented by the rules engine1925by creating, deleting, or modifying records in the output tables, which are then propagated to the virtualization application1905by the publisher1955.

As shown inFIG. 21, the multi-conditional rule2115uses only the AND operator to express the rule. In other words, each of the conditions A, B, C and D has to be true before the Action X is to be taken. In some embodiments, the declaration toolkit2105only allows the developers to only utilize the AND operator because excluding the other operators (such as ORs, XORs, etc.) that are allowed by datalog allows nLog to operate faster than datalog.

The compiler2110converts each rule specified by the declaration toolkit2105into a query plan2120of the rules engine.FIG. 21illustrates the creation of three query plans2120a-2120cfor three rules2115a-2115c. Each query plan includes one or more sets of join operations. Each set of join operations specifies one or more join operations that are to be performed upon the occurrence of a particular event in a particular RE input table, where the particular event might correspond to the addition, deletion or modification of an entry in the particular RE input table.

In some embodiments, the compiler2110converts each multi-conditional rule into several sets of join operations, with each set of join operations being specified for execution upon the detection of the occurrence of one of the conditions. Under this approach, the event for which the set of join operations is specified is one of the conditions of the multi-conditional rule. Given that the multi-conditional rule has multiple conditions, the compiler in these embodiments specifies multiple sets of join operations to address the occurrence of each of the conditions.

FIG. 21illustrates this conversion of a multi-conditional rule into several sets of join operations. Specifically, it illustrates the conversion of the four-condition rule2115into the query plan2120a, which has four sets of join operations. In this example, one join-operation set2125is to be performed when condition A occurs, one join-operation set2130is to be performed when condition B occurs, one join-operation set2135is to be performed when condition C occurs, and one join-operation set2140is to be performed when condition D occurs.

These four sets of operations collectively represent the query plan2120athat the rules engine1925performs upon the occurrence of a RE input table event relating to any of the parameters A, B, C, or D. When the input table event relates to one of these parameters (e.g., parameter B) but one of the other parameters (e.g., parameters A, C, and D) is not true, then the set of join operations fails and no output table is modified. But, when the input table event relates to one of these parameters (e.g., parameter B) and all of the other parameters (e.g., parameters A, C, and D) are true, then the set of join operations does not fail and an output table is modified to perform the action X. In some embodiments, these join operations are internal join operations. In the example illustrated inFIG. 21, each set of join operations terminates with a select command that selects entries in the record(s) resulting from the set of join operations to output to one or more output tables.

To implement the nLog engine in a distributed manner, some embodiments partition management of logical data path sets by assigning the management of each logical data path set to one controller instance. This partition management of the LDPS is also referred to as serialization of management of the LDPS. The rules engine1925of some embodiments implements this partitioned management of the LDPS by having a join to the LDPS entry be the first join in each set of join operations that is not triggered by an event in a LDPS input table.

FIG. 22illustrates one such approach. Specifically, for the same four-condition rule2115aillustrated inFIG. 21, it generates a different query plan2220a. This query plan is part of three query plans2220a-2220cthat this figure shows the compiler2210generating for the three rules2115a-2115cspecified through the declaration toolkit2105. Like the query plan2120athat has four sets of join operations2125,2130,2135and2140for the four-condition rule2115a, the query plan2220aalso has four sets of join operations2230,2235,2240and2245for this rule2115a.

The four sets of join operations2230,2235,2240and2245are operational sets that are each to be performed upon the occurrence of one of the conditions A, B, C, and D. The first join operation in each of these four sets2230,2235,2240and2245is a join with the LDPS table managed by the control application instance. Accordingly, even when the input table event relates to one of these four parameters (e.g., parameter B) and all of the other parameters (e.g., parameters A, C, and D) are true, the set of join operations may fail if the event has occurred for a LDPS that is not managed by this control application instance. The set of join operations does not fail and an output table is modified to perform the desire action only when (1) the input table event relates to one of these four parameters (e.g., parameter B), all of the other parameters (e.g., parameters A, C, and D) are true, and (3) the event relates to a LDPS that is managed by this control application instance. Sub-section D below further describes how the insertion of the join operation to the LDPS table allows the control application to partition management of the LDPS′.

C. Table Mapping Operations Upon Occurrence of Event

FIG. 23conceptually illustrates a process2300that the control application1900performs in some embodiments each time a record in a RE input table changes. This change may be a change made through the control application1900. Alternatively, it may be a change that is made by the NIB monitor1950after it receives from the NIB a notification regarding a change in the NIB. The change to the RE input table record can entail the addition, deletion or modification of the record.

As shown inFIG. 23, the process2300initially detects (at2305) a change in a RE input table1910. In some embodiments, the event processor1922is the module that detects this change. Next, at2310, the process2300identifies the query plan associated with the detected RE input table event. As mentioned above, each query plan in some embodiments specifies a set of join operations that are to be performed upon the occurrence of an input table event. In some embodiments, the event processor1922is also the module that performs this operation (i.e., is the module that identifies the query plan).

At2315, the process2300executes the query plan for the detected input table event. In some embodiments, the event processor1922directs the table processor1930to execute the query plan. To execute a query plan that is specified in terms of a set of join operations, the table processor1930in some embodiments performs the set of join operations specified by the query plan to produce one or more records that represent one or more sets of data values from one or more input and miscellaneous tables1910and1915.

FIG. 24illustrates an example of a set of join operations2405. This set of join operations is performed when an event is detected with respect to record2410of an input table2415. The join operations in this set specify that the modified record2410in table2415should be joined with the matching record(s) in table2420, this joined record should then be joined with the matching record(s) in table2425, and this resulting joined record should finally be joined with the matching record(s) in table2430.

Two records in two tables “match” when values of a common key (e.g., a primary key and a foreign key) that the two tables share are the same, in some embodiments. In the example inFIG. 24, the records2410and2435in tables2415and2420match because the values C in these records match. Similarly, the records2435and2440in tables2420and2425match because the values F in these records match. Finally, the records2440and2445in tables2425and2430match because the values R in these records match. The joining of the records2410,2435,2440, and2445results in the combined record2450. In the example shown inFIG. 24, the result of a join operation between two tables (e.g., tables2415and2420) is a single record (e.g., ABCDFGH). However, in some cases, the result of a join operation between two tables may be multiple records.

Even though in the example illustrated inFIG. 24a record is produced as the result of the set of join operations, the set of join operations in some cases might result in a null record. For instance, as further described in sub-section D below, a null record results when the set of join operations terminates on the first join because the detected event relates to a LDPS not managed by a particular instance of the virtualization application. Accordingly, at2320, the process determines whether the query plan has failed (e.g., whether the set of join operations resulted in a null record). If so, the process ends. In some embodiments, the operation2320is implicitly performed by the table processor when it terminates its operations upon the failure of one of the join operations.

When the process2300determines (at2320) that the query plan has not failed, it stores (at2325) the output resulting from the execution of the query plan in one or more of the output tables. In some embodiments, the table processor1930performs this operation by (1) performing a select operation to select a subset of the data values from the record(s) produced by the join operations, and (2) writing the selected subset of data values in one or more RE output tables1945.FIG. 24illustrates an example of this selection operation. Specifically, it illustrates the selection of values B, F, P and S from the combined record2450and the writing of these values into a record2465of an output table2460.

As mentioned above, the RE output tables can be categorized in some embodiments as (1) a RE input table only, (2) a CA output table only, or (3) both a RE input table and a CA output table. When the execution of the query plan results in the modification of a CA output table, the process2300publishes (at2330) the changes to this output table to the virtualization application. In some embodiments, the publisher1955detects changes to the CA output tables2005of the RE output tables1945, and in response, it propagates the modified data tuple in the modified CA output table into the virtualization application.

At2335, the process determines whether the execution of the query plan resulted in the modification of a RE input table. This operation is implicitly performed in some embodiments when the event processor1922determines that the output table that was modified previously at2325modified a RE input table. As mentioned above, a RE output table1945can also be a RE input table1910that generates an event that causes the rules engine to perform another query plan after it is modified by the rules engine. Such an event is referred to as an internal input event, and it is to be contrasted with an external input event, which is an event that is caused by a RE input table modification made by the control application1905or the NIB monitor1950. When the process determines (at2330) that an internal input event was created, it returns to2310to perform operations2310-2335for this new internal input event. The process terminates when it determines (at2335) that the execution of the query plan did not result in an internal input event.

One of ordinary skill in the art will recognize that process2300is a conceptual representation of the operations used to map a change in one or more input tables to one or more output tables. The specific operations of process2300may not be performed in the exact order shown and described. The specific operations may not be performed in one continuous series of operations, and different specific operations may be performed in different embodiments. For instance, the process2300in some embodiments batches up a set of changes in RE input tables1910and identifies (at2310) a query plan associated with the set of detected RE input table events. The process in these embodiments executes (at2320) the query plan for the whole set of the RE input table events rather than for a single RE input table event. Batching up the RE input table events in some embodiments results in better performance of the table mapping operations. For example, batching the RE input table events improves performance because it reduces the number of instance that the process2300will produce additional RE input table events that would cause it to start another iteration of itself.

As mentioned above, some embodiments implement the nLog engine as a distributed table mapping engine that is executed by different control applications of different controller instances. To implement the nLog engine in a distributed manner, some embodiments partition the management of the logical data path sets by specifying for each particular logical data path set only one controller instance as the instance responsible for specifying the NIB records associated with that particular logical data path set. Partitioning the management of the LDPS′ also assigns in some embodiments the table mapping operations for each LDPS to the nLog engine of the controller instance responsible for the LDPS.

As described above by reference toFIG. 20, some embodiments partition the nLog table mapping operations across the different instances by designating the first join operation that is performed by each nLog instance to be based on the LDPS parameter. This designation ensures that each nLog instance's join operations fail and terminate immediately when the instance has started a set of join operations that relate to a LDPS that is not managed by the nLog instance.

FIG. 25illustrates an example of a set of join operations failing when they relate to a LDPS that does not relate to an input table event that has occurred. Specifically, this figure illustrates four query plans2505,2510,2515and2520of a rules engine2525of a particular control application instance2530. Two of these query plans2510and2515specify two sets of join operations that should be performed upon occurrence of input table events B and W respectively, while two of the query plans2505and2520specify two sets of join operations that should be performed upon occurrence of input table event A.

In the example illustrated inFIG. 25, the two query plans2510and2515are not executed because an input table event A has occurred for a LDPS2and these two plans are not associated with such an event. Instead, the two query plans2505and2520are executed because they are associated with the input table event A that has occurred. As shown in this figure, the occurrence of this event results in two sets of join operations being performed to execute the two query plans2505and2520. The first set of join operations2540for the query plan2505fails because the query plan2505is specified for a LDPS1, which is a LDPS not managed by the control application instance2530. This set of join operations fails on the first join operation2535because it is a join with the LDPS table, which for the control application instance2530does not contain a record for the LDPS1. In some embodiments, even though the first join operation2535has failed, the remaining join operations (not shown) of the query plan2540will still be performed and fail. In other embodiments, the remaining join operations of the query plan2540will not be performed as shown.

The second set of join operations2545does not fail, however, because it is for the LDPS2, which is a LDPS managed by the control application instance2530and therefore has a record in the LDPS table of this application instance. This set of join operations has four stages that each performs one join operation. Also, as shown inFIG. 25, the set of join operations terminates with a selection operation that selects a portion of the combined record produced through the join operations.

The distribution of the nLog table mapping operations across several nLog instances reduces the load on each nLog instance and thereby increases the speed by which each nLog instance can complete its mapping operations.FIG. 26illustrates an example that describes this reduction in workload. Specifically, these figures illustrate an example where two controller instances2605and2610are responsible for the control application functionality of two different LDPS′ A and B for different tenants A and B of a multi-tenant computing environment. The two controller instances manage two sets of managed switches2615and2620. Each of the two sets of managed switches manages a set of machines2625or2630, which may be host machines running on dedicated machines, or may be virtual machines running on shared machines.

In four stages, these figures illustrate the results of the table mapping operations that are performed by the control applications of these two different controller instances. The first stage2601shows that no machines have been deployed in the managed system for either tenant A or tenant B. The second stage2602shows the computing environment with several machines that have been deployed for tenant A in the two sets of machines2625and2630. It also shows the CA output table2639of the control application of the controller instance2605with logical forwarding entries (shown as “L.F.E.” in these figures) for the LDPS A that were specified by this instance's control application. In addition, the second stage2602shows output table2640of the virtualization application of the controller instance2605with flow entries for the LDPS A that were specified by this instance's virtualization application. The second stage further shows the NIB2645of the controller instance2605containing the flow entries for the LDPS A. At this stage, the NIB2645also contains LDPS data relating to LDPS A in some embodiments, but this data is not shown inFIG. 26.

The third stage2603inFIG. 26shows that the flow entries for the LDPS A have migrated to the NIB2655of the controller instance2610. This migration occurs because of the NIB replication across the controller instances. Also, this replication causes LDPS data relating to LDPS A to be copied to the NIB2655. The third stage2680further shows the computing environment with several machines that have been deployed for tenant B in the two sets of machines2625and2630. It also shows the CA output table2649of the control application of the controller instance2610with logical forwarding entries for the LDPS B that were specified by this instance's control application. In addition, the third stage2603also shows the output table2650of the virtualization application of the controller instance2610with flow entries for the LDPS B that were specified by this instance's virtualization application. The third stage further shows the NIB2655of the controller instance2610containing the flow entries for the LDPS B. At this stage, the NIB2655also contains LDPS data relating to LDPS B in some embodiments, but this data is not shown inFIG. 26.

The fourth stage2604shows that the flow entries for the LDPS B have migrated to the NIB2645of the controller instance2605. This migration occurs because of the NIB replication across the controller instances. This replication also causes LDPS data relating to LDPS B to be copied to the NIB2645. As shown at the stage2604, the NIBs2645and2655have LDPS data relating to both LDPS A and LDPS B. However, the CA output tables of one controller instance do not store logical forwarding entries for the LDPS of another controller instance. That is, in this example, the CA output tables2639of controller instance A do not store the logical forwarding entries for the LDPS B and the CA output tables2649of controller instance B do not store the logical forwarding entries for the LDPS A. This depiction is meant to illustrate that some embodiments partition the storage of the logical state data across several controller instances. This allows these embodiments to keep the size of tables (e.g., the input or output tables) small in order to increase the speed by which each nLog instance can complete its mapping operations as described above. For a similar reason, in some embodiments, the input tables (not shown) of a controller instance only contains logical records that are for the LDPS's of another controller instance.

While the input and output tables of each controller instance in some embodiments only store or practically only store logical state data for only the LDPS′ for which the controller instance is responsible, the NIB for each controller instance in some of these embodiments contains all or practically all of the logical state data (e.g., except some logical port statistics that are stored in the DHTs of controller instances that are not replicated across) for all LDPS of all controller instances. However, other embodiments will partition the logical state data for the LDPS's across the NIBs of different controller instances.

V. Use Cases

A. Logical Switch

FIG. 27conceptually illustrates a logical switch2700of some embodiments. Many of the logical switches illustrated in the figures through this application may be the same or similar to the logical switch2700as described below. The logical switch2700receives network data (e.g., packets) through a set of ingress ports, ports1through N. The logical switch2700then sends the network data out through a set of egress ports, ports1through N, according to the routing criteria specified in the forwarding tables2705. As described above, a logical switch is mapped to one or more physical machines/switches.

The ingress ports1-N, represent a set of ports through which the logical switch2700receives network data. The ingress ports may include different number of ingress ports in different embodiments. As shown, the ingress ports can receive network data that is external to the logical switch2700, which is indicated as incoming packets. When the ingress ports1-N receive network data, the logical switch2700uses the forwarding tables2705to find one or more egress ports to which to forward the network data.

The forwarding tables2705represent a set of forwarding tables for routing and modifying network data that the logical switch2700received through the ingress ports1-N. In some embodiments, the forwarding tables2705include a set of records (e.g., flow entries) that instruct the logical switch2700to route and/or modify network data and send the network data to the egress ports based on defined routing criteria. Examples of routing criteria include source media access control (MAC) address, destination MAC, packet type, source Internet Protocol (IP) address, destination IP address, source port, destination port, and/or virtual local area network (VLAN) identifier, among other routing criteria. In some embodiments, the logical switch2700routes network data to a particular egress port according to the routing criteria.

In some embodiments, network data that switch2700receives and sends are in the form of packets. A packet includes a header and a payload in some embodiments. The header includes a set of fields that contains information used for routing the packet through a network. Switches may determine switching decisions based on the information contained in the header and may, in some cases, modify some or all of the header fields. Some embodiments determine switching decisions based on flow entries in the logical switches' forwarding tables.

The forwarding tables2705include an ingress ACL table2710, L2 (i.e., a data link layer) forwarding table2715, and an egress ACL table2720in some embodiments. In some embodiments, the logical switch2700performs logical forwarding lookups to determine to which egress port(s) that the logical switch2700should route a packet received through an ingress port using the forwarding tables2705. Specifically, the logical forwarding lookups include a logical ingress ACL lookup for determining access control when the logical switch receives the packet using the ingress ACL table2710. The logical forwarding lookups include a logical L2 lookup for determining to which egress port(s) to send the packet using the L2 forwarding table2715. The logical forwarding lookups also include a logical egress ACL lookup for determining access control before the logical switch routes the packet out of the logical switch using the egress ACL table2720. These logical lookups are performed based on the information in the header of a packet or the logical context tag of the packet in some of these embodiments. For example, flow entries defined to match against the information in the header or the logical context tag of the packet may be used to perform these logical forwarding lookups.

The egress ports1-N conceptually represent a set of ports through which the logical switch2700sends network data out of the logical switch. The egress ports1-N may include different number of egress ports in different embodiments. In some embodiments, some or all of the egress ports may overlap with some or all of the ingress ports. For instance, the egress ports1-N are the same as the ingress ports1-N as shown. As illustrated inFIG. 27, the egress ports1-N receives network data from the ingress ports1-N. When the egress ports1-N receive network data based on the routing criteria specified in the forwarding tables2705, the logical switch2700sends the network data out of the egress ports1-N, which is indicated as outgoing packets.

B. Port Isolation

FIG. 28conceptually illustrates an example of enabling port isolation for a logical switch2800of some embodiments. Specifically, this figure illustrates the logical switch2800at two different stages2801and2802to show different forwarding behaviors of the logical switch2800before and after the logical switch2800is enabled for port isolation. Port isolation is a technique to apply to a logical switch in order to drop packets sent from one port to another port of the switch. That is, the switch enabled for port isolation is prevented from internally routing packets. The port isolation is often applied to implement private virtual local area network (PVLAN).

As shown,FIG. 28illustrates that the logical switch2800includes logical ports1-4and other ports. These ports are ingress ports as well as egress ports in this example. The logical switch2800also includes forwarding tables2805, which include an ingress ACL table2806among other forwarding tables. The logical switch2800is similar to the logical switch2700described above by reference toFIG. 27. That is, the logical switch2800receive network data (e.g., packets) through the ingress ports and routes the network data based on the flow entries specified in the forwarding tables2805to the egress ports, through which the logical switch2800sends out the network data.FIG. 28also illustrates a user interface2810. The user interface2810is provided by a control application in some embodiments. In some embodiments, the user interface2810is a graphical user interface (GUI). In some such embodiments, the user interface2810may also include a command-line interface. The GUI2810shows NIB states upon user's request to query the NIB. The GUI2810also receives user inputs which will be parsed and processed by a control application to generate logical data paths.

A virtual machine (VM)1sends and receives network data to and from the logical switch2800through port1. That is, port1is serving both as an ingress port and an egress port for VM1. Likewise, VM2and VM3are virtual machines that use ports2and3, respectively, to send and receive data to and from the logical switch2800. A shared resource is a machine (e.g., a printer, a file server, etc.) that is used by other machines by exchanging network data through the logical switch2800. The shared resource uses port4to send and receive the network data that is originated from or sent to other machines (e.g., VMs1-3).

The logical switch2800performs logical ingress lookups using the ingress ACL table2806in order to control the network data (e.g., packets) coming through the ingress ports. For instance, the logical switch2800reads information stored in the header of a packet that is received through an ingress port, looks up the matching flow entry or entries in the ingress ACL table2806, and determines an action to perform on the received packet. As described above, a logical switch may perform further logical lookups using other forwarding tables that are storing flow entries.

In the first stage2801, the logical switch2800receives packet1from VM1through port1. Packet1includes in the packet header a source MAC address and a destination MAC address. The source MAC address (SMAC) field of the header includes the MAC address of VM1to indicate the packet1is sent by the VM1. The destination MAC address (DMAC) field includes the MAC address of VM3to indicate that packet1is sent to VM3. The logical switch2800performs an ingress lookup. The logical switch2800reads the header of packet1, specifically the destination MAC address field, and sees that the packet is sent to VM3. The ingress ACL has an entry for packets that are sent to VM3. Accordingly, the logical switch2800performs the remaining logical lookups using other logical forwarding tables (not shown) to determine to which egress port the logical switch2800should send the packet. In this example, the results of the remaining logical lookups lead the packet to VM3through port3.

As shown in the stage2801, the ingress ACL table2806allows packets sent from any VM to any other VM that are coupled to the logical switch2800, pending the results of other logical lookups performed by the logical switch2801. Specifically, the VMs can send packets to any VMs as well as to the shared resource. That is, the ingress ACL does not drop any packets sent to any ports. This is because the logical switch2800is not enabled for port isolation, as indicated by the GUI2810.

In the second stage2802, a user using the GUI2810of control application enables the logical switch2800for port isolation in this example. As will be described further below, the control application translates the user's input into a table, which the control application uses to generate logical data path(s). The ingress ACL table2806is modified according to the user input. As shown, the ingress ACL table2806specifies that any packets from a VM to another VM that are coupled to the logical switch2800should be dropped. Specifically, the ingress ACL table2806specifies that packets sent from one VM of VMs1-3to another VM of VMs1-3should be dropped in this example. For instance, packets sent from VM1to VM2or VM3will be dropped while packets sent from VM1to VM1itself would not be dropped. Accordingly, packet2that is received by the logical switch2800through port1is dropped as shown because the packet includes VM3's MAC address as the destination MAC address. The logical switch2800in some embodiments discards packet2and does not perform any more logical lookups for packet2.

As shown in the stage2802, the VMs are still able to send packets to the shared resource, pending the results of other logical lookups performed by the logical switch2800. Also, the shared resource is still able to send packets to VMs coupled to the logical switch2800. This is because the port isolation allows the VMs to send packets to the shared resource and the shared resource to respond back to the VMs in some embodiments.

Different embodiments implement port isolation differently using different combinations of the forwarding tables. For instance,FIG. 28illustrates some embodiments in which the ingress ACL table2806is changed to enable the logical switch2800for port isolation. In other embodiments, another ACL table (not shown) that has a higher priority than the ingress ACL table2806is created or modified in order to enable the switch for port isolation. That is, the higher priority ACL table will specify that traffic from one VM of the logical switch2800to another VM of the switch should be dropped, while leaving the ingress ACL table2806unchanged from the stage2801to the stage2802. In these embodiments, the logical switch2800looks up the higher priority ACL table first and determine that the packets from one VM to another VM of the switch should be dropped.

FIG. 29conceptually illustrates an example of enabling port isolation for a logical switch by control application2900of some embodiments.FIG. 29illustrates in four different stages2901,2902,2903, and2904that the control application2900enables port isolation for the logical switch2800described above by reference toFIG. 28. As described above, a control application generates flow entries and/or logical data paths based on inputs the control application receives from user or based on the network events the control application detects by monitoring a NIB. As shown, these figures illustrate that the control application2900includes a user interface2905, RE input tables2910, a rules engine2915, RE output tables2920, and a publisher2925. The figures also illustrate a GUI2930and tables2935and2940.

The user interface2905in some embodiments provides a user with a management tool with which the user can view and/or modify a logical network state. Different embodiments provide different management tools to the user. For instance, the user interface2905in some embodiments provides a graphical tool such as the GUI2930. Instead of, or in conjunction with, a graphical tool, other embodiments may provide the user with a command-line tool or any other type of management tool. The user interface2905receives inputs from the user through the management tool and processes the received inputs to create, populate and/or modify one or more input tables2910.

The GUI2930conceptually represents a management tool provided by the user interface2905to the user. In some embodiments, the GUI2930is provided as a web application and thus can be opened up with a web browser. With GUI2930, the user can manage the logical network elements (e.g., a logical switch), e.g., by entering inputs and receiving responses from the control application. For instance, the user can query whether port isolation is enabled for a logical switch that the user is managing.

The RE input tables2910are similar to the RE input tables1910described above by reference toFIG. 19. As described above, a RE input table in some cases represents the state of the logical network that the user is managing. For instance, the RE input table2935is a table that stores port isolation information of the logical switches that the user is managing through the control application. The control application modifies RE input tables with user inputs that the control application receives through the management tool or with any network events that the control application detects by monitoring a NIB. After the control application2900modifies RE input tables, the control application2900uses the rules engine2915to process the modified RE input tables. It is to be noted that the input and output tables depicted and described in this Section (i.e., Section V) are conceptual representations of tables. The actual tables used in some embodiments of the invention may not look exactly like these conceptual representations.

The rules engine2915is similar to the rules engine1925described above by reference toFIG. 19. The rules engine2915of different embodiments performs different combinations of database operations on different sets of RE input tables to populate and/or modify different sets of output tables2920. For instance, the rules engine2915modifies logical data paths specified in the output table2940when the RE input table2935is changed to indicate that a logical switch is enabled for port isolation. The output table2940includes flow entries and/or logical data paths that specify the actions for the logical switch to perform on the network data sent from one port to another of the logical switch. In addition to the input table2935, the rules engine2915may use other input tables that store the data link layer addresses of the ports in the logical switch in order to modify the output table2940.

The publisher2925is similar to the publisher1955described above by reference toFIG. 19, in that the publisher2925publishes or sends the modified output tables in the output tables2920to a virtualization application (not shown). As described above, a virtualization application will map the logical data paths to physical data paths to update the NIB.

In the first stage2901, the logical switch2800is not enabled for port isolation. As shown, the GUI2930displays whether the logical switch2800, which is identified by an identifier value “LSW01,” is enabled for port isolation. The unchecked box in the GUI2930indicates that the logical switch2800is not enabled for port isolation. The RE input table2935has an entry for the logical switch2800. The RE input table2935indicates that the logical switch2800is not enabled for port isolation. A number of different scenarios may provide explanations for the values in the entries of the RE input table2935. In one scenario, the user may have disabled port isolation for the logical switch2800by entering appropriate inputs to the management tool provided by the control application. In another scenario, the user has not yet managed the logical switch2800since the switch's creation. In this scenario, the control application may populate the RE input table with default values. Or, the control application may leave the “isolated” column empty (i.e., no values) instead of zeros to indicate the logical switch has not been configured for port isolation. In yet another scenario, the RE input table2935may have been populated by the control application in response to a change in the NIB that is detected by the control application.

The output table2940indicates that the logical switch2800allows network data from any of the VMs that are coupled to the logical switch2800to another of such VMs. In some cases, the action column for each row of the logical switch2800may not contain any value when the logical switch2800has not been configured for port isolation.

In the second stage2902, the user provides input to indicate that user wishes to enable the logical switch2800for port isolation. As shown, the user has checked the box in the GUI2930. The user interface2905receives the user's input through the GUI2930and parses the input. The user interface2905selects one or more RE input tables2910as well as functions and constants (not shown) in order to populate and/or modify one or more entries of the selected RE input tables. The user interface2905uses the parsed information (e.g., a switch identifier, etc.) to select the input tables to populate and/or modify. As shown, the input table2935and the output table2940have not been changed. That is, the values in the entries in these tables have not been changed from the values that these tables had in the stage2901.

In the third stage2903illustrated inFIG. 29, the user interface2905has selected the input table2935using the information that the user interface2905received from the user through the management tool. The user interface2905selects the RE input table2935because the RE input table2935indicates whether a logical switch that the user is managing is enabled for port isolation. With the switch identifier value “LSW01”, the user interface2905in this example finds an entry for the logical switch2800in the RE input table2935. The user interface2905then populates or modifies the value for the logical switch2800in the table to indicate that the logical switch2800is enabled for port isolation. The output table2940has not been changed. AlthoughFIG. 29illustrates that a RE input table is updated by the user interface2905based on the inputs that the user interface2905receives from the user, it is possible that the RE input tables are populated and/or modified based on the changes in the NIB that are detected by the control application as described above.

In the fourth stage2904illustrate inFIG. 29, the control application2900uses the rules engine2915to map the changes in the input tables that are stored in the RE input tables2910to the logical data paths specified in the output tables stored in the output tables2920. The rules engine2915performs table mapping operations that map the entries in the input tables to the logical data paths to be specified in the output tables. In this example, the rules engine2915maps the entry for the logical switch2800in the input table2935into logical data paths for the network data that the logical switch2800routes. Specifically, the output table2940is a logical ingress ACL table for the logical switch2800in this example. The populated and/or modified entry for the logical switch2800in the input table2935indicates that the logical switch2800is to be enabled for port isolation. Therefore, the rules engine2915modifies the output table2940, by performing table mapping operations, such that the logical switch2800drops network data sent from one of the VMs that are coupled to the logical switch2800to another of such VMs.

FIG. 29illustrates only one RE input table and one output table for the simplicity of description. However, the rules engine2915performs table mapping operations using several more RE input tables2910and function and constant tables (not shown) that are similar to function and constant tables1915described above by reference toFIG. 19. For instance, the rules engine2915can use a table that contains a list of logical ingress and egress ports that a logical switch may have, a table that contains a list of VMs that are coupled to a logical switch through ingress and egress ports of the logical switch, a table for data link layer addresses (e.g., MAC addresses, etc.) of the VMs coupled to the logical switch, etc. When the rules engine2915completes the table mapping operations to modify the output table2940, the logical switch2800is enabled for port isolation as described above by reference to the stage2802ofFIG. 28.

Moreover, output tables other than the output table2940may be used to enable the switch for port isolation. For instance, the rules engine2915may create and/or modify a higher priority ACL table (not shown) instead of modifying the output table2940(an ACL table) in some embodiments. This higher priority ACL table will specify that the traffic from one VM of the switch to another VM of the switch is to be dropped. In these embodiments, hen port isolation is disabled for the switch, this higher priority ACL table will be removed or will not be used so that the output table2940allow traffics between VMs.

C. Port Security

FIG. 30conceptually illustrates an example of enabling port security for a logical port of a logical switch3000of some embodiments. Specifically, this figure illustrates the logical switch3000at two different stages3001and3002to show different forwarding behaviors of the logical switch3000before and after port1of the logical switch3000is enabled for port security. Port security in some embodiments is a technique to apply to a particular port of a switch such that the network data entering and existing the logical switch through the particular port have certain addresses that the switch has restricted the port to use. For instance, a switch may restrict a particular port to a certain MAC address and/or a certain IP address. That is, any network traffic coming in or going out through the particular port must have the restricted addresses as source or destination addresses. Port security may be enabled for ports of switches to prevent address spoofing.

As shown,FIG. 30illustrates that the logical switch3000includes logical ports1and2and other ports. These ports are ingress ports as well as egress ports in this example. The logical switch3000also includes forwarding tables3005, which include an ingress ACL table3006and an egress ACL table3007among other forwarding tables. The logical switch3000is similar to the logical switch2700described above by reference toFIG. 27. That is, the logical switch3000receive network data (e.g., packets) through the ingress ports and routes the network data based on the flow entries specified in the forwarding tables3005to the egress ports, through which the logical switch3000sends out the network data.FIG. 30also illustrates a GUI3010. The GUI3010is provided by a control application in some embodiments. The GUI3010displays NIB states upon user's request to query the NIB. The GUI3010also receives user inputs which will be parsed and processed by a control application to generate logical data paths.

VM1is a virtual machine that sends and receives network data to and from the logical switch3000through port1. That is, port1of the logical switch3000is serving both as an ingress port and an egress port for VM1. VM1has “A” as the virtual machine's MAC address. “A” represents a MAC address in the proper MAC address format (e.g., “01:23:45:67:89:ab”). This MAC address is a default MAC address assigned to VM1when VM1is created. In some embodiments, VM1's MAC address is virtual interface (VIF) addresses which may be the same or different than physical interface (PIF) address. An IP address is usually not assigned to a virtual machine but a MAC address is always assigned to a virtual machine when it is created in some embodiments. VM2is a virtual machine that uses port2of the logical switch3000to send and receive data to and from the logical switch3000.

The logical switch3000performs logical ingress lookups using the ingress ACL table3006in order to control the network data (e.g., packets) coming through the ingress ports. For instance, the logical switch3000reads information stored in the header of a packet that is received through an ingress port, looks up the matching flow entry or entries in the ingress ACL table3006, and determines an action to perform on the received packet. As described above, a logical switch may perform further logical lookups using other forwarding tables that are storing flow entries.

In the first stage3001, none of the logical ports of the logical switch3000is enabled for port security. As shown, the ingress ACL table3006shows that port1has a MAC address but does not impose an address restriction on packets that are coming in through port1. The port1's MAC address is a VIF address. The egress ACL table3007does not impose an address restriction on the packets going out of the switch3000through port1. There may be other restrictions imposed by the ingress and egress ACLs3006and3007based on the VIF addresses of the ports which are not shown in this figure for simplicity.

In this example, the logical switch3000receives packets1-3from VM1through port1. Each of packets1-3includes in the packet header a source MAC address and a source IP address. Each of packets1-3may include other information (e.g., destination MAC and IP addresses, etc.) that the logical switch may use when performing logical lookups. For packet1, the source MAC address field of the header includes a value “A” to indicate that the MAC address of the sender of packet1(i.e., VM1) is “A.” Packet1also includes in the source IP address field of the header the IP address of VM1a value “B” to indicate that the IP address of VM1is “B.” “B” represents an IP address in the proper IP address format (e.g., an IPv4 or IPv6 format, etc.). By putting “B” in packet1as a source IP address, VM1indicates that the virtual machine's IP address is “B.” However, VM1may or may not have an IP address assigned to VM1.

Packet2includes in packet2's header “A” and “B” as VM1's MAC and IP addresses, respectively. In addition, packet2includes an Address Resolution Protocol (ARP) response with “C” and “B” as VM1's MAC and IP addresses, respectively. “C” represents a MAC address in the proper MAC address format. VM1is sending this ARP message in response to an ARP request that asks for information about a machine that has a certain IP address. As shown, the MAC addresses in the header of packet2and in the ARP response do not match. That is, VM1did not use the virtual machine's MAC address (i.e., “A”) in the ARP response. As shown in the stage3001, the logical switch3000routes packets1and2from port1to the packets' respective egress ports because no address restriction has been imposed by the ingress ACL table3006and the egress ACL table3007.

Packet3includes in packet3's header “C” and “B” as VM1's MAC and IP addresses, respectively. The logical switch3000in some embodiments drops packets from port1if the packets do not have in their headers source MAC addresses that do not match to VM1MAC address. The logical switch3000drops such packets regardless of whether the logical switch3000is enabled for port security. As such, the logical switch3000drops packet3because source MAC field of packet3does not have VM's MAC address “A” in the packet's source MAC address field.

In the stage3001, the logical switch3000also receives packet4from VM4through port2. Packet4includes in packet4's header “A” and “D” as the destination MAC and IP addresses, respectively. “D” represents an IP address in the proper IP address format. Packet4may include other information (e.g., source MAC and IP addresses, etc.) that the logical switch may use when performing logical lookups to route the packet. The logical switch3000routes packet4to port1in order to send packet4to VM1through port1. The logical switch3000routes packet4to VM1through port1even though the destination IP address of packet4(i.e., “D”) does not match to the IP address of VM1(i.e., “B”). This is because port1is not enabled for port security.

In the second stage3002, a user using the GUI3010of control application enables port1of the logical switch3000for port security by checking the box in the GUI3010in this example. The user also sets “A” and “B” as the MAC and IP addresses to which a packet that is coming in or going out through port1is restricted. The ingress ACL table3005and the egress ACL table3006are modified according to the user input. As shown, the ingress ACL table3006specifies that the packets coming into the logical switch3000must have “A” and “B” as the sender's (i.e., VM1's) MAC and IP addresses, respectively, in the headers of the packets and in the ARP responses if any ARP responses are included in the packets. In other words, VM1cannot use a MAC address or an IP address that is not the virtual machine's address.

In the stage3002, the logical switch3000receives packets5-7from VM1through port1. Packets5-7are similar to packets1-3, respectively, that the logical switch3000received from VM in the stage3001. Packets5-7have the same source MAC and IP addresses as packets1-3, respectively. As shown in the stage3002, the logical switch3000routes packet5to another port according to the ingress ACL table3006which specifies that packets with “A” and “B” as the packets' source MAC and IP addresses are allowed to be sent to an egress port. However, the logical switch3000drops packets6and7. The logical switch3000drops packet6because packet6's APR response has “C” as a MAC address which is different than the MAC address to which a packet that is coming in through port1is restricted (i.e., “A”). The logical switch3000drops packet6even though the packet has source MAC and IP addresses in the header that match to the addresses to which a packet that is coming in through port1is restricted. The logical switch3000also drops packet7because packet7includes “C” as source MAC address in the header, which is different than VM1's MAC address “A.”

In the stage3002, the logical switch3000also receives packet8from VM4through port2. Packet8is similar to packet4that the logical switch3000received from VM4through port4in the stage3001. Packet8includes in packet8's header “A” and “D” as the destination MAC and IP addresses, respectively. The logical switch3000routes packet8to port1in order to send packet8to VM1through port1. However, the egress ACL table3007specifies that the switch3000should drop a packet with a destination IP address that is different than the IP address to which a packet that is going out through port1is restricted (i.e., “B”). Accordingly, the logical switch3000drops packet8after the switch routes the packet to port1because packet8includes “D” as the packet's destination IP address which is different than “B.”

FIG. 31conceptually illustrates an example of enabling port security for a port of a logical switch by control application3100of some embodiments.FIG. 31illustrates in four different stages3101,3102,3103, and3104that the control application3100enables port security for port1of the logical switch3000described above by reference toFIG. 30. As shown, these figures illustrate that the control application3100includes a user interface3105, RE input tables3110, rules engine3115, RE output tables3120, and a publisher3125. The figures also illustrate a GUI3130and tables3135and3140.

The user interface3105in some embodiments provides a user with a management tool with which the user can view and/or modify a logical network state. Different embodiments provide different management tools to the user. For instance, the user interface3105in some embodiments provides a graphical tool such as the GUI3130. Instead of or in conjunction with a graphical tool, other embodiments may provide the user with a command-line tool or any other type of management tool. The user interface3105receives inputs from the user through the management tool and processes the received inputs to populate and/or modify one or more input tables3110.

The GUI3130conceptually represents a management tool provided by the user interface3105to the user. In some embodiments, the GUI3130is provided as a web application and thus can be opened up with a web browser. With GUI3130, the user can manage the logical network elements (e.g., a logical switch), e.g., by entering inputs and receiving responses from the control application. For instance, the user can query whether port security is enabled for ports of a logical switch that the user is managing.

The RE input tables3110are similar to RE input tables1910described above by reference toFIG. 19. As described above, a RE input table in some cases represents the state of the logical network that the user is managing. For instance, the RE input table3135is a table that stores port security information of the ports of a logical switch that the user is managing through the control application. The RE input table3135conceptually represent a table in this example. As described above, the RE input table may be a result of several table joins and selects performed on a set of RE input tables. The control application modifies one or more RE input tables with user inputs that the control application receives through the management tool or with any network events that the control application detects by monitoring a NIB. After the control application3100modifies RE input tables, the control application3100uses the rules engine3115to process the modified RE input tables.

The rules engine3115is similar to the rules engine1925described above by reference toFIG. 19. The rules engine3115of different embodiments performs different combinations of database operations on different sets of RE input tables to populate and/or modify different sets of output tables3120. For instance, the rules engine3115modifies logical data paths specified in the output table3140when the input table3135is changed to indicate that a port of a logical switch is enabled for port security. The output table3140includes flow entries and/or logical data paths that specify the actions for the logical switch to perform on the network data sent from one port to another of the logical switch. The output table3140may be a result of several table joins and selects performed by the rules engine3115on a set of input tables as well as functions and constants. In addition to the input table3135, the rules engine3115may use other input tables as well as functions and constants in order to modify the output table3140. Other input tables may include tables that store the data link layer addresses (e.g., MAC addresses, etc.) of the ports of the logical switch and tables that store the network layer addresses (e.g., IP addresses, etc.) of the ports. Other input tables may also include tables that store VIF addresses and tables that store PIF addresses of the ports.

The publisher3125is similar to the publisher1955described above by reference toFIG. 1955, in that the publisher3125publishes or sends the populated and/or modified output tables in the output tables3120to a virtualization application (not shown). As described above, a virtualization application will map the logical data paths to physical data paths to update the NIB.

In the first stage3101, the ports of the logical switch3000are not enabled for port security. As shown, the GUI3130displays whether the ports of the logical switch3000, which is identified by an identifier “LSW08,” are enabled for port security. The unchecked boxes in the GUI3130indicate that ports1and2of the logical switch3000are not enabled for the port security. In some embodiments, the GUI3130allows the user to specify one or both of the MAC and IP addresses to which a particular port of the switch is to be restricted. In some such embodiments, the particular port of the switch is deemed enabled for port security when the MAC and IP addresses pair is specified for the port. In these embodiments, the control application3100determines that a port is not enabled for port security if the port does not have a MAC and/or IP address assigned. In other embodiments, the GUI3130may only allow the user to specify whether the particular port of the switch should be enabled for port security. However, to enable a port for port security, there must be a MAC address and/or IP address assigned to the port in some such embodiments. In these embodiments, instead of the user, the user interface3105or the rules engine3115specify the MAC and IP addresses to which to restrict this port. In some of these embodiments, the user interface3105or the rules engine3115uses the PIF MAC address and/or PIF IP address as the addresses to which to restrict the port.

The RE input table3135includes a list of the ports of the logical switch3000. The input table3135indicates that the ports of the logical switch3000are not enabled for port security. A number of different scenarios may provide explanations for the values in the entries of the input table3135. In one scenario, the user may have disabled port security for ports1and2of the logical switch3000by entering appropriate inputs to the management tool provided by the control application. In another scenario, the user has not yet managed the logical switch3000since the switch's creation. In this scenario, the control application may populate the RE input table with default values. Or, the control application may leave the “secured” column empty (i.e., no values) instead of zeros to indicate ports1and2of the logical switch3000have not been configured for port security. In yet another scenario, the RE input table3135may have been populated by the control application in response to a change in the NIB that is detected by the control application.

The RE input table3135also includes a list of MAC addresses and a list of IP addresses to which the ports of the logical switch3000are restricted when port security is enabled for the switch. As described above, these lists may be stored as one or more separate tables. The output table3140indicates that the logical switch3000allows packets that are coming in and/or going out of the switch3000through port1of the logical switch3000are not restricted to particular MAC and IP addresses. As shown in the first stage3101, the RE input table3135lists the default MAC addresses “A” and “A1” for ports1and2, respectively. “A” and “A1” are in the proper MAC address format. As described above, source MAC addresses of the packets from the ports1and2of the logical switch in some embodiments are restricted to these two MAC addresses regardless of whether this logical switch has been enabled for port security. That is, even if the logical switch is not enabled for port security, the switch will drop packets from ports1and2when these packets do not have “A” and “A1,” respectively, as their source MAC addresses in these embodiments. In some cases, the action column and/or the MAC column for each row of the output table3140may not contain any value when ports1and2of the logical switch3000have not been configured for port security.

In the second stage3102, the user provides input to indicate that user wishes to enable port1of the logical switch3000for port security. As shown, the user has checked a box next to “port1” in the GUI3130and entered “X” and “B” as the MAC and IP addresses, respectively, to which to restrict port1. “X” is in the proper MAC address format and “B” is in the proper IP address format. The user interface3105receives the user's inputs through the GUI3130and parses the inputs. The user interface3105selects one or more RE input tables3110in order to populate and/or modify one or more entries of the selected RE input tables. The user interface3105uses the parsed information (e.g., a switch identifier, etc.) to select the RE input tables to populate and/or modify. As shown, the RE input table3135and the output table3140have not been changed. That is, the values in the entries in these tables have not been changed from the values that these tables had in the stage3101.

In the third stage3103illustrated inFIG. 31, the user interface3105has selected the input table3135using the information that the user interface3105received from the user through the management tool. The user interface3105selects the RE input table3135because the RE input table3135indicates whether ports of the logical switch3000that the user is managing are enabled for port security. The user interface3105then populates and/or modifies the output table3140to indicate that port1of the logical switch3000is enabled for port security. Specifically, the user interface3105modifies the value of the “secured” column for port1to 1 from 0 to indicate that the port is enabled for port security. The user interface3105also populates the MAC and IP columns for port1with the MAC address “X” and the IP address “B” that the user has specified. Since the default MAC address for port1was “A” in the second stage3102, the MAC address for port1is now changed to “X.” Accordingly, the traffic coming through port1would be restricted to MAC address “X” and IP address “B.” That is, the logical switch will drop the packets that have source MAC address different than port1's MAC address “X,” the packets that have source IP address different than “B,” or the packets that have ARP messages with MAC and IP addresses that are different than “X” and “B.” Even if a packet that has “A,” which was the default MAC address for port1, as source MAC address, the logical switch will drop the packet.

As described above, the user may not have an ability to specify the MAC and IP addresses to which to restrict a port of a logical switch in some embodiments. In these embodiments, the user interface3105may perform table joins and selects on several RE input tables to populate the MAC and IP columns for port1in the RE input table3135. In other embodiments, the RE input table may not include the MAC and IP columns. In some such embodiments, the rules engine3115may perform table joins and selects on several output tables and populate the output table3140with logical data paths that specify MAC and IP addresses to which the port is to be restricted.

In the third stage3103, the output table3140has not been changed from what it was in the stage3102. AlthoughFIG. 31illustrates that an RE input table is updated by the user interface3105based on the inputs that the user interface3105receives from the user, it is possible that the RE input tables are populated and/or modified based on the changes in the NIB that are fed back to the control application.

In the fourth stage3104illustrate inFIG. 31, the control application3100uses the rules engine3115to map the changes in the RE input tables3110to the logical data paths specified in the output tables3120. The rules engine3115performs table mapping operations that map the entries in the RE input tables to the logical data paths to be specified in the output tables. In this example, the rules engine3115maps the entry for port1of the logical switch3000in the RE input table3135into logical data paths for the network data that the logical switch3000routes. Specifically, the output table3140includes logical data paths for a logical ingress ACL table and a logical egress ACL table for the logical switch3000. The modified and/or populated entry for port1of the logical switch3000in the RE input table3135indicates that port1of the logical switch3000is to be enabled for port security. Therefore, the rules engine3115modifies the output table3140, by performing table mapping operations, such that the logical switch3000drops network data (e.g., packets) after the logical switch3000receives network data or before the logical switch3000sends out network data through port1.

Specifically, the output table3140specifies that a packet should be dropped when the packet's source MAC address or source IP address does not match the MAC address (“X”) or the IP address (“B”) to which a packet that is coming through port1of the switch3000is restricted. The output table3140also specifies that a packet should be dropped when the packet's MAC address or IP address in any ARP response the packet contains does not match the MAC address or the IP address to which a packet that is coming through port1of the switch3000is restricted. The output table3140also specifies that a packet should be dropped when the packet's destination IP address does not match the IP address that a packet that is going out through port1of the switch3000is restricted.

FIG. 31illustrates only one RE input table and one output table for the simplicity of description. However, the rules engine3115performs table mapping operations using several more RE input tables and function and constant tables (not shown) that are similar to function and constant tables1915described above by reference toFIG. 19. For instance, the rules engine3115can use a table that provides MAC addresses of logical ports, a table that provides VIF addresses of logical ports, a table that provides PIF addresses of logical ports, a table that provides a IP addresses of logical ports, etc. When the rules engine3115completes the table mapping operations to populate and/or modify the output table3140, port1of the logical switch3000is enabled for port security as described above by reference to the stage3002ofFIG. 30.

D. Quality of Service

FIG. 32conceptually illustrates an example of enabling Quality of Service (QoS) for a logical port of a logical switch3000of some embodiments. Specifically, this figure illustrates the logical switch3200at two different stages3201and3202to show that, after port1of the logical switch is enabled for QoS, the logical switch3200queues network data that comes into the logical switch3000through port1. The logical switch3200queues the network data in order to provide QoS to a machine that sends the network data to switch3200through port1. QoS in some embodiments is a technique to apply to a particular port of a switch such that the switch can guarantee a certain level of performance to network data that a machine sends through the particular port. For instance, by enabling QoS for a particular port of a switch, the switch guarantees a minimum bitrate and/or a maximum bitrate to network data sent by a machine to the network through the switch.

As shown,FIG. 32illustrates that the logical switch3200includes logical ports1and2. These ports are ingress ports and some of them may be egress ports in this example. The logical switch3200also includes forwarding tables3205. The logical switch3200is similar to the logical switch2700described above by reference toFIG. 27. That is, the logical switch3200receive network data (e.g., packets) through the ingress ports and routes the network data based on the flow entries specified in the forwarding tables3205to the egress ports3207, through which the logical switch3200sends out the network data.FIG. 32also illustrates a GUI3210. The GUI3210is provided by a control application in some embodiments. The GUI3210displays NIB states upon user's request to query the NIB. The GUI3210also receives user inputs which will be parsed and processed by a control application to generate logical data paths.

VM1is a virtual machine that sends network data to the logical switch3200through port1. That is, port1of the logical switch3200is serving as an ingress port for VM1. The logical switch3200performs logical ingress lookups using an ingress ACL table (not shown), which is one of forwarding tables3205, in order to control the network data (e.g., packets) coming through the ingress ports. For instance, the logical switch3200reads information stored in the header of a packet that is received through an ingress port, looks up the matching flow entry or entries in the ingress ACL table, and determines an action to perform on the received packet. As described above, a logical switch may perform further logical lookups using other forwarding tables that are storing flow entries.

FIG. 32also illustrates a host3215. The host3215in this example is a server on which VM1runs. The host3215in some embodiments includes a network interface (e.g., a network interface card (NIC) with an Ethernet port, etc.) through which one or more VMs hosted in the host3215send out packets. In this example, port1of the logical switch3200is mapped to the network interface (i.e., PIF1) of the host3215. That is, PIF1is a physical transport port to which the logical port1is mapped. When the packets are sent out through PIF1, the packets may be sent to the intended destinations through a managed switching element (not shown). As mentioned above, managed switching elements in some embodiments can include standalone physical switching elements, software switching elements that operate within a computer, or another other type of virtual switching element. The software or virtual switching elements may operate on a dedicated computer, or on a computer that performs non-switching operations.

When a logical port is enabled for QoS, the logical port needs a logical queue to en-queue the packets that are going into the logical switch through the logical port. In some embodiments, the user assigns a logical queue to a logical port. A logical queue may be created based on the user inputs in some embodiments. For instance, the user may enter a queue creation request through a UI provided by the control application in some embodiments. The user may specify the minimum and maximum bitrates for the queue. When enabling a logical port for QoS, the user may then point the logical port to the logical queue. In some embodiments, multiple logical ports can share the same logical queue. By sharing the same logical queue, the machines that send data to the logical switch through these logical ports can share the minimum and maximum bitrates associated with the logical queue.

In some embodiments, the control application creates a logical queue collection for the logical port. The control application then has the logical queue collection point to the logical queue. The logical port and the logical queue collection have a one-to-one relationship. However, in some embodiments, several logical ports (and corresponding logical queue collections) can share one logical queue. That is, the traffic coming through these several logical ports together are guaranteed for some level of performance specified for the logical queue.

Once a logical port points to a logical queue (once the relationship between logical port, the logical queue collection, and the logical queue is established), physical queue collection and physical queue are created. In some embodiments, the logical queue collection and the logical queue are mapped to a physical queue collection and a physical queue, respectively. When the packets are coming into the logical switch through a logical port that points to a logical queue, the packets are actually queued in the physical queue to which the logical queue is mapped. That is, a logical queue is a logical concept that does not actually queue packets. Instead, a logical queue indicates that the logical port that is associated with the logical queue is enabled for QoS.

In the first stage3201, neither of the logical ports1and2of the logical switch3200is enabled for QoS. The logical switch3200routes packets that are coming from VM1and VM2through ports1and2to the egress ports3207without guaranteeing certain performance level because logical ports1and2are not enabled for QoS. On the physical side, packets from VM1are sent out through PIF1. In this example, the packets sent out through PIF1are sent to a managed switching element (not shown) which may be one of the managed switching elements that physically implement the logical switch3200.

In the second stage3202, a user using the GUI3210of control application enables port1of the logical switch3200for QoS by specifying information in the box next to “port1” in the GUI3210in this example. The user specifies “LQ1” as the ID of the logical queue to which to point port1. The user also specifies “A” and “B” as the minimum and maximum bitrates, respectively, of the logical queue. “A” and “B” here represent bitrates, which are numerical values that quantify amount of data that the port allows to go through per unit of time (e.g., 1,024 bit/second, etc.).

The control application creates a logical queue according to the specified information. The control application also creates a logical queue collection that would be set between port1and the logical queue LQ1. The logical queue LQ1queues the packets coming into the logical switch3200through port1in order to guarantee that the packets are routed at a bitrate between the minimum and the maximum bitrates. For instance, the logical queue LQ1will hold some of the packets in the queue when the packets are coming into the logical queue LQ1through port1at a higher bitrate than the maximum bitrate. The logical switch3200will send the packets to the egress ports3207at a bitrate that is lower than the maximum bitrate (but at a higher bitrate than the minimum bitrate). Conversely, when the packets coming through port1are routed at a bitrate above but close to the minimum bitrate, the logical queue LQ1may prioritize the packets in the queue such that the logical switch3200routes these packets first over other packets in some embodiments.

On the physical side, the control application through a NOS creates a physical queue collection3230and a physical queue3235in the host3215. The physical queue collection3230includes a physical queue3235. The logical queue3225is mapped to the physical queue3235actual queuing takes place. That is, the packets coming through port1of the logical switch3200in this example are queued in the physical queue3230. The physical queue3230in some embodiments is implemented as a storage such as memory. The packets from VM1are queued in the physical queue before the packets are sent out through PIF1. In this example, the NIC (not shown) with which PIF1is associated manages the physical queue3235to guarantee that the packets that are sent out through PIF1at a bitrate between the minimum and maximum bitrates.

FIG. 33conceptually illustrates an example of enabling QoS for a port of a logical switch by control application3300of some embodiments.FIG. 33illustrates in seven different stages3301,3302,3303,3304,3305,3306, and3307that the control application3300enables QoS for port1of the logical switch3200described above by reference toFIG. 32. These figures illustrate that enabling a logical port for QoS results in creation of network constructs. As described above, creation of a network construct is a network event that causes one or more input tables to be updated. The updates to the input tables in turn trigger a series of table joins and selects that results in a change in a NIB. As shown, these figures illustrate that the control application3300includes a user interface3370, input tables3310, rules engine3315, output tables3320, and a publisher3325. The figures also illustrate a GUI3330, tables3335,3336,3340,3345, and3350, a virtualization application3355, and a NOS3360.

The user interface3370in some embodiments provides a user with a management tool with which the user can view and/or modify a logical network state. Different embodiments provide different management tools to the user. For instance, the user interface3370in some embodiments provides a graphical tool such as the GUI3330. Instead of or in conjunction with a graphical tool, other embodiments may provide the user with a command-line tool or any other type of management tool. The user interface3370receives inputs from the user through the management tool and processes the received inputs to populate and/or modify one or more input tables3310.

The GUI3330conceptually represents a management tool provided by the user interface3370to the user. In some embodiments, the GUI3330is provided as a web application and thus can be opened up with a web browser. With GUI3330, the user can manage the logical network elements (e.g., a logical switch), e.g., by entering inputs and receiving responses from the control application. For instance, the user can query whether QoS is enabled for ports of a logical switch that the user is managing.

The RE input tables3310are similar to RE input tables1910described above by reference toFIG. 19. As described above, a RE input table in some cases represents the state of the logical network that the user is managing. For instance, the RE input table3335is a table that stores QoS information of the ports of a logical switch that the user is managing through the control application. The RE input table3335may be a result of several table and joins and selects performed on a set of input tables (not shown). The control application modifies input tables with user inputs that the control application receives through the management tool or with any network events that the control application detects by monitoring a NIB (e.g., using a query manager). After the control application3300modifies RE input tables, the control application3300uses the rules engine3315to process the modified RE input tables.

The rules engine3315is similar to the rules engine1925described above by reference toFIG. 19. The rules engine3315of different embodiments performs different combinations of database operations on different sets of RE input tables to populate and/or modify different sets of output tables3320. For instance, the rules engine3315modifies the output table3350when the RE input table3336is changed to indicate that a logical queue is created. The output table3350in some embodiments includes entries that specify requests for the virtualization application3355through a NOS to create network constructs. For instance, the output table3350may specify that the virtualization application to create a physical queue collection and/or a physical queue. These entries in the input table3335will be processed by the virtualization application3355to generate and/or modify output tables and publish the generated and/or modified output tables to the NIB3365. The output table3350may be a result of several table joins and selects performed by the rules engine3315on a set of input tables, functions, and constants. In some embodiments, the rules engine3355may generate and/or use other input tables in order to populate and/or modify the output table3350. The generation and/or use of these other input tables will be described further below.

The publisher3325is similar to the publisher1955described above by reference toFIG. 19, in that the publisher3325publishes or sends the modified output tables in the output tables3320to the virtualization application3355. As described above, a virtualization application will map the logical data paths to physical data paths to update the NIB.

In some embodiments, the control application3300also uses a query manager (not shown) that interfaces with the NIB3365to query the NIB to receive state information regarding the network elements or constructs. In other embodiments, the query manager queries the output tables3320to obtain LDPS data.

In the first stage3301, the GUI3330displays QoS information of ports1and2of the logical switch3200. The user interface3370displays this information on the GUI3330upon the user's request (not shown) in this example. The logical ports of the logical switch3200are not enabled for QoS. As shown, the GUI3330displays whether ports1and2of the logical switch3200, which is identified by an identifier “LSW12,” are enabled for QoS. The unchecked boxes in the GUI3330indicate that ports1and2of the logical switch3000are not enabled for QoS. In some embodiments, the GUI3330allows the user to specify a logical queue to which to point a logical port.

The input table3335includes a list of the ports of the logical switch3200. The RE input table3335indicates that the ports of the logical switch3200are not enabled for QoS. A number of different scenarios may provide explanations for the values in the entries of the input table3335. In one scenario, the user may have disabled QoS for ports1and2of the logical switch3200by entering appropriate inputs to the management tool provided by the control application. In another scenario, the user has not yet managed the logical switch3200since creation of the switch. In this scenario, the control application may populate the RE input table with default values. Or, the control application may leave the “queue” column empty (i.e., no values) instead of zeros to indicate ports1and2of the logical switch3200have not been configured for QoS. In yet another scenario, the RE input table3335may have been populated by the control application in response to a change in the NIB that is detected by the control application.

The RE input table3336includes a list of logical queues and each logical queue's minimum and maximum bitrates. As described above, a logical port that points to a logical queue is guaranteed for a certain level of performance. That is, the packets coming through the logical port will be routed, for example, at a bitrate between the minimum and maximum bitrates specified for the logical queue. Also, in some embodiments, a logical queue is global. That is, different logical ports of different logical switches can point to the same logical queue and share the bitrates and other features specified for the logical queue. The RE input table3340associates a logical queue and a physical queue. The RE input table3345associates physical interfaces with physical queue collections. As described above, the output table3350includes entries that specify requests for the virtualization application3355to create network constructs. The action column is empty in the stage3301in this example.

In the second stage3302, the user provides input to indicate that user wishes to enable port1of the logical switch3200for QoS. As shown, the user has checked a box next to “port1” in the GUI3330and entered “LQ1” as the logical queue ID to which to point port1. The user has also entered a command to create the logical queue with “A” and “B” as the minimum and maximum bitrates, respectively. The user interface3370receives the user's inputs through the GUI3330and parses the inputs. The user interface3370selects one or more input tables3310in order to populate and/or modify one or more entries of the selected RE input tables. The user interface3370uses the parsed information (e.g., a switch identifier, etc.) to select the RE input tables to populate and/or modify. As shown, the RE input tables3335-3345and the output table3350have not been changed. That is, the values in the entries in these tables have not been changed from the values that these tables had in the stage3301.

In the third stage3303illustrated inFIG. 33, the user interface3370has selected the RE input table3336using the information that the user interface3370received from the user through the management tool. The user interface3370selects the RE table3335because the RE input table3335indicates whether ports of the logical switch3200that the user is managing are enabled for QoS. The user interface3370then populates and/or modifies the RE input table3335to indicate that port1of the logical switch3200is enabled for QoS. Specifically, the user interface3370in this example modifies the value of the “queue” column for port1to1to indicate that the port is enabled for QoS. The user interface3370also selects the RE table3336because the RE input table3336includes information about all logical queues. The user interface3370then populates and/or modifies the RE input table3336to indicate that a logical queue with a queue ID “LQ1” is to be created. The user interface3370obtains the queue ID from another table by performing table mapping operations on other input tables, functions, and constants. The user interface3370also populates the bitrate columns for the logical queue with the minimum bitrate “A” and the maximum bitrate “B” that the user has specified. The user interface3370also selects the RE input table3340and populates the table with the queue ID of the logical queue. As described above, the RE input table3340associates logical queues with physical queues.

In the third stage3303, the RE input table3345and the output table3350have not been changed from what the tables were in the stage3302. AlthoughFIG. 33illustrates that a RE input table is updated by the user interface3370based on the RE inputs that the user interface3370receives from the user, it is possible that the RE input tables are populated and/or modified based on the changes in the NIB3365that are fed back to the control application3300(by, e.g., the query manager).

In the fourth stage3304illustrate inFIG. 33, the control application3300uses the rules engine3315to map the changes in the RE input tables to the logical data paths and/or the requests to create network constructs specified in the output tables. The rules engine3315performs table mapping operations that map the entries in the RE input tables to the logical data paths or requests for creation of network constructs to be specified in the output tables. In this example, the rules engine3315generates a request to create a physical queue collection for the logical queue because PIF1that is associated with the logical queue LQ1does not have a physical queue collection associated with the PIF. As described above, a physical queue collection and a physical queue need to be created to handle actual queuing of the packets that are queue in a logical queue. In order to create a physical queue, a physical queue collection should be created first. Accordingly, the rules engine3315modifies and/or populates the output table3350, by performing table mapping operations, such that a physical queue collection is created for PIF1.

The rules engine3315performs several table joins and selects to generate table entries with which to populate and/or modify output tables. The rules engine3315generates and/or uses a table that associates a logical port that is enabled for QoS with a logical queue collection, a table that associates a logical queue collection with a logical queue, a table that associates a logical port with a PIF, a table that associates a logical port with a managed switching element, etc. The rules engine3315generates the request to create a physical queue collection when all information necessary to create the queue collection is available in the RE input tables. That is, all necessary information must be present in the tables that are joined in order to successfully generate the request because any missing information would fail table joins operations.

The publisher3325then publishes the output table3350to the NIB3365of the NOS3360or to the virtualization application3355. The virtualization application3355may perform a set of table mapping operations to generate and/or modify data to send to the NIB3365. The NOS3360creates a physical queue collection and notifies of the result to the virtualization application3355. The query manager in some embodiments receives the updated state of the network and creates and/or modifies input tables3310accordingly for the control application to process.

In the fifth stage3305illustrated inFIG. 33, the control application3300updates the RE input table3345when the control application is notified (e.g., by the query manager) of the creation of a physical queue collection for PIF1. As described above, the RE input table3345associates physical interfaces with physical queue collections. The control application3300selects the RE input table3345and populates the entry for PIF1with the identifier of the created physical queue collection. In the stage3305, the RE input tables3335,3336and3340and the output table3350have not been changed from what the tables were in the stage3304. The control application3300also updates other RE input tables including a table that associates a PIF or a physical port with a physical queue collection, a table that associates a physical queue collection and physical queues in the physical queue collection, etc.

In the sixth stage3306illustrate inFIG. 33, the control application3300uses the rules engine3315to map the changes in the RE input tables to the logical data paths and/or the requests for creation of network constructs specified in the output tables. In this example, the rules engine3315detects the creation of the physical queue collection for PIF1and generates a request to create a physical queue at the created physical queue collection for PIF1. The rules engine3315maps the entry to the request by performing several table joins and selects on the RE input tables3310. The rules engine3315generates and/or uses several RE input tables to perform table joins and selects. For instance, the rules engine3315uses the RE input table3336so that the physical queue to be created will perform at a bitrate between the minimum and the maximum bitrates specified in the RE input able3336. The rules engine3315may also use the RE table3340to get the ID for the logical queue for which the physical queue is being created. The rules engine3315also modifies and/or populates other output tables including a table that includes a request to create a unique queue identifier for a physical queue, a table that includes a request to assign a queue number to a physical queue for a physical port or a PIF, etc.

The publisher3325then publishes the output table3350to the NIB3365of the NOS3360or to the virtualization application3355. The virtualization application3355may perform a set of table mapping operations to generate and/or modify data to send to the NIB3365. The NOS3360creates a physical queue at the physical queue collection for PIF1and notifies of the result to the virtualization application3355. The query manager in some embodiments receives the updated state of the network and creates and/or modifies input tables3310accordingly for the control application to process.

In the seventh stage3307illustrated inFIG. 33, the control application3300updates the RE input table3340when the control application is notified of the creation of a physical queue. As described above, the RE input table3340associates logical queues and physical queues. The control application3300selects the RE input table3340and populates the entry for the physical queue that is to be associated with the logical queue being created. Other RE input tables that the control application may use and/or update include a table that associates physical ports and physical queue collections, a table that associates a physical queue collections with physical queues, a table that contains all physical ports, a table that contains all PIFs, and etc.

With port1pointing to the logical queue that is mapped to the physical queue, the flow tables of the logical switch3200will specify that the traffic from port1, which is now enabled for QoS, should be queued. The virtualization application3355and the NOS3360will implement and configure network constructs according to the logical flows specified in the logical flow tables.

VI. Electronic System

FIG. 34conceptually illustrates an electronic system3400with which some embodiments of the invention are implemented. The electronic system3400can be used to execute any of the control, virtualization, or operating system applications described above. The electronic system3400may be a computer (e.g., a desktop computer, personal computer, tablet computer, server computer, mainframe, a blade computer etc.), phone, PDA, or any other sort of electronic device. Such an electronic system includes various types of computer readable media and interfaces for various other types of computer readable media. Electronic system3400includes a bus3405, processing unit(s)3410, a system memory3425, a read-only memory3430, a permanent storage device3435, input devices3440, and output devices3445.

The bus3405collectively represents all system, peripheral, and chipset buses that communicatively connect the numerous internal devices of the electronic system3400. For instance, the bus3405communicatively connects the processing unit(s)3410with the read-only memory3430, the system memory3425, and the permanent storage device3435.

The read-only-memory (ROM)3430stores static data and instructions that are needed by the processing unit(s)3410and other modules of the electronic system. The permanent storage device3435, on the other hand, is a read-and-write memory device. This device is a non-volatile memory unit that stores instructions and data even when the electronic system3400is off. Some embodiments of the invention use a mass-storage device (such as a magnetic or optical disk and its corresponding disk drive) as the permanent storage device3435.

Other embodiments use a removable storage device (such as a floppy disk, flash drive, etc.) as the permanent storage device. Like the permanent storage device3435, the system memory3425is a read-and-write memory device. However, unlike storage device3435, the system memory is a volatile read-and-write memory, such a random access memory. The system memory stores some of the instructions and data that the processor needs at runtime. In some embodiments, the invention's processes are stored in the system memory3425, the permanent storage device3435, and/or the read-only memory3430. For example, the various memory units include instructions for processing multimedia clips in accordance with some embodiments. From these various memory units, the processing unit(s)3410retrieve instructions to execute and data to process in order to execute the processes of some embodiments.

The bus3405also connects to the input and output devices3440and3445. The input devices enable the user to communicate information and select commands to the electronic system. The input devices3440include alphanumeric keyboards and pointing devices (also called “cursor control devices”). The output devices3445display images generated by the electronic system. The output devices include printers and display devices, such as cathode ray tubes (CRT) or liquid crystal displays (LCD). Some embodiments include devices such as a touchscreen that function as both input and output devices.

Finally, as shown inFIG. 34, bus3405also couples electronic system3400to a network3465through a network adapter (not shown). In this manner, the computer can be a part of a network of computers (such as a local area network (“LAN”), a wide area network (“WAN”), or an Intranet, or a network of networks, such as the Internet. Any or all components of electronic system3400may be used in conjunction with the invention.

While the invention has been described with reference to numerous specific details, one of ordinary skill in the art will recognize that the invention can be embodied in other specific forms without departing from the spirit of the invention. In addition, a number of the figures (includingFIG. 23) conceptually illustrate processes. The specific operations of these processes may not be performed in the exact order shown and described. The specific operations may not be performed in one continuous series of operations, and different specific operations may be performed in different embodiments. Furthermore, the process could be implemented using several sub-processes, or as part of a larger macro process.

Also, several embodiments were described above in which a user provides logical data path sets in terms of logical control plane data. In other embodiments, however, a user may provide logical data path sets in terms of logical forwarding plane data. In addition, several embodiments were described above in which a controller instance provides physical control plane data to a switching element in order to manage the switching element. In other embodiments, however, the controller instance may provide the switching element with physical forwarding plane data. In such embodiments, the NIB would store physical forwarding plane data and the virtualization application would generate such data.

Furthermore, in several examples above, a user specifies one or more logic switches. In some embodiments, the user can provide physical switch configurations along with such logic switch configurations. Also, even though controller instances are described that in some embodiments are individually formed by several application layers that execute on one computing device, one of ordinary skill will realize that such instances are formed by dedicated computing devices or other machines in some embodiments that perform one or more layers of their operations.

Also, several examples described above show that a logical data path set is associated with one user. One of the ordinary skill in the art will recognize that then a user may be associated with one or more sets of logical data paths in some embodiments. That is, the relationship between a logical data path set is not always a one-to-one relationship as a user may be associated with multiple logical data path sets. Thus, one of ordinary skill in the art would understand that the invention is not to be limited by the foregoing illustrative details.