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

performs erasure correction computation to recover the data blocks whenever N S − K video

blocks of a parity group are received.

13.3.1 System Reliability
To quantify the amount of redundancy needed to achieve a given target system MTTF, we
can model the system using a continuous-time Markov chain. We assume server failures are
independent and exponentially distributed with a MTTF of 1/ . Failed servers are repaired

immediately and independently with a mean-time-to-repair (MTTR) of 1/

λ

. Thus, the system
forms a Markov chain with state h representing the state with h failed servers (see Figure 13.2,
for an example). Assume the system is configured with K redundant blocks per parity group,
then the system fails when more than K servers fail, i.e., when the Markov chain enters the
absorbing state h

µ

= K + 1. Otherwise, servers in the system in state h will have an aggregate

failure rate λ h , given by

λ h = λ ( N S − h ) (13.1)

and an aggregate repair rate µ h , given by

µ h = h µ. (13.2)

Thus, the MTTF of the system is equivalent to the first passage time for the system to reach
state h

0. It can be shown that the MTTF for a system with
N S servers and K redundancies using FEC is given by

= K + 1 from the initial state h =

.

j − 1

0 µ i − l

K i

l =

MTTF FEC = (13.3)

l = 0 λ i − l

j

i = 0 j = 0

Therefore, using equation (13.3) we can determine the amount of redundancy needed for a
given target system MTTF.

λ 0 λ 0 λ 0

λ 1 λ 1 λ 1 λ 2 λ 2 λ 2 λ 3 λ 3 λ 3

0,3 0,3 0,3 1,3 1,3 1,3 2,3 2,3 2,3 3,3 3,3 3,3 4,3 4,3 4,3

µ 3 µ 3 µ 3

µ 1 µ 1 µ 1

µ 2 µ 2 µ 2

: : state with h servers failed and k level of redundancy

h , k h , k

λ h λ h

µ h

: aggregate server failure rate with h server failed

µ h : aggregate repair rate with h server failed

Figure 13.2 A Markov chain mode for FEC with K = 3