FEC versus PRT - Scalable Continuous Media Streaming Systems - page 238

. . . . . . . . . . . . 6 630 3 0

S 0

3 3 0 0

. . . . . . . . . . . . 7 4 1 1

S 1

4 4 1 1

. . . . . . . . . . . . 8 8 5 2 2

S 2

Transmission

5 5 2 2

. . . . . . . . . . . .

P PPP P P

S 3

P P

P P

. . . . . . . . . . . .

S 4 P PP P P P

P P P P

Qbytes
(Transaction/Striping Size)

... ...

P P 1 1 0 0

Playout

Video Client

Figure 13.1 Data placement and transmission in a parallel streaming server

time. Surprisingly, instead of having a lower reliability than FEC, we discover that we can
configure PRT to outperform FEC (achieving longer MTTF) and consume significantly less
transmission bandwidth overhead (half that of FEC). We first introduce the system model in
the next section and then analyze the two redundant data transmission protocols.

13.2 System Model
Figure 13.1 depicts the generic system model for a parallel streaming server. Let N S be the
number of servers in the system. Each server (denoted by S i , 1) is au-

tonomous, and equipped with its own CPU, memory, disk storage, and network interface. This
ensures that any server failure will not spread to other servers. Specifically, we assume the
servers to fail independently and, when they fail, they simply stop all data transmissions.
A media object such as a video stream is first divided into fixed-size data blocks of Q bytes
each, denoted by

i = 0 , 1 ,..., N S −

. To generate redundant data we use a ( N S , K) erasure
correction code and compute K redundant data blocks for every ( N S −

b i | i = 0, 1, . . .

{ }

K ) data blocks. For
example, K redundant blocks (i.e., blocks marked with 'P' in Figure 13.1) are computed from
data blocks and together they form a parity group. Each of the

data/redundant blocks in a parity group will be stored in a separate server in the system. The
client can recover all ( N S −

b i | i = 0, 1, . . . , ( N S − K − 1)

{ }

K ) data/redundant blocks of
a parity group are available, thus enabling it to tolerate up to K simultaneous server failures.

K ) data blocks as long as any ( N S −

13.3 Forward Erasure Correction
In the FEC protocol, all N S data blocks in a parity group are transmitted to the clients at all
time, irrespective of server failure. This protocol is simple to implement as the server schedules
are fixed irrespective of individual server failures. The system does not even need to detect
server failures or to reconfigure the system for degraded-mode operation. The client simply