Allocation Of Symbols Of An Erasure Code Across A Plurality Of Devices

• US 20100083068A1
• Filed: 10/01/2008
• Published: 04/01/2010
• Est. Priority Date: 06/18/2008
• 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: Greenan, Kevin M., Wylie, John Johnson
• Granted Patent: US 8,250,433 B2
• Time in Patent Office: Days
• US Class Current: 714/752
• CPC Class Codes: H03M 13/015 Simulation or testing of codes, e.g. bit error rate [BER] measurements
• CPC Class Codes: H03M 13/1191 Codes on graphs other than LDPC codes
• 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
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes

Abstract

A technique is provided for determining an allocation of the symbols of an erasure code across a plurality of devices. A list of erasure patterns is provided for the erasure code and, based on the list, minimal erasures of minimal weight are identified for the code'"'"'s symbols. Precedences of the symbols are determined based on the size of the corresponding MEMW. An allocation of the symbols across a plurality of devices is determined based on the precedences.

Claims

1. A method of determining an allocation of symbols of an erasure code across a plurality of devices, comprising:

providing a list of erasure patterns for an erasure code, the erasure code having a plurality of symbols;

based on the list, identifying a minimal erasure of minimal weight (MEMW) for each symbol;

determining precedences of the symbols of the erasure code based on a size of the corresponding MEMWs for the symbols; and

determining an allocation of the symbols across a plurality of devices based on the determined precedences.

2. The method as recited in claim 1, further comprising:

allocating the symbols across the plurality of devices based on the allocation, wherein the plurality of devices have corresponding failure rates, and wherein a symbol having a highest precedence in the ordering is allocated to a device having a lowest failure rate.

3. The method as recited in claim 2, wherein the devices include at least one device from a group of storage devices and communication devices.

4. The method as recited in claim 2, wherein a symbol has the highest precedence if the symbol has a smallest size MEMW.

5. The method as recited in claim 1, further comprising:

grouping the symbols in sets, wherein the symbols in a set have a same size MEMW;

ordering the symbols within each of the sets based on a quantity of same size MEMWs for each symbol, wherein a symbol having a greatest quantity of same size MEMWs is accorded a highest precedence in the set.

6. The method as recited in claim 1, further comprising:

grouping the symbols in sets, wherein the symbols in a set have a same size MEMW;

generating histograms for the sets of symbols, wherein the histogram identifies a count of same size MEMWs for the symbols in the corresponding set;

ordering a first symbol in a first set of symbols based on the count; and

adjusting the count for each remaining symbol in the first set based on the ordering of the first symbol in the first set.

7. The method as recited in claim 6, wherein the count for each remaining symbol is adjusted based on whether the remaining symbol appears in a same size MEMW along with the first symbol.

8. The method as recited in claim 6, further comprising updating the histogram for a second set of symbols based on the ordering of the first symbol in the first set.

9. A method of determining an allocation of a plurality of symbols of an erasure code, comprising:

providing a list of erasure patterns for an erasure code, the erasure code having a plurality of symbols;

based on the list of erasure patterns, generating an erasures vector for each symbol of the erasure code;

determining a precedence of each symbol based on the erasure vectors for the symbols; and

determining an allocation of the symbols of the erasure code across a plurality of devices based on the determined precedences.

10. The method as recited in claim 9, wherein the plurality of devices include at least one device from a group of storage devices and communication devices.

11. The method as recited in claim 9, wherein the plurality of devices have corresponding failure rates, and wherein a symbol having a highest precedence is allocated to a device having a lowest failure rate of the corresponding failure rates.

12. The method as recited in claim 9, wherein the list of erasure patterns is a list of minimal erasure patterns, and wherein a symbol has a highest precedence in the ordering if the symbol appears in a smallest size minimal erasure pattern.

13. The method as recited in claim 9, wherein the list of erasure patterns is a list of minimal erasure patterns, and wherein a symbol has a highest precedence in the ordering if the symbol appears in a largest number of smallest size minimal erasure patterns.

14. An article comprising at least one computer-readable storage medium containing instructions that when executed cause a processor-based system to:

generate a list of erasure patterns corresponding to an erasure code having a plurality of symbols;

based on the list, identify minimal erasures of minimal weight (MEMWs) corresponding to the symbols;

determine precedences of the symbols of the erasure code based on sizes of the corresponding MEMW for the symbols;

order the symbols of the erasure code based on the determined precedences; and

determine an allocation of the symbols across a plurality of devices based on the order.

15. The article as recited in claim 14, wherein the plurality of devices include at least one from a group of storage devices and communication devices.