Fault-Tolerant Algorithms for the Concurrent-Push Architecture - Scalable Continuous Media Streaming Systems - page 198

S 0

25 20 P4 13 9 5 0

S 1

26 21 P3 16 10 6 1

S 2

P6 22 P2 17 12 7 2

S 3

8 3

S 4

24 P5 19 15 11 4

T D

S 3 failed
Failure detected

Server
Reconfig

Failure mode Normal mode

Figure 11.4 Server reconfiguration under PRT with block striping

upon server failure. More investigations are therefore needed to quantify the gains and the
associated tradeoffs.
Now assuming that failure occurs during service round j , then the servers will receive the
failure notification latest by round

T D
T F

= +

k j (11.2)

where T F is the length of a service round defined in equation (11.4) below.
Knowing the failure, the servers will transmit redundant video blocks in addition to video
blocks in the next round ( k 1)

stripes that are transmitted after the failure but before the failure is detected will have no
redundant blocks transmitted (e.g., stripes 2 and 3). To enable the client to re-compute the lost
stripe units, it is therefore necessary to retransmit the required redundant units (e.g., P2 and
P3) for these stripes.
In a systemwith N S servers and K redundant blocks per stripe, a maximum of ( k

+ 1) if there is one (e.g., P4 in Figure 11.4). However, the ( k − j +

1) K
redundant blocks will have to be retransmitted. Note that this is the maximum because re-
transmission is not needed for lost redundant blocks. Assume the failure is a simultaneous
K -server failure (worst-case scenario), leaving ( N S −

− j +

K ) working servers, the remaining

servers can then retrieve and transmit ( N S − K ) redundant units in a service round. Hence, a

maximum of

( k (

− j + 1) K T D / T F + 1) K

N R = = (11.3)

( N S − K ) ( N S − K )