Information Technology Reference
In-Depth Information
Errors and erasures are different, because, for errors, data are still being received but the
content may be corrupted. In case of erasure, the expected data are simplymissing and hence no
erroneous data will be received. Here we have implicitly assumed that the server is fail-stop, i.e.,
it stops sending out data upon failure. This type of failure could be caused by disk subsystem
failure, network failure, power loss, or even software crashes. In any case, erasures are intro-
duced into the video stream because data stored in the failed server will become unavailable.
According to coding theory, to recover an erased symbol (a unit of data) in a codeword (also
called a parity group, or a stripe), one needs to encode the data with at least one redundant
symbol per codeword. One well-known coding algorithm called Reed-Solomon Erasure cor-
rection (RSE) code [2, 3] can encode data with any codeword size and level of redundancies.
If one needs to protect the system from only single-server failure, then an even simpler code -
parity - can be used instead. For simplicity, we assume in this chapter a generic code where
each additional redundant symbol can recover one erasure.
Drawing related principles from RAID [4], Figures 11.1 and 11.2 depict the proposed
redundant striping policies for block striping and sub-schedule striping. The basic idea is the
same - introduces one or more redundant stripe units in every stripe. The redundant units are
S
0
. . .
9
5
0
S
1
. . .
10
6
1
...
. . .
P
7
2
P
1
0
S
2
Playout
. . .
8
P
3
Video Client
S
3
11
4
P
S
4
. . .
Q bytes
(Transaction/Striping Size)
Figure 11.1
Fixed-size block striping with redundancy of one
S
0
. . .
5 0
S
1
. . .
6 1
. . .
S
2
7 2
P 7 6 5 4 P 3 2 1 0
Playout
. . .
Video Client
P 3
S
3
. . .
4 P
S
4
Q bytes
(Transaction Size)
U bytes
(Striping Size)
Figure 11.2
Fixed-size sub-schedule striping with redundancy of one
Search WWH ::
Custom Search