System and method for maintaining a distributed and fault-tolerant state over an information centric network

• US 10,204,013 B2
• Filed: 09/03/2014
• Issued: 02/12/2019
• Est. Priority Date: 09/03/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Scott, Glenn C.
• Primary Examiner(s): Andersen, Kristopher
• Application Number:
  US14/476,264
• Publication Number:
  US 20160062840A1
• Time in Patent Office: 1,623 Days
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A replica management system facilitates maintaining a distributed and fault-tolerant state for a variable over an Information Centric Network (ICN) by replicating the variable across a set of ICN nodes. During operation, a variable-hosting ICN node can receive an Interest that includes a value-updating command for a replica instance of the variable, current values for a set of replicas of the variable, and a new value for the variable. The ICN node can determine, based on the current values for the set of replica variables, whether the current value for the local replica variable is an authoritative value. If so, the ICN node updates the local replica variable to the new value. However, if the current local value is not the authoritative value, the ICN node rolls back a state of the local replica variable to a previous state, and updates the local replica variable to the new value.

Claims

1. A computer-implemented method, comprising:

disseminating in a computer network, by a client device, one or more Interest packets for reading a set of replicas of a variable, wherein the replicas of the variable are hosted by one or more replica servers distinct from the client device, and wherein the client device stores a local copy of the variable;

wherein an Interest packet comprises a value-reading command for reading a replica of the variable, and further comprises a name that includes a routable name prefix which is associated with the variable, wherein the name further includes a unique identifier which identifies the variable or is a logical value associated with the replica server that hosts the variable;

receiving, by the client device from the one or more replica servers, a set of Content Object packets that satisfy the one or more Interest packets, wherein a Content Object packet comprises a same name as the name for a satisfied Interest packet and includes a current value for the variable;

determining, by the client device, whether an authoritative value exists for the variable based on current values in the set of Content Object packets, wherein the current values in the set of Content Object packets received from the one or more replica servers are determined by a respective replica server, and wherein determining whether the authoritative value exists comprises;

determining, by the client device, a largest subset, that exceeds a first pre-determined threshold, of the set of Content Object packets that has a matching value in the current values for the variable;

responsive to determining that the authoritative value does exist, updating, by the client device, the local copy of the variable to the matching value for the variable in the largest subset; and

responsive to determining that the authoritative value does not exist, rolling back, by the client device, a state for the local copy of the variable to a previous state,

wherein when a number of the largest subset is less than the first pre-determined threshold and greater than a second pre-determined subset, the client device updates variable history of another subset of the replicas other than the largest subset, to include the matching value as the authoritative value for the another subset of the replicas.

2. The method of claim 1, wherein responsive to determining that the authoritative value does not exist, the method further comprises rolling back the state of the local copy of the variable without informing a replica server of non-authoritative values across replica variables.

3. The method of claim 1, further comprising updating the set of replicas of the variable, wherein updating the set of replicas of the variable involves:

selecting at least a subset of replica variables to update;

generating a second Interest packet comprising a value-updating command for updating the variable in the subset of replica variables, the current values previously received for the set of replica variables, and a new value for the variable; and

disseminating the second Interest for the variable.

4. The method of claim 3, wherein a number of the at least a subset of replica variables is greater than or equal to a minimum quorum threshold.

5. The method of claim 3, wherein the second Interest packet for the variable includes a name comprising the routable name prefix which is associated with the variable, followed by a name component associated with a respective replica of the variable.

6. The method of claim 5, wherein the routable name prefix is a hierarchically structured variable-length identifier.

7. The method of claim 1, wherein the first pre-determined threshold depends on a maximum expected number of replicas that are offline during an operation, and a maximum number of replicas that are maintained at a malicious node or that are not up to date.

8. One or more non-transitory computer readable storage media encoded with computer readable instructions which, when executed by a processor of a computing device, cause the processor to:

disseminate in a computer network one or more Interest packets for reading a set of replicas of a variable, wherein the replicas of the variable are hosted by one or more replica servers distinct from the computing device, and wherein the computing device stores a local copy of the variable;

wherein an Interest packet comprises a value-reading command for reading a replica of the variable, and further comprises a name that includes a routable name prefix which is associated with the variable, wherein the name further includes a unique identifier which identifies the variable or is a logical value associated with the replica server that hosts the variable;

receive, from the one or more replica servers, a set of Content Object packets that satisfy the one or more Interest packets, wherein a Content Object packet comprises a same name as the name for a satisfied Interest packet and includes a current value for the variable;

