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

Network

. . . . . .

S 0 S 1 S S N−1 S Ns−1

Spare Server

k

Figure 14.6 The distributed rebuild algorithm

Interestingly, being the bottleneck in baseline rebuild the spare server is no longer the
limiting factor in distributed rebuild. The following theorem shows that the rebuild data rate
R distributed is always smaller than the transfer capacity of the spare server, regardless of the
system utilization ρ .

Theorem 14.2. In distributed rebuild, the rate of data transfer from the active servers to the
spare server will never exceed the capacity of the spare server.

Proof. We note that ( N S − 1) ≤ 2( N S − 3) for all N S ≥ 2 in (14.5) thus R distributed ≤ S S (1 − ρ )

S S .
The corresponding rebuild time in distributed rebuild is thus given by

U
R distributed =

U (2 N S − 3)

T distributed = (14.6)

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

14.6 Mixed Distributed Baseline Rebuild
In distributed rebuild, the spare server is never fully utilized. This is due to the fact that for
every data unit rebuilt, a total of (2 N S − 3) data/redundant units will need to be transferred

among the remaining active servers. By contrast, the ratio is only ( N S − 1) in baseline rebuild,

albeit at the cost of ( N S − 1) times more capacity required at the spare server. In other words,

in baseline rebuild the remaining servers are underutilized while in distributed rebuild the
spare server is underutilized. This suggests a mixed algorithm to rebuild part of the data using
distributed rebuild and the rest by baseline rebuild to maximize the server utilizations to reduce
the rebuild time.