Logical router processing by network controller

• US 9,313,129 B2
• Filed: 03/14/2014
• Issued: 04/12/2016
• Est. Priority Date: 03/14/2014
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Ganichev, Igor, Zhang, Ronghua, Koponen, Teemu, Dubovik, Gleb, Thakkar, Pankaj
• Primary Examiner(s): Phan, Tri H
• Application Number:
  US14/214,545
• Publication Number:
  US 20150263952A1
• Time in Patent Office: 760 Days
• Field of Search: 370/230, 370/235, 370396-399, 370400-401, 370/409, 709/223, 709238-244
• US Class Current: 1/1
• CPC Class Codes: H04L 41/0813 characterised by the conditions triggering a change of settings
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

Some embodiments provide a network controller for managing a logical network implemented across several managed network elements. The logical network includes at least one logical router. The network controller includes an input interface for receiving configuration state for the logical router. The network controller includes a table mapping engine for generating data tuples for distribution to the managed network elements in order for the managed network elements to implement the logical router. The network controller includes a route processing engine for receiving a set of input routes from the table mapping engine based on the configuration state for the logical router, performing a recursive route traversal process to generate a set of output routes, and returning the set of output routes to the table mapping engine. The table mapping engine uses the set of output routes to generate the data tuples for distribution to the plurality of managed network elements.

Claims

1. A network controller for managing a logical network that is implemented across a plurality of managed network elements, the logical network comprising at least one logical router, the network controller comprising:

an input interface for receiving configuration state for the logical router;

a table mapping engine for generating data tuples for distribution to the plurality of managed network elements in order for the managed network elements to implement the logical router; and

a route processing engine for (i) receiving a set of input routes from the table mapping engine based on the configuration state for the logical router, (ii) performing a recursive route traversal process to generate a set of output routes, and (iii) returning the set of output routes to the table mapping engine,

wherein the table mapping engine uses the set of output routes to generate the data tuples for distribution to the plurality of managed network elements.

2. The network controller of claim 1, wherein the table mapping engine is implemented in a first programming language, and the route processing engine is implemented in a second, different programming language.

3. The network controller of claim 2, wherein the first programming language is a table mapping language for mapping input tables to output tables using join operations.

4. The network controller of claim 2, wherein the second programming language is an object-oriented language optimal for recursive processes and error checking.

5. The network controller of claim 1, wherein the network controller further comprises a network state data storage structure that stores (i) the configuration state received by the input interface and (ii) computed state generated by the table mapping engine.

6. The network controller of claim 5, wherein the computed state comprises the data tuples for distribution to the plurality of managed network elements.

7. The network controller of claim 1, wherein the managed network elements comprise managed forwarding elements that operate in virtualization software of a plurality of host machines at which virtual machines that communicate through the logical network are hosted.

8. The network controller of claim 7, wherein the data tuples generated by the table mapping engine comprise flow entries for distribution to the managed forwarding elements, wherein at least one of the flow entries specifies a set of actions to take with a packet when the packet matches a set of conditions.

9. The network controller of claim 8, wherein the set of conditions comprises a range of destination network addresses and the set of actions comprises logically forwarding the packet to an egress port of the logical router.

10. The network controller of claim 1, wherein the managed network elements comprise L3 gateways implemented in virtualized containers at gateway host machines in order to connect the logical network to an external network.

11. The network controller of claim 10, wherein the data tuples generated by the table mapping engine comprise configuration data defining the virtualized container and a routing table for implementation by the virtualized container.

12. The network controller of claim 11, wherein the virtualized container is a namespace and the routing table is one of several elements of a network stack operating in the namespace.

13. The network controller of claim 10, wherein the managed network elements further comprise managed forwarding elements that operate in virtualization software at the gateway host machines in order to forward packets to and receive packets from the virtualized containers.

14. The network controller of claim 13, wherein the data tuples generated by the table mapping engine comprise (i) flow entries for distribution to the managed forwarding elements and (ii) configuration data for distribution to applications that manage the virtualized containers.

15. For a network controller, a method comprising:

receiving configuration state for a logical router managed by the network controller, the configuration state comprising a first set of routes for the logical router;

at a route processing engine of the network controller, performing a recursive route traversal process to generate a second set of routes from the first set of routes; and

at a table mapping engine of the network controller, generating a plurality of data tuples based on the second set of routes, for distribution to a plurality of managed network elements that operate on a plurality of host machines in order to implement the logical router.

16. The method of claim 15, wherein each route in the first set of routes specifies one of (i) a next hop network address, (ii) an output port, and (iii) a drop packet action for packets with network addresses in a network address range for which the route is defined, wherein performing the recursive route traversal process to generate the second set of routes comprises:

when the first set of routes comprises multiple routes for a particular network address range, removing from the second set of routes all routes for the particular network address range other than a highest priority route for the particular network address range;

removing from the second set of routes any route in the first set of routes that specifies an output port that does not exist or that is not in use;

for each route in the first set of routes that specifies a next hop network address, identifying one of an output port and a drop packet action by traversing the first set of routes based on the next hop network address.

17. The method of claim 16, wherein traversing the first set of routes for a first route that specifies a first next hop network address comprises:

identifying a second route for packets with the first next hop network address;

when the second route specifies one of an output port and a drop packet action, using the specified output port or drop packet action for the first route; and

when the second route specifies a second next hop network address, identifying a third route for packets with the second next hop network address.

18. The method of claim 15, wherein the route processing engine is implemented in a first programming language and the table mapping engine is implemented in a second table mapping language.

19. The method of claim 15 further comprising, at the table mapping engine, generating a second plurality of data tuples for a logical switch managed by the network controller based on configuration state defined for the logical switch, without using any data generated by the route processing engine.

20. The method of claim 19, wherein the configuration state is received through an application programming interface of the network controller.

21. The method of claim 19, wherein the network controller is a first network controller, wherein the configuration state is received through an interface with a second network controller.

22. The method of claim 21, wherein the second network controller receives the configuration state through an application programming interface.