Arrangement in a network node for secure storage and retrieval of encoded data distributed among multiple network nodes

• US 20050273686A1
• Filed: 06/03/2004
• Published: 12/08/2005
• Est. Priority Date: 06/03/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Toebes, John, Turner, Bryan C.
• Granted Patent: US 7,203,871 B2
• Time in Patent Office: Days
• US Class Current: 714/752
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• 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/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• 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
• CPC Class Codes: H04Q 2213/13034 A/D conversion, code compression/expansion
• CPC Class Codes: H04Q 2213/13174 Data transmission, file transfer
• CPC Class Codes: H04Q 2213/13215 Code checking, CRC

Abstract

Data is stored using multiple selected network nodes in a network based on encoding of the data into multiple distinct encoded data units according to a prescribed encoding operation. The secure encoding operation generates a first prescribed number of encoded data units, whereas merely a second prescribed number of the encoded data units are necessary for recovery of the original data, the second prescribed number being less than the first prescribed number. The encoded data units are distributed among selected network nodes in a network, where any one network node receives less than the second prescribed number to ensure security. A requesting node recovers the original data by requesting the second prescribed number of encoded data units from among the network nodes having stored the respective encoded data units.

Claims

1. A method in a network node configured for connection to a network, the method comprising:

encoding an unencoded data unit into a first prescribed number of encoded data units according to a prescribed encoding operation, the prescribed encoding operation causing each encoded data unit to be distinct from other ones of the encoded data units, the prescribed encoding operation further requiring at least a second prescribed number of the encoded data units for recovery of the unencoded data unit, the second prescribed number being less than the first prescribed number; and

distributing the first prescribed number of encoded data units among selected network nodes for storage of the encoded data units in the network, the distributing including selecting the selected network nodes based on identified attributes of the unencoded data unit.

2. The method of claim 1, wherein the encoding includes executing Reed Solomon encoding as the prescribed encoding operation.

3. The method of claim 2, wherein the first prescribed number equals at least seven (7) and the second prescribed number equals at least four (4).

4. The method of claim 2, wherein the distributing includes selecting the selected network nodes, from among available network nodes, based on a prescribed selection attribute.

5. The method of claim 4, wherein the prescribed selection attribute includes at least one of random selection, distance from the corresponding selected network node, and reliability of the corresponding selected network node.

6. The method of claim 4, wherein the selecting includes generating location identifiers for identifying respective encoded data units and the respective selected network nodes based on a prescribed function and applying, as the prescribed selection attribute, an identifier of the unencoded data unit.

7. The method of claim 2, wherein the distributing includes:

generating a copy of at least one of the encoded data units; and

sending the copy of the corresponding at least one encoded data unit to another selected network node distinct from the selected network node having received the corresponding at least one encoded data unit.

8. The method of claim 2, further comprising providing at least one identifier to another network node, distinct from the selected network nodes, for enabling identification and retrieval by the another network node of at least the second prescribed number of encoded data units.

9. The method of claim 8, wherein the at least one identifier includes storage addresses for the respective encoded data units stored in the network.

10. The method of claim 9, wherein the providing includes supplying the storage addresses in response to a request for access to the unencoded data unit from a requesting network node.

11. The method of claim 9, wherein the another network node is a prescribed shared directory configured for supplying groups of the storage addresses for recovery of respective unencoded data units by requesting network nodes.

12. The method of claim 8, wherein the providing includes supplying the identifier in response to a request for access to the unencoded data unit from the another network node.

13. The method of claim 1, wherein each encoded data unit is secure and unreadable relative to the unencoded data unit.

14. The method of claim 1, wherein the distributing including supplying less than the second prescribed number to any one of the network nodes

15. A method in a network node configured for connection to a network, the method comprising:

requesting from among network nodes a first prescribed number of encoded data units, the encoded data units having been generated based on encoding an unencoded data unit into a second prescribed number of the encoded data units according to a prescribed encoding operation, the first prescribed number of encoded data units representing a minimum number of the encoded data units required for recovery of the unencoded data unit, wherein each encoded data unit is distinct from other ones of the encoded data units, the second prescribed number greater than the first prescribed number;

