Using transactions to minimize churn in a distributed network control system

• US 9,843,476 B2
• Filed: 04/18/2013
• Issued: 12/12/2017
• Est. Priority Date: 04/18/2012
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Koponen, Teemu, Lambeth, W. Andrew, Thakkar, Pankaj
• Primary Examiner(s): Eskandarnia, Arvin
• Application Number:
  US14/348,886
• Publication Number:
  US 20140351432A1
• Time in Patent Office: 1,699 Days
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 41/08 Configuration management of networks or network elements address allocation H04L61/50
• CPC Class Codes: H04L 41/0803 Configuration setting
• 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/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 43/0823 Errors, e.g. transmission errors
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 45/72 Routing based on the source address
• CPC Class Codes: H04L 49/70 Virtual switches

Abstract

A particular network controller receives a first set of inputs from the first controller and a second set of inputs from the second controller. The particular controller then starts to compute a set of outputs using the first set of inputs. After a failure of the first controller, the particular controller receives a third set of inputs from the second controller. The third set of inputs and the first or second set of inputs makes up a group of inputs for being processed together and separately from another group of inputs. The particular controller then receives an indicator from the second controller, which indicates that all inputs of the group of inputs have arrived at the particular controller. After receiving the indicator and after computing the set of outputs completely, the particular controller sends the set of outputs to a fourth controller or to a managed forwarding element.

Claims

1. For a particular controller for managing a network by generating configuration data for a plurality of managed forwarding elements that forward data to each other in the network, a method for computing sets of managed forwarding element configuration outputs using corresponding sets of configuration inputs from first and second controllers, the method comprising:

receiving a first set of inputs that are part of a particular transaction relating to a logical forwarding element that is implemented by the plurality of managed forwarding elements from the first controller and a second set of inputs that are redundant of the first set of inputs and are part of the particular transaction relating to the logical forwarding element from the second controller, wherein the inputs of the particular transaction are (i) for processing together to compute a set of managed forwarding element configuration output changes and (ii) for processing separately from other, separate transactions processed by the particular controller that relate to other logical forwarding elements;

storing the second set of inputs while computing a first portion of the set of managed forwarding element configuration output changes using the first set of inputs;

after a failure of the first controller, receiving a third set of inputs from the second controller, the third set of inputs comprising inputs that are part of the particular transaction relating to the logical forwarding element and are not in the second set of inputs;

while maintaining the first portion of the set of managed forwarding element configuration output changes, computing a second portion of the set of managed forwarding element configuration output changes using the second and third sets of inputs; and

after computing the complete set of managed forwarding element configuration output changes, outputting the set of managed forwarding element configuration output changes for distribution to a set of managed forwarding elements.

2. The method of claim 1,

wherein at least one input in the second set of inputs is duplicative of an input in the first set of inputs,

wherein computing the second portion of the set of managed forwarding element configuration output changes comprises computing the second portion of the set of managed forwarding element configuration output changes such that the duplicative input does not affect the first portion of the set of managed forwarding element configuration output changes.

3. The method of claim 1 further comprising receiving an indicator from the second controller, the indicator indicating that the last input in the third set of inputs of the particular transaction has been sent by the second controller and thereby indicating that all inputs of the particular transaction have been received at the controller, wherein the indicator is part of an input in the third set of inputs.

4. The method of claim 1, wherein the inputs of the first, second and third sets of inputs are data tuples.

5. The method of claim 1, wherein the managed forwarding element configuration output changes define forwarding behaviors of the managed forwarding elements.

6. A non-transitory machine readable medium of a controller computer storing a program for a recipient network controller which when executed by a set of processing units computes forwarding state configuration data for a set of managed forwarding elements using inputs from a set of source controllers, the program comprising sets of instructions for:

receiving, from the set of source controllers, a plurality of groups of inputs that define a set of logical forwarding elements, each group of inputs for being processed together by the recipient network controller and separately from the processing of other groups of inputs, wherein the processing of each group of inputs by the recipient network controller generates a corresponding set of managed forwarding element configuration outputs used by a set of managed forwarding elements to implement the set of logical forwarding elements;

generating sets of managed forwarding element configuration outputs corresponding to each group of received inputs;

