Concurrent coding of data streams

• US 8,930,649 B2
• Filed: 08/02/2012
• Issued: 01/06/2015
• Est. Priority Date: 09/06/2011
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): Rojas, Midys
• Application Number:
  US13/565,562
• Publication Number:
  US 20130061008A1
• Time in Patent Office: 887 Days
• Field of Search: None
• US Class Current: 711/154
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: H03M 13/1148 Structural properties of the code parity-check or generator matrix
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H04L 65/70 Media network packetisation

Abstract

A method begins by a dispersed storage (DS) processing module concurrently receiving a first data stream and a second data stream for transmission to a receiving entity. The method continues with the DS processing module segmenting each of the first and second data streams to produce a first plurality of data segments and a second plurality of data segments, dividing one of the first plurality of data segments into a first plurality of data blocks, and dividing one of the second plurality of data segments into a second plurality of data blocks. The method continues with the DS processing module creating a data matrix from the first and second plurality of data blocks and generating a coded matrix from the data matrix and an encoding matrix. The method continues with the DS processing module outputting one or more pairs of coded values of the coded matrix to the receiving entity.

Claims

1. A method comprises:

concurrently receiving a first data stream and a second data stream for transmission to a receiving entity;

segmenting each of the first and second data streams to produce a first plurality of data segments corresponding to the first data stream and a second plurality of data segments corresponding to the second data stream;

dividing one of the first plurality of data segments into a first plurality of data blocks;

dividing one of the second plurality of data segments into a second plurality of data blocks, wherein the one of the first plurality of data segments is time aligned with the one of the second plurality of data segments;

creating a data matrix from the first and second plurality of data blocks;

generating a coded matrix by multiplying the data matrix with an encoding matrix; and

outputting at least one pair of coded values of the coded matrix to the receiving entity, wherein a pair of coded values of the at least one pair of coded values includes a coded value corresponding to the one of the first plurality of data segments and a coded value corresponding to the one of the second plurality of data segments.

2. The method of claim 1, wherein the outputting the at least one pair of coded values comprises:

outputting pairs of coded values of the coded matrix in a sequential order corresponding to a time ordering of the first and second plurality of data blocks such that the receiving entity is able to decode the pairs of coded values to maintain concurrency of the first and second data streams.

3. The method of claim 1, wherein the outputting the at least one pair of coded values comprises:

outputting a decode threshold number of pairs of coded values of the coded matrix such that the receiving entity is able to decode coded values of the decode threshold number of pairs of coded values associated with the one of the first plurality of data segments to recapture the one of the first plurality of data segments and is able to decode coded values of the decode threshold number of pairs of coded values associated with the one of the second plurality of data segments to recapture the one of the second plurality of data segments.

4. The method of claim 1, wherein the outputting the at least one pair of coded values further comprises:

receiving a request for at least one additional pair of coded values from the receiving entity; and

outputting the at least one pair of coded values to the receiving entity when the at least one additional pair of coded values is available.

5. The method of claim 1, wherein the encoding matrix comprises at least one of:

a Reed-Solomon based encoding matrix, an on-line coding based matrix, a Cauchy Reed-Solomon based encoding matrix, a forward error correction based matrix, and an erasure code based matrix.

6. The method of claim 1 further comprises:

locally storing the coded matrix for a given period of time.

7. The method of claim 1 further comprises:

concurrently receiving a third data stream with the first and second data streams;

segmenting each of the first, second, and third data streams to produce the first plurality of data segments, the second plurality of data segments, and a third plurality of data segments corresponding to the third data stream;

dividing one of the third plurality of data segments into a third plurality of data blocks, wherein the one of the third plurality of data segments is time aligned with the one of the first plurality of data segments and with the one of the second plurality of data segments;

creating the data matrix from the first, second, and third plurality of data blocks;

generating the coded matrix by multiplying the data matrix with the encoding matrix; and

outputting at least one trio of coded values of the coded matrix to the receiving entity, wherein a trio of coded values of the at least one trio of coded values includes the coded value corresponding to the one of the first plurality of data segments, the coded value corresponding to the one of the second plurality of data segments, and a coded value corresponding to the one of the third plurality of data segments.

8. The method of claim 1, wherein the creating the data matrix comprises:

