Method and Apparatus for Distributed Data Replication
First Claim
1. A distributed method for converting original data into a replica set comprising a plurality of unique replica fragments using a multicast tree of network nodes, said method comprising:
- performing first level encoding by encoding at least a portion of said original data at at least one first level network node to generate at least one first level intermediate encoded data block; and
for each of a plurality of further encoding levels (n), performing nth level encoding of at least one n-1 level intermediate encoded data block at at least one nth level network node in said multicast tree to generate at least one nth level intermediate encoded data block.
2 Assignments
0 Petitions
Accused Products
Abstract
Disclosed is a data replication technique for providing erasure encoded replication of large data sets over a geographically distributed replica set. The technique utilizes a multicast tree to store, forward, and erasure encode the data set. The erasure encoding of data may be performed at various locations within the multicast tree, including the source, intermediate nodes, and destination nodes. In one embodiment, the system comprises a source node for storing the original data set, a plurality of intermediate nodes, and a plurality of leaf nodes for storing the unique replica fragments. The nodes are configured as a multicast tree to convert the original data into the unique replica fragments by performing distributed erasure encoding at a plurality of levels of the multicast tree.
135 Citations
17 Claims
-
1. A distributed method for converting original data into a replica set comprising a plurality of unique replica fragments using a multicast tree of network nodes, said method comprising:
-
performing first level encoding by encoding at least a portion of said original data at at least one first level network node to generate at least one first level intermediate encoded data block; and
for each of a plurality of further encoding levels (n), performing nth level encoding of at least one n-1 level intermediate encoded data block at at least one nth level network node in said multicast tree to generate at least one nth level intermediate encoded data block. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for converting original data into a replica data set comprising a plurality of unique replica fragments, said method comprising:
-
performing first level encoding by encoding at least a portion of said original data at at least one network node to generate at least one first level intermediate encoded data block;
transmitting said at least one first level intermediate encoded data block to at least one other network node; and
performing second level encoding of said at least one first level intermediate encoded data block at said at least one other network node. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A system for converting original data into a replica data set comprising a plurality of unique replica fragments, said system comprising:
-
a source node storing said original data set;
a plurality of leaf nodes for storing said unique replica fragments; and
a plurality of intermediate nodes;
said source node, plurality of leaf nodes, and plurality of intermediate nodes logically configured as a multicast tree;
said nodes configured to convert said original data into said unique replica fragments by performing distributed erasure encoding at a plurality of levels of said multicast tree. - View Dependent Claims (15, 16, 17)
-
Specification