REDUCTION OF NETWORK CHURN BASED ON DIFFERENCES IN INPUT STATE

• US 20160294604A1
• Filed: 07/30/2015
• Published: 10/06/2016
• Est. Priority Date: 04/06/2015
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Wang, Su, Shakimov, Amre, Neginhal, Srinivas, Chanda, Anupam, Thakkar, Pankaj
• Granted Patent: US 9,967,134 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 41/0695 the faulty arrangement being the maintenance, administration or management system
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

Some embodiments provide a network control system with techniques for handling failover of network controllers with minimal churn in the network state distributed to the forwarding elements of the network. Specifically, in some embodiments, the local controller designates a waiting period before computing output network state data entries based on the new version of the input network state data entries. Alternatively, or conjunctively, the local controller of some embodiments calculates the changes between the new version of input state data entries and its stored existing version of the input state data entries, and only generates new output network state data entries based on the calculated changes, in order to minimize unnecessary recalculations of the output network state data entries. The new output network state data entries may then be used by the local controller to provision its managed forwarding element.

Claims

1. For a first network controller of a network, a method comprising:

generating a first plurality of output network state data entries from a first plurality of input network state data entries received from a second network controller, the first plurality of input network state data entries for defining a network state and the first plurality of output network state data entries for implementing the first network state;

upon determining that a connection to the second network controller has been lost, marking the first plurality of input network state data entries for deletion;

upon receiving a second plurality of input network state data entries that defines a second network state from a third network controller, unmarking a first set of input network state data entries of the marked first plurality of input network state data entries, wherein each entry of the first set of input network state data entries corresponds to an entry in the second plurality of input network state data entries; and

generating a second plurality of output network state data entries comprising (i) a first set of output network state data entries corresponding to the unmarked first set of input network state data entries and (ii) a second set of new output network state data entries generated from a second set of input network state data entries of the second plurality of input network state data entries that do not have a corresponding entry in the first plurality of input network state data entries, the second plurality of output network state data entries for implementing the second network state.

2. The method of claim 1, wherein the input network state data entries comprise data tuples for defining forwarding behaviors for a logical forwarding element to be implemented by a physical forwarding element managed by the first network controller.

3. The method of claim 1 further comprising, after unmarking the first set of input network state data entries, deleting the remaining marked input network state data entries and output network state data entries generated from the marked input network state data entries.

4. The method of claim 1, wherein generating the first and second pluralities of output network state data entries comprises:

storing the input network state data entries in a set of input tables; and

using a table mapping engine to process the input network state data entries in the set of input tables to create output network state data entries stored in a set of output tables.

5. The method of claim 4, wherein processing the input data entries in the set of input tables comprises performing a series of table joins on the set of input tables to generate the set of output tables.

6. The method of claim 4, wherein marking the first plurality of input network state data entries for deletion comprises storing a set of records in a set of shadow tables, wherein the set of records identify state data entries to be deleted from the sets of input and output tables.

7. The method of claim 6, wherein unmarking the first set of input network state data entries comprises removing records from the set of shadow tables that correspond with the first set of input network state data entries.

8. The method of claim 6, wherein generating the second plurality of output network state data entries from the second set of input network state data entries comprises:

adding records to the set of shadow tables for adding the second set of input network state data entries to the set of input tables;

waiting for a period of time before adding the second set of input network state data entries to the set of input tables; and

generating output network state data entries in the set of output tables based on the added second set of input network state data entries in the set of input tables.

9. The method of claim 1 further comprising propagating the second plurality of output network state data entries to a set of managed forwarding elements, wherein the second plurality of output network state data entries are for defining forwarding behaviors of the managed forwarding elements to implement the second network state, wherein the forwarding behaviors control the forwarding of data packets between a plurality of machines of the network.

10. The method of claim 9, wherein generating the second plurality of output network state data entries comprises customizing the second plurality of output network state data entries in a format understandable by the set of managed forwarding elements.

11. The method of claim 9, wherein the set of managed forwarding elements is a virtual switch that executes on a same computing device as the first network controller.

