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

whichever is larger. However, from equation (11.6): D F = K ) T avg .

Therefore, the two equations are in fact equivalent. The total client buffer requirement is thus
given by

N F T F and T F = ( N S −

2 τ + τ + ( N S −

f + − f − − f + − f − + T E T L

B BS

PRT =

+ N F + + K ) Q

( N S − K ) T avg ( N S − K ) T avg

(11.26)

11.5.2 Buffer Requirement under Sub-Schedule Striping
To derive the client buffer requirement for sub-schedule striping, we again consider stripe units
in groups of ( N S −

.
Now unlike FEC, each group of stripe units has the size of Q bytes, instead of Q S bytes under
FEC. Hence, the client buffer comprises L

K ), i.e., group i comprises stripe units { i , i + 1 ,..., ( i + N S − K − 1) }

Z buffer units, each of Q bytes. Proceeding
the derivations in the same manner (see Appendix A.4 for details), we can obtain the total
buffer requirements from

= Y +

2 τ + τ + Q

f + − f − − f + − f − + T E T L

B SSS
PRT

= + N F + + (11.27)

T avg T avg

From equation (11.12), we can see that N F is proportional to N S . This implies that the buffer
requirement is also proportional to N S . As sub-schedule striping (cf., Section 10.5) is originally
introduced to maintain a constant client buffer requirement independent of system scale (i.e.,
N S ), the extension to PRT appears to have defeated this goal. We introduce a redundant server
scheme in the next section to tackle this problem.

11.6 Redundant Server Scheme
A closer look at Figure 11.5 will reveal why buffer requirement increases with system scale in
PRT. First, retransmission of redundant stripe units cannot start in the current service round.
This incurs a worst-case delay equal to ( N S −

1) T avg seconds, which obviously is proportional
to the system scale. Second, retransmissions cannot start even in the next service round due to
the need to retrieve redundant stripe units, incurring another delay of N S T avg seconds, which
again is proportional to the system scale.
The key to the previous two observations is in the server scheduler. First, under the AGSS
scheduler (cf., Section 10.4), redundant units are discarded together with the video data units
once the service round ends to allow buffer reuse. Hence, if the failure-detection period spans
two service rounds as shown in Figure 11.6, redundant units for the previous round will have
been discarded by the time the failure is detected, rendering immediate retransmission of
redundant stripe units impossible.
To tackle this problem, one can modify the AGSS scheduler so that redundant units are
retained longer to cater for server failure. However, we propose a redundant server scheme
(RSS) to store all redundant units centrally in one or more ( K to be exact) redundant servers
instead of distributing them over all servers. RSS has three advantages over simply increasing
the buffer holding time in AGSS.