RELAYING DATA TRANSMITTED AS ENCODED DATA SLICES

• US 20120089886A1
• Filed: 10/03/2011
• Published: 04/12/2012
• Est. Priority Date: 10/06/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: BAPTIST, ANDREW, VOLVOVSKI, ILYA, GRUBE, GARY W., MARKISON, TIMOTHY W., GLADWIN, S. CHRISTOPHER, DHUSE, GREG, RESCH, JASON K.
• Granted Patent: US 9,037,937 B2
• Time in Patent Office: Days
• US Class Current: 714/752
• CPC Class Codes: G06F 11/1028 Adjacent errors, e.g. error in n-bit (n>1) wide storage units, i.e. package error
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• 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
• CPC Class Codes: H04L 45/24 Multipath

Abstract

A method begins by a first device determining an error coding distributed routing protocol and transmitting a set of encoded data slices, identity of a second device, and the error coding distributed routing protocol to a network, wherein the set of encoded data slices represents data that has been dispersed storage error encoded. The method continues with the network routing a plurality of sub-sets of the set of encoded data slices via an initial plurality of routing paths towards the second, comparing anticipated routing performance with a desired routing performance, and altering the routing path to obtain a favorable comparison. The method continues with the second device receiving at least some of the set of encoded data slices from the network and decoding at least a threshold number of encoded data slices to reproduce the data when at least the threshold number of encoded data slices have been received.

Claims

1. A method comprises:

determining, by a first device, an error coding distributed routing protocol;

transmitting, by the first device, a set of encoded data slices, identity of a second device, and the error coding distributed routing protocol to a network, wherein the set of encoded data slices represents data that has been dispersed storage error encoded;

routing, by the network, a plurality of sub-sets of the set of encoded data slices via an initial plurality of routing paths towards the second device in accordance with the error coding distributed routing protocol;

comparing, by the network, anticipated routing performance of the routing of the plurality of sub-sets with a desired routing performance;

when the comparison of a routing path of the initial plurality of routing paths is unfavorable, altering the routing path to obtain a favorable comparison;

receiving, by the second device, at least some of the set of encoded data slices from the network; and

when at least a threshold number of encoded data slices have been received, decoding, by the second device, the at least a threshold number of encoded data slices to reproduce the data.

2. The method of claim 1, wherein the error coding distributed routing protocol comprises at least one of:

identity of the initial plurality of routing paths;

a number of routing paths;

a number of sub-sets of the set of encoded data slices;

the desired routing performance for one or more of the sub-sets of the set of encoded data slices;

a request for multiple path transmission of the set of encoded data slices;

a capacity estimate of the initial plurality of routing paths;

a priority indicator for at least one of the sub-sets;

a security indicator for at least one of the sub-sets; and

a performance indicator for at least one of the sub-sets.

3. The method of claim 1, wherein the comparing, by the network, the anticipated routing performance comprises:

for a link of a plurality of links of the routing path, determining the anticipated routing performance of the link;

comparing the anticipated routing performance of the link with a corresponding portion of the desired routing performance; and

when the comparison of the anticipated routing performance of the link with the corresponding portion of the desired routing performance is unfavorable, indicating that the comparison of the anticipated routing performance of the routing of the plurality of sub-sets with the desired routing performance is unfavorable.

4. The method of claim 1, wherein the altering the routing path further comprises:

dispersed storage error encoding an encoded data slice of a corresponding sub-set of the plurality of sub-sets to produce a set of encoded data sub-slices;

determining a plurality of sub-routing paths; and

routing the set of encoded data sub-slices to the second device via the plurality of sub-routing paths.

5. The method of claim 1, wherein the altering the routing path further comprises at least one of:

selecting a lower latency routing path;

selecting a higher data rate routing path;

selecting a routing path with higher capacity;

selecting a routing path with a lower error rate;

selecting a routing path with a higher cost;

selecting a higher latency routing path;

selecting a lower data rate routing path;

selecting a routing path with a higher error rate;

selecting a routing path with a lower cost; and

selecting a routing path with lower capacity.

6. A method comprises:

receiving, from a first device, a set of encoded data slices, identity of a second device, and an error coding distributed routing protocol, wherein the set of encoded data slices represents data that has been dispersed storage error encoded;

routing a plurality of sub-sets of the set of encoded data slices via an initial plurality of routing paths from the first device towards the second device in accordance with the error coding distributed routing protocol;

comparing anticipated routing performance of the routing of the plurality of sub-sets with a desired routing performance; and

when the comparison of a routing path of the initial plurality of routing paths is unfavorable, altering the routing path to obtain a favorable comparison.

7. The method of claim 6, wherein the comparing the anticipated routing performance comprises:

for a link of a plurality of links of the routing path, determining the anticipated routing performance of the link;

comparing the anticipated routing performance of the link with a corresponding portion of the desired routing performance; and

when the comparison of the anticipated routing performance of the link with the corresponding portion of the desired routing performance is unfavorable, indicating that the comparison of the anticipated routing performance of the routing of the plurality of sub-sets with the desired routing performance is unfavorable.

8. The method of claim 6, wherein the altering the routing path further comprises:

dispersed storage error encoding an encoded data slice of a corresponding sub-set of the plurality of sub-sets to produce a set of encoded data sub-slices;

determining a plurality of sub-routing paths; and

routing the set of encoded data sub-slices to the second device via the plurality of sub-routing paths.

9. The method of claim 6, wherein the altering the routing path further comprises at least one of:

selecting a lower latency routing path;

selecting a higher data rate routing path;

selecting a routing path with higher capacity;

selecting a routing path with a lower error rate;

selecting a routing path with a higher cost;

selecting a higher latency routing path;

selecting a lower data rate routing path;

selecting a routing path with a higher error rate;