obtaining the first prescribed number of encoded data units from the network, the obtaining including receiving less than the first prescribed number of encoded data units from any network node that supplies any one of the encoded data units; and

recovering the unencoded data unit based on decoding the obtained first prescribed number of encoded data units.

16. The method of claim 15, wherein the requesting includes determining an identifier for one of the unencoded data unit and stored locations of the second prescribed number of the encoded data units.

17. The method of claim 16, wherein the determining includes sending a request for the identifier to a source network node having generated the encoded data units.

18. The method of claim 17, wherein the determining further includes determining the stored locations based on applying a prescribed function to the identifier.

19. The method of claim 16, wherein the requesting includes sending a query for the stored locations to a prescribed shared directory configured for supplying storage addresses identifying the respective stored locations of the encoded data units.

20. The method of claim 15, wherein the requesting includes:

sending requests for each of the first prescribed number of the encoded data units among the plurality of network nodes; and

sending a second request for another one of the encoded data units to an alternate network node distinct from the plurality of network nodes.

21. The method of claim 20, wherein the sending a second request is based on one of:

a determined absence of receiving one of encoded data units having been requested from among the plurality of network nodes;

determining one of the encoded data units has been corrupted; and

adding integrity to the recovering of the unencoded data unit.

22. The method of claim 21, wherein the prescribed encoding operation is Reed Solomon encoding, the recovering including executing Reed Solomon-based decoding of the first prescribed number of encoded data units to recover the unencoded data unit, the another one of the encoded data units used for one of adding integrity to the recovering of the unencoded data unit, and substituting the another one of the encoded data units in place of the one encoded data unit having been corrupted.

23. The method of claim 15, wherein the prescribed encoding operation is Reed Solomon encoding, the recovering including executing Reed Solomon-based decoding of the first prescribed number of encoded data units to recover the unencoded data unit.

24. The method of claim 23, wherein the first prescribed number equals at least (4) and the second prescribed number equals at least seven (7).

25. A computer readable medium having stored thereon sequences of instructions for secure storage by a network node of an unencoded data unit in a network, the sequences of instructions including instructions for:

encoding the unencoded data unit into a first prescribed number of encoded data units according to a prescribed encoding operation, the prescribed encoding operation causing each encoded data unit to be distinct from other ones of the encoded data units, the prescribed encoding operation further requiring at least a second prescribed number of the encoded data units for recovery of the unencoded data unit, the second prescribed number being less than the first prescribed number; and

distributing the first prescribed number of encoded data units among selected network nodes for storage of the encoded data units in the network, the distributing including selecting the selected network nodes based on identified attributes of the unencoded data unit.

26. The medium of claim 25, wherein the encoding includes executing Reed Solomon encoding as the prescribed encoding operation.

27. The medium of claim 26, wherein the first prescribed number equals at least seven (7) and the second prescribed number equals at least four (4).

28. The medium of claim 26, wherein the distributing includes selecting the selected network nodes, from among available network nodes, based on a prescribed selection attribute.

29. The medium of claim 28, wherein the prescribed selection attribute includes at least one of random selection, distance from the corresponding selected network node, and reliability of the corresponding selected network node.

30. The medium of claim 28, wherein the selecting includes generating location identifiers for identifying respective encoded data units and the respective selected network nodes based on a prescribed function and applying, as the prescribed selection attribute, an identifier of the unencoded data unit.

31. The medium of claim 26, wherein the distributing includes:

generating a copy of at least one of the encoded data units; and

sending the copy of the corresponding at least one encoded data unit to another selected network node distinct from the selected network node having received the corresponding at least one encoded data unit.

32. The medium of claim 26, further comprising instructions for providing at least one identifier to another network node, distinct from the selected network nodes, for enabling identification and retrieval by the another network node of at least the second prescribed number of encoded data units.

33. The medium of claim 32, wherein the at least one identifier includes storage addresses for the respective encoded data units stored in the network.

34. The medium of claim 33, wherein the providing includes supplying the storage addresses in response to a request for access to the unencoded data unit from a requesting network node.

