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

Network

. . .

S 0 S 1 S 2

S Ns−1

S N−1

Spare Server

Figure 14.5 The baseline rebuild algorithm

then rebuilds the data lost in the failed server (Figure 14.5). This algorithm is similar to the
baseline rebuild scheme in disk arrays [3].
To recover an unavailable data unit we need to perform erasure correction using the remain-
ing ( N S −

1) data/redundant units. Since we want to keep the process transparent to normal
streaming sessions, we can only utilize the servers' idle capacities. Assuming the system is
running at a utilization of ρ ∈ [0,1], the average available transfer rate from each server will

be equal to S S (1 − ρ ). The aggregate data transfer rate of the remaining ( N S − 1) servers is

therefore equal to

r = S S (1 − ρ )( N S − 1) (14.2)

Now as the spare server has a transfer capacity of S S , the aggregate data rate r will exceed the
spare server's transfer capacity if

ρ − /

( N S −

1)). This is stated in the Theorem
14.1 which computes the upper limit on the baseline rebuild rate.

is less than (1

Theorem 14.1. The data rebuild rate of baseline rebuild, denoted by R baseline is bounded by
the capacity S S of the spare server and is given by

S S /

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

R baseline = (14.3)

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

Proof. Case 1: ρ< (1 − 1 / ( N S − 1))

From equation (14.2):

r = S S (1 − ρ )( N S − 1)

≥ S S (1 − (1 − 1 / ( N S − 1)))( N S − 1)

= S S