# US 2019/0173744 A1 · Unified replication mechanism for fault-tolerance of state > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0173744 A1 - Document ID: US20190173744A1 - Status: Published application - Kind: A1 - Application number: 16/270,588 - Filed: 2019-02-07 - Published: 2019-06-06 - Earliest claimed: 2013-07-08 - Assignees: Nicira, Inc. - Applicants: Nicira, Inc. - Inventors: Teemu Koponen; Alan Shieh; Igor Ganichev - Web page: https://patentgrep.com/patent/US20190173744A1 ## CPC - H04L 41/0695: the faulty arrangement being the maintenance, administration or management system - G06F 11/2005: {using redundant communication controllers} - G06F 11/2038: {with a single idle spare processing component} - G06F 11/2097: {maintaining the standby controller/processing unit updated (initialisation or re-synchronisation thereof G06F11/1658 and subgroups)} - H04L 41/0668: by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure - H04L 45/28: using route fault recovery - H04L 45/586: of virtual routers - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 ### Claim at position 1 1-22. (canceled) ### Claim 23 For a first controller instance of a network control system that manages a set of forwarding elements implementing logical datapath sets, 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: receiving, at a first table, a set of input records that indicate changes to a forwarding state of the network control system, wherein each input record triggers a plurality of modifications to a plurality of tables for storing a plurality of tuples used for defining the forwarding state; for each input record: performing the plurality of modifications to the plurality of tables; and logging the modifications for each table in the plurality of tables; and based on resources of the first controller instance, pruning the logged modifications for a subset of the tables from a log; and storing a snapshot for each table of the plurality of tables that is not in the subset of tables. ### Claim 24 (depends on 23) The machine-readable medium of claim 23, wherein the plurality of modifications comprises a first set of modifications triggered by the input record and a second set of modifications triggered by the first set of modifications, wherein the first set of modifications are at a first level of a hierarchy and the second set of modifications are at a second lower level of the hierarchy. ### Claim 25 (depends on 24) The machine-readable medium of claim 24, wherein the set of instructions for pruning comprises a set of instructions for removing modifications at the lowest level of the hierarchy. ### Claim 26 (depends on 23) The machine-readable medium of claim 23, wherein the set of instructions for pruning is performed when available memory resources of the first controller instance reach a threshold value. ### Claim 27 (depends on 23) The machine-readable medium of claim 23, wherein the program further comprises a set of instructions for replicating the pruned log and the stored snapshots to a second controller instance. ### Claim 28 (depends on 27) The machine-readable medium of claim 27, wherein the first controller instance replicates the pruned log and the stored snapshots to the second controller instance at periodic intervals. ### Claim 29 (depends on 27) The network control system of claim 27, wherein the second controller instance is for assuming management of the set of forwarding elements when the first controller instance fails. ### Claim 30 (depends on 27) The machine-readable medium of claim 27, wherein the replicated log and snapshots are for reproducing the pruned tables at the second controller instance. ### Claim 31 A method for implementing logical datapath sets and a machine-readable medium storing a program executable by at least one processing unit of the first controller instance, the method comprising: receiving, at a first table, a set of input records that indicate changes to a forwarding state of the network control system, wherein each input record triggers a plurality of modifications to a plurality of tables for storing a plurality of tuples used for defining the forwarding state; for each input record: performing the plurality of modifications to the plurality of tables; and logging the modifications for each table in the plurality of tables; and based on resources of the first controller instance, pruning the logged modifications for a subset of the tables from a log; and storing a snapshot for each table of the plurality of tables that is not in the subset of tables. ### Claim 32 (depends on 31) The method of claim 31, wherein the plurality of modifications comprises a first set of modifications triggered by the input record and a second set of modifications triggered by the first set of modifications, wherein the first set of modifications are at a first level of a hierarchy and the second set of modifications are at a second lower level of the hierarchy. ### Claim 33 (depends on 32) The method of claim 32, wherein pruning comprises removing modifications at the lowest level of the hierarchy. ### Claim 34 (depends on 31) The method of claim 31, wherein pruning is performed when available memory resources of the first controller instance reach a threshold value. ### Claim 35 (depends on 31) The method of claim 31 further comprising replicating the pruned log and the stored snapshots to a second controller instance. ### Claim 36 (depends on 35) The method of claim 35, wherein the first controller instance replicates the pruned log and the stored snapshots to the second controller instance at periodic intervals. ### Claim 37 (depends on 35) The method of claim 35, wherein the second controller instance is for assuming management of the set of forwarding elements when the first controller instance fails. ### Claim 38 (depends on 35) The method of claim 35, wherein the replicated log and snapshots are for reproducing the pruned tables at the second controller instance.