35. The medium of claim 33, wherein the another network node is a prescribed shared directory configured for supplying groups of the storage addresses for recovery of respective unencoded data units by requesting network nodes.

36. The medium of claim 32, wherein the providing includes supplying the identifier in response to a request for access to the unencoded data unit from the another network node.

37. The medium of claim 25, wherein each encoded data unit is secure and unreadable relative to the unencoded data unit.

38. The medium of claim 25, wherein the distributing includes supplying less than the second prescribed number to any one of the network nodes.

39. A computer readable medium having stored thereon sequences of instructions for recovering an unencoded data unit by a network node configured for connection to a network, the sequences of instructions including instructions for:

requesting from among network nodes a first prescribed number of encoded data units, the encoded data units having been generated based on encoding an unencoded data unit into a second prescribed number of the encoded data units according to a prescribed encoding operation, the first prescribed number of encoded data units representing a minimum number of the encoded data units required for recovery of the unencoded data unit, wherein each encoded data unit is distinct from other ones of the encoded data units, the second prescribed number greater than the first prescribed number;

obtaining the first prescribed number of encoded data units from the network, the obtaining including receiving less than the first prescribed number of encoded data units from any network node that supplies any one of the encoded data units; and

recovering the unencoded data unit based on decoding the obtained first prescribed number of encoded data units.

40. The medium of claim 39, wherein the requesting includes determining an identifier for one of the unencoded data unit and stored locations of the second prescribed number of the encoded data units.

41. The medium of claim 40, wherein the determining includes sending a request for the identifier to a source network node having generated the encoded data units.

42. The medium of claim 41, wherein the determining further includes determining the stored locations based on applying a prescribed function to the identifier.

43. The medium of claim 40, wherein the requesting includes sending a query for the stored locations to a prescribed shared directory configured for supplying storage addresses identifying the respective stored locations of the encoded data units.

44. The medium of claim 39, wherein the requesting includes:

sending requests for each of the first prescribed number of the encoded data units among the plurality of network nodes; and

sending a second request for another one of the encoded data units to an alternate network node distinct from the plurality of network nodes.

45. The medium of claim 44, wherein the sending a second request is based on one of:

a determined absence of receiving one of encoded data units having been requested from among the plurality of network nodes;

determining one of the encoded data units has been corrupted; and

adding integrity to the recovering of the unencoded data unit.

46. The medium of claim 45, wherein the prescribed encoding operation is Reed Solomon encoding, the recovering including executing Reed Solomon-based decoding of the first prescribed number of encoded data units to recover the unencoded data unit, the another one of the encoded data units used for one of adding integrity to the recovering of the unencoded data unit, and substituting the another one of the encoded data units in place of the one encoded data unit having been corrupted.

47. The medium of claim 39, wherein the prescribed encoding operation is Reed Solomon encoding, the recovering including executing Reed Solomon-based decoding of the first prescribed number of encoded data units to recover the unencoded data unit.

48. The medium of claim 47, wherein the first prescribed number equals at least (4) and the second prescribed number equals at least seven (7).

49. A network node configured for connection to a network, the network node comprising:

means for encoding an unencoded data unit into a first prescribed number of encoded data units according to a prescribed encoding operation, the prescribed encoding operation causing each encoded data unit to be distinct from other ones of the encoded data units, the prescribed encoding operation further requiring at least a second prescribed number of the encoded data units for recovery of the unencoded data unit, the second prescribed number being less than the first prescribed number; and

means for distributing the first prescribed number of encoded data units among selected network nodes for storage of the encoded data units in the network, the distributing including selecting the selected network nodes based on identified attributes of the unencoded data unit.

50. The network node of claim 49, wherein the means for encoding is configured for executing Reed Solomon encoding as the prescribed encoding operation.

51. The network node of claim 50, wherein the first prescribed number equals at least seven (7) and the second prescribed number equals at least four (4).

52. The network node of claim 50, wherein the means for distributing is configured for selecting the selected network nodes, from among available network nodes, based on a prescribed selection attribute.

53. The network node of claim 52, wherein the prescribed selection attribute includes at least one of random selection, distance from the corresponding selected network node, and reliability of the corresponding selected network node.

