System and method for determining the fault-tolerance of an erasure code

• US 20090083590A1
• Filed: 09/26/2007
• Published: 03/26/2009
• Est. Priority Date: 09/26/2007
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Swaminathan, Ram, Wylie, John Johnson
• Granted Patent: US 8,127,212 B2
• Time in Patent Office: Days
• US Class Current: 714/703
• CPC Class Codes: H03M 13/015 Simulation or testing of codes, e.g. bit error rate [BER] measurements
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes

Abstract

A method for determining a fault tolerance of an erasure code comprises deriving base erasure patterns from a generator matrix of an erasure code, determining which of the base erasure patterns are adjacent to one another and XORing the adjacent base erasure patterns with one another to produce child erasure patterns of the erasure code. The method further comprises combining the base erasure patterns and the child erasure patterns to form a minimal erasures list (MEL) for the erasure code, whereby the MEL corresponds to the fault tolerance of the erasure code. Also provided are methods for communicating and storing data by using the fault tolerance of erasure codes.

Claims

1. A method for determining a fault tolerance of an erasure code, comprising:

deriving base erasure patterns from a generator matrix of an erasure code;

determining which of the base erasure patterns are adjacent to one another;

XORing the adjacent base erasure patterns with one another to generate child erasure patterns of the erasure code; and

combining the base erasure patterns and the child erasure patterns to form a minimal erasure list (MEL) for the erasure code, wherein the MEL corresponds to the fault tolerance of the erasure code, and wherein the MEL is used for allocating the erasure code across multiple devices.

2. The method of claim 1, comprising XORing the child erasure patterns with the base erasure patterns to produce additional child erasure patterns that are added to the MEL.

3. The method of claim 1, comprising determining whether each of the generated child erasure patterns is already in the MEL, or whether each of the generated child erasure patterns is a composite erasure.

4. The method of claim 3, comprising adding a generated child erasure patterns to the MEL if the child erasure pattern is not already in the MEL or if the child erasure pattern is not a composite erasure.

5. The method of claim 1, wherein the method terminates when the produced child erasure patterns are not adjacent to any of the base erasures, or when the produced child erasure patterns are identical to previously generated child erasure patterns, or when a specific number of child erasure patterns are produced.

7. The method of claim 1, wherein adjacency of the base erasure patterns with one another and/or with the child erasure patterns is determined using a Tanner graph, or the generator matrix, or a lookup table, or a combination thereof.

11. The method of claim 1, wherein the erasure code is a systematic erasure code.

12. The method of claim 1, wherein the erasure code is non-systematic erasure code.

14. The method of claim 1, wherein the devices are multiple storage devices, and wherein the method comprises determining a reliability for each of the storage devices, and storing data within each of the storage devices in accordance with the reliability of each storage device and in accordance with the fault tolerance of the erasure code associated with the storage devices.

15. The method of claim 1, wherein the devices are multiple communication channels, and wherein the method comprises determining a reliability for each of the communication channels, and communicating data over each of the communication channels in accordance with the reliability of each communication channel and the fault tolerance of the erasure code associated with the communication channels.

6. (canceled)

8-10. -10. (canceled)

13. (canceled)

16. A method for storing data in storage devices, wherein the storage devices are associated with an erasure code, the method comprising;

determining a fault tolerance for the erasure code associated with the storage devices, wherein the method comprises;

deriving base erasure patterns from a generator matrix of an erasure code;

determining which of the base erasure patterns are adjacent to one another;

XORing the adjacent base erasure patterns with one another to produce child erasure patterns of the erasure code;

combining the base erasure patterns and the child erasure patterns to form a minimal erasure list (MEL) for the erasure code, wherein the MEL corresponds to the fault tolerance of the erasure code; and

determining a reliability for each storage device comprising the storage devices and storing data within each of the storage devices in accordance with the reliability of each storage device and in accordance with the fault tolerance of the erasure code associated with the storage devices.

17. The method of claim 16, comprising fragmenting the erasure code across the storage devices.

18. The method of claim 16, comprising associating erasure codes with the storage devices, determining the fault tolerance of each erasure code comprising the erasure codes, and storing data within each of the storage devices in accordance with the reliability of each storage device and the fault tolerance of each erasure code.

19. The method of claim 16, comprising associating an erasure code with a single storage device.

20. The method of claim 16, wherein the storage devices comprise magnetic memory storage devices, optical memory storage devices, flash memory storage devices or a combination thereof.

23. The method of claim 16, comprising creating redundancies in the data stored in the storage devices, wherein the amount of redundancies created in data stored in each of the storage devices depends on the reliability of the storage device and on the MEL of the erasure code.

21-22. -22. (canceled)

24. A method for communicating data over communication channels, wherein the communication channels are associated with an erasure code, the method comprising;

determining a fault tolerance for the erasure code associated with the communication channels, wherein the method comprises;

deriving base erasure patterns from a generator matrix of an erasure code;

determining which of the base erasure patterns are adjacent to one another;

XORing the adjacent base erasure patterns with one another to produce child erasure patterns of the erasure code;

combining the base erasure patterns and the child erasure patterns to form a minimal erasure list (MEL) for the erasure code, wherein the MEL corresponds to the fault tolerance of the erasure code; and

determining a reliability associated with each of the communication channels; and

communicating data over each of the communication channels in accordance with the reliability of each communication channel and the fault tolerance of the erasure code associated with the communication channels.

25. The method of claim 24, comprising fragmenting the erasure code across the communication channels.

26. The method of claim 24, comprising associating erasure codes with the communication channels, determining the fault tolerance of each erasure code comprising the erasure codes, and communicating data over each of the communication channels in accordance with the reliability of each communication channel and the fault tolerance of each erasure code.

27. The method of claim 24, comprising associating an erasure code with a single storage communication channel.

30. The method of claim 24, comprising creating redundancies in the data communicated over the communication channels, wherein the amount of redundancies created in data communicated over each communication channel depends on the reliability of the communication channel and on the MEL of the erasure code.

28-29. -29. (canceled)

31. A tangible machine readable medium, comprising:

code adapted to derive base erasure patterns from a generator matrix of an erasure code;

code adapted to determine which of the base erasure patterns are adjacent to one another;

code adapted to XOR the adjacent base erasure patterns with one another to produce child erasure patterns of the erasure code; and

code adapted to combine the base erasure patterns and the child erasure patterns to form a minimal erasure list (MEL) for the erasure code, wherein the MEL corresponds to the fault tolerance of the erasure code, and wherein the MEL is used for allocating the erasure code across multiple devices.

32. The tangible machine readable medium of claim 31, wherein execution terminates when the produced child erasure patterns are not adjacent to any of the base erasures, or when the produced child erasure patterns are identical to previously generated child erasure patterns, or when a predetermined amount of child erasure patterns are produced.

37. The tangible machine readable medium of claim 31, comprising code adapted for determining a reliability for each of the storage devices;

and code adapted for storing data within each of the storage devices in accordance with the reliability of each storage device and in accordance with the fault tolerance of the erasure code associated with the storage devices.

38. The tangible machine readable medium of claim 31, comprising code adapted for determining a reliability for each of the communication channels;

and code adapted for communicating data over each of the communication channels in accordance with the reliability of each communication channel and the fault tolerance of the erasure code associated with the communication channels.

33-36. -36. (canceled)