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

data. However, in PRT, not all servers are actively transmitting data. When an idle server fails,
it will undergo repair and then return to the normal state after some time. The difference is
that when an idle server fails, the operation of the system is not affected since none of the
data transmissions are affected by the failure. By contrast, failure of an active server will
require the system to increase the level of redundancy transmitted. Thus, the failure of an idle
server is equivalent to the failure of an active server with an additional redundancy activated
immediately, i.e., the failure detection time is equal to zero. The previous Markov chain model,
which assumes a failure-detection time of 1/ , is therefore a conservative estimation of the

system MTTF. Nevertheless, our numerical results show that such differences are negligible
and so we will ignore this subtle complexity.
Using the Markov chain model, we can then derive the systemMTTF from the first passage
time of the Markov chain to reach any of the absorbing states (e.g., states (3, 2), (4, 3), and
(5, 4) in Figure 13.3). For systems with small K min and K max , we can solve the Markov chain
analytically to obtain the equation for the system MTTF. For example, when K min =

ω

1 and

K max = 2, the system MTTF is given by

µ 1 λ 1 λ 2 + λ 1 2 λ 2 + λ 1 λ 2 ω + λ 2 µ 1 2 λ 1 µ 1 µ 2 + 2 + µ 1 µ 2 ω + λ 0 µ 1 µ 2

+ µ 1 2

µ 2 + ωλ 0 µ 2 + ωλ 2 µ 1 + µ 1 λ 0 λ 2 + ωλ 0 λ 1 + ωλ 0 λ 2 + λ 0 λ 1 λ 2
λ 0 λ 1 (

MTTF = (13.5)

µ 1 µ 2 + µ 1 λ 2 + λ 1 λ 2 + ωλ 2 )

However, for a system with larger values of K min and K max , the number of equations in-
volved increases drastically. Although still solvable in principle, the process soon becomes too
tedious to perform manually. Therefore we resort to using mathematical software packages
(e.g., Maple [2]) to compute the symbolic solutions. For still larger values of K min and K max ,
even this computation time can become too long. Also the resultant analytic solutions are often
too complicated to be useful. For example, the solution for system MTTF of the configuration
in Figure 13.3 with K min = 4 has 474 terms in the numerator and 66 terms in

the denominator. In these cases we need to resort to computing the results numerically instead
of symbolically.

2 and K max =

13.4.2 Modeling the Failure-Detection Time
So far we have assumed that the failure-detection time is exponentially distributed. In practice,
the exact distribution of the failure-detection time will depend on the failure detection protocol
employed and thus may not conform to the exponential distribution. To investigate the impact
of the type of distribution for the failure-detection time, we extend the model by representing
the failure-detection time as an Erlang- k random variable. Thus, by varying the parameter k we
can obtain a series of different probability distributions, ranging from exponential distribution
(for k

1) to normal distribution (for large k ).
To extend the systemmodel to use Erlang- k distributed failure-detection time, we decompose
the Erlang- k distribution into a series of k independent exponential random processes, each
having a rate equal to k

=

2. Thus, the mean detection time
for the Erlang- k process is exactly the same as the exponential process in the original model.
Similarly, the systemMTTF is the first passage time to reach any of the absorbing states, i.e.,
states

ω as shown in Figure 13.4 for k =

in
this generalized Markov chain model. For small values, of N S , K min , and K max , we can solve

( K min + i , K min + i − 1 , j ) | i = 1 , 2,...,( K max − K min + 1), j = 0 , 1 ,..., k − 1

{ }