Network control apparatus and method with table mapping engine

• US 8,750,119 B2
• Filed: 07/06/2011
• Issued: 06/10/2014
• Est. Priority Date: 07/06/2010
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Lambeth, W. Andrew, Koponen, Teemu, Thakkar, Pankaj, Yip, Alexander, Casado, Martin
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US13/177,540
• Publication Number:
  US 20130058340A1
• Time in Patent Office: 1,070 Days
• Field of Search: 370/235, 370/397, 370/409, 370/428, 370/465, 709/223, 709/238, 711/206, 711/221
• US Class Current: 370/235
• CPC Class Codes: G06F 11/07 Responding to the occurrence of a fault, e.g. fault tolerance
• CPC Class Codes: G06F 15/17312 Routing techniques specific to parallel machines, e.g. wormhole, store and forward, shortest path problem congestion routing on a LAN H04L45/00
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/036 Updating the topology between route computation elements, e.g. between OpenFlow controllers
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/76 Routing in software-defined topologies, e.g. routing between virtual machines
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 49/00 Packet switching elements
• CPC Class Codes: H04L 49/1546 using pipelined operation
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/70 : Virtual switches
• CPC Class Codes: H04L 61/5007 : Internet protocol [IP] addresses

Abstract

Some embodiments provide a controller for managing a plurality of managed switching elements that forward data through a network. The controller comprising a first set of tables for storing input logical control plane data, and a second set of tables for storing output logical forwarding plane data. It also includes a table mapping engine for mapping the input logical control plane data in the first set of tables to output logical forwarding plane data in the second set of tables by performing a set of database join operations on the input logical control plane data in the first set of tables. The logical forwarding plane data is subsequently translated into physical forwarding behaviors that direct the forwarding of data by the managed switching elements.

Claims

1. A controller that executes a control application that manages a plurality of managed switching elements that forward data through a network, the control application comprising:

a first set of tables for storing input logical control plane data tuples for specifying one or more logical switching elements;

a second set of tables for storing output logical forwarding plane data tuples that define a logical data path set as a plurality of logical flow entries for the one or more logical switching elements; and

a table mapping engine for mapping the input logical control plane data tuples in the first set of tables to output logical forwarding plane data tuples in the second set of tables by performing a set of database join operations on the input logical control plane data tuples in the first set of tables,

wherein at least a portion of the output logical forwarding plane data tuples are for a virtualization application to subsequently translate into physical control plane data tuples for propagating to a set of the plurality of managed switching elements.

2. The controller of claim 1, wherein the table mapping engine comprises:

a plurality of different query plans for specifying different sets of database join operations to execute upon occurrence of different input data events; and

a table processor for executing a particular set of database join operations associated with a particular query plan upon occurrence of a particular input data event.

3. The controller of claim 2, wherein the table mapping engine further comprises an event processor that (i) detects an occurrence of an input data event, (ii) identifies a query plan associated with the detected input data event, and (iii) directs the table processor to execute a set of database join operations associated with the identified query plan.

4. The controller of claim 1, wherein the input logical control plane data tuples are at least partially based on data supplied by at least one user.

5. The controller of claim 1, wherein the control application further comprises a monitor for (i) monitoring a network data structure that stores a state of the set of managed switching elements and (ii) supplying the first set of tables with input logical control plane data tuples based on the state of the set of managed switching elements.

6. The controller of claim 1,

wherein the first set of tables are further for storing input physical control plane data tuples,

the control application further comprising a monitor for monitoring a state of the set of managed switching elements and supplying the first set of tables with the input physical control plane data tuples based on the state of the set of managed switching elements.

7. The controller of claim 1, wherein the first set of tables comprises at least one table for storing constant values necessary for the database join operations.

8. The controller of claim 1, wherein the first set of tables comprises at least one table for storing functions necessary for the database join operations.

9. The controller of claim 1, wherein the control application further comprises a publisher for publishing data from the second set of tables to a data storage structure for storing the output logical forwarding plane data tuples.

10. The controller of claim 1, wherein the set of database join operations includes inner join operations and does not include outer join operations.

11. The controller of claim 1, wherein the physical control plane data tuples are for subsequent translation by the set of managed switching elements into physical forwarding behaviors that direct the forwarding of data by the set of managed switching elements in order to effectuate the logical data path set.

12. The controller of claim 1, wherein the control application and the virtualization application execute on a same computer, wherein said computer is the controller.

13. The controller of claim 1, wherein the control application and the virtualization application execute on two different computers, wherein the controller is one of the computers.

14. The controller of claim 1, wherein the output logical forwarding plane data tuples comprises a set of logical flow entries that is not accessible for input by a source of input of the logical control plane data tuples.

15. The controller of claim 14, wherein a plurality of the logical flow entries specify at least one of layer 2 (L2) forwarding rules for forwarding of data between logical media access control (MAC) addresses and layer 3 (L3) forwarding rules for forwarding of data between logical internet protocol (IP) addresses of the logical switching elements.

16. The controller of claim 1,

wherein the table mapping engine is for mapping records in the first set of tables to records in the second set of tables,

wherein a plurality of the records in the second set of tables contain the output logical forwarding plane data tuples,

wherein the second set of tables includes tables that have records that upon changing cause the table mapping engine to perform additional database join operations to produce additional output logical forwarding plane data tuples.

17. A non-transitory computer readable medium storing a program which when executed by at least one processing unit generates logical forwarding plane data from logical control plane data, the program comprising sets of instructions for:

detecting a change in input logical control plane data tuples for controlling one or more logical switching elements;

upon detecting the change, selecting a query plan from a plurality of different query plans for the input logical control plane data tuples based on the change, the selected query plan comprising a set of database join operations; and

executing the selected query plan on the input logical control plane data tuples to generate output logical forwarding plane data tuples that define a logical data path set as a plurality of logical flow entries for the one or more logical switching elements.

18. The non-transitory computer readable medium of claim 17, wherein the input logical control plane data tuples are stored in a first set of tables and the output logical forwarding plane data tuples are stored in a second set of tables.

19. The non-transitory computer readable medium of claim 17, wherein the program further comprises a set of instructions for publishing the output logical forwarding plane data tuples for propagation to a virtualization application for translation by the virtualization application into physical control plane data tuples that specify rules for the set of managed switching elements to follow in order to implement the logical data path set when processing data packets.

20. A method for managing a network comprising a plurality of network elements, the network elements comprising a plurality of managed switching elements that forward data among the network elements, the method comprising:

receiving input logical control plane data tuples from a user, the input logical control plane data tuples for controlling one or more logical switching elements;

storing the received input logical control plane data tuples in a first set of tables;

mapping the input logical control plane data tuples to output logical forwarding plane data tuples by performing a set of database join operations on the input logical control plane data tuples, wherein the output logical forwarding plane data tuples define a logical data path set as a plurality of logical flow entries for the one or more logical switching elements; and

storing the output logical forwarding plane data tuples in a second set of tables, wherein the stored output logical forwarding plane data tuples are for sending to a virtualization application for translation by the virtualization application into physical control plane data tuples that specify rules for a set of the plurality of managed switching elements to follow in order to implement the logical data path set when processing data packets.

21. The method of claim 20 further comprising publishing the stored output physical control plane data tuples to a data storage structure that stores network state information.

22. The method of claim 21, wherein the output logical forwarding plane data tuples are sent to the virtualization application from the data storage structure.