selecting a routing path with a lower cost; and

selecting a routing path with lower capacity.

10. A method comprises:

receiving a sub-set of encoded data slices, identity of a second device, and an error coding distributed routing protocol, wherein a set of encoded data slices represents data that has been dispersed storage error encoded and includes the sub-set of encoded data slices;

determining anticipated routing performance of routing the sub-set of encoded data slices via a routing path to the second device in accordance with the error coding distributed routing protocol;

comparing the anticipated routing performance with a desired routing performance;

when the comparison of the anticipated routing performance to the desired routing performance is unfavorable, altering the routing path to obtain a favorable comparison to produce an altered routing path; and

routing the sub-set of encoded data slices to the second device via the altered routing path.

11. The method of claim 10, wherein the comparing the anticipated routing performance comprises:

for a link of a plurality of links of the routing path, determining anticipated routing performance of the link;

comparing the anticipated routing performance of the link with a corresponding portion of the desired routing performance; and

when the comparison of the anticipated routing performance of the link with the corresponding portion of the desired routing performance is unfavorable, indicating that the comparison of the anticipated routing performance of the routing of the plurality of sub-sets with the desired routing performance is unfavorable.

12. The method of claim 10, wherein the altering the routing path further comprises:

dispersed storage error encoding an encoded data slice of the sub-set of encoded data slices to produce a set of encoded data sub-slices;

determining a plurality of sub-routing paths; and

routing the set of encoded data sub-slices to the second device via the plurality of sub-routing paths.

13. The method of claim 10, wherein the altering the routing path further comprises at least one of:

selecting a lower latency routing path;

selecting a higher data rate routing path;

selecting a routing path with higher capacity;

selecting a routing path with a lower error rate;

selecting a routing path with a higher cost;

selecting a higher latency routing path;

selecting a lower data rate routing path;

selecting a routing path with a higher error rate;

selecting a routing path with a lower cost; and

selecting a routing path with lower capacity.

14. A computer comprises:

an interface;

a memory; and

a processing module operable to;

receive, from a first device via the interface, a set of encoded data slices, identity of a second device, and an error coding distributed routing protocol, wherein the set of encoded data slices represents data that has been dispersed storage error encoded;

route a plurality of sub-sets of the set of encoded data slices via an initial plurality of routing paths from the first device towards the second device in accordance with the error coding distributed routing protocol;

compare anticipated routing performance of the routing of the plurality of sub-sets with a desired routing performance; and

when the comparison of a routing path of the initial plurality of routing paths is unfavorable, alter the routing path to obtain a favorable comparison.

15. The computer of claim 14, wherein the processing module functions to compare the anticipated routing performance by:

for a link of a plurality of links of the routing path, determining the anticipated routing performance of the link;

comparing the anticipated routing performance of the link with a corresponding portion of the desired routing performance; and

when the comparison of the anticipated routing performance of the link with the corresponding portion of the desired routing performance is unfavorable, indicating that the comparison of the anticipated routing performance of the routing of the plurality of sub-sets with the desired routing performance is unfavorable.

16. The computer of claim 14, wherein the processing module further functions to alter the routing path by:

dispersed storage error encoding an encoded data slice of a corresponding sub-set of the plurality of sub-sets to produce a set of encoded data sub-slices;

determining a plurality of sub-routing paths; and

routing the set of encoded data sub-slices to the second device via the plurality of sub-routing paths.

17. The computer of claim 14, wherein the processing module further functions to alter the routing path by at least one of:

selecting a lower latency routing path;

selecting a higher data rate routing path;

selecting a routing path with higher capacity;

selecting a routing path with a lower error rate;

selecting a routing path with a higher cost;

selecting a higher latency routing path;

selecting a lower data rate routing path;

selecting a routing path with a higher error rate;

selecting a routing path with a lower cost; and

selecting a routing path with lower capacity.

18. A computer comprises:

an interface;

a memory; and

a processing module operable to;

receive, via the interface, a sub-set of encoded data slices, identity of a second device, and an error coding distributed routing protocol, wherein a set of encoded data slices represents data that has been dispersed storage error encoded and includes the sub-set of encoded data slices;

determine anticipated routing performance of routing the sub-set of encoded data slices via a routing path to the second device in accordance with the error coding distributed routing protocol;

compare the anticipated routing performance with a desired routing performance;

when the comparison of the anticipated routing performance to the desired routing performance is unfavorable, alter the routing path to obtain a favorable comparison to produce an altered routing path; and

route the sub-set of encoded data slices to the second device via the altered routing path.

19. The computer of claim 18, wherein the processing module functions to compare the anticipated routing performance by:

for a link of a plurality of links of the routing path, determining anticipated routing performance of the link;

comparing the anticipated routing performance of the link with a corresponding portion of the desired routing performance; and

when the comparison of the anticipated routing performance of the link with the corresponding portion of the desired routing performance is unfavorable, indicating that the comparison of the anticipated routing performance of the routing of the plurality of sub-sets with the desired routing performance is unfavorable.

20. The computer of claim 18, wherein the processing module further functions to alter the routing path by:

dispersed storage error encoding an encoded data slice of the sub-set of encoded data slices to produce a set of encoded data sub-slices;

determining a plurality of sub-routing paths; and

routing the set of encoded data sub-slices to the second device via the plurality of sub-routing paths.

21. The computer of claim 18, wherein the processing module further functions to alter the routing path by at least one of:

selecting a lower latency routing path;

selecting a higher data rate routing path;

selecting a routing path with higher capacity;

selecting a routing path with a lower error rate;

selecting a routing path with a higher cost;

selecting a higher latency routing path;

selecting a lower data rate routing path;

selecting a routing path with a higher error rate;

selecting a routing path with a lower cost; and

selecting a routing path with lower capacity.