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

additional service rounds are required to retransmit the necessary redundant units. Conse-
quently, transmission of subsequent stripes will be delayed by at most N R rounds.
Now consider the recovery of stripe j (e.g., stripe 2 in Figure 11.4). At the time (round k )
the failure is detected, the current disk cycle is already retrieving stripe units for the next
transmission cycle k

+

1. Hence, redundant units for stripe j can only be scheduled for
retrieval in the next disk retrieval cycle, which in turn will be sent in transmission round k

+
2. Therefore, delivery of the redundant block required to recover stripe j will be delayed by

2

R V T D
Q ( N S −

N F = ( k − j + 2) = + (11.4)

K )

service rounds. For a transmission rate of R V /( N S − K ) Bps under Std-Rate transmission,

the time it takes to transmit a video block of Q bytes, i.e., length of a service round, is
equal to

Q ( N S − K )

T F = (11.5)

R V

Therefore, using equations (11.4) and (11.5) we can compute the delay for delivering the
redundant block for stripe j from

2 Q ( N S −

R V T D
Q ( N S −

K )

D F = N F T F = + (11.6)

K ) R V

K , equation (11.6) also bounds the delay for all stripes. To see
why, begin with equation (11.3):

Provided that ( N S − K ) ≥

( k

− j + 1) K

N R =

( N S − K )

≤ ( k − j + 1) , (( N S − K ) ≥ K ) (11.7)

∵

< ( k − j + 2) = N F

This shows that the delay experienced by stripes transmitted after the failure is

detected ( N R ) is smaller than the delay experienced by stripe j ( N F ). Therefore, the worst-case
delay in equation (11.6) also bounds the delay for all stripes.
The additional delay will likely lead to video playback hiccups for the clients. If tempo-
rary service interruption can be tolerated, then the clients can simply suspend playback for
D F seconds to resynchronize with the new transmission schedule. Otherwise, we can intro-
duce additional buffers at the client to sustain non-stop video playback during reconfiguration
(Section 11.5).

i | i > k + 1

{ }

11.3.3 Server Reconfiguration for Sub-Schedule Striping
Figure 11.5 depicts the server reconfiguration process for sub-schedule striping, with N S = 5

and K 1. Instead of considering service rounds, we consider micro-rounds - defined as the

period for transmitting a stripe. Hence, a system with N S servers will have N S micro-rounds

=