Optimizing routing of data across a communications network

• US 9,843,412 B2
• Filed: 02/06/2015
• Issued: 12/12/2017
• Est. Priority Date: 10/06/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Grube, Gary W., Markison, Timothy W., Gladwin, S. Christopher, Dhuse, Greg, Baptist, Andrew, Volvovski, Ilya, Resch, Jason K.
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US14/615,655
• Publication Number:
  US 20150155968A1
• Time in Patent Office: 1,040 Days
• Field of Search: None
• 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 determining a routing plan to route a set of encoded data slices from the first computing device to a second computing device via a plurality of network paths of a communications network. The method continues with the second computing device receiving encoded data slices via one or more network paths. When the second computing device receives a decode threshold number of encoded data slices, the method continues with the second computing device sending a message to the communications network indicating receipt of the decode threshold number of encoded data slices. The method continues with a relay unit determining whether the relay unit is in possession of a not-yet delivered encoded data slice. When the relay unit is in possession of the not-yet delivered encoded data slice, the method continues with the relay unit ceasing forwarding of the not-yet delivered encoded data slice.

Claims

1. A method comprises:

determining, by a first computing device, a routing plan to route a set of encoded data slices from the first computing device to a second computing device via a plurality of network paths within a communications network, wherein a data segment was dispersed storage error encoded to produce the set of encoded data slices, wherein a decode threshold number of encoded data slices of the set of encoded data slices is needed to recover the data segment, wherein the first and second computing devices are operably coupled to the communications network, and wherein each network path of the plurality of network paths includes one or more relay units;

receiving, by the second computing device, encoded data slices of the set of encoded data slices via one or more network paths of the plurality of network paths;

when the second computing device receives the decode threshold number of encoded data slices, sending, by the second computing device, a message to the communications network; and

when the message indicates receipt of the decode threshold number of encoded data slices;

determining, by a relay unit of the one or more relay units of a corresponding network path of the plurality of network paths, whether the relay unit is in possession of a not-yet delivered encoded data slice of the set of encoded data slices; and

when the relay unit is in possession of the not-yet delivered encoded data slice, ceasing, by the relay unit, forwarding of the not-yet delivered encoded data slice along the corresponding network path.

2. The method of claim 1 further comprises:

determining, by the relay unit, that the relay unit is not in possession of the not-yet delivered encoded data slice;

determining, by the relay unit, whether the corresponding network path is assigned to the not-yet delivered encoded data slice; and

when the corresponding network path is assigned to the not-yet delivered encoded data slice, forwarding, by the relay unit, the message upstream along the corresponding network path.

3. The method of claim 1 further comprises:

when the message indicates receipt of the decode threshold number of encoded data slices and the message is indicative of a pause message, the ceasing, by the relay unit, forwarding of the not-yet delivered encoded data slice along the corresponding network path includes temporarily storing the not-yet delivered encoded data slice; and

continuing, by the relay unit, to temporarily store the not-yet delivered encoded data slice until a further processing event occurs.

4. The method of claim 3, wherein the further processing event comprises one or more:

deleting the not-yet delivered encoded data slice after expiration of a pause time period;

receiving a second message indicating deletion of the not-yet delivered encoded data slice; and

receiving a third message indicating forwarding of the not-yet delivered encoded data slice downstream along the corresponding network path.

5. The method of claim 1 further comprises:

interpreting, by the relay unit, that the message indicates receipt of the decode threshold number of encoded data slices and the message is a delete command regarding the not-yet delivered encoded data slice; and

ceasing, by the relay unit, the forwarding of the not-yet delivered encoded data slice by deleting the not-yet delivered encoded data slice.

6. The method of claim 1 further comprises:

decoding, by the second computing device, the decode threshold number of encoded data slices to produce a decoded data segment; and

when the decoded data segment is validated, sending a second message indicating deletion of the not-yet delivered encoded data slice and other not-yet delivered encoded data slices.

7. The method of claim 1 further comprises:

decoding, by the second computing device, the decode threshold number of encoded data slices to produce a decoded data segment; and

when the decoded data segment is not validated, sending a second message indicating a request for delivery of the not-yet delivered encoded data slice.

