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

S 0

49 45 40 33 29 25 20 13 9 5 0

P9 P4

S 1

50 46 41 P3 36 P8 30 26 21 16 P3 10 6 1

S 2

P12 47 42 P2 37 32 P7 27 22 17 12 P2 7 2

S 3

8 3

S 4

51 44 P10 39 35 31 24 P5 19 15 11 4

T D

S 3 failed
Failure detected

Server Reconfiguration

Failure mode Normal mode

Figure 11.5 Server reconfiguration under PRT with sub-schedule striping

per service round. Note that in each service round, a server retrieves

N S
( N S −

Q S = Q (11.8)

K )

bytes of video data (instead of Q bytes in block striping) for every video stream and the length
of a service round is

N S
( N S −

T S = T F (11.9)

K )

seconds (instead of T F seconds in block striping).
We assume that a K -server failure occurs during micro-round j and is detected in micro-
round k . Similar to equation (11.2), we can obtain k from

N S T D
T S

k = j + (11.10)

Once notified of the failure, the servers will begin transmitting redundant units for subsequent
stripes ( > k ). As each stripe contains K redundant units, the system needs to retransmit up to

( k − j + 1) K redundant units. This will require up to

( k (

− j + 1) K ( N S − K ) T D / T F + 1) K

n R = = (11.11)

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

micro-rounds for retransmitting the redundant units.
Note that this process has two subtle constraints. First, retransmission cannot start immedi-
ately in the next service round because the servers need another service round to retrieve the
required redundant units. Second, even if n R <

N S , the last service round for retransmission
cannot be shortened because the disk requires a full service round to retrieve video blocks for
transmission in the next round.