Distributed storage system with high bandwidth utilization

• US 20090106269A1
• Filed: 12/20/2008
• Published: 04/23/2009
• Est. Priority Date: 06/20/2006
• Status: Active Grant

• Current Assignee: Patentvc Limited
• Original Assignee: Patentvc Limited
• Inventors: Thieberger, Gil, Zuckerman, Gal
• Granted Patent: US 8,677,008 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 16/70 of video data
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1044 Group management mechanisms management of multicast group membership H04L12/185; reconfiguring of node membership in a computing system to eliminate errors G06F11/1425
• CPC Class Codes: H04L 67/1046 Joining mechanisms

Abstract

A distributed storage system comprising a plurality of storage-and-computing elements, each storing a plurality of small content fragments associated with a plurality of contents, wherein a content retrieval load is shared between the storage-and-computing elements such that approximately the total uplink bandwidth of the distributed storage system can be utilized, on a continuous basis, by virtually any combination of multiple storage-and-computing elements simultaneously retrieving many contents or retrieving the same content with different time shifts.

Claims

1. A distributed storage and retrieval system comprising:

a plurality of storage-and-computing elements, each storage-and-computing element stores a plurality of content fragments according to fragment distribution information featuring a low autocorrelation, and can retrieve other stored content fragments from other storage-and-computing elements;

the content fragments are associated with a plurality of streaming contents;

wherein the distributed storage and retrieval system can support, on a continuous basis, ‘

N’

storage-and-computing elements retrieving ‘

N’

streaming contents concurrently, where ‘

N’

approximately approaches the aggregated uplink throughput of all participating storage-and-computing elements divided by the average bitrate of the streams retrieved by the storage-and-computing elements.

2. The distributed storage and retrieval system of claim 1, wherein ‘

N’

is almost independent of what streaming contents are retrieved by the storage-and-computing elements.

3. The distributed storage and retrieval system of claim 1, wherein ‘

N’

is almost independent of the number of storage-and-computing elements retrieving the same streaming contents.

4. The distributed storage and retrieval system of claim 1, wherein the plurality of content fragments are distributed approximately homogeneously between the storage-and-computing elements which are relevant to the retrieving, and the average content fragment size is between about 1 KB and 64 KB.

5. The distributed storage and retrieval system of claim 1, wherein each streaming content is associated with different fragment distribution information and each fragment distribution information features a low autocorrelation and a low correlation with other fragment distribution information.

6. A system comprising:

‘

N’

storage-and-computing elements having an aggregated uplink bandwidth ‘

B’ and

an aggregated storage ‘

S’

;

the ‘

N’

storage-and-computing elements store ‘

M’

unique contents having an aggregated size approaching ‘

S’

;

wherein the system can provide, on a continuous basis, concurrent transmissions of ‘

K’

streams of almost any combination of streaming or progressive download contents having a total bandwidth approaching B, with almost no coordination or cooperation needed between the different storage-and-computing elements.

7. The system of claim 6, wherein ‘

N’

is greater than 30, the bandwidth of the average stream is between about 100 Kbps and 20 Mbps, B/N is between about 100 Kbps and 25 Mbps, the average content size is between about 50 MB and 20 GB, and the duration of time between requesting any of the ‘

K’

streams and being able to play the stream is less than about 2 minutes.

8. The system of claim 7, wherein the aggregated size of the ‘

M’

contents is between about 0.5 times ‘

S’ and

0.95 times ‘

S’

, S/N is between about 64 MB and 20 GB, and the duration of time between requesting almost any of the ‘

K’

streams and being able to play the stream is less than about 15 seconds.

9. The system of claim 7, wherein most or all of the ‘

N’

storage-and-computing elements comprise one or more of the following;

the same storage space, or the same uplink bandwidth.

10. The system of claim 6, wherein the contents are comprised of small content fragments that are distributed approximately homogeneously between the storage-and-computing elements.

11. The system of claim 10, wherein the plurality of the small content fragments are distributed among the storage-and-computing elements utilizing a distribution function having a low autocorrelation and a low correlation with other distribution functions used by the system.

12. A system comprising:

‘

N’

storage-and-computing elements having an aggregated uplink bandwidth ‘

B’ and

an aggregated storage ‘

S’

;

the ‘

N’

storage-and-computing elements store ‘

M’

unique contents having an aggregated size approximately approaching ‘

S’

divided by ‘

R’

, wherein ‘

R’

denotes the number of times that the ‘

M’

contents are duplicated in the aggregated storage;

wherein the system can provide, on a continuous basis, concurrent transmissions of ‘

K’

streams of almost any combination of contents, with almost no coordination or cooperation needed between the different storage-and-computing elements, and the ‘

K’

streams have a total bandwidth approximately approaching ‘

B’

,

13. The system of claim 12, wherein the storage-and-computing elements are associated with storage element types, ‘

R’

equals the average number of storage-and-computing elements per storage element type, and ‘

R’

ranges between about 2 and 10,000.

14. The system of claim 12, wherein the bandwidth of the average stream is between about 100 Kbps and 20 Mbps, and B/N is between about 100 Kbps and 25 Mbps.

15. The system of claim 12, wherein the average content size is between about 50 MB and 20 GB, and S/N is between about 64 MB and 20 GB.

16. The system of claim 12, wherein the contents are comprised of small content fragments that are distributed approximately homogeneously between the storage-and-computing elements.

17. A distributed storage system comprising:

a plurality of storage-and-computing elements, each storing a plurality of small content fragments associated with a plurality of contents, wherein a content retrieval load is shared between the storage-and-computing elements such that approximately the total uplink bandwidth of the distributed storage system can be utilized, on a continuous basis, by virtually any combination of multiple storage-and-computing elements simultaneously retrieving many contents or retrieving the same content with different time shifts.

18. The distributed storage system of claim 17, wherein each content is associated with a different fragment distribution information and the plurality of content fragments are distributed between the storage-and-computing elements according to the fragment distribution information, and each fragment distribution information features a low autocorrelation and a low correlation with the other fragment distribution information.

19. The distributed storage system of claim 18, wherein the content delivery method is streaming or progressive download.

20. The distributed storage system of claim 18, wherein the plurality of storage-and-computing elements are spanned by one network node, and the network node is selected from the group of:

DSLAM, B-RAS, IP services switch, IP services router, or a combination thereof.

21. The distributed storage system of claim 17, wherein the contents are streaming or progressive download contents and up to ‘

N’

storage-and-computing elements, within ‘

T’

seconds of receiving a request, can play the contents, wherein ‘

T’

is shorter than BUF/(3×

R) seconds, wherein BUF is the buffered data needed to start playing the content (expressed in Kbits), ‘

R’

(expressed in Kbps) is the average available uplink bandwidth of a storage-and-computing element, and ‘

N’

is approximately proportional to the available aggregated uplink bandwidth of the storage-and-computing elements divided by an average streaming content bit rate.