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

server; and (3) the transfer capacity of the spare server is all used in rebuild. The first assump-
tion excludes manual and hardware replacement schemes. The second assumption excludes
the use of back-up devices to reload data into the spare server. The third assumption guarantees
the transfer capacity available at the spare server. Note that the rebuild of unavailable units is
performed either at the spare server, the remaining ( N S − 1) servers, or partially done at both.

Therefore, we have the next lemma.

Lemma 14.1. For any unavailable data unit rebuilt and stored into the spare server, we need
at least (N S −

1 ) transmissions from the remaining active servers.

Proof. If the unavailable data unit is rebuilt by the spare server, then the ( N S − 1) data/redundant

units of the same parity group will need to be sent to the spare server, resulting in ( N S − 1)

transmissions.
If the unavailable data unit is rebuilt by one of the remaining servers, then ( N S −

2)
data/redundant units from servers other than the rebuild server and the spare server will need to
be sent to the rebuild server, resulting in ( N S − 2) transmissions. After that, the rebuild server

will send the rebuilt data unit to the spare server for storage, incurring one more transmission.
Together the whole process thus generates ( N S −

1) transmissions.

Each server contributes its idle transfer capacity to the rebuild process either for transmission,
reception, or both. Let be the proportion of transfer capacity each server has

used for transmission in the rebuild process. The sum of the transmission capacities of the
remaining servers is then equal to

ϕ { 0 ≤ ϕ ≤ 1

}

ϕ S S (1 − ρ )( N S − 1) (14.12)

Note that the transmitted data will have to be received. Therefore, the total reception capacities
must be at least as large as the total transmission capacities, i.e.,

(1 − ϕ ) S S (1 − ρ )( N S − 1) + S S ≥ ϕ S S (1 − ρ )( N S − 1) (14.13)

where on the L.H.S. the first term is the reception capacities of the remaining servers and the
second term is the reception capacity of the spare server.
Now Lemma 14.1 shows that the rebuild rate is proportional to the sum of transmission rates
by the remaining servers. Therefore, to maximize the rebuild rate we need to maximize the
transmission capacity of the system, subject to the constraint in equation (14.13). Noting the
constraint 0 ≤ ϕ ≤ 1 we can solve for ϕ by rearranging equation (14.13) to give

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

1) ,

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

2(1 − ρ )( N S −

ϕ = (14.14)

1 , otherwise

Next we substitute equation (14.14) into equation (14.12) and invoke Lemma 14.1 to obtain
the maximum achievable data rebuild rate:

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

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

2( N S − 1)

R max = (14.15)

− ρ

S S (1 ) otherwise