Information Technology Reference
In-Depth Information
15.3 Row-Permutated Data Reorganization
We present in this section the Row-Permutated Data Reorganization algorithm to redistribute
media data after a new node is added to the system. We use two performance metrics, namely,
data reorganization overhead and streaming load balance to compare its performance with the
round-robin data reorganization algorithm [2] and the SCADDAR algorithm [3].
15.3.1 Placement Policy
In striped storage a media object is first divided into fixed-size blocks, denoted by
v
i
,
j
, where
i
1) is the media block number within
the same group. To maintain streaming load balance it is necessary to ensure that every block
in the same group resides in a different node of the system.
As Ghandeharizadeh and Kim's study [2] showed, the data reorganization overhead in-
curred in maintaining the round-robin data placement order is very high. This is illustrated
in Figure 15.1 which shows the data placement before and after adding a node to a 4-node
system. The shaded data blocks all have to be moved from one node to another to restore
the round-robin placement in the new 5-node configuration. This obviously incurs significant
overhead.
In streaming applications, the client will process and play back media data sequentially
(ignoring interactive playback control). This implies that if the client always receives one
group of media data before playback, then the exact order in which the data blocks arrival at
the client will become irrelevant. Therefore, instead of enforcing the round-robin placement
order we can relax the constraint to reduce the number of block movements - row-permutated
placement policy.
∈
0
,
1
,...
is the group number and
j
∈
0
,
1
,...,
(
N
−
v
0,0
v
0,1
v
0,2
v
0,3
v
0,0
v
0,1
v
0,2
v
0,3
v
0,4
v
0,4
v
1,0
v
1,1
v
1,2
v
1,0
v
1,1
v
1,2
v
1,3
v
1,4
v
1,3
v
1,4
v
2,0
v
2,1
v
2,0
v
2,1
v
2,2
v
2,3
v
2,4
v
3,0
v
3,1
v
3,2
v
3,3
v
2,2
v
2,3
v
2,4
v
3,0
v
3,4
.
.
.
.
.
v
3,1
v
3,2
v
3,3
v
3,4
.
.
.
.
n
0
n
1
n
2
n
3
n
4
n
0
n
1
n
2
n
3
n
4
Before reorganization
After reorganization
Figure 15.1
Reorganization under round-robin placement (from 4 to 5 nodes). The shaded blocks all
need to be relocated to form the new configuration
Search WWH ::
Custom Search