Efficient Management of Fragmented Replica in Data Grids

Related Work

Chang et al. introduced the concept of fragmented replicas and proposed algorithms for their retrieval (Chang & Chen, 2007). Though the transmission time can be improved by either the AR algorithm or the OOCA algorithm, their proposed algorithms do not always find an optimal solution. For instance, the OOCA will select the appropriate server for data blocks one by one. In each run, the algorithm will select the server having the minimum accumulative transfer time after serving the subsequent block.

We give an example with the following assumptions to explain why the OOCA algorithm cannot get the optimal solution. There are four servers, S₁, S₂, S₃ and S₄, in the system and the transferring times of one block by the servers are 6, 13, 8, and 17, respectively. The target file consists of four data blocks, B₁, B₂, B₃ and B₄. The possession relationship between servers and blocks is represented by a table as shown in Figure 1. The value of each element is either 1 or 0. If the server S_i has the block B_j, the value of the corresponding element e(i, j) is 1.

Figure 1.

The relation between servers and blocks. S_i has a replica of B_j if (S_i, B_j) is 1.