12. The method of claim 11, wherein the plurality of machines comprises at least one virtual machine hosted on the computing device.

13. The method of claim 1, wherein the first network controller is a local controller that operates on a same computing device as a managed forwarding element provisioned by the first network controller with the output network state data entries, and the second network controller is a centralized network controller that manages a logical network.

14. The method of claim 13, wherein the centralized network controller provides input network state data entries defining the logical network to a plurality of other local controllers operating on computing devices with other managed forwarding elements.

15. A non-transitory machine readable medium storing a program which when executed by at least one processing unit of a first controller maintains a consistent network state, the program comprising sets of instructions for:

generating a first plurality of output network state data entries from a first plurality of input network state data entries received from a second network controller, the first plurality of input network state data entries for defining a network state and the first plurality of output network state data entries for implementing the first network state;

upon determining that a connection to the second network controller has been lost, marking the first plurality of input network state data entries for deletion;

upon receiving a second plurality of input network state data entries that defines a second network state from a third network controller, unmarking a first set of input network state data entries of the marked first plurality of input network state data entries, wherein each entry of the first set of input network state data entries corresponds to an entry in the second plurality of input network state data entries; and

generating a second plurality of output network state data entries comprising (i) a first set of output network state data entries corresponding to the unmarked first set of input network state data entries and (ii) a second set of new output network state data entries generated from a second set of input network state data entries of the second plurality of input network state data entries that do not have a corresponding entry in the first plurality of input network state data entries, the second plurality of output network state data entries for implementing the second network state.

16. The non-transitory machine readable medium of claim 15, wherein the input network state data entries comprise data tuples for defining forwarding behaviors for a logical forwarding element to be implemented by a physical forwarding element managed by the first network controller.

17. The non-transitory machine readable medium of claim 15, wherein the program further comprises a set of instructions for deleting, after unmarking the first set of input network state data entries, the remaining marked input network state data entries and output network state data entries generated from the marked input network state data entries.

18. The non-transitory machine readable medium of claim 15, wherein the set of instructions for generating the first and second pluralities of output network state data entries comprises sets of instructions for:

storing the input network state data entries in a set of input tables; and

using a table mapping engine to a series of table joins on the set of input tables to generate the set of output tables.

19. The non-transitory machine readable medium of claim 18, wherein the set of instructions for marking the first plurality of input network state data entries for deletion comprises a set of instructions for storing a set of records in a set of shadow tables, wherein the set of records identify state data entries to be deleted from the sets of input and output tables.

20. The non-transitory machine readable medium of claim 19, wherein the set of instructions for unmarking the first set of input network state data entries comprises a set of instructions for removing records from the set of shadow tables that correspond with the first set of input network state data entries.

21. The non-transitory machine readable medium of claim 19, wherein the set of instructions for generating the second plurality of output network state data entries from the second set of input network state data entries comprises sets of instructions for:

adding records to the set of shadow tables for adding the second set of input network state data entries to the set of input tables;

waiting for a period of time before adding the second set of input network state data entries to the set of input tables; and

generating output network state data entries in the set of output tables based on the added second set of input network state data entries in the set of input tables.

22. The non-transitory machine readable medium of claim 15, wherein the program further comprises sets of instructions for:

propagating the second plurality of output network state data entries to a set of managed forwarding elements; and

customizing the second plurality of output network state data entries in a format understandable by the set of managed forwarding elements, wherein the second plurality of output network state data entries are for defining forwarding behaviors of the managed forwarding elements to implement the second network state, wherein the forwarding behaviors control the forwarding of data packets between a plurality of machines of the network.

23. The non-transitory machine readable medium of claim 15, wherein the first network controller is a local controller that operates on a same computing device as a managed forwarding element provisioned by the first network controller with the output network state data entries, and the second network controller is a centralized network controller that manages a logical network.

24. The non-transitory machine readable medium of claim 24, wherein the centralized network controller provides input network state data entries defining the logical network to a plurality of other local controllers operating on computing devices with other managed forwarding elements.