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

this overhead may not be acceptable for systems with a small number of servers. The PRT
scheme discussed in the next section is designed to reduce this bandwidth overhead.

11.3 Progressive Redundancy Transmission (PRT)
In PRT, the system does not transmit all the redundant data. Instead, the server transmits only
a subset of the redundant data and then activates more redundant data transmissions when
a server failure is detected, thus reducing the network bandwidth overhead incurred during
normal-mode operation. Obviously the system must be able to detect server failures quickly
so that the system can be reconfigured to send additional redundant data. By contrast, this
extra step of failure detection is not needed in FEC. For simplicity, we will focus on a special
type of PRT algorithm where none of the redundant data are transmitted until a server failure
is detected. We will revisit the more general PRT algorithm in Chapter 13 when we compare
FEC and PRT in details.
In a system with N S servers and a video data rate of R V , each server only needs to transmit
at a rate of R V /

N S - we call it Min-Rate transmission. Upon a simultaneous x -server failure

(0 < x ≤ K ), the surviving servers will have to increase the transmission rate from R V / N S

to R V / x ) to maintain the same aggregate video bit-rate. This Min-Rate transmission

scheme thus requires dynamic reconfiguration of the server scheduler as well as network band-
width allocations. Alternatively, the systemcanmaintain the transmission rate at R V ( N S −

( N S −

K )-
we call it Std-Rate transmission, evenwhen there is no failure. The servers just skipped transmit-
ting the redundant units. When an x -server failure occurs, the systemwill simply reconfigure x
of the servers to start transmitting redundant data, thereby maintaining enough data for erasure
correction at the clients. This approach eliminates the need to dynamically reconfigure the
server scheduler and network connections.
If the network does not require per-channel resource allocation (e.g., FastEthernet),Min-Rate
transmission will have no advantage over Std-Rate transmission, as the average rate is the same
for both schemes. On the other hand, if the network requires per-channel resource allocation
such as CBR service in Asynchronous Transfer Mode (ATM), then under Min-Rate trans-
mission the servers will need to re-negotiate a higher bandwidth allocation from the network
upon detecting a failure. However, reconfiguring hundreds or even thousands of connections
simultaneously could overload the network management center, which in turn could delay the
reconfiguration process significantly. Therefore, we conclude that the Min-Rate transmission
scheme does not offer significant advantages over Std-Rate and is difficult to implement effi-
ciently. By contrast, the Std-Rate transmission scheme is much simpler to implement, and so
we will only consider the Std-Rate transmission scheme in the rest of the chapter.

11.3.1 Failure-Detection Protocol
As discussed in the previous section, failure detection is necessary in PRT because redundant
data are not normally transmitted. The goal then is to detect a server failure quickly and
accurately, so that the remaining servers can be reconfigured to begin transmitting redundant
data. If the detection delay , defined as the time from a server fails to the time the remaining
servers are notified of the failure, is too large, then video playback hiccups can occur at the
clients. On the other hand, the detection algorithm should not be overly sensitive in order