Unified replication mechanism for fault-tolerance of state

• US 10,218,564 B2
• Filed: 03/31/2014
• Issued: 02/26/2019
• 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): Moore, Ian N
• Assistant Examiner(s): Le, Brian T
• Application Number:
  US14/231,527
• Publication Number:
  US 20150009804A1
• Time in Patent Office: 1,793 Days
• 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 reduce network traffic between the controllers, fewer tables are replicated to slave controllers, which then recompute the forwarding state of the master controller in order to have a replicate copy of the master controller'"'"'s forwarding state for possible failover. In other embodiments, more tables are replicated to minimize the recomputations and processor load on the slave controller. The network control system of some embodiments performs continuous snapshotting to minimize downtime associated with reaching a fixed point and replicating the state.

Claims

1. A network control system for managing a plurality of forwarding elements that forward data messages in a network, the system comprising:

a first controller instance executing on a first computing device and maintaining forwarding state data that represents a forwarding state of a set of forwarding elements of the plurality of forwarding elements, the first controller instance for (1) managing the set of forwarding elements, and (2) modifying the forwarding state data when the first controller instance receives configuration data that modifies the forwarding state of at least one forwarding element in the set of forwarding elements; and

a second controller instance executing on a second computing device, said second controller instance for (1) receiving from the first controller instance, when the modification of the forwarding state data at the first controller instance reaches a fixed point, backup data comprising only a first portion of the modified forwarding state data, (2) computing a second portion of the modified forwarding state data from the received first portion, and (3) storing the second portion of the modified forwarding state data in order to serve as a backup controller instance to the first controller instance for managing the set of forwarding elements.

2. The network control system of claim 1, wherein the second controller instance receives the backup data from the first controller instance in response to the first controller instance receiving the configuration data that modifies the forwarding state of the set of forwarding elements.

3. The network control system of claim 1, wherein the second controller instance receives the backup data from the first controller instance at periodic intervals.

4. The network control system of claim 1, wherein the forwarding state data comprises a first input set of tables and a second output set of tables, wherein the second output set of tables is generated based on the first input set of tables.

5. The network control system of claim 4, wherein the backup data comprises a copy of the first input set of tables, wherein the second controller instance computes the second portion of the modified forwarding state data by:

calculating a third output set of tables based on the copy of the first input set of tables; and

storing the copy of the first input set of tables and the third output set of tables as a copy of the forwarding state data.

6. The network control system of claim 4, wherein the backup data comprises a copy of the second output set of tables, wherein the second controller instance is further for modifying a third input set of tables based on the copy of the second output set of tables.

7. The network control system of claim 1, wherein the second controller instance is further for assuming management of the set of forwarding elements when the first controller instance fails.

8. The network control system of claim 1, wherein the set of forwarding elements is a first set of forwarding elements and the forwarding state data is a first set of forwarding state data, wherein the second controller instance is further for (1) managing a second set of forwarding elements, and (2) modifying a second set of forwarding state data that represents a forwarding state of the second set of forwarding elements when the second controller instance receives configuration data that modifies the forwarding state of the second set of forwarding elements.

9. The network control system of claim 8 further comprising a third controller instance executing on a third computing device, said third controller instance for (1) receiving backup data comprising only a first portion of the modified second set of forwarding state data, (2) computing a second portion of the modified second set of forwarding state data from the received first portion of the modified second set of forwarding state data, and (3) storing the second portion of the modified second set of forwarding state data in order to serve as a backup controller instance to the second controller instance for managing the second set of forwarding elements.

10. For a first controller instance of a network control system that manages a plurality of forwarding elements forwarding data messages in a network, 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 forwarding state data that represents a forwarding state of a set of forwarding elements of the plurality of forwarding elements;

receiving configuration data that modifies the forwarding state of the set of forwarding elements;

modifying the forwarding state data according to the received configuration data as a single transaction; and

after reaching a fixed point in modifying the forwarding state data and performing a commit operation that signifies completion of the single transaction, sending backup data comprising at least a portion of the modified forwarding state data to a second controller instance of the network control system for the second controller instance to store the portion of the modified forwarding state data.

11. The machine-readable medium of claim 10, wherein the second controller instance is for assuming management of the set of forwarding elements when the first controller instance fails.

12. The machine-readable medium of claim 10, wherein the backup data comprises a log of changes to the forwarding state of the set of forwarding elements.

13. The machine-readable medium of claim 10, wherein the configuration data is received from a database external to the first controller instance.

14. The machine-readable medium of claim 10, wherein the forwarding state data comprises a set of internal configuration tables and a set of output tables, wherein the configuration data comprises a set of changes to the set of output tables, wherein the set of instructions for modifying the forwarding state data comprises sets of instructions for:

performing the set of changes to the set of output tables; and

modifying the set of internal configuration tables based on the set of changes to the set of output tables.

15. For a first controller instance that serves as a backup controller instance to a second controller instance of a network control system for managing a plurality of forwarding elements that forward data messages in a network, a machine-readable medium storing a program that when executed by at least one processing unit of the first controller instance provides fault tolerance for the second controller instance, the program comprising sets of instructions for:

receiving from the second controller instance when a modification of forwarding state data at the second controller instance reaches a fixed point, backup data comprising a first portion of the forwarding state data that represents a forwarding state of a set of forwarding elements of the plurality of forwarding elements;

from the received first portion, computing a second portion of the forwarding state data of the set of forwarding elements; and

storing the first and second portions of the forwarding state data as the backup data for the first controller.

16. The machine-readable medium of claim 15, wherein the first portion of the forwarding state data comprises a set of input tables, the program further comprising a set of instructions for calculating a set of output tables based on the set of input tables, wherein the stored first and second portions of the forwarding state data comprises the set of input tables and the set of output tables.

17. The machine-readable medium of claim 16, wherein the set of instructions for calculating the set of output tables comprises a set of instructions for using a table-mapping engine to perform a set of queries on a first set of records of the set of input tables to generate a second set of records in the set of output tables.

18. The machine-readable medium of claim 15, wherein the program further comprises a set of instructions for replacing at least a portion of the forwarding state data with the backup data.

19. The machine-readable medium of claim 15, wherein the program further comprises a set of instructions for assuming the management of the set of forwarding elements from the second controller instance when the second controller instance fails.

20. The machine-readable medium of claim 15, wherein the backup data comprises configuration data that represents the forwarding state of the set of forwarding elements.

21. The machine-readable medium of claim 20, wherein the set of instructions for computing the second portion further comprises sets of instructions for:

analyzing the first portion of the forwarding state data to identify the configuration data; and

computing the second portion of the forwarding state data based on the identified configuration data.