Network coded storage with multi-resolution codes

Abstract

Multi-resolution encoded files are stored on a plurality of disk drives using systematic network coded storage. In some embodiments, the stored files are used to provide video streaming services for users.

What is claimed is: 
     
       1. In a system that uses multi-resolution coding to store files at multiple different resolutions within a plurality of disk drives, a method comprising:
 storing a base layer of a first file on each of a first set of disk drives in the plurality of disk drives, the base layer in non-network coded form; 
 generating linear combinations of the base layer of the first the and a first refinement layer of the first file using systematic network coding; and 
 storing a linear combination of the base layer of the first file and the first refinement layer of the first file on each of a second set of disk drives in the plurality of disk drives. 
 
     
     
       2. The method of  claim 1  further comprising:
 receiving a request for the first file from a user; 
 
       retrieving a first linear combination of the base layer of the first file and the first refinement layer of the first file from one of the second set of disk drives; 
       determine if any of the disk drives in the first set of disk drives has sufficient bandwidth available to process the request;
 in response to determining that at least one the disk drives in the first set of disk drives has sufficient bandwidth available to process the request, retrieving the base layer of the first file from one of the first set of disk drives; 
 in response to determining that none of the disk drives in the first set of disk drives has sufficient bandwidth available to process the request, retrieving a second linear combination of the base layer of the first file and the first refinement layer of the first file from one of the second set of disk drives; and 
 sending data to the user based upon the retrieved data. 
 
     
     
       3. The method of  claim 2  wherein receiving the request for the first file comprises receiving a request for the first file at a specified resolution. 
     
     
       4. The method of  claim 3  wherein sending data to the user based upon the retrieved data comprises sending data to the user at the specified resolution. 
     
     
       5. The method of  claim 3  wherein sending data to the user based upon the retrieved data comprises sending data to the user at a resolution different from the specified resolution. 
     
     
       6. The method of  claim 1  wherein generating linear combinations of the base layer of the first file and a first refinement layer of the first file comprises generating a linear combination for each of the second set of disk drives using different random coefficients. 
     
     
       7. The method of  claim 1 , wherein storing a linear combination of the base layer and the first refinement layer on each of the second set of disk drives includes storing the different random coefficients with each linear combination on each of the second set of disk drives. 
     
     
       8. A method for storing files within a plurality of disk drives in a system that uses multi-resolution coding, the method comprising:
 storing a base layer of a first file on each of a first set of disk drives in the plurality of disk drives; 
 generating a linear combination of the base layer of the first file and at least one refinement layer of the first file using random coefficients; and 
 storing the linear combination of the base layer of the first file and the at least one refinement layer of the first file on each of a second set of disk drives in the plurality of disk drives. 
 
     
     
       9. The method of  claim 8  wherein:
 storing the base layer includes storing the base layer in non-network coded form, 
 generating a linear combination of the base layer of the first file and at least one refinement layer includes generating one or more linear combinations of the base layer of the first file and a first refinement layer of the first file using systematic network coding; and 
 storing the linear combination of the base layer of the first file and the at least one refinement layer of the first file on each of a second set of disk drives in the plurality of disk drives includes storing at least one of the one or more linear combinations of the base layer of the first file and the first refinement layer of the first file on each of a second set of disk drives in the plurality of disk drives. 
 
     
     
       10. The method of  claim 9  further comprising:
 receiving a request for the first file from a user; 
 retrieving a first linear combination of the base layer of the first file and the first refinement layer of the first file from one of the second set of disk drives; 
 determine if any of the disk drives in the first set of disk drives has sufficient bandwidth available to process the request; 
 in response to determining that at least one the disk drives in the first set of disk drives has sufficient bandwidth available to process the request, retrieving the base layer of the first file from one of the first set of disk drives; 
 in response to determining that none of the disk drives in the first set of disk drives has sufficient bandwidth available to process the request, retrieving a second linear combination of the base layer of the first file and the first refinement layer of the first file from one of the second set of disk drives; and 
 sending data to the user based upon the retrieved data. 
 
     
     
       11. The method of  claim 10  wherein receiving the request for the first file comprises receiving a request for the first file at a specified resolution. 
     
     
       12. The method of  claim 11  wherein sending data to the user based upon the retrieved data comprises sending data to the user at the specified resolution. 
     
     
       13. The method of  claim 8 , wherein:
 storing a linear combination of the base layer and the refinement layer on each of the second set of disk drives includes generating a linear combination for each of the second set of disk drives using different random coefficients. 
 
     
     
       14. The method of  claim 13 , wherein storing a linear combination of the base layer and the refinement layer on each of the second set of disk drives includes storing the different random coefficients with each linear combination on each of the second set of disk drives. 
     
     
       15. The method of  claim 8 , wherein the first set of disk drives and the second set of disk drives have no disk drives in common. 
     
     
       16. The method of  claim 8 , further comprising:
 storing a linear combination of the base layer of the first file, the refinement layer of the first file, and a second refinement layer of the first file on each of a third set of disk drives in the plurality of disk drives. 
 
     
     
       17. The method of  claim 8 , wherein the method is implemented in a data center associated with a content distribution network. 
     
     
       18. The method of  claim 8 , further comprising:
 storing a base layer of a second file on each of the first set of disk drives in the plurality of disk drives; and 
 storing a linear combination of the base layer of the second file and a refinement layer of the second file on each of the second set of disk drives in the plurality of disk drives. 
 
     
     
       19. The method of  claim 8 , wherein the first file includes a video file. 
     
     
       20. A system comprising:
 a plurality of disk drives; and 
 a controller to store files on the plurality of disk drives in multiple different resolutions using a multi-resolution code, the controller being configured to:
 store a base layer of a first file on each of a first group of disk drives in the plurality of disk drives; 
 generate a linear combination of the base layer of the first file and at least one refinement layer of the first file using random coefficients; and 
 store the linear combination of the base layer of the first file and the at least one refinement layer of the first file on each of a second group of disk drives in the plurality of disk drives. 
 
 
     
     
       21. The system of  claim 20 , wherein the controller is configured to store a linear combination of the base layer of the first file, a first refinement layer of the first file, and a second refinement layer of the first file on each of a third group of disk drives in the plurality of disk drives. 
     
     
       22. The system of  claim 20 , wherein the controller is configured to:
 generate the linear combination for each of the second set of disk drives using different random coefficients; and 
 store the random coefficients on the each of the second set of disk drives in association with the corresponding linear combination. 
 
     
     
       23. The system of  claim 20 , wherein the controller is configured to store a linear combination of the base layer of the first file, the first refinement layer of the first file, and a second refinement layer of the first file on each of a third set of disk drives in the plurality of disk drives. 
     
     
       24. The system of  claim 20 , further comprising:
 a plurality of servers for use in servicing requests from users, wherein each server in the plurality of servers is associated with a different set of disk drives within the plurality of disk drives. 
 
     
     
       25. The system of  claim 20 , wherein the system is part of a data center associated with a content distribution network. 
     
     
       26. The system of  claim 20 , wherein:
 the controller is configured to retrieve files from the plurality of disk drives in response to user requests, the controller to receive a user request for the first file at a next to lowest resolution and, in response thereto, retrieve a first linear combination of the base layer associated with the first file and the first refinement layer associated with the first file from a disk drive in the second group of disk drives, and retrieve either a base layer associated with the first file from a disk drive in the first group of disk drives or a second linear combination of the base layer associated with the first file and the first refinement layer associated with the first file from another disk drive in the second group of disk drives.