54. The network node of claim 52, wherein the means for selecting is configured for generating location identifiers for identifying respective encoded data units and the respective selected network nodes based on a prescribed function and applying, as the prescribed selection attribute, an identifier of the unencoded data unit.

55. The network node of claim 50, wherein the distributing means is configured for:

generating a copy of at least one of the encoded data units; and

sending the copy of the corresponding at least one encoded data unit to another selected network node distinct from the selected network node having received the corresponding at least one encoded data unit.

56. The network node of claim 50, wherein the distributing means is configured for providing at least one identifier to another network node, distinct from the selected network nodes, for enabling identification and retrieval by the another network node of at least the second prescribed number of encoded data units.

57. The network node of claim 56, wherein the at least one identifier includes storage addresses for the respective encoded data units stored in the network.

58. The network node of claim 57, wherein the means for distributing is configured for supplying the storage addresses in response to a request for access to the unencoded data unit from a requesting network node.

59. The network node of claim 57, wherein the another network node is a prescribed shared directory configured for supplying groups of the storage addresses for recovery of respective unencoded data units by requesting network nodes.

60. The network node of claim 56, wherein the means for distributing is configured for supplying the identifier in response to a request for access to the unencoded data unit from the another network node.

61. The network node of claim 49, wherein each encoded data unit is secure and unreadable relative to the unencoded data unit.

62. The network node of claim 49, wherein the means for distributing is configured for supplying less than the second prescribed number to any one of the network nodes.

63. A network node configured for connection to a network, the network node comprising:

means for requesting from among network nodes a first prescribed number of encoded data units, the encoded data units having been generated based on encoding an unencoded data unit into a second prescribed number of the encoded data units according to a prescribed encoding operation, the first prescribed number of encoded data units representing a minimum number of the encoded data units required for recovery of the unencoded data unit, wherein each encoded data unit is distinct from other ones of the encoded data units, the second prescribed number greater than the first prescribed number;

means for obtaining the first prescribed number of encoded data units from the network, wherein the means for obtaining receives less than the first prescribed number of encoded data units from any network node that supplies any one of the encoded data units; and

means for recovering the unencoded data unit based on decoding the obtained first prescribed number of encoded data units.

64. The network node of claim 63, wherein the means for requesting is configured for determining an identifier for one of the unencoded data unit and stored locations of the second prescribed number of the encoded data units.

65. The network node of claim 64, wherein the means for requesting is configured for sending a request for the identifier to a source network node having generated the encoded data units.

66. The network node of claim 65, wherein the means for requesting is configured for determining the stored locations based on applying a prescribed function to the identifier.

67. The network node of claim 64, wherein the means for requesting is configured for sending a query for the stored locations to a prescribed shared directory configured for supplying storage addresses identifying the respective stored locations of the encoded data units.

68. The network node of claim 63, wherein the means for requesting is configured for:

sending requests for each of the first prescribed number of the encoded data units among the plurality of network nodes; and

sending a second request for another one of the encoded data units to an alternate network node distinct from the plurality of network nodes.

69. The network node of claim 68, wherein the means for requesting is configured for sending the second request based on one of:

a determined absence of receiving one of encoded data units having been requested from among the plurality of network nodes;

a determination that one of the encoded data units has been corrupted; and

attempting addition of integrity to the recovering of the unencoded data unit.

70. The network node of claim 69, wherein the prescribed encoding operation is Reed Solomon encoding, the means for recovering configured for executing Reed Solomon-based decoding of the first prescribed number of encoded data units to recover the unencoded data unit, the another one of the encoded data units used for one of adding integrity to the recovering of the unencoded data unit, and substituting the another one of the encoded data units in place of the one encoded data unit having been corrupted.

71. The network node of claim 63, wherein the prescribed encoding operation is Reed Solomon encoding, the means for recovering configured for executing Reed Solomon-based decoding of the first prescribed number of encoded data units to recover the unencoded data unit.

72. The network node of claim 71, wherein the first prescribed number equals at least (4) and the second prescribed number equals at least seven (7).