US6748441B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data carousel receiving and caching
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1999-12-02
•
Granted: 2004-06-08
•
Expires: 2019-12-02
Abstract
Abstract Data objects are sent using a data carousel and forward error correction. This involves segregating a file into groups, wherein each group represents k data blocks. From the k data blocks of each group, n erasure-encoded blocks are calculated, where n>k. The n erasure-encoded blocks are sent in a round-robin fashion using IP multicast technology: the first erasure-encoded block for each group, then the second block of each group, and so on. At a receiver, the blocks are stored on disk as they are received. However, they are segregated by group as they are stored. When reception is complete, each group is read into RAM, decoded, and written back to disk. In another embodiment, the receiver segregates allocated disk space into areas corresponding to sets of groups. Received blocks are then segregated only by set as they are written to disk. One or more RAM buffers can be used in this embodiment. When reception is complete, each set is read into RAM, decoded, and then written back to disk.
Inventors
- 👤 David James Gemmell
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 07:57
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0041; H04L1/0056; H04L1/0057; H04L1/0071; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L12/1863; H04L12/1877; H04L67/00; H04L67/01; H04L67/06; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/329
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
116 words
A method of reconstructing a data object that is transmitted from a remote source using a data carousel of erasure-encoded blocks, the erasure-encoded blocks being encoded in groups, wherein the erasure-encoded blocks of respective groups are transmitted non-contiguously, the method comprising the following steps: receiving the erasure-encoded blocks of the data carousel, the erasure-encoded blocks being encoded in groups, wherein the erasure-encoded blocks of respective groups are transmitted non-contiguously from the remote source; storing erasure-encoded blocks of the groups in secondary storage; the storing step including a step of segregating the erasure-encoded blocks into sets of groups within the secondary storage; decoding each set of groups after receiving the erasure-encoded blocks of the set of groups.
Claim 2
Independent Claim
116 words
A method of reconstructing a data object that is transmitted from a remote source using a data carousel of erasure-encoded blocks, the erasure-encoded blocks being encoded in groups, wherein the erasure-encoded blocks of respective groups are transmitted non-contiguously, the method comprising the following steps: receiving the erasure-encoded blocks of the data carousel, the erasure-encoded blocks being encoded in groups, wherein the erasure-encoded blocks of respective groups are transmitted non-contiguously from the remote source; storing erasure-encoded blocks of the groups in secondary storage; the storing step including a step of segregating the erasure-encoded blocks into sets of groups within the secondary storage; decoding each set of groups after receiving the erasure-encoded blocks of the set of groups.
Claim 3
Dependent Claim
28 words
A method as recited in claim 1 , further comprising a step of buffering a plurality of erasure-encoded blocks in primary memory before storing them in secondary storage.
Claim 4
Dependent Claim
54 words
A method as recited in claim 1 , further comprising a step of buffering a plurality of erasure-encoded blocks in primary memory buffers before storing the erasure-encoded blocks in secondary storage, wherein each primary memory buffer has a number of blocks equal to at least the number of groups in each set of groups.
Claim 5
Dependent Claim
38 words
A method as recited in claim 1 , further comprising a step of buffering any contiguously-received erasure-encoded blocks that are from a common set of groups in primary memory before storing the contiguously-received erasure-encoded blocks in secondary storage.
Claim 6
Dependent Claim
65 words
A method as recited in claim 1 , further comprising: buffering contiguously-received erasure-encoded blocks in a primary memory buffer as long as said contiguously-received erasure-encoded blocks are from a common set of groups; upon receiving a new erasure-encoded block from a set of groups other than said common set of groups, flushing the primary memory buffer to secondary storage before buffering the new erasure-encoded block.
Claim 7
Dependent Claim
76 words
A method as recited in claim 1 , further comprising: buffering each received erasure-encoded block in one of three primary memory buffers before storing the erasure-encoded blocks in secondary storage; wherein each primary memory buffer has a number of blocks equal to at least the number of groups in each set of groups; flushing each primary memory buffer after it contains a number of blocks equal to the number of groups in each set of groups.
Claim 8
Dependent Claim
36 words
A method as recited in claim 1 , further comprising: buffering received erasure-encoded blocks in a plurality of primary memory buffers corresponding respectively to different sets of groups before storing the erasure-encoded blocks in secondary storage.
Claim 9
Dependent Claim
50 words
A method as recited in claim 1 , further comprising: buffering received erasure-encoded blocks in a plurality of primary memory buffers corresponding respectively to different sets of groups before storing the erasure-encoded blocks in secondary storage; flushing each primary memory buffer to secondary storage when said primary buffer becomes full.
Claim 10
Dependent Claim
96 words
A method as recited in claim 1 , further comprising: buffering received erasure-encoded blocks in a primary memory buffer before storing the erasure-encoded blocks in secondary storage; while receiving, repeatedly selecting one set of groups and writing the erasure-encoded blocks of said set from the primary memory buffer to the determined location in the allocated secondary storage for the contiguous data blocks represented by the selected set of groups; wherein the selecting step comprises: if possible, selecting a set of groups having at least a predefined number of erasure-encoded blocks buffered in the primary memory buffer.
Claim 11
Dependent Claim
120 words
A method as recited in claim 1 , further comprising: buffering the received erasure-encoded blocks in a primary memory buffer before storing the erasure-encoded blocks in secondary storage; while receiving, repeatedly selecting one set of groups and writing the erasure-encoded blocks of said selected set from the primary memory buffer to the determined location in the allocated secondary storage for the contiguous data blocks represented by the selected set of groups; wherein the selecting step comprises: whenever possible, selecting a set of groups having at least a predefined number b of erasure-encoded blocks buffered in the primary memory buffer; wherein the primary memory buffer has a size of bc+b−c+1 blocks, and c is the number of groups in a set.
Claim 12
Dependent Claim
59 words
A method as recited in claim 1 , wherein the decoding step comprises: reading the set of groups of erasure-encoded blocks into primary memory; decoding said set of groups of erasure-encoded blocks to produce decoded blocks of the data object; replacing said set of groups of erasure-encoded blocks in secondary storage with the decoded blocks of the data object.
Claim 13
Independent Claim
119 words
A method comprising: reconstructing a data object on secondary storage, wherein the data object is transmitted from a remote source using a data carousel of erasure-encoded blocks, the erasure-encoded blocks being encoded in groups that represent contiguous data blocks of the data object, wherein the erasure-encoded blocks of respective groups are transmitted non-contiguously, the reconstructing comprising: allocating secondary storage for the data object and determining locations in the allocated secondary storage for the respective data blocks represented by sets of contiguous groups of erasure-encoded blocks; receiving the erasure-encoded blocks; storing erasure-encoded blocks of any particular set of groups at the determined location in the allocated secondary storage for the contiguous data blocks represented by the particular set of groups.
Claim 14
Independent Claim
119 words
A method comprising: reconstructing a data object on secondary storage, wherein the data object is transmitted from a remote source using a data carousel of erasure-encoded blocks, the erasure-encoded blocks being encoded in groups that represent contiguous data blocks of the data object, wherein the erasure-encoded blocks of respective groups are transmitted non-contiguously, the reconstructing comprising: allocating secondary storage for the data object and determining locations in the allocated secondary storage for the respective data blocks represented by sets of contiguous groups of erasure-encoded blocks; receiving the erasure-encoded blocks; storing erasure-encoded blocks of any particular set of groups at the determined location in the allocated secondary storage for the contiguous data blocks represented by the particular set of groups.
Claim 15
Dependent Claim
20 words
A method as recited in claim 12 , further comprising: decoding each set of groups after storing their erasure-encoded blocks.
Claim 16
Dependent Claim
81 words
A method as recited in claim 12 , further comprising: after receiving and storing the erasure-encoded blocks for a given set of groups, reading the given set of groups into primary memory from secondary storage; decoding the erasure-encoded blocks of the given set of groups to produce the data blocks represented by the given set of groups; replacing the erasure-encoded blocks of the given set of groups in secondary storage with the data blocks represented by the given set of groups.
Claim 17
Dependent Claim
34 words
A method as recited in claim 12 , the storing step further including a step of storing the erasure-encoded blocks of each set of groups in the order in which the blocks are received.
Claim 18
Dependent Claim
29 words
A method as recited in claim 12 , further comprising a step of buffering a plurality of the erasure-encoded blocks in primary memory before storing them in secondary storage.
Claim 19
Dependent Claim
55 words
A method as recited in claim 12 , further comprising a step of buffering a plurality of the erasure-encoded blocks in primary memory buffers before storing the erasure-encoded blocks in secondary storage, wherein each primary memory buffer has a number of blocks equal to at least the number of groups in each set of groups.
Claim 20
Dependent Claim
38 words
A method as recited in claim 12 , further comprising a step of buffering any contiguously-received erasure-encoded blocks that are from a common set of groups in primary memory before storing such contiguously-received erasure-encoded blocks in secondary storage.
Claim 21
Dependent Claim
65 words
A method as recited in claim 12 , further comprising: buffering contiguously-received erasure-encoded blocks in a primary memory buffer as long as the contiguously-received erasure-encoded blocks are from a common set of groups; upon receiving a new erasure-encoded block from a set of groups other than said common set of groups, flushing the primary memory buffer to secondary storage before buffering the new erasure-encoded block.
Claim 22
Dependent Claim
76 words
A method as recited in claim 12 , further comprising: buffering each received erasure-encoded block in one of three primary memory buffers before storing the erasure-encoded blocks in secondary storage; wherein each primary memory buffer has a number of blocks equal to at least the number of groups in each set of groups; flushing each primary memory buffer after it contains a number of blocks equal to the number of groups in each set of groups.
Claim 23
Dependent Claim
36 words
A method as recited in claim 12 , further comprising: buffering received erasure-encoded blocks in a plurality of primary memory buffers corresponding respectively to different sets of groups before storing the erasure-encoded blocks in secondary storage.
Claim 24
Dependent Claim
50 words
A method as recited in claim 12 , further comprising: buffering received erasure-encoded blocks in a plurality of primary memory buffers corresponding respectively to different sets of groups before storing the erasure-encoded blocks in secondary storage; flushing each primary memory buffer to secondary storage when said primary buffer becomes full.
Claim 25
Dependent Claim
96 words
A method as recited in claim 22 , further comprising: buffering received erasure-encoded blocks in a primary memory buffer before storing the erasure-encoded blocks in secondary storage; while receiving, repeatedly selecting one set of groups and writing the erasure-encoded blocks of said set from the primary memory buffer to the determined location in the allocated secondary storage for the contiguous data blocks represented by the selected set of groups; wherein the selecting step comprises: if possible, selecting a set of groups having at least a predefined number of erasure-encoded blocks buffered in the primary memory buffer.
Claim 26
Dependent Claim
120 words
A method as recited in claim 12 , further comprising: buffering the received erasure-encoded blocks in a primary memory buffer before storing the erasure-encoded blocks in secondary storage; while receiving, repeatedly selecting one set of groups and writing the erasure-encoded blocks of said selected set from the primary memory buffer to the determined location in the allocated secondary storage for the contiguous data blocks represented by the selected set of groups; wherein the selecting step comprises: whenever possible, selecting a set of groups having at least a predefined number b of erasure-encoded blocks buffered in the primary memory buffer; wherein the primary memory buffer has a size of bc+b−c+1 blocks, and c is the number of groups in a set.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-06-08 | 2007-12-08 | 2008-06-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-06-08 | 2011-12-08 | 2012-06-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-06-08 | 2015-12-08 | 2016-06-08 | $7700.00 | Window Closed / Lapsed |