8. The method of claim 1 further comprises:

determining, by the relay unit, whether delivery of a sub-set of encoded data slices of the set of encoded data slices allocated for delivery via the corresponding network path have been delivered to the second computing device; and

when delivery of the sub-set of encoded data slices of the set of encoded data slices allocated for delivery via the corresponding network path have been delivered to the second computing device, ignoring, by the relay unit, the message.

9. 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;

determine, by a first computing device of the one or more computing devices, a routing plan to route a set of encoded data slices from the first computing device to a second computing device of the one or more computing devices via a plurality of network paths within a communications network, wherein a data segment was dispersed storage error encoded to produce the set of encoded data slices, wherein a decode threshold number of encoded data slices of the set of encoded data slices is needed to recover the data segment, wherein the first and second computing devices are operably coupled to the communications network, and wherein each network path of the plurality of network paths includes one or more relay units of the one or more computing devices;

receive, by the second computing device, encoded data slices of the set of encoded data slices via one or more network paths of the plurality of network paths;

when the second computing device receives the decode threshold number of encoded data slices, send, by the second computing device, a message to the communications network; and

when the message indicates receipt of the decode threshold number of encoded data slices;

determine, by a relay unit of the one or more relay units of a corresponding network path of the plurality of network paths, whether the relay unit is in possession of a not-yet delivered encoded data slice of the set of encoded data slices; and

when the relay unit is in possession of the not-yet delivered encoded data slice, cease, by the relay unit, forwarding of the not-yet delivered encoded data slice along the corresponding network path.

10. The non-transitory computer readable storage medium of claim 9 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;

determine, by the relay unit, that the relay unit is not in possession of the not-yet delivered encoded data slice;

determine, by the relay unit, whether the corresponding network path is assigned to the not-yet delivered encoded data slice; and

when the corresponding network path is assigned to the not-yet delivered encoded data slice, forward, by the relay unit, the message upstream along the corresponding network path.

11. The non-transitory computer readable storage medium of claim 9 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;

when the message indicates receipt of the decode threshold number of encoded data slices and the message is indicative of a pause message, cease, by the relay unit, forwarding of the not-yet delivered encoded data slice along the corresponding network path by temporarily storing the not-yet delivered encoded data slice; and

continue, by the relay unit, to temporarily store the not-yet delivered encoded data slice until a further processing event occurs.

12. The non-transitory computer readable storage medium of claim 11, wherein the further processing event comprises the one or more processing modules functioning to execute the operational instructions stored by the at least one memory section causing the one or more computing devices to:

delete the not-yet delivered encoded data slice after expiration of a pause time period;

or

receive a second message indicating deletion of the not-yet delivered encoded data slice;

or

receive a third message indicating forwarding of the not-yet delivered encoded data slice downstream along the corresponding network path.

13. The non-transitory computer readable storage medium of claim 9 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;

interpret, by the relay unit, that the message indicates receipt of the decode threshold number of encoded data slices and the message is to be a delete command regarding the not-yet delivered encoded data slice; and

cease, by the relay unit, the forwarding of the not-yet delivered encoded data slice by deleting the not-yet delivered encoded data slice.

14. The non-transitory computer readable storage medium of claim 9 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;

decode, by the second computing device, the decode threshold number of encoded data slices to produce a decoded data segment; and

when the decoded data segment is validated, send a second message indicating deletion of the not-yet delivered encoded data slice and other not-yet delivered encoded data slices.

15. The non-transitory computer readable storage medium of claim 9 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;

decode, by the second computing device, the decode threshold number of encoded data slices to produce a decoded data segment; and

when the decoded data segment is not validated, send a second message indicating a request for delivery of the not-yet delivered encoded data slice.

16. The non-transitory computer readable storage medium of claim 9 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;

determine, by the relay unit, whether delivery of a sub-set of encoded data slices of the set of encoded data slices allocated for delivery via the corresponding network path have been delivered to the second computing device; and

when delivery of the sub-set of encoded data slices of the set of encoded data slices allocated for delivery via the corresponding network path have been delivered to the second computing device, ignore, by the relay unit, the message.