Algorithms for Server Rebuild - Scalable Continuous Media Streaming Systems - page 256

14.6.1 Rebuild Rate Analysis
To analyze the mixed distributed-baseline rebuild, we allocate a fraction µ (0 ≤ µ ≤ 1) of the

server capacity to distributed rebuild, and the remaining fraction (1 ) to baseline rebuild.

Assuming all idle capacities in the remaining servers are employed for data rebuild, then the
aggregate rate at which data are transferred to the spare server will be equal to

− µ

S S (1 − ρ )( N S − 1) µ

R mixed = + S S (1 − ρ )(1 − µ ) (14.7)

2 N S − 3

where the first and second terms are the rebuild data rates generated from distributed rebuild
and baseline rebuild respectively.
Differentiating equation (14.7) with respect to

µ

, we obtain

) N S − 1

dR mixed
d

1
2 N S −

= S S (1 − ρ

3 −

(14.8)

µ

< ∀

N S ≥

0 3

Therefore, for systems with three or more servers reducing (i.e., allocatingmore idle capacity

to baseline rebuild) always increases the aggregate data rebuild rate. When N S =

µ

2, the rebuild

rate is independent of ,we

invoke the constraint that the aggregate rate at which data are transmitted to the spare server
cannot exceed S S :

µ and simply equal to S S (1 − ρ ). To find the lower bound for µ

S S (1 − ρ )( N S − 1) µ

+ S S (1 − ρ )( N S − 1)(1 − µ ) ≤ S S (14.9)

2 N S − 3

Solving for , we can then obtain its lower bound subject to the spare server's capacity

constraint and the constraint that

µ

µ ≥ 0:

(1 − (1 − ρ )( N S − 1))

1) 1
2 N S −

1 ,

for ρ ≤ (1 − 1 / ( N S − 1))

µ =

(1 − ρ )( N S −

3 −

(14.10)

0 , otherwise

Using this allocation ratio all idle capacities in the system will be fully utilized. Substituting
equation (14.10) into equation (14.7) gives the maximum rebuild rate:

S S [1 + (1 − ρ )( N S − 1)]

for ρ ≤ (1 − 1 / ( N S − 1))

R mixed = (14.11)

2( N S − 1)

S S (1 − ρ ) otherwise

14.6.2 Optimality
In this section, we derive the optimal rebuild rate for a system and show that the mixed
distributed-baseline rebuild scheme can achieve this optimal rate. We assume that (1) unavail-
able data are rebuilt automatically without human intervention using erasure-correcting code
computation; (2) all processing is performed by the remaining active servers and the spare