determine whether an authoritative value exists for the variable based on current values in the set of Content Object packets, wherein the current values in the set of Content Object packets received from the one or more replica servers are determined by a respective replica server, and wherein the processor is configured to determine whether the authoritative value exists by determining a largest subset, that exceeds a first pre-determined threshold, of the set of Content Object packets that has a matching value in the current values for the variable;

responsive to determining that the authoritative value does exist, update the local copy of the variable to the matching value for the variable in the largest subset; and

responsive to determining that the authoritative value does not exist, roll back a state for the local copy of the variable to a previous state,

wherein when a number of the largest subset is less than the first pre-determined threshold and greater than a second pre-determined subset, the instructions further cause the processor to update variable history of another subset of the replicas other than the largest subset, to include the matching value as the authoritative value for the another subset of the replicas.

9. The non-transitory computer readable storage media of claim 8, wherein responsive to determining that the authoritative value does not exist, the instructions further cause the processor to roll back the state of the local copy of the variable without informing a replica server of non-authoritative values across replica variables.

10. The non-transitory computer readable storage media of claim 8, wherein the instructions further cause the processor to update the set of replicas of the variable by:

selecting at least a subset of replica variables to update;

generating a second Interest packet comprising a value-updating command for updating the variable in the subset of replica variables, the current values previously received for the set of replica variables, and a new value for the variable; and

disseminating the second Interest for the variable.

11. The non-transitory computer readable storage media of claim 10, wherein a number of the at least a subset of replica variables is greater than or equal to a minimum quorum threshold.

12. The non-transitory computer readable storage media of claim 10, wherein the second Interest packet for the variable includes a name comprising the routable name prefix which is associated with the variable, followed by a name component associated with a respective replica of the variable.

13. The non-transitory computer readable storage media of claim 12, wherein the routable name prefix is a hierarchically structured variable-length identifier.

14. The non-transitory computer readable storage media of claim 8, wherein the first pre-determined threshold depends on a maximum expected number of replicas that are offline during an operation, and a maximum number of replicas that are maintained at a malicious node or that are not up to date.

15. An apparatus comprising:

a processor; and

a storage device for storing instructions, wherein the processor is configured to execute the instructions to;

disseminate in a computer network one or more Interest packets for reading a set of replicas of a variable, wherein the replicas of the variable are hosted by one or more replica servers distinct from the apparatus, and wherein the apparatus stores a local copy of the variable;

wherein an Interest packet comprises a value-reading command for reading a replica of the variable, and further comprises a name that includes a routable name prefix which is associated with the variable, wherein the name further includes a unique identifier which identifies the variable or is a logical value associated with the replica server that hosts the variable;

receive, from the one or more replica servers, a set of Content Object packets that satisfy the one or more Interest packets, wherein a Content Object packet comprises a same name as the name for a satisfied Interest packet and includes a current value for the variable;

determine whether an authoritative value exists for the variable based on current values in the set of Content Object packets, wherein the current values in the set of Content Object packets received from the one or more replica servers are determined by a respective replica server, and wherein the processor is configured to determine whether the authoritative value exists by determining a largest subset, that exceeds a first pre-determined threshold, of the set of Content Object packets that has a matching value in the current values for the variable;

responsive to determining that the authoritative value does exist, update the local copy of the variable to the matching value for the variable in the largest subset; and

responsive to determining that the authoritative value does not exist, roll back a state for the local copy of the variable to a previous state,

wherein when a number of the largest subset is less than the first pre-determined threshold and greater than a second pre-determined subset, the processor is configured to update variable history of another subset of the replicas other than the largest subset, to include the matching value as the authoritative value for the another subset of the replicas.

16. The apparatus of claim 15, wherein responsive to determining that the authoritative value does not exist, the processor is configured to roll back the state of the local copy of the variable without informing a replica server of non-authoritative values across replica variables.

17. The apparatus of claim 15, wherein the processor is further configured to update the set of replicas of the variable by:

selecting at least a subset of replica variables to update;

generating a second Interest packet comprising a value-updating command for updating the variable in the subset of replica variables, the current values previously received for the set of replica variables, and a new value for the variable; and

disseminating the second Interest for the variable.

18. The apparatus of claim 17, wherein a number of the at least a subset of replica variables is greater than or equal to a minimum quorum threshold.

19. The apparatus of claim 17, wherein the second Interest packet for the variable includes a name comprising the routable name prefix which is associated with the variable, followed by a name component associated with a respective replica of the variable.

20. The apparatus of claim 15, wherein the first pre-determined threshold depends on a maximum expected number of replicas that are offline during an operation, and a maximum number of replicas that are maintained at a malicious node or that are not up to date.