DATA TRANSMISSION UTILIZING ROUTE SELECTION AND DISPERSED STORAGE ERROR ENCODING

• US 20120089885A1
• 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: GRUBE, GARY W., MARKISON, TIMOTHY W., GLADWIN, S. CHRISTOPHER, DHUSE, GREG, BAPTIST, ANDREW, VOLVOVSKI, ILYA, RESCH, JASON K.
• Granted Patent: US 8,612,821 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 processing module obtaining a set of encoded data slices for transmission to a receiving entity via a network, wherein the set of encoded data slices represents data that has been dispersed storage error encoded. The method continues with the processing module dividing the set into a plurality of sub-sets of encoded data slices in accordance with an error coding distributed routing protocol. The method continues with the processing module determining a plurality of routing paths within the network in accordance with the error coding distributed routing protocol. The method continues with the processing module transmitting the plurality of sub-sets of encoded data slices via the plurality of routing paths to the receiving entity in accordance with the error coding distributed routing protocol.

Claims

1. A method comprises:

obtaining a set of encoded data slices for transmission to a receiving entity via a network, wherein the set of encoded data slices represents data that has been dispersed storage error encoded;

dividing the set into a plurality of sub-sets of encoded data slices in accordance with an error coding distributed routing protocol;

determining a plurality of routing paths within the network in accordance with the error coding distributed routing protocol; and

transmitting the plurality of sub-sets of encoded data slices via the plurality of routing paths to the receiving entity in accordance with the error coding distributed routing protocol.

2. The method of claim 1, wherein the obtaining the set of encoded data slices comprises at least one of:

receiving the set of encoded data slices from a sending entity;

retrieving the set of encoded data slices from a dispersed storage network (DSN) memory; and

retrieving the set of encoded data slices.

3. The method of claim 1 further comprises:

obtaining the data;

determining error coding dispersal storage function parameters based on at least one of a data characterization, a routing approach, a reliability requirement, a performance requirement, a lookup, a data encoding policy, a predetermination, a message, and a previous data encoding approach; and

dispersed storage error encoding the data in accordance with the error coding dispersal storage function parameters to produce the set of encoded data slices.

4. The method of claim 1, wherein the determining the plurality of routing paths comprises:

obtaining routing path quality of service information corresponding to a plurality of candidate routing paths to the receiving entity; and

selecting the plurality of routing paths from the plurality of candidate routing paths based on the routing path quality of service information and the error coding distributed routing protocol.

5. The method of claim 1, wherein the dividing the set into the plurality of sub-sets comprises:

determining a number of sub-sets in accordance with the error coding distributed routing protocol, wherein the error coding distributed routing protocol includes at least one of routing path quality of service information, a partitioning function, a capacity estimate of the plurality of routing paths, a sub-set size indicator, a priority indicator, a security indicator, a performance indicator, an estimated routing path performance indicator, a lookup, and a message.

6. The method of claim 1 further comprises:

obtaining a second set of encoded data slices for transmission to the receiving entity via the network;

dividing the second set into a second plurality of sub-sets of encoded data slices in accordance with the error coding distributed routing protocol, wherein a sub-set of the plurality of sub-sets includes one or more like pillar number encoded data slices as a corresponding sub-set of the second plurality of sub-sets;

determining a second plurality of routing paths within the network in accordance with the error coding distributed routing protocol; and

transmitting the second plurality of sub-sets of encoded data slices via the second plurality of routing paths to the receiving entity in accordance with the error coding distributed routing protocol.

7. A method comprises:

receiving a plurality of sub-sets of encoded data slices via a plurality of routing paths within a network from a sending entity in accordance with an error coding distributed routing protocol;

combining at least some of the plurality of sub-sets of encoded data slices in accordance with the error coding distributed routing protocol to produce at least a decode threshold number of encoded data slices; and

dispersed storage error decoding the at least a decode threshold number of encoded data slices to produce data.

8. The method of claim 7 further comprises:

obtaining the error coding distributed routing protocol that includes at least one of routing path quality of service information, a partitioning function, a capacity estimate of the plurality of routing paths, a sub-set size indicator, a priority indicator, a security indicator, a performance indicator, an estimated routing path performance indicator, a lookup, and a message.

9. A computer comprises:

an interface;

a memory; and

a processing module operable to;

obtain a set of encoded data slices for transmission to a receiving entity via a network, wherein the set of encoded data slices represents data that has been dispersed storage error encoded;

divide the set into a plurality of sub-sets of encoded data slices in accordance with an error coding distributed routing protocol;

determine a plurality of routing paths within the network in accordance with the error coding distributed routing protocol; and

transmit, via the interface, the plurality of sub-sets of encoded data slices via the plurality of routing paths to the receiving entity in accordance with the error coding distributed routing protocol.

10. The computer of claim 9, wherein the processing module functions to obtain the set of encoded data slices by at least one of:

receiving, via the interface, the set of encoded data slices from a sending entity;

retrieving, via the interface, the set of encoded data slices from a dispersed storage network (DSN) memory; and

retrieving the set of encoded data slices.

11. The computer of claim 9, wherein the processing module further functions to:

obtain the data;

determine error coding dispersal storage function parameters based on at least one of a data characterization, a routing approach, a reliability requirement, a performance requirement, a lookup, a data encoding policy, a predetermination, a message, and a previous data encoding approach; and

dispersed storage error encode the data in accordance with the error coding dispersal storage function parameters to produce the set of encoded data slices.

12. The computer of claim 9, wherein the processing module functions to determine the plurality of routing paths by:

obtaining routing path quality of service information corresponding to a plurality of candidate routing paths to the receiving entity; and

selecting the plurality of routing paths from the plurality of candidate routing paths based on the routing path quality of service information and the error coding distributed routing protocol.

13. The computer of claim 9, wherein the processing module functions to divide the set into the plurality of sub-sets by:

determining a number of sub-sets in accordance with the error coding distributed routing protocol, wherein the error coding distributed routing protocol includes at least one of routing path quality of service information, a partitioning function, a capacity estimate of the plurality of routing paths, a sub-set size indicator, a priority indicator, a security indicator, a performance indicator, an estimated routing path performance indicator, a lookup, and a message.

14. The computer of claim 9, wherein the processing module further functions to:

obtain a second set of encoded data slices for transmission to the receiving entity via the network;

divide the second set into a second plurality of sub-sets of encoded data slices in accordance with the error coding distributed routing protocol, wherein a sub-set of the plurality of sub-sets includes one or more like pillar number encoded data slices as a corresponding sub-set of the second plurality of sub-sets;

determine a second plurality of routing paths within the network in accordance with the error coding distributed routing protocol; and

transmit, via the interface, the second plurality of sub-sets of encoded data slices via the second plurality of routing paths to the receiving entity in accordance with the error coding distributed routing protocol.

15. A computer comprises:

an interface;

a memory; and

a processing module operable to;

receive, via the interface, a plurality of sub-sets of encoded data slices via a plurality of routing paths within a network from a sending entity in accordance with an error coding distributed routing protocol;

combine at least some of the plurality of sub-sets of encoded data slices in accordance with the error coding distributed routing protocol to produce at least a decode threshold number of encoded data slices; and

dispersed storage error decode the at least a decode threshold number of encoded data slices to produce data.

16. The computer of claim 15, wherein the processing module further functions to:

obtain the error coding distributed routing protocol that includes at least one of routing path quality of service information, a partitioning function, a capacity estimate of the plurality of routing paths, a sub-set size indicator, a priority indicator, a security indicator, a performance indicator, an estimated routing path performance indicator, a lookup, and a message.