when at least two of the groups of inputs meet a certain condition, sending the corresponding sets of outputs to the set of managed forwarding elements as a single transaction to configure the managed forwarding elements to implement the set of logical forwarding elements; and

when no combination of the groups of inputs meets the certain condition, sending the corresponding sets of outputs to the set of managed forwarding elements as separate transactions to configure the managed forwarding elements to implement the set of logical forwarding elements.

7. The non-transitory machine readable medium of claim 6, wherein the certain condition comprises a number of groups of inputs stored in a storage structure.

8. The non-transitory machine readable medium of claim 6, wherein the certain condition comprises the at least two groups of inputs having a specific amount of data.

9. The non-transitory machine readable medium of claim 6, wherein the certain condition comprises an amount of time elapsed after previously sending outputs to the set of managed forwarding elements.

10. The non-transitory machine readable medium of claim 6, wherein the set of managed forwarding elements that receives the sets of outputs treats the sets of outputs as a group of inputs for being processed together and separately from other groups of inputs.

11. A non-transitory machine readable medium for storing a first controller program which when executed by at least one processing unit manages a network comprising a plurality of managed forwarding elements that forward data in the network, the first controller comprising sets of instructions for:

for a first request for information about a logical forwarding element that logically connects a set of end machines, identifying a set of second controllers that manage forwarding behaviors of a set of managed forwarding elements that implement the logical forwarding element;

generating a set of second requests for information about the set of managed forwarding elements based on the first request;

distributing the set of second requests to the set of second controllers;

receiving, from each controller of the set of second controllers, a response to the second request of the set of second requests sent to the second controller, the response including at least a portion of the requested information from the second requests; and

when the set of responses meets certain criteria, combining the responses received from the set of second controllers to generate a combined response to the first request providing information about the logical forwarding element and sending the combined response to a source of the first request.

12. The non-transitory machine readable medium of claim 11, wherein the set of second requests meets the certain criteria when the set of second requests comprises at least a specified amount of data.

13. The non-transitory machine readable medium of claim 11, wherein the certain criteria comprises an amount of time having elapsed after distributing the set of second requests to the set of second controllers.

14. The non-transitory machine readable medium of claim 11, wherein the first request is expressed in terms of names of logical constructs of the logical forwarding element.

15. The non-transitory machine readable medium of claim 14,

wherein the set of instructions for generating the set of second requests comprises a set of instructions for translating the first request into a set of universal physical requests that is expressed in terms of universal names of physical constructs of the set of managed forwarding elements,

wherein the set of instructions for distributing the set of second requests comprises a set of instructions for distributing the set of universal physical requests.

16. The non-transitory machine readable medium of claim 15, wherein the set of second controllers subsequently translate the set of universal physical requests into customized physical requests which are expressed in terms of customized names of the physical constructs of the set of managed forwarding elements.

17. The non-transitory machine readable medium of claim 16, wherein each universal physical request comprises a set of data tuples.

18. For a first controller for managing a network by generating configuration data for a plurality of managed forwarding elements that forward data in the network, a method for computing forwarding state to send to a second controller, the method comprising:

receiving a plurality of input data tuples defining a set of logical forwarding elements;

generating, from the input data tuples, output forwarding state data tuples that define forwarding behaviors of the set of managed forwarding elements to implement the set of logical forwarding elements;

sending each output data tuple to the second controller as the output tuple is generated; and

upon determining that a first set of output data tuples for a set of input data tuples has been generated and sent to the second controller, sending an indicator, which indicates an end of the set of output data tuples, to the second controller,

wherein the second controller generates a second set of output data tuples from the first set of output data tuples by processing the first set of output data tuples separately from other sets of output data tuples received by the second controller,

wherein the second controller generates its own indicator for the second set of output data tuples only after receiving the indicator from the first controller.

19. The method of claim 18, wherein the indicator is sent as part of an output data tuple that is the last output data tuple generated of the first set of output data tuples.

20. The method of claim 18, wherein the indicator is also a data tuple.

21. The method of claim 18, wherein when the second controller receives the indicator, all of the output data tuples in the first set of output data tuples are deemed to have arrived at the second controller.

22. The method of claim 18, wherein the indicator also indicates that all input data tuples of the set of input data tuples have been used to generate the first set of output data tuples.