A Random linear coding approach to distributed data storage

• US 20060149753A1
• Filed: 12/30/2004
• Published: 07/06/2006
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Board of Trustees of The University of Illinois, Massachusetts Institute of Technology
• Original Assignee: Board of Trustees of The University of Illinois, Massachusetts Institute of Technology
• Inventors: Medard, Muriel, Koetter, Ralf, Deb, Supratim
• Granted Patent: US 8,046,426 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is detrmined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.

Claims

1. A method of using random linear coding for performing distributed data storage in a peer-to-peer network, the method comprising:

breaking a file into a plurality of pieces;

determining a number of coded-pieces each peer can store;

determining the coded-pieces for each peer by taking random linear combination of all the pieces of the file;

calculating an associated code vector for said random combination of pieces; and

storing a respective random combination of coded pieces and the associated code vector at each peer of said number of peers.

2. The method of claim 1 wherein said calculating an associated code vector comprises calculating an associated code vector in accordance with the formula:

3. The method of claim 2 wherein said determining a random combination of particular pieces of said plurality of pieces to store at a peer is done in accordance with the formula:

4. The method of claim 1 further comprising retrieving the file.

5. The method of claim 4 wherein said retrieving the file comprises:

collecting code vectors from at least one peer;

viewing collected code vectors as a matrix;

determining whether a dimension of the matrix is equal to a predefined number, and when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and

when the dimension of the matrix equals the predefined number, then recovering said file using the collection of code vectors in the matrix.

6. The method of claim 5 wherein said viewing collected code vectors as a matrix comprises viewing said collected code vectors as a kr×

m matrix of F_q wherein k is the number of pieces stored at a peer, r is the number of peers and F_q is a matrix having vectors of size s in a field of size q.

7. The method of claim 5 wherein determining comprises determining when the dimension of the matrix is equal to the number of pieces the file is broken into.

8. A method of retrieving a file comprising:

collecting code vectors from at least one peer;

viewing collected code vectors as a matrix;

determining whether a dimension of the matrix is equal to a predefined number, and when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and

when the dimension of the matrix equals the predefined number, then recovering said file using the collection of code vectors in the matrix.

9. The method of claim 8 wherein said viewing collected code vectors as a matrix comprises viewing said collected code vectors as a kr×

m matrix of F_q wherein k is the number of pieces stored at a peer, r is the number of peers and F_q is a matrix having vectors of size s in a field of size q.

10. The method of claim 8 wherein determining comprises determining when the dimension of the matrix is equal to the number of pieces the file is broken into.

11. A computer readable medium having computer readable code thereon for providing a random linear coding approach to distributed data storage, the medium comprising:

instructions for breaking a file into a plurality of pieces;

instructions for determining a number of peers to use to store pieces of the file instructions for determining a random combination of particular pieces of said plurality of pieces to store at a peer of the number of peers in the network;

instructions for calculating an associated code vector for said random combination of particular pieces; and

instructions for storing a respective random combination of pieces and the associated code vector at each peer of said number of peers.

12. The computer readable medium of claim 11 wherein said instructions for calculating an associated code vector comprises instructions for calculating an associated code vector in accordance with the formula:

13. The computer readable medium of claim 12 wherein said instructions for determining a random combination of particular pieces of said plurality of pieces to store at a is done in accordance with the formula:

14. The computer readable medium of claim 11 further comprising instructions for retrieving the file.

15. The computer readable medium of claim 14 wherein said instructions for retrieving the file comprises:

instructions for collecting code vectors from at least one peer;

instructions for viewing collected code vectors as a matrix;

instructions for determining whether a dimension of the matrix is equal to a predefined number, and instructions for when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and

instructions for when the dimension of the matrix equals the predefined number, then recovering said file using the collection of code vectors in the matrix.

16. The computer readable medium of claim 15 wherein said instructions for viewing collected code vectors as a matrix comprises instructions for viewing said collected code vectors as a kr×

m matrix of F_q wherein k is the number of pieces stored at a peer, r is the number of peers and F_q is a matrix having vectors of size s in a field of size q.

17. The computer readable medium of claim 15 wherein instructions for determining comprises instructions for determining when the dimension of the matrix is equal to the number of pieces the file is broken into.

18. A computer readable medium having computer readable code thereon for retrieving a file previously stored using a random linear coding approach to distributed data storage, the medium comprising:

instructions for collecting code vectors from at least one peer;

instructions for viewing collected code vectors as a matrix;

instructions for determining whether a dimension of the matrix is equal to a predefined number, and instructions for when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and

instructions for when the dimension of the matrix equals the predefined number, then recovering said file using the collection of code vectors in the matrix.

19. The computer readable medium of claim 18 wherein said instructions for viewing collected code vectors as a matrix comprises instructions for viewing said collected code vectors as a kr×

m matrix of F_q wherein k is the number of pieces stored at a peer, r is the number of peers and F_q is a matrix having vectors of size s in a field of size q.

20. The computer readable medium of claim 18 wherein said instructions for determining comprises instructions for determining when the dimension of the matrix is equal to the number of pieces the file is broken into.