Algorithms for System Expansion - Scalable Continuous Media Streaming Systems - page 273

0.4

SCADDAR

0.35

0.3

10 -RPDR

0.25

5- RPDR

0.2

2- RPDR

0.15

0.1

Round-Robin
and 1 -RPDR

0.05

0

0 50 100 150 200

System Size (nodes)

Figure 15.10 Comparison of streaming load balance

will need to update the redundant data blocks according to the newly reorganized data place-
ments. In this section we develop a Sequential Redundant Data Update (SRDU) algorithm that
exploits structure of the Reed-Solomon erasure correction (RSE) code [4-6] to substantially
reduce the number of block movements required in redundant data update.

15.4.1 Redundant Data Regeneration
Figure 15.11 depicts the placement of data and redundant blocks in a system of 6 nodes. There
are two redundant data blocks per parity group, denoted by c i , 0 and c i , 1 for parity group i .
This enables the system to survive two node failures. Note that while the round-robin data
placement order is shown in Figure 15.11, it is not a requirement. The exact ordering of the
data blocks within a parity group is irrelevant to redundant data block generation. Thus, the
RPDR algorithm is also compatible with redundant data generation.
After adding a new node to the system and reorganizing the data blocks, the new data
block placements become the one shown in Figure 15.12. Again the order of data block
placements is arbitrary and irrelevant to the process of redundant data generation. Under this
new configuration the original redundant data

will need to be updated.
In general, for a system of N nodes and h redundancies, we will need all ( N

{ c i , j | i , j ∈ 0 , 1 ,... }

h ) data blocks
in a parity group to compute the corresponding h redundant blocks. As data and redundant
blocks of the same parity group are all stored individually in separate nodes, the system will
need to send all data blocks to the redundant nodes to generate the new redundant blocks. This
simple algorithm is clearly very inefficient.

−