Unified replication mechanism for fault-tolerance of state

• US 9,432,252 B2
• Filed: 03/31/2014
• Issued: 08/30/2016
• Est. Priority Date: 07/08/2013
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Koponen, Teemu, Shieh, Alan, Ganichev, Igor
• Primary Examiner(s): Jung, Min
• Application Number:
  US14/231,543
• Publication Number:
  US 20150009800A1
• Time in Patent Office: 883 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2005 using redundant communication controllers
• CPC Class Codes: G06F 11/2038 with a single idle spare processing component
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• 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 45/28 using route fault recovery
• CPC Class Codes: H04L 45/586 of virtual routers

Abstract

A network control system that achieves high availability for forwarding state computation within a controller cluster by replicating different levels of table state between controllers of the controller cluster. To build a highly available controller cluster, the tables for storing the forwarding state are replicated across the controllers. In order to take responsibility for a slice, the slave controller of some embodiments performs merging of replicated state on a slice-by-slice basis. The merging is performed in a manner to prevent disruptions to the network state while the slave controller is updated.

Claims

1. For a first controller instance that manages a first set of forwarding elements implementing logical datapath sets of a network control system, a machine-readable medium storing a program executable by at least one processing unit of the first controller instance, the program comprising sets of instructions for:

maintaining a first set of forwarding state data that represents a forwarding state of the first set of forwarding elements;

receiving a second set of forwarding state data that represents a forwarding state of a second set of forwarding elements from a second controller instance;

propagating the first set of forwarding state data to the first set of forwarding elements;

upon detecting a failure of the second controller instance, merging the second set of forwarding state data into the first set of forwarding state data to produce a third set of forwarding state data; and

propagating the third set of forwarding state data to the first and second sets of forwarding elements.

2. The machine-readable medium of claim 1, wherein the set of instructions for maintaining the first set of forwarding state data comprises a set of instructions for calculating the first set of forwarding state data for managing the first set of forwarding elements based on a fourth set of forwarding state data received from a third controller instance.

3. The machine-readable medium of claim 2, wherein the program further comprises a set of instructions for receiving a fifth set of forwarding state data for managing the second set of forwarding elements from the second controller instance.

4. The machine-readable medium of claim 3, wherein the program further comprises a set of instructions for merging the fifth set of forwarding state data into the first and second sets of forwarding state data.

5. The machine-readable medium of claim 1, wherein the program further comprises a set of instructions for storing the second set of forwarding state data separately from the first set of forwarding state data.

6. The machine-readable medium of claim 1, wherein the first set of forwarding elements comprises at least one particular forwarding element of the second set of forwarding elements.

7. The machine-readable medium of claim 6, wherein the set of instructions for merging comprises sets of instructions for:

identifying a first portion of the first set of forwarding data related to the particular forwarding element that corresponds to a second portion of the second set of forwarding data related to the particular forwarding element;

determining whether the first portion is newer than the second portion; and

when the first portion is newer, replacing the second portion with the first portion.

8. The machine-readable medium of claim 1, wherein the logical datapath sets are logical forwarding elements, wherein the first and third sets of forwarding state data are for implementing the logical forwarding elements on a set of physical forwarding elements.

9. The machine-readable medium of claim 1, wherein the first controller instance is a master controller for the first set of forwarding elements and a backup controller for the second set of forwarding elements, and the second controller instance is a master controller for the second set of forwarding elements.

10. For a first controller instance that manages a first set of forwarding elements implementing logical datapath sets of a network control system, a machine-readable medium storing a program executable by at least one processing unit of the first controller instance, the program comprising sets of instructions for:

generating, from a first set of input tuples for a first logical datapath set, a first set of output tuples;

receiving a second set of input tuples for a second logical datapath set from a second controller instance that manages a second set of forwarding elements;

propagating the first set of output tuples to the first set of forwarding elements in order to define a first state for the first logical datapath set, wherein the first state comprises a set of forwarding rules to implement the first logical datapath set;

upon detecting a failure of the second controller instance, generating, from the first and second sets of input tuples, a second set of output tuples while maintaining the first state for the first logical datapath set; and

upon completion of said generating, propagating the second set of output tuples to the first and second sets of forwarding elements in order to define a second state for the first and second logical datapath sets.

11. The machine-readable medium of claim 10, wherein the set of instructions for generating the first set of output tuples for the first logical datapath set comprises a set of instructions for, upon detecting a failure of the second controller instance, disabling changes to a set of head tables, wherein contents of the head tables represent the first state.

12. The machine-readable medium of claim 11, wherein the set of instructions for propagating the second set of output tuples comprises a set of instructions for re-enabling changes to the set of head tables.

13. The machine-readable medium of claim 10, wherein the set of instructions for generating the second set of output tuples comprises a set of instructions for merging the second set of input tuples with the first set of input tuples.

14. The machine-readable medium of claim 13, wherein the set of instructions for merging the second set of input tuples comprises sets of instructions for:

identifying a first portion of the first set of input tuples that corresponds to a second portion of the second set of input tuples;

determining whether the second portion is newer than the first portion; and

when the second portion is newer than the first portion, replacing the first portion of the first set of input tuples with the second portion of the second set of input tuples.

15. The machine-readable medium of claim 10, wherein the second set of input tuples is received from the second controller when processing at the second controller reaches a fixed point.

16. The machine-readable medium of claim 10, wherein the second logical datapath set comprises at least one logical datapath of the first logical datapath set.

17. The machine-readable medium of claim 10, wherein the program further comprises sets of instructions for:

storing the second set of input tuples separately from the first set of input tuples.

18. For a first controller instance that manages a first set of forwarding elements implementing logical datapath sets of a network control system, a method comprising:

generating, from a first set of input tuples for a first logical datapath set, a first set of output tuples;

receiving a second set of input tuples for a second logical datapath set from a second controller instance that manages a second set of forwarding elements;

propagating the first set of output tuples to the first set of forwarding elements in order to define a first state for the first logical datapath set, wherein the first state comprises a set of forwarding rules to implement the first logical datapath set;

upon detecting a failure of the second controller instance, generating, from the first and second sets of input tuples, a second set of output tuples while maintaining the first state for the first logical datapath set; and

upon completion of said generating, propagating the second set of output tuples to the first and second sets of forwarding elements in order to define a second state for the first and second logical datapath sets.

19. The method of claim 18, wherein generating the first set of output tuples for the first logical datapath set comprises, upon detecting a failure of the second controller instance, disabling changes to a set of head tables, wherein contents of the head tables represent the first state.

20. The method of claim 18, wherein generating the second set of output tuples comprises merging the second set of input tuples with the first set of input tuples.