placing first time corresponding data blocks of the first and second plurality of data blocks into a first row of the data matrix; and

placing second time corresponding data blocks of the first and second plurality of data blocks into a second row of the data matrix.

9. The method of claim 1 further comprises:

the first data stream corresponding to a first recording of an environment, wherein the environment includes at least one of a physical space, a status, and a condition; and

the second data stream corresponding to a second recording of the environment.

10. A dispersed storage (DS) module comprises:

a first module, when operable within a computing device, causes the computing device to;

concurrently receive a first data stream and a second data stream for transmission to a receiving entity;

a second module, when operable within the computing device, causes the computing device to;

segment each of the first and second data streams to produce a first plurality of data segments corresponding to the first data stream and a second plurality of data segments corresponding to the second data stream;

divide one of the first plurality of data segments into a first plurality of data blocks;

divide one of the second plurality of data segments into a second plurality of data blocks, wherein the one of the first plurality of data segments is time aligned with the one of the second plurality of data segments; and

create a data matrix from the first and second plurality of data blocks;

a third module, when operable within the computing device, causes the computing device to;

generate a coded matrix by multiplying the data matrix with an encoding matrix; and

a fourth module, when operable within the computing device, causes the computing device to;

output at least one pair of coded values of the coded matrix to the receiving entity, wherein a pair of coded values of the at least one pair of coded values includes a coded value corresponding to the one of the first plurality of data segments and a coded value corresponding to the one of the second plurality of data segments.

11. The DS module of claim 10, wherein the fourth module functions to output the at least one pair of coded values by:

outputting pairs of coded values of the coded matrix in a sequential order corresponding to a time ordering of the first and second plurality of data blocks such that the receiving entity is able to decode the pairs of coded values to maintain concurrency of the first and second data streams.

12. The DS module of claim 10, wherein the fourth module further functions to output the at least one pair of coded values by:

outputting a decode threshold number of pairs of coded values of the coded matrix such that the receiving entity is able to decode coded values of the decode threshold number of pairs of coded values associated with the one of the first plurality of data segments to recapture the one of the first plurality of data segments and is able to decode coded values of the decode threshold number of pairs of coded values associated with the one of the second plurality of data segments to recapture the one of the second plurality of data segments.

13. The DS module of claim 10, wherein the fourth module further functions to output the at least one pair of coded values by:

receiving a request for at least one additional pair of coded values from the receiving entity; and

outputting the at least one additional pair of coded values to the receiving entity when the at least one additional pair of coded values are available.

14. The DS module of claim 10, wherein the encoding matrix comprises at least one of:

a Reed-Solomon based encoding matrix, an on-line coding based matrix, a Cauchy Reed-Solomon based encoding matrix, a forward error correction based matrix, and an erasure code based matrix.

15. The DS module of claim 10 further comprises:

the third module further functions to locally store the coded matrix for a given period of time.

16. The DS module of claim 10 further comprises:

the first module further functions to concurrently receive a third data stream with the first and second data streams;

the second module further functions to;

segment each of the first, second, and third data streams to produce the first plurality of data segments, the second plurality of data segments, and a third plurality of data segments corresponding to the third data stream;

divide one of the third plurality of data segments into a third plurality of data blocks, wherein the one of the third plurality of data segments is time aligned with the one of the first plurality of data segments and with the one of the second plurality of data segments; and

create the data matrix from the first, second, and third plurality of data blocks;

the third module further functions to generate the coded matrix from the data matrix and the encoding matrix; and

the fourth module further functions to output at least one trio of coded values of the coded matrix to the receiving entity, wherein a trio of coded values of the at least one trio of coded values includes the coded value corresponding to the one of the first plurality of data segments, the coded value corresponding to the one of the second plurality of data segments, and a coded value corresponding to the one of the third plurality of data segments.

17. The DS module of claim 10, wherein the second module functions to create the data matrix by:

placing first time corresponding data blocks of the first and second plurality of data blocks into a first row of the data matrix; and

placing second time corresponding data blocks of the first and second plurality of data blocks into a second row of the data matrix.

18. The DS module of claim 10 further comprises:

the first data stream corresponding to a first recording of an environment, wherein the environment includes at least one of a physical space, a status, and a condition; and

the second data stream corresponding to a second recording of the environment.