ROUTER-BASED DISPERSED STORAGE NETWORK METHOD AND APPARATUS

• US 20110106972A1
• Filed: 08/04/2010
• Published: 05/05/2011
• Est. Priority Date: 10/30/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: GRUBE, GARY W., MARKISON, TIMOTHY W.
• Granted Patent: US 9,043,489 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: G06F 11/2089 Redundant storage control functionality
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/1045 associated with a data cache
• CPC Class Codes: G06F 13/1668 Details of memory controller
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• 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/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method begins by a router receiving data for storage and interpreting the data to determine whether the data is to be forwarded or error encoded. The method continues with the router obtaining a routing table when the data is to be error encoded. Next, the method continues with the router selecting a routing option from the plurality of routing options and determining error coding dispersal storage function parameters based on the routing option. Next, the method continues with the router encoding the data based on the error coding dispersal storage function parameters to produce a plurality of sets of encoded data slices. Next, the method continues with the router outputting at least some of the encoded data slices of a set of the plurality of sets of encoded data slices to an entry point of the routing option.

Claims

1. A method for execution by a router, the method comprises:

receiving data for storage;

interpreting the data to determine whether the data is to be forwarded or error encoded; and

when the data is to be error encoded;

obtaining a routing table that includes one or more of;

a source identifier (ID) associated with the data, a destination identifier (ID) associated with the data, and information regarding a plurality of routing options;

selecting a routing option from the plurality of routing options;

determining error coding dispersal storage function parameters based on the routing option;

encoding the data based on the error coding dispersal storage function parameters to produce a plurality of sets of encoded data slices; and

outputting at least some of the encoded data slices of a set of the plurality of sets of encoded data slices to an entry point of the routing option.

2. The method of claim 1 further comprises at least one of:

receiving the data from a source associated with the source ID; and

receiving the data from another router.

3. The method of claim 1, wherein the obtaining the routing table comprises at least one of:

receiving the routing table in response to a request message;

retrieving the routing table from a routing table database; and

receiving the routing table in conjunction with receiving the data.

4. The method of claim 1, wherein the selecting the routing option comprises at least one of:

a source associated with the source ID;

a destination associated with the destination ID;

routing performance information;

a routing preference; and

a routing requirement.

5. The method of claim 1 further comprises:

receiving metadata associated with the data; and

utilizing the metadata to obtain the routing table.

6. The method of claim 1, wherein the outputting further comprises:

partitioning the plurality of sets of encoded data slices into a plurality of pillars of encoded data slices;

determining destinations for each of the plurality of pillars of encoded data slices in accordance with the destination ID; and

outputting the plurality of pillars of encoded data slices to the destinations.

7. The method of claim 6 further comprises:

determining whether one of the plurality of pillars of encoded data slices is to be stored locally; and

when the one of the plurality of pillars of encoded data slices is to be stored locally, outputting the one of the plurality of pillars of encoded data slices to a local memory.

8. The method of claim 1 further comprises:

when the data is to be forwarded, determining whether the data is to be forwarded to local memory or to another router;

when the data is to be forwarded to the local memory, outputting the data to the local memory; and

when the data is to be forwarded to the other router, outputting the data to the other router.

9. A router comprises:

an interface;

a memory; and

a processing module operable to;

receive, via the interface, data for storage;

interpret the data to determine whether the data is to be forwarded or error encoded; and

when the data is to be error encoded;

obtain a routing table that includes one or more of;

a source identifier (ID) associated with the data, a destination identifier (ID) associated with the data, and information regarding a plurality of routing options;

select a routing option from the plurality of routing options;

determine error coding dispersal storage function parameters based on the routing option;

encode the data based on the error coding dispersal storage function parameters to produce a plurality of sets of encoded data slices; and

output, via the interface, at least some of the encoded data slices of a set of the plurality of sets of encoded data slices to an entry point of the routing option.

10. The router of claim 9, wherein the processing module is further operable to:

receive, via the interface, the data from a source associated with the source ID; and

receive, via the interface, the data from another router.

11. The router of claim 9, wherein the processing module further functions to obtain the routing table by at least one of:

receiving, via the interface, the routing table in response to a request message;

retrieving the routing table from a routing table database; and

receiving, via the interface, the routing table in conjunction with receiving the data.

12. The router of claim 9, wherein the processing module further functions to select the routing option comprising at least one of:

a source associated with the source ID;

a destination associated with the destination ID;

routing performance information;

a routing preference; and

a routing requirement.

13. The router of claim 9, wherein the processing module is further operable to:

receive, via the interface, metadata associated with the data; and

utilize the metadata to obtain the routing table.

14. The router of claim 9, wherein the processing module further functions to output by:

partitioning the plurality of sets of encoded data slices into a plurality of pillars of encoded data slices;

determining destinations for each of the plurality of pillars of encoded data slices in accordance with the destination ID; and

outputting, via the interface, the plurality of pillars of encoded data slices to the destinations.

15. The router of claim 14, wherein the processing module is further operable to:

determine whether one of the plurality of pillars of encoded data slices is to be stored locally; and

output the one of the plurality of pillars of encoded data slices to the memory when the one of the plurality of pillars of encoded data slices is to be stored locally.

16. The router of claim 9, wherein the processing module is further operable to:

determine whether the data is to be forwarded to the memory or to another router when the data is to be forwarded;

output the data to the memory when the data is to be forwarded to the memory; and

output, via the interface, the data to the other router when the data is to be forwarded to the other router.