Adjusting routing of data within a network path

• US 9,571,230 B2
• Filed: 02/06/2015
• Issued: 02/14/2017
• Est. Priority Date: 10/06/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Volvovski, Ilya, Baptist, Andrew, Grube, Gary W., Markison, Timothy W., Gladwin, S. Christopher, Dhuse, Greg, Resch, Jason K.
• Primary Examiner(s): McMahon, Daniel
• Application Number:
  US14/615,701
• Publication Number:
  US 20150155969A1
• Time in Patent Office: 739 Days
• Field of Search: None
• US Class Current: 1/1
• 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: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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/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 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 69/24 Negotiation of communication capabilities

Abstract

A method begins by a first computing device generating an initial routing plan that identifies network paths for transmitting encoded data slices of an encoded data segment from the first computing device to a second computing device. The method continues with the first computing device sending a plurality of subsets of encoded data slices to network paths. Within a network path, the method continues by a relay unit determining whether the network path defined by the initial routing plan requires adjusting. When the network path requires adjusting, the method continues with the relay unit establishing an adjusted network path by at least one of adding a relay unit and deleting a relay unit. The method continues with the relay unit sending, via the adjusted network path, the corresponding subset of encoded data slices to the second computing device.

Claims

1. A method comprises:

generating, by a first computing device, an initial routing plan that identifies a plurality of network paths for transmitting encoded data slices of an encoded data segment from the first computing device to a second computing device, wherein each network path of the plurality of network paths includes one or more relay units, wherein a data segment was dispersed storage error encoded to produce the encoded data segment, wherein the encoded data segment includes a set of encoded data slices, and wherein a decode threshold number of encoded data slices of the set of encoded data slices is needed to recover the data segment by the second computing device;

sending, by the first computing device, a plurality of subsets of encoded data slices to the plurality of network paths; and

within a network path of the plurality of network paths;

determining, by a relay unit of the one or more relay units of the network path, whether the network path defined by the initial routing plan requires adjusting based on characteristics of other network paths of the plurality of network paths and the decode threshold number of encoded data slices being received by the second computing device;

when the network path requires adjusting, establishing, by the relay unit, an adjusted network path by at least one of;

adding a relay unit to the one or more relay units; and

deleting a relay unit from the one or more relay units; and

sending, via the adjusted network path, a corresponding subset of the plurality of subsets of encoded data slices to the second computing device.

2. The method of claim 1, wherein the sending the plurality of subsets of encoded data slices comprises:

dividing, by the first computing device, the set of encoded data slices into the plurality of subsets of encoded data slices, wherein a network path of the plurality of network paths is allocated to transmit a subset of encoded data slices of the plurality of subsets of encoded data slices from the first computing device to the second computing device.

3. The method of claim 1 further comprises:

generating, by the second computing device, an updated routing plan based on receiving the corresponding subset of the plurality of subsets of encoded data slices via the adjusted network path.

4. The method of claim 1, wherein the establishing the adjusted network path further comprises:

dividing the network path into two or more network paths to produce the adjusted network path.

5. The method of claim 1, wherein the determining, by the relay unit, that the network path defined by the initial routing plan requires adjusting comprises:

determining that the decode threshold number of encoded data slices will be received by the second computing device prior to receiving one or more encoded data slices of the corresponding subset of the plurality of subsets of encoded data slices.

6. The method of claim 1 further comprises:

within the network path of the plurality of network paths;

determining, by the relay unit, whether the decode threshold number of encoded data slices will be received by the second computing device prior to receiving one or more encoded data slices of the corresponding subset of the plurality of subsets of encoded data slices; and

when the decode threshold number of encoded data slices will be received by the second computing device prior to receiving the one or more encoded data slices, pausing, by the relay unit, routing of the one or more encoded data slices to the second computing device.

7. A non-transitory computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by one or more processing modules of one or more computing devices, causes the one or more computing devices to;

generate, by a first computing device of the one or more computing devices, an initial routing plan that identifies a plurality of network paths for transmitting encoded data slices of an encoded data segment from the first computing device to a second computing device of the one or more computing devices, wherein each network path of the plurality of network paths includes one or more relay units of the one or more computing devices, wherein a data segment was dispersed storage error encoded to produce the encoded data segment, wherein the encoded data segment includes a set of encoded data slices, and wherein a decode threshold number of encoded data slices of the set of encoded data slices is needed to recover the data segment by the second computing device;

send, by the first computing device, a plurality of subsets of encoded data slices to the plurality of network paths; and

within a network path of the plurality of network paths;

determine, by a relay unit of the one or more relay units of the network path, whether the network path defined by the initial routing plan requires adjusting based on characteristics of other network paths of the plurality of network paths and the decode threshold number of encoded data slices being received by the second computing device;

when the network path requires adjusting, establish, by the relay unit, an adjusted network path by at least one of;

adding a relay unit to the one or more relay units; and

deleting a relay unit from the one or more relay units; and

send, via the adjusted network path, a corresponding subset of the plurality of subsets of encoded data slices to the second computing device.

8. The non-transitory computer readable storage medium of claim 7, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices to send the plurality of subsets of encoded data by:

dividing, by the first computing device, the set of encoded data slices into the plurality of subsets of encoded data slices, wherein a network path of the plurality of network paths is allocated to transmit a subset of encoded data slices of the plurality of subsets of encoded data slices from the first computing device to the second computing device.

9. The non-transitory computer readable storage medium of claim 7 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices to;

generate, by the second computing device, an updated routing plan based on receiving the corresponding subset of the plurality of subsets of encoded data slices via the adjusted network path.

10. The non-transitory computer readable storage medium of claim 7, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices to further establish the adjusted network path by:

dividing the network path into two or more network paths to produce the adjusted network path.

11. The non-transitory computer readable storage medium of claim 7, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices to determine, by the relay unit, that the network path defined by the initial routing plan requires adjusting by:

determining that the decode threshold number of encoded data slices will be received by the second computing device prior to receiving one or more encoded data slices of the corresponding subset of the plurality of subsets of encoded data slices.

12. The non-transitory computer readable storage medium of claim 7 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices to;

within the network path of the plurality of network paths;

determine, by the relay unit, whether the decode threshold number of encoded data slices will be received by the second computing device prior to receiving one or more encoded data slices of the corresponding subset of the plurality if subsets of encoded data slices; and

when the decode threshold number of encoded data slices will be received by the second computing device prior to receiving the one or more encoded data slices, pause, by the relay unit, routing of the one or more encoded data slices to the second computing device.