draft-ietf-rmt-bb-fec-rs-05.txt   rfc5510.txt 
Reliable Multicast Transport J. Lacan Network Working Group J. Lacan
Internet-Draft ISAE/LAAS-CNRS Request for Comments: 5510 ISAE/LAAS-CNRS
Intended status: Standards Track V. Roca Category: Standards Track V. Roca
Expires: May 15, 2008 INRIA INRIA
J. Peltotalo J. Peltotalo
S. Peltotalo S. Peltotalo
Tampere University of Technology Tampere University of Technology
November 12, 2007
Reed-Solomon Forward Error Correction (FEC) Schemes Reed-Solomon Forward Error Correction (FEC) Schemes
draft-ietf-rmt-bb-fec-rs-05.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Status of This Memo
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at This document specifies an Internet standards track protocol for the
http://www.ietf.org/ietf/1id-abstracts.txt. Internet community, and requests discussion and suggestions for
improvements. Please refer to the current edition of the "Internet
Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is unlimited.
The list of Internet-Draft Shadow Directories can be accessed at Copyright Notice
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on May 15, 2008. Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
Copyright Notice This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Copyright (C) The IETF Trust (2007). This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November
10, 2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s) controlling
the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other
than English.
Abstract Abstract
This document describes a Fully-Specified Forward Error Correction This document describes a Fully-Specified Forward Error Correction
(FEC) Scheme for the Reed-Solomon FEC codes over GF(2^^m), with m in (FEC) Scheme for the Reed-Solomon FEC codes over GF(2^^m), where m is
{2..16}, and its application to the reliable delivery of data objects in {2..16}, and its application to the reliable delivery of data
on the packet erasure channel (i.e., a communication path where objects on the packet erasure channel (i.e., a communication path
packets are either received without any corruption or discarded where packets are either received without any corruption or discarded
during transmission). during transmission). This document also describes a Fully-Specified
FEC Scheme for the special case of Reed-Solomon codes over GF(2^^8)
This document also describes a Fully-Specified FEC Scheme for the when there is no encoding symbol group. Finally, in the context of
special case of Reed-Solomon codes over GF(2^^8) when there is no the Under-Specified Small Block Systematic FEC Scheme (FEC Encoding
encoding symbol group. ID 129), this document assigns an FEC Instance ID to the special case
of Reed-Solomon codes over GF(2^^8).
Finally, in the context of the Under-Specified Small Block Systematic
FEC Scheme (FEC Encoding ID 129), this document assigns an FEC
Instance ID to the special case of Reed-Solomon codes over GF(2^^8).
Reed-Solomon codes belong to the class of Maximum Distance Separable Reed-Solomon codes belong to the class of Maximum Distance Separable
(MDS) codes, i.e., they enable a receiver to recover the k source (MDS) codes, i.e., they enable a receiver to recover the k source
symbols from any set of k received symbols. The schemes described symbols from any set of k received symbols. The schemes described
here are compatible with the implementation from Luigi Rizzo. here are compatible with the implementation from Luigi Rizzo.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 1. Introduction ....................................................4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 2. Terminology .....................................................5
3. Definitions Notations and Abbreviations . . . . . . . . . . . 7 3. Definitions Notations and Abbreviations .........................5
3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 7 3.1. Definitions ................................................5
3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2. Notations ..................................................6
3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 8 3.3. Abbreviations ..............................................7
4. Formats and Codes with FEC Encoding ID 2 . . . . . . . . . . . 10 4. Formats and Codes with FEC Encoding ID 2 ........................7
4.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 10 4.1. FEC Payload ID .............................................7
4.2. FEC Object Transmission Information . . . . . . . . . . . 11 4.2. FEC Object Transmission Information ........................8
4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 11 4.2.1. Mandatory Elements ..................................8
4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 11 4.2.2. Common Elements .....................................8
4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 11 4.2.3. Scheme-Specific Elements ............................9
4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 12 4.2.4. Encoding Format .....................................9
5. Formats and Codes with FEC Encoding ID 5 . . . . . . . . . . . 14 5. Formats and Codes with FEC Encoding ID 5 .......................11
5.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 14 5.1. FEC Payload ID ............................................11
5.2. FEC Object Transmission Information . . . . . . . . . . . 14 5.2. FEC Object Transmission Information .......................12
5.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 14 5.2.1. Mandatory Elements .................................12
5.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 14 5.2.2. Common Elements ....................................12
5.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 15 5.2.3. Scheme-Specific Elements ...........................12
5.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 15 5.2.4. Encoding Format ....................................12
6. Procedures with FEC Encoding IDs 2 and 5 . . . . . . . . . . . 16 6. Procedures with FEC Encoding IDs 2 and 5 .......................13
6.1. Determining the Maximum Source Block Length (B) . . . . . 16 6.1. Determining the Maximum Source Block Length (B) ...........13
6.2. Determining the Number of Encoding Symbols of a Block . . 16 6.2. Determining the Number of Encoding Symbols of a Block .....14
7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129)
and Reed-Solomon Codes over GF(2^^8) . . . . . . . . . . . . . 19 and Reed-Solomon Codes over GF(2^^8) ...........................15
8. Reed-Solomon Codes Specification for the Erasure Channel . . . 20 8. Reed-Solomon Codes Specification for the Erasure Channel .......16
8.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 20 8.1. Finite Field ..............................................16
8.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 21 8.2. Reed-Solomon Encoding Algorithm ...........................17
8.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 21 8.2.1. Encoding Principles ................................17
8.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 22 8.2.2. Encoding Complexity ................................18
8.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 22 8.3. Reed-Solomon Decoding Algorithm ...........................18
8.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 22 8.3.1. Decoding Principles ................................18
8.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 23 8.3.2. Decoding Complexity ................................19
8.4. Implementation for the Packet Erasure Channel . . . . . . 23 8.4. Implementation for the Packet Erasure Channel .............19
9. Security Considerations . . . . . . . . . . . . . . . . . . . 27 9. Security Considerations ........................................22
9.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 27 9.1. Problem Statement .........................................22
9.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 27 9.2. Attacks against the Data Flow .............................23
9.2.1. Access to Confidential Objects . . . . . . . . . . . . 27 9.2.1. Access to Confidential Objects .....................23
9.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 28 9.2.2. Content Corruption .................................23
9.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 29 9.3. Attacks against the FEC Parameters ........................24
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 30 10. IANA Considerations ...........................................25
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 31 11. Acknowledgments ...............................................25
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 32 12. References ....................................................26
12.1. Normative References . . . . . . . . . . . . . . . . . . . 32 12.1. Normative References .....................................26
12.2. Informative References . . . . . . . . . . . . . . . . . . 32 12.2. Informative References ...................................26
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 34
Intellectual Property and Copyright Statements . . . . . . . . . . 35
1. Introduction 1. Introduction
The use of Forward Error Correction (FEC) codes is a classical The use of Forward Error Correction (FEC) codes is a classical
solution to improve the reliability of multicast and broadcast solution to improve the reliability of multicast and broadcast
transmissions. The [RFC5052] document describes a general framework transmissions. The [RFC5052] document describes a general framework
to use FEC in Content Delivery Protocols (CDP). The companion to use FEC in Content Delivery Protocols (CDPs). The companion
document [RFC3453] describes some applications of FEC codes for document [RFC3453] describes some applications of FEC codes for
content delivery. content delivery.
Recent FEC schemes like [RFC5053] and [draft-ietf-rmt-bb-fec-ldpc] Recent FEC schemes like [RFC5053] and [RFC5170] proposed erasure
proposed erasure codes based on sparse graphs/matrices. These codes codes based on sparse graphs/matrices. These codes are efficient in
are efficient in terms of processing but not optimal in terms of terms of processing but not optimal in terms of correction
correction capabilities when dealing with "small" objects. capabilities when dealing with "small" objects.
The FEC scheme described in this document belongs to the class of The FEC schemes described in this document belongs to the class of
Maximum Distance Separable codes that are optimal in terms of erasure Maximum Distance Separable codes that are optimal in terms of erasure
correction capability. In others words, it enables a receiver to correction capability. In others words, it enables a receiver to
recover the k source symbols from any set of exactly k encoding recover the k source symbols from any set of exactly k encoding
symbols. Even if the encoding/decoding complexity is larger than symbols. They are also systematic codes, which means that the k
that of [RFC5053] or [draft-ietf-rmt-bb-fec-ldpc], this family of source symbols are part of the encoding symbols. Even if the
codes is very useful. encoding/decoding complexity is larger than that of [RFC5053] or
[RFC5170], this family of codes is very useful.
Many applications dealing with content transmission or content Many applications dealing with content transmission or content
storage already rely on packet-based Reed-Solomon codes. In storage already rely on packet-based Reed-Solomon codes. In
particular, many of them use the Reed-Solomon codec of Luigi Rizzo particular, many of them use the Reed-Solomon codec of Luigi Rizzo
[RS-codec] [Rizzo97]. The goal of the present document is to specify [RS-codec] [Rizzo97]. The goal of the present document is to specify
an implementation of Reed-Solomon codes that is compatible with this an implementation of Reed-Solomon codes that is compatible with this
codec. codec.
The present document: The present document:
o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 2 o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 2,
that specifies the use of Reed-Solomon codes over GF(2^^m), with m which specifies the use of Reed-Solomon codes over GF(2^^m), where
in {2..16}, m is in {2..16},
o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 5 o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 5,
that focuses on the special case of Reed-Solomon codes over which focuses on the special case of Reed-Solomon codes over
GF(2^^8) and no encoding symbol group (i.e., exactly one symbol GF(2^^8) and no encoding symbol group (i.e., exactly one symbol
per packet), and per packet), and
o in the context of the Under-Specified Small Block Systematic FEC o in the context of the Under-Specified Small Block Systematic FEC
Scheme (FEC Encoding ID 129) Scheme (FEC Encoding ID 129) [RFC5445], assigns the FEC Instance
[draft-ietf-rmt-bb-fec-basic-schemes-revised], assigns the FEC ID 0 to the special case of Reed-Solomon codes over GF(2^^8) and
Instance ID 0 to the special case of Reed-Solomon codes over no encoding symbol group.
GF(2^^8) and no encoding symbol group.
For a definition of the terms Fully-Specified and Under-Specified FEC For a definition of the terms Fully-Specified and Under-Specified FEC
Schemes, see [RFC5052], section 4. Schemes, see [RFC5052], Section 4.
2. Terminology 2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119]. document are to be interpreted as described in RFC 2119 [RFC2119].
3. Definitions Notations and Abbreviations 3. Definitions Notations and Abbreviations
3.1. Definitions 3.1. Definitions
skipping to change at page 7, line 19 skipping to change at page 5, line 25
This document uses the same terms and definitions as those specified This document uses the same terms and definitions as those specified
in [RFC5052]. Additionally, it uses the following definitions: in [RFC5052]. Additionally, it uses the following definitions:
Source symbol: unit of data used during the encoding process. Source symbol: unit of data used during the encoding process.
Encoding symbol: unit of data generated by the encoding process. Encoding symbol: unit of data generated by the encoding process.
Repair symbol: encoding symbol that is not a source symbol. Repair symbol: encoding symbol that is not a source symbol.
Code rate: the k/n ratio, i.e., the ratio between the number of Code rate: the k/n ratio, i.e., the ratio between the number of
source symbols and the number of encoding symbols. The code rate source symbols and the number of encoding symbols. By
belongs to a ]0; 1] interval. A code rate close to 1 indicates definition, the code rate is such that: 0 < code rate <= 1. A
that a small number of repair symbols have been produced during code rate close to 1 indicates that a small number of repair
the encoding process. symbols have been produced during the encoding process.
Systematic code: FEC code in which the source symbols are part of Systematic code: FEC code in which the source symbols are part of
the encoding symbols. the encoding symbols.
Source block: a block of k source symbols that are considered Source block: a block of k source symbols that are considered
together for the encoding. together for the encoding.
Encoding Symbol Group: a group of encoding symbols that are sent Encoding Symbol Group: a group of encoding symbols that are sent
together within the same packet, and whose relationships to the together within the same packet, and whose relationships to the
source block can be derived from a single Encoding Symbol ID. source block can be derived from a single Encoding Symbol ID.
Source Packet: a data packet containing only source symbols. Source Packet: a data packet containing only source symbols.
Repair Packet: a data packet containing only repair symbols. Repair Packet: a data packet containing only repair symbols.
Packet Erasure Channel: a communication path where packets are Packet Erasure Channel: a communication path where packets are
either dropped (e.g., by a congested router, or because the number either dropped (e.g., by a congested router, or because the
of transmission errors exceeds the correction capabilities of the number of transmission errors exceeds the correction
physical layer codes) or received. When a packet is received, it capabilities of the physical layer codes) or received. When a
is assumed that this packet is not corrupted. packet is received, it is assumed that this packet is not
corrupted.
3.2. Notations 3.2. Notations
This document uses the following notations: This document uses the following notations:
L denotes the object transfer length in bytes. L the object transfer length in bytes.
k denotes the number of source symbols in a source block. k the number of source symbols in a source block.
n_r denotes the number of repair symbols generated for a source n_r the number of repair symbols generated for a source block.
block.
n denotes the encoding block length, i.e., the number of encoding n the encoding block length, i.e., the number of encoding
symbols generated for a source block. Therefore: n = k + n_r. symbols generated for a source block. Therefore: n = k +
n_r.
max_n denotes the maximum number of encoding symbols generated for max_n the maximum number of encoding symbols generated for any
any source block. source block.
B denotes the maximum source block length in symbols, i.e., the B the maximum source block length in symbols, i.e., the
maximum number of source symbols per source block. maximum number of source symbols per source block.
N denotes the number of source blocks into which the object shall N the number of source blocks into which the object shall be
be partitioned. partitioned.
E denotes the encoding symbol length in bytes. E the encoding symbol length in bytes.
S denotes the symbol size in units of m-bit elements. When m = 8, S the symbol size in units of m-bit elements. When m = 8,
then S and E are equal. then S and E are equal.
m defines the length of the elements in the finite field, in bits. m the length of the elements in the finite field, in bits.
In this document, m belongs to {2..16}. In this document, m belongs to {2..16}.
q defines the number of elements in the finite field. We have: q q the number of elements in the finite field. We have: q =
= 2^^m in this specification. 2^^m in this specification.
G denotes the number of encoding symbols per group, i.e., the G the number of encoding symbols per group, i.e., the number
number of symbols sent in the same packet. of symbols sent in the same packet.
GM denotes the Generator Matrix of a Reed-Solomon code. GM the Generator Matrix of a Reed-Solomon code.
CR denotes the "code rate", i.e., the k/n ratio. CR the "code rate", i.e., the k/n ratio.
a^^b denotes a raised to the power b. a^^b a raised to the power b.
a^^-1 denotes the inverse of a. a^^-1 the inverse of a.
I_k denotes the k*k identity matrix. I_k the k*k identity matrix.
3.3. Abbreviations 3.3. Abbreviations
This document uses the following abbreviations: This document uses the following abbreviations:
ESI stands for Encoding Symbol ID. ESI Encoding Symbol ID.
FEC OTI stands for FEC Object Transmission Information. FEC OTI FEC Object Transmission Information.
RS stands for Reed-Solomon. RS Reed-Solomon.
MDS stands for Maximum Distance Separable code. MDS Maximum Distance Separable code.
GF(q) denotes a finite field (also known as Galois Field) with q GF(q) a finite field (also known as Galois Field) with q
elements. We assume that q = 2^^m in this document. elements. We assume that q = 2^^m in this document.
4. Formats and Codes with FEC Encoding ID 2 4. Formats and Codes with FEC Encoding ID 2
This section introduces the formats and codes associated with the This section introduces the formats and codes associated with the
Fully-Specified FEC Scheme with FEC Encoding ID 2 that specifies the Fully-Specified FEC Scheme with FEC Encoding ID 2, which specifies
use of Reed-Solomon codes over GF(2^^m). the use of Reed-Solomon codes over GF(2^^m).
4.1. FEC Payload ID 4.1. FEC Payload ID
The FEC Payload ID is composed of the Source Block Number and the The FEC Payload ID is composed of the Source Block Number and the
Encoding Symbol ID. The length of these two fields depends on the Encoding Symbol ID. The lengths of these two fields depend on the
parameter m (which is transmitted in the FEC OTI) as follows: parameter m (which is transmitted in the FEC OTI) as follows:
o The Source Block Number (field of size 32-m bits) identifies from o The Source Block Number (field of size 32-m bits) identifies from
which source block of the object the encoding symbol(s) in the which source block of the object the encoding symbol(s) in the
payload is(are) generated. There is a maximum of 2^^(32-m) blocks payload are generated. There is a maximum of 2^^(32-m) blocks per
per object. object.
o The Encoding Symbol ID (field of size m bits) identifies which o The Encoding Symbol ID (field of size m bits) identifies which
specific encoding symbol(s) generated from the source block specific encoding symbol(s) generated from the source block are
is(are) carried in the packet payload. There is a maximum of 2^^m carried in the packet payload. There is a maximum of 2^^m
encoding symbols per block. The first k values (0 to k - 1) encoding symbols per block. The first k values (0 to k - 1)
identify source symbols, the remaining n-k values identify repair identify source symbols, the remaining n-k values identify repair
symbols. symbols.
There MUST be exactly one FEC Payload ID per source or repair packet. There MUST be exactly one FEC Payload ID per source or repair packet.
In case of an Encoding Symbol Group, when multiple encoding symbols In case of an Encoding Symbol Group, when multiple encoding symbols
are sent in the same packet, the FEC Payload ID refers to the first are sent in the same packet, the FEC Payload ID refers to the first
symbol of the packet. The other symbols can be deduced from the ESI symbol of the packet. The other symbols can be deduced from the ESI
of the first symbol by incrementing sequentially the ESI. of the first symbol by incrementing sequentially the ESI.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Block Number (32-8=24 bits) | Enc. Symb. ID | | Source Block Number (32-8=24 bits) | Enc. Symb. ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: FEC Payload ID encoding format for m = 8 (default) Figure 1: FEC Payload ID Encoding Format for m = 8 (Default)
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) | | Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: FEC Payload ID encoding format for m = 16 Figure 2: FEC Payload ID Encoding Format for m = 16
The format of the FEC Payload ID for m = 8 and m = 16 is illustrated The formats of the FEC Payload ID for m = 8 and m = 16 are
in Figure 1 and Figure 2 respectively. illustrated in Figure 1 and Figure 2, respectively.
4.2. FEC Object Transmission Information 4.2. FEC Object Transmission Information
4.2.1. Mandatory Elements 4.2.1. Mandatory Elements
o FEC Encoding ID: the Fully-Specified FEC Scheme described in this o FEC Encoding ID: the Fully-Specified FEC Scheme described in this
section uses FEC Encoding ID 2. section uses FEC Encoding ID 2.
4.2.2. Common Elements 4.2.2. Common Elements
The following elements MUST be defined with the present FEC scheme: The following elements MUST be defined with the present FEC scheme.
o Transfer-Length (L): a non-negative integer indicating the length o Transfer-Length (L): a non-negative integer indicating the length
of the object in bytes. There are some restrictions on the of the object in bytes. There are some restrictions on the
maximum Transfer-Length that can be supported: maximum Transfer-Length that can be supported:
max_transfer_length = 2^^(32-m) * B * E max_transfer_length = 2^^(32-m) * B * E
For instance, for m = 8, for B = 2^^8 - 1 (because the codec For instance, for m = 8, for B = 2^^8 - 1 (because the codec
operates on a finite field with 2^^8 elements) and if E = 1024 operates on a finite field with 2^^8 elements), and if E = 1024
bytes, then the maximum transfer length is approximately equal to bytes, then the maximum transfer length is approximately equal to
2^^42 bytes (i.e., 4 Tera Bytes). Similarly, for m = 16, for B = 2^^42 bytes (i.e., 4 terabytes). Similarly, for m = 16, for B =
2^^16 - 1 and if E = 1024 bytes, then the maximum transfer length 2^^16 - 1, and if E = 1024 bytes, then the maximum transfer length
is also approximately equal to 2^^42 bytes. For larger objects, is also approximately equal to 2^^42 bytes. For larger objects,
another FEC scheme, with a larger Source Block Number field in the another FEC scheme, with a larger Source Block Number field in the
FEC Payload ID, could be defined. Another solution consists in FEC Payload ID, could be defined. Another solution consists in
fragmenting large objects into smaller objects, each of them fragmenting large objects into smaller objects, each of them
complying with the above limits. complying with the above limits.
o Encoding-Symbol-Length (E): a non-negative integer indicating the o Encoding-Symbol-Length (E): a non-negative integer indicating the
length of each encoding symbol in bytes. length of each encoding symbol in bytes.
o Maximum-Source-Block-Length (B): a non-negative integer indicating o Maximum-Source-Block-Length (B): a non-negative integer indicating
skipping to change at page 11, line 49 skipping to change at page 9, line 20
o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer
indicating the maximum number of encoding symbols generated for indicating the maximum number of encoding symbols generated for
any source block. any source block.
Section 6 explains how to derive the values of each of these Section 6 explains how to derive the values of each of these
elements. elements.
4.2.3. Scheme-Specific Elements 4.2.3. Scheme-Specific Elements
The following element MUST be defined with the present FEC Scheme. The following element MUST be defined with the present FEC scheme.
It contains two distinct pieces of information: It contains two distinct pieces of information:
o G: a non-negative integer indicating the number of encoding o G: a non-negative integer indicating the number of encoding
symbols per group used for the object. The default value is 1, symbols per group used for the object. The default value is 1,
meaning that each packet contains exactly one symbol. When no G meaning that each packet contains exactly one symbol. When no G
parameter is communicated to the decoder, then this latter MUST parameter is communicated to the decoder, then the latter MUST
assume that G = 1. assume that G = 1.
o m: The m parameter is the length of the finite field elements, in o m: The m parameter is the length of the finite field elements, in
bits. It also characterizes the number of elements in the finite bits. It also characterizes the number of elements in the finite
field: q = 2^^m elements. The default value is m = 8. When no field: q = 2^^m elements. The default value is m = 8. When no
finite field size parameter is communicated to the decoder, then finite field size parameter is communicated to the decoder, then
this latter MUST assume that m = 8. the latter MUST assume that m = 8.
4.2.4. Encoding Format 4.2.4. Encoding Format
This section shows the two possible encoding formats of the above FEC This section shows the two possible encoding formats of the above FEC
OTI. The present document does not specify when one encoding format OTI. The present document does not specify when one encoding format
or the other should be used. or the other should be used.
4.2.4.1. Using the General EXT_FTI Format 4.2.4.1. Using the General EXT_FTI Format
The FEC OTI binary format is the following, when the EXT_FTI The FEC OTI binary format is the following, when the EXT_FTI
mechanism is used (e.g., within the ALC mechanism is used (e.g., within the ALC [ALC] or NORM [NORM]
[draft-ietf-rmt-pi-alc-revised] or NORM protocols).
[draft-ietf-rmt-pi-norm-revised] protocols).
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| HET = 64 | HEL = 4 | | | HET = 64 | HEL = 4 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| Transfer-Length (L) | | Transfer Length (L) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| m | G | Encoding Symbol Length (E) | | m | G | Encoding Symbol Length (E) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Max Source Block Length (B) | Max Nb Enc. Symbols (max_n) | | Max Source Block Length (B) | Max Nb Enc. Symbols (max_n) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: EXT_FTI Header Format Figure 3: EXT_FTI Header Format
4.2.4.2. Using the FDT Instance (FLUTE specific) 4.2.4.2. Using the FDT Instance (FLUTE specific)
When it is desired that the FEC OTI be carried in the FDT (File When it is desired that the FEC OTI be carried in the FDT (File
Delivery Table) Instance of a FLUTE session Delivery Table) Instance of a FLUTE session [FLUTE], the following
[draft-ietf-rmt-flute-revised], the following XML attributes must be XML attributes must be described for the associated object:
described for the associated object:
o FEC-OTI-FEC-Encoding-ID o FEC-OTI-FEC-Encoding-ID
o FEC-OTI-Transfer-Length (L) o FEC-OTI-Transfer-Length (L)
o FEC-OTI-Encoding-Symbol-Length (E) o FEC-OTI-Encoding-Symbol-Length (E)
o FEC-OTI-Maximum-Source-Block-Length (B) o FEC-OTI-Maximum-Source-Block-Length (B)
o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n)
o FEC-OTI-Scheme-Specific-Info o FEC-OTI-Scheme-Specific-Info
skipping to change at page 13, line 24 skipping to change at page 10, line 47
The FEC-OTI-Scheme-Specific-Info contains the string resulting from The FEC-OTI-Scheme-Specific-Info contains the string resulting from
the Base64 encoding (in the XML Schema xs:base64Binary sense) of the the Base64 encoding (in the XML Schema xs:base64Binary sense) of the
following value: following value:
0 1 0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| m | G | | m | G |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4: FEC OTI Scheme Specific Information to be included in the Figure 4: FEC OTI Scheme Specific Information To Be Included in the
FDT Instance FDT Instance
When no m parameter is to be carried in the FEC OTI, the m field is When no m parameter is to be carried in the FEC OTI, the m field is
set to 0 (which is not a valid seed value). Otherwise the m field set to 0 (which is not a valid seed value). Otherwise, the m field
contains a valid value as explained in Section 4.2.3. Similarly, contains a valid value as explained in Section 4.2.3. Similarly,
when no G parameter is to be carried in the FEC OTI, the G field is when no G parameter is to be carried in the FEC OTI, the G field is
set to 0 (which is not a valid seed value). Otherwise the G field set to 0 (which is not a valid seed value). Otherwise, the G field
contains a valid value as explained in Section 4.2.3. When neither m contains a valid value as explained in Section 4.2.3. When neither m
nor G are to be carried in the FEC OTI, then the sender simply omits nor G are to be carried in the FEC OTI, then the sender simply omits
the FEC-OTI-Scheme-Specific-Info attribute. the FEC-OTI-Scheme-Specific-Info attribute.
During Base64 encoding, the 2 bytes of the FEC OTI Scheme Specific During Base64 encoding, the 2 bytes of the FEC OTI Scheme-Specific
Information are transformed into a string of 4 printable characters Information are transformed into a string of 4 printable characters
(in the 64-character alphabet) that is added to the FEC-OTI-Scheme- (in the 64-character alphabet) that is added to the FEC-OTI-Scheme-
Specific-Info attribute. Specific-Info attribute.
5. Formats and Codes with FEC Encoding ID 5 5. Formats and Codes with FEC Encoding ID 5
This section introduces the formats and codes associated with the This section introduces the formats and codes associated with the
Fully-Specified FEC Scheme with FEC Encoding ID 5 that focuses on the Fully-Specified FEC Scheme with FEC Encoding ID 5, which focuses on
special case of Reed-Solomon codes over GF(2^^8) and no encoding the special case of Reed-Solomon codes over GF(2^^8) and no encoding
symbol group. symbol group.
5.1. FEC Payload ID 5.1. FEC Payload ID
The FEC Payload ID is composed of the Source Block Number and the The FEC Payload ID is composed of the Source Block Number and the
Encoding Symbol ID: Encoding Symbol ID:
o The Source Block Number (24 bit field) identifies from which o The Source Block Number (24-bit field) identifies from which
source block of the object the encoding symbol in the payload is source block of the object the encoding symbol in the payload is
generated. There is a maximum of 2^^24 blocks per object. generated. There is a maximum of 2^^24 blocks per object.
o The Encoding Symbol ID (8 bit field) identifies which specific o The Encoding Symbol ID (8-bit field) identifies which specific
encoding symbol generated from the source block is carried in the encoding symbol generated from the source block is carried in the
packet payload. There is a maximum of 2^^8 encoding symbols per packet payload. There is a maximum of 2^^8 encoding symbols per
block. The first k values (0 to k - 1) identify source symbols, block. The first k values (0 to k - 1) identify source symbols;
the remaining n-k values identify repair symbols. the remaining n-k values identify repair symbols.
There MUST be exactly one FEC Payload ID per source or repair packet. There MUST be exactly one FEC Payload ID per source or repair packet.
This FEC Payload ID refers to the one and only symbol of the packet. This FEC Payload ID refers to the one and only symbol of the packet.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Block Number (24 bits) | Enc. Symb. ID | | Source Block Number (24 bits) | Enc. Symb. ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5: FEC Payload ID encoding format with FEC Encoding ID 5 Figure 5: FEC Payload ID Encoding Format with FEC Encoding ID 5
5.2. FEC Object Transmission Information 5.2. FEC Object Transmission Information
5.2.1. Mandatory Elements 5.2.1. Mandatory Elements
o FEC Encoding ID: the Fully-Specified FEC Scheme described in this o FEC Encoding ID: the Fully-Specified FEC Scheme described in this
section uses FEC Encoding ID 5. section uses FEC Encoding ID 5.
5.2.2. Common Elements 5.2.2. Common Elements
The Common Elements are the same as those specified in Section 4.2.2 The Common elements are the same as those specified in Section 4.2.2
when m = 8 and G = 1. when m = 8 and G = 1.
5.2.3. Scheme-Specific Elements 5.2.3. Scheme-Specific Elements
No Scheme-Specific elements are defined by this FEC Scheme. No Scheme-Specific elements are defined by this FEC scheme.
5.2.4. Encoding Format 5.2.4. Encoding Format
This section shows the two possible encoding formats of the above FEC This section shows the two possible encoding formats of the above FEC
OTI. The present document does not specify when one encoding format OTI. The present document does not specify when one encoding format
or the other should be used. or the other should be used.
5.2.4.1. Using the General EXT_FTI Format 5.2.4.1. Using the General EXT_FTI Format
The FEC OTI binary format is the following, when the EXT_FTI The FEC OTI binary format is the following, when the EXT_FTI
mechanism is used (e.g., within the ALC mechanism is used (e.g., within the ALC [ALC] or NORM [NORM]
[draft-ietf-rmt-pi-alc-revised] or NORM protocols).
[draft-ietf-rmt-pi-norm-revised] protocols).
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| HET = 64 | HEL = 3 | | | HET = 64 | HEL = 3 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| Transfer-Length (L) | | Transfer Length (L) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoding Symbol Length (E) | MaxBlkLen (B) | max_n | | Encoding Symbol Length (E) | MaxBlkLen (B) | max_n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6: EXT_FTI Header Format with FEC Encoding ID 5 Figure 6: EXT_FTI Header Format with FEC Encoding ID 5
5.2.4.2. Using the FDT Instance (FLUTE specific) 5.2.4.2. Using the FDT Instance (FLUTE specific)
When it is desired that the FEC OTI be carried in the FDT Instance of When it is desired that the FEC OTI be carried in the FDT Instance of
a FLUTE session [draft-ietf-rmt-flute-revised], the following XML a FLUTE session [FLUTE], the following XML attributes must be
attributes must be described for the associated object: described for the associated object:
o FEC-OTI-FEC-Encoding-ID o FEC-OTI-FEC-Encoding-ID
o FEC-OTI-Transfer-Length (L) o FEC-OTI-Transfer-Length (L)
o FEC-OTI-Encoding-Symbol-Length (E) o FEC-OTI-Encoding-Symbol-Length (E)
o FEC-OTI-Maximum-Source-Block-Length (B) o FEC-OTI-Maximum-Source-Block-Length (B)
o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n)
6. Procedures with FEC Encoding IDs 2 and 5 6. Procedures with FEC Encoding IDs 2 and 5
skipping to change at page 16, line 9 skipping to change at page 13, line 16
o FEC-OTI-Encoding-Symbol-Length (E) o FEC-OTI-Encoding-Symbol-Length (E)
o FEC-OTI-Maximum-Source-Block-Length (B) o FEC-OTI-Maximum-Source-Block-Length (B)
o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n)
6. Procedures with FEC Encoding IDs 2 and 5 6. Procedures with FEC Encoding IDs 2 and 5
This section defines procedures that are common to FEC Encoding IDs 2 This section defines procedures that are common to FEC Encoding IDs 2
and 5. In case of FEC Encoding ID 5, m = 8 and G = 1. The block and 5. In case of FEC Encoding ID 5, m = 8 and G = 1. The block
partitioning algorithm that is defined in section 9.1 of [RFC5052] partitioning algorithm that is defined in Section 9.1 of [RFC5052]
MUST be used with FEC Encoding IDs 2 and 5. MUST be used with FEC Encoding IDs 2 and 5.
6.1. Determining the Maximum Source Block Length (B) 6.1. Determining the Maximum Source Block Length (B)
The finite field size parameter, m, defines the number of non zero The finite field size parameter, m, defines the number of non-zero
elements in this field which is equal to: q - 1 = 2^^m - 1. Note elements in this field, which is equal to: q - 1 = 2^^m - 1. Note
that q - 1 is also the theoretical maximum number of encoding symbols that q - 1 is also the theoretical maximum number of encoding symbols
that can be produced for a source block. For instance, when m = 8 that can be produced for a source block. For instance, when m = 8
(default) there is a maximum of 2^^8 - 1 = 255 encoding symbols. (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols.
Given the target FEC code rate (e.g., provided by the user when Given the target FEC code rate (e.g., provided by the user when
starting a FLUTE sending application), the sender calculates: starting a FLUTE sending application), the sender calculates:
max1_B = floor((2^^m - 1) * CR) max1_B = floor((2^^m - 1) * CR)
This max1_B value leaves enough room for the sender to produce the This max1_B value leaves enough room for the sender to produce the
skipping to change at page 17, line 26 skipping to change at page 14, line 37
max_n: Maximum number of encoding symbols generated for any source max_n: Maximum number of encoding symbols generated for any source
block. block.
n: Number of encoding symbols generated for this source block. n: Number of encoding symbols generated for this source block.
Algorithm: Algorithm:
max_n = ceil(B / CR); max_n = ceil(B / CR);
if (max_n > 2^^m - 1) then return an error ("invalid code rate"); if (max_n > 2^^m - 1), then return an error ("invalid code rate");
n = floor(k * max_n / B); n = floor(k * max_n / B);
AT A RECEIVER: AT A RECEIVER:
Input: Input:
B: Extracted from the received FEC OTI. B: Extracted from the received FEC OTI.
max_n: Extracted from the received FEC OTI. max_n: Extracted from the received FEC OTI.
skipping to change at page 18, line 7 skipping to change at page 15, line 21
n = floor(k * max_n / B); n = floor(k * max_n / B);
It is RECOMMENDED that the "n-algorithm" be used by a sender, but It is RECOMMENDED that the "n-algorithm" be used by a sender, but
other algorithms remain possible to determine max_n and/or n. other algorithms remain possible to determine max_n and/or n.
At a receiver, the max_n value is extracted from the received FEC At a receiver, the max_n value is extracted from the received FEC
OTI. Since the Reed-Solomon decoder does not need to know the actual OTI. Since the Reed-Solomon decoder does not need to know the actual
n value, using the receiver part of the "n-algorithm" is not n value, using the receiver part of the "n-algorithm" is not
necessary from a decoding point of view. necessary from a decoding point of view.
However a receiver may want to have an estimate of n for other However, a receiver may want to have an estimate of n for other
reasons (e.g., for memory management purposes). In that case, a reasons (e.g., for memory management purposes). In that case, a
receiver knows that the number of encoding symbols of a block cannot receiver knows that the number of encoding symbols of a block cannot
exceed max_n. Additionally, if a receiver believes that a sender exceed max_n. Additionally, if a receiver believes that a sender
uses the "n-algorithm", this receiver MAY use the receiver part of uses the "n-algorithm", this receiver MAY use the receiver part of
the "n-algorithm" to get a better estimate of n. When this is the the "n-algorithm" to get a better estimate of n. When this is the
case, a receiver MUST be prepared to handle symbols with an Encoding case, a receiver MUST be prepared to handle symbols with an Encoding
Symbol ID superior or equal to the computed n value (e.g., it can Symbol ID superior or equal to the computed n value (e.g., it can
choose to simply drop them). choose to simply drop them).
7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed- 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed-
Solomon Codes over GF(2^^8) Solomon Codes over GF(2^^8)
In the context of the Under-Specified Small Block Systematic FEC In the context of the Under-Specified Small Block Systematic FEC
Scheme (FEC Encoding ID 129) Scheme (FEC Encoding ID 129) [RFC5445], this document assigns the FEC
[draft-ietf-rmt-bb-fec-basic-schemes-revised], this document assigns Instance ID 0 to the special case of Reed-Solomon codes over GF(2^^8)
the FEC Instance ID 0 to the special case of Reed-Solomon codes over and no encoding symbol group.
GF(2^^8) and no encoding symbol group.
The FEC Instance ID 0 uses the Formats and Codes specified in The FEC Instance ID 0 uses the Formats and Codes specified in
[draft-ietf-rmt-bb-fec-basic-schemes-revised]. [RFC5445].
The FEC Scheme with FEC Instance ID 0 MAY use the block partitioning The FEC scheme with FEC Instance ID 0 MAY use the block partitioning
algorithm defined in Section 9.1. of [RFC5052] to partition the algorithm defined in Section 9.1 of [RFC5052] to partition the object
object into source blocks. This FEC Scheme MAY also use another into source blocks. This FEC scheme MAY also use another algorithm.
algorithm. For instance the CDP sender may change the length of each For instance, the CDP sender may change the length of each source
source block dynamically, depending on some external criteria (e.g., block dynamically, depending on some external criteria (e.g., to
to adjust the FEC coding rate to the current loss rate experienced by adjust the FEC coding rate to the current loss rate experienced by
NORM receivers) and inform the CDP receivers of the current block NORM receivers) and inform the CDP receivers of the current block
length by means of the EXT_FTI mechanism. This choice is out of the length by means of the EXT_FTI mechanism. This choice is out of the
scope of the current document. scope of the current document.
8. Reed-Solomon Codes Specification for the Erasure Channel 8. Reed-Solomon Codes Specification for the Erasure Channel
Reed-Solomon (RS) codes are linear block codes. They also belong to Reed-Solomon (RS) codes are linear block codes. They also belong to
the class of MDS codes. A [n,k]-RS code encodes a sequence of k the class of MDS codes. A [n,k]-RS code encodes a sequence of k
source elements defined over a finite field GF(q) into a sequence of source elements defined over a finite field GF(q) into a sequence of
n encoding elements, where n is upper bounded by q - 1. The n encoding elements, where n is upper bounded by q - 1. The
implementation described in this document is based on a generator implementation described in this document is based on a generator
matrix built from a Vandermonde matrix put into systematic form. matrix built from a Vandermonde matrix put into systematic form.
Section 8.1 to Section 8.3 specify the [n,k]-RS codes when applied to Sections 8.1 to 8.3 specify the [n,k]-RS codes when applied to m-bit
m-bit elements, and Section 8.4 the use of [n,k]-RS codes when elements, and Section 8.4 specifies the use of [n,k]-RS codes when
applied to symbols composed of several m-bit elements, which is the applied to symbols composed of several m-bit elements. The use
target of this specification. described in Section 8.4 is the crux of this specification.
A reader who wants to understand the underlying theory is invited to A reader who wants to understand the underlying theory is invited to
refer to references [Rizzo97] and [MWS77]. refer to references [Rizzo97] and [MWS77].
8.1. Finite Field 8.1. Finite Field
A finite field GF(q) is defined as a finite set of q elements which A finite field GF(q) is defined as a finite set of q elements that
has a structure of field. It contains necessarily q = p^^m elements, has a structure of field. It contains necessarily q = p^^m elements,
where p is a prime number. With packet erasure channels, p is always where p is a prime number. With packet erasure channels, p is always
set to 2. The elements of the field GF(2^^m) can be represented by set to 2. The elements of the field GF(2^^m) can be represented by
polynomials with binary coefficients (i.e., over GF(2)) of degree polynomials with binary coefficients (i.e., over GF(2)) of degree
lower or equal to m-1. The polynomials can be associated with binary lower or equal to m-1. The polynomials can be associated with binary
vectors of length m. For example, the vector (11001) represents the vectors of length m. For example, the vector (11001) represents the
polynomial 1 + x + x^^4. This representation is often called polynomial 1 + x + x^^4. This representation is often called
polynomial representation. The addition between two elements is polynomial representation. The addition between two elements is
defined as the addition of binary polynomials in GF(2) and the defined as the addition of binary polynomials in GF(2) and the
multiplication is the multiplication modulo a given irreducible multiplication is the multiplication modulo a given irreducible
skipping to change at page 21, line 44 skipping to change at page 17, line 44
GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding
vector of n elements over GF(2^^m). Being a linear code, encoding is vector of n elements over GF(2^^m). Being a linear code, encoding is
performed by multiplying the source vector by a generator matrix, GM, performed by multiplying the source vector by a generator matrix, GM,
of k rows and n columns over GF(2^^m). Thus: of k rows and n columns over GF(2^^m). Thus:
e = s * GM. e = s * GM.
The definition of the generator matrix completely characterizes the The definition of the generator matrix completely characterizes the
RS code. RS code.
Let us consider that: n = 2^^m - 1 and: 0 < k <= n. Let us denote by Let us consider that n = 2^^m - 1 and that 0 < k <= n. Let us denote
alpha the root of the primitive polynomial of degree m chosen in the by alpha the root of the primitive polynomial of degree m chosen in
list of Section 8.1 for the corresponding value of m. Let us the list of Section 8.1 for the corresponding value of m. Let us
consider a Vandermonde matrix of k rows and n columns, denoted by consider a Vandermonde matrix of k rows and n columns, denoted by
V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j} V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j}
= alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This = alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This
matrix generates a MDS code. However, this MDS code is not matrix generates a MDS code. However, this MDS code is not
systematic, which is a problem for many networking applications. To systematic, which is a problem for many networking applications. To
obtain a systematic matrix (and code), the simplest solution consists obtain a systematic matrix (and code), the simplest solution consists
in considering the matrix V_{k,k} formed by the first k columns of in considering the matrix V_{k,k} formed by the first k columns of
V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}. V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}.
Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity
matrix I_k on its first k columns, meaning that the first k encoding matrix I_k on its first k columns, meaning that the first k encoding
elements are equal to source elements. Besides the associated code elements are equal to source elements. Besides, the associated code
keeps the MDS property. keeps the MDS property.
Therefore, the generator matrix of the code considered in this Therefore, the generator matrix of the code considered in this
document is: document is:
GM = (V_{k,k}^^-1) * V_{k,n} GM = (V_{k,k}^^-1) * V_{k,n}
Note that, in practice, the [n,k]-RS code can be shortened to a Note that, in practice, the [n,k]-RS code can be shortened to a
[n',k]-RS code, where k <= n' < n, by considering the sub-matrix [n',k]-RS code, where k <= n' < n, by considering the sub-matrix
formed by the n' first columns of GM. formed by the n' first columns of GM.
skipping to change at page 22, line 51 skipping to change at page 18, line 51
complexity of this encoding algorithm is then O((k/(n-k)) * complexity of this encoding algorithm is then O((k/(n-k)) *
(log(k))^^2 + log(k)) operations per repair element. (log(k))^^2 + log(k)) operations per repair element.
8.3. Reed-Solomon Decoding Algorithm 8.3. Reed-Solomon Decoding Algorithm
8.3.1. Decoding Principles 8.3.1. Decoding Principles
The Reed-Solomon decoding algorithm for the erasure channel allows The Reed-Solomon decoding algorithm for the erasure channel allows
the recovery of the k source elements from any set of k received the recovery of the k source elements from any set of k received
elements. It is based on the fundamental property of the generator elements. It is based on the fundamental property of the generator
matrix which is such that any k*k-submatrix is invertible (see matrix, which is such that any k*k-submatrix is invertible (see
[MWS77]). The first step of the decoding consists in extracting the [MWS77]). The first step of the decoding consists in extracting the
k*k submatrix of the generator matrix obtained by considering the k*k submatrix of the generator matrix obtained by considering the
columns corresponding to the received elements. Indeed, since any columns corresponding to the received elements. Indeed, since any
encoding element is obtained by multiplying the source vector by one encoding element is obtained by multiplying the source vector by one
column of the generator matrix, the received vector of k encoding column of the generator matrix, the received vector of k encoding
elements can be considered as the result of the multiplication of the elements can be considered as the result of the multiplication of the
source vector by a k*k submatrix of the generator matrix. Since this source vector by a k*k submatrix of the generator matrix. Since this
submatrix is invertible, the second step of the algorithm is to submatrix is invertible, the second step of the algorithm is to
invert this matrix and to multiply the received vector by the invert this matrix and to multiply the received vector by the
obtained matrix to recover the source vector. obtained matrix to recover the source vector.
skipping to change at page 23, line 25 skipping to change at page 19, line 25
8.3.2. Decoding Complexity 8.3.2. Decoding Complexity
The decoding algorithm described previously includes the matrix The decoding algorithm described previously includes the matrix
inversion and the vector-matrix multiplication. With the classical inversion and the vector-matrix multiplication. With the classical
Gauss-Jordan algorithm, the matrix inversion requires O(k^^3) Gauss-Jordan algorithm, the matrix inversion requires O(k^^3)
operations and the vector-matrix multiplication is performed in operations and the vector-matrix multiplication is performed in
O(k^^2) operations. O(k^^2) operations.
This complexity can be improved by considering that the received This complexity can be improved by considering that the received
submatrix of GM is the product between the inverse of a Vandermonde submatrix of GM is the product between the inverse of a Vandermonde
matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V' matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V',
which is a submatrix of V_(k,n)). The decoding can be done by which is a submatrix of V_(k,n)). The decoding can be done by
multiplying the received vector by V'^^-1 (interpolation problem with multiplying the received vector by V'^^-1 (interpolation problem with
complexity O( k * (log(k))^^2) ) then by V_{k,k} (multipoint complexity O( k * (log(k))^^2) ) then by V_{k,k} (multipoint
evaluation with complexity O(k * log(k))). The global decoding evaluation with complexity O(k * log(k))). The global decoding
complexity is then O((log(k))^^2) operations per source element. complexity is then O((log(k))^^2) operations per source element.
8.4. Implementation for the Packet Erasure Channel 8.4. Implementation for the Packet Erasure Channel
In a packet erasure channel, each packet (and symbol(s) since packets In a packet erasure channel, each packet (including its symbol(s),
contain G >= 1 symbols) is either correctly received or erased. The since packets contain G >= 1 symbols) is either correctly received or
location of the erased symbols in the sequence of symbols MUST be erased. The location of the erased symbols in the sequence of
known. The following specification describes the use of Reed-Solomon symbols MUST be known. The following specification describes the use
codes for generating redundant symbols from the k source symbols and of Reed-Solomon codes for generating redundant symbols from the k
for recovering the source symbols from any set of k received symbols. source symbols and for recovering the source symbols from any set of
k received symbols.
The k source symbols of a source block are assumed to be composed of The k source symbols of a source block are assumed to be composed of
S m-bit elements. Each m-bit element corresponds to an element of S m-bit elements. Each m-bit element corresponds to an element of
the finite field GF(2^^m) through the polynomial representation the finite field GF(2^^m) through the polynomial representation
(Section 8.1). If some of the source symbols contain less than S (Section 8.1). If some of the source symbols contain less than S
elements, they MUST be virtually padded with zero elements (this can elements, they MUST be virtually padded with zero elements (this can
be the case for the last symbol of the last block of the object). be the case for the last symbol of the last block of the object).
However, this padding does not need to be actually sent with the data However, this padding does not need to be actually sent with the data
to the receivers. to the receivers.
The encoding process produces n encoding symbols of size S m-bit The encoding process produces n encoding symbols of size S m-bit
elements, of which k are source symbols (this is a systematic code) elements, of which k are source symbols (this is a systematic code)
and n-k are repair symbols (Figure 7). The m-bit elements of the and n-k are repair symbols (Figure 7). The m-bit elements of the
repair symbols are calculated using the corresponding m-bit elements repair symbols are calculated using the corresponding m-bit elements
of the source symbol set. A logical u-th source vector, comprised of of the source symbol set. A logical u-th source vector, comprised of
the u-th elements from the set of source symbols, is used to the u-th elements from the set of source symbols, is used to
calculate a u-th encoding vector. This u-th encoding vector then calculate a u-th encoding vector. This u-th encoding vector then
provides the u-th elements for the set encoding symbols calculated provides the u-th elements for the set encoding symbols calculated
for the block. As a systematic code, the first k encoding symbols for the block. As a systematic code, the first k encoding symbols
are the same as the k source symbols and the last n-k repair symbols are the same as the k source symbols, and the last n-k repair symbols
are the result of the Reed-Solomon encoding. are the result of the Reed-Solomon encoding.
Input: k source symbols Input: k source symbols
0 u S-1 0 u S-1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |X| | source symbol 0 | |X| | source symbol 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |X| | source symbol 1 | |X| | source symbol 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. . . . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |X| | source symbol k-1 | |X| | source symbol k-1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
* *
+--------------------+ +--------------------+
| generator matrix | | generator matrix |
| GM | | GM |
| (k x n) | | (k x n) |
+--------------------+ +--------------------+
| |
V V
Output: n encoding symbols (source + repair) Output: n encoding symbols (source + repair)
0 u S-1 0 u S-1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |X| | enc. symbol 0 | |X| | enc. symbol 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |X| | enc. symbol 1 | |X| | enc. symbol 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. . . . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |Y| | enc. symbol n-1 | |Y| | enc. symbol n-1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 7: Packet encoding scheme Figure 7: Packet Encoding Scheme
An asset of this scheme is that the loss of some encoding symbols An asset of this scheme is that the loss of some encoding symbols
produces the same erasure pattern for each of the S encoding vectors. produces the same erasure pattern for each of the S encoding vectors.
It follows that the matrix inversion must be done only once and will It follows that the matrix inversion must be done only once and will
be used by all the S encoding vectors. For large S, this matrix be used by all the S encoding vectors. For large S, this matrix
inversion cost becomes negligible in front of the S matrix-vector inversion cost becomes negligible in front of the S vector-matrix
multiplications. multiplications.
Another asset is that the n-k repair symbols can be produced on Another asset is that the n-k repair symbols can be produced on
demand. For instance, a sender can start by producing a limited demand. For instance, a sender can start by producing a limited
number of repair symbols and later on, depending on the observed number of repair symbols and later on, depending on the observed
erasures on the channel, decide to produce additional repair symbols, erasures on the channel, decide to produce additional repair symbols,
up to the n-k upper limit. Indeed, to produce the repair symbol e_j, up to the n-k upper limit. Indeed, to produce the repair symbol e_j,
where k <= j < n, it is sufficient to multiply the S source vectors where k <= j < n, it is sufficient to multiply the S source vectors
with column j of GM. with column j of GM.
skipping to change at page 27, line 22 skipping to change at page 22, line 30
others target the Content Delivery Protocol (CDP) (e.g., to others target the Content Delivery Protocol (CDP) (e.g., to
compromise its normal behavior), and finally some attacks target the compromise its normal behavior), and finally some attacks target the
content itself. Since this document focuses on a FEC building block content itself. Since this document focuses on a FEC building block
independently of any particular CDP (even if ALC and NORM are two independently of any particular CDP (even if ALC and NORM are two
natural candidates), this section only discusses the additional natural candidates), this section only discusses the additional
threats that an arbitrary CDP may be exposed to when using this threats that an arbitrary CDP may be exposed to when using this
building block. building block.
More specifically, several kinds of attacks exist: More specifically, several kinds of attacks exist:
o those that are meant to give access to a confidential content o those that are meant to give access to confidential content (e.g.,
(e.g., in case of a non-free content), in case of non-free content),
o those that try to corrupt the object being transmitted (e.g., to o those that try to corrupt the object being transmitted (e.g., to
inject malicious code within an object, or to prevent a receiver inject malicious code within an object or to prevent a receiver
from using an object), from using an object),
o and those that try to compromise the receiver's behavior (e.g., by o and those that try to compromise the receiver's behavior (e.g., by
making the decoding of an object computationally expensive). making the decoding of an object computationally expensive).
These attacks can be launched either against the data flow itself These attacks can be launched either against the data flow itself
(e.g. by sending forged symbols) or against the FEC parameters that (e.g., by sending forged symbols) or against the FEC parameters that
are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out- are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out-
of-band (e.g., in a session description). of-band (e.g., in a session description).
9.2. Attacks Against the Data Flow 9.2. Attacks against the Data Flow
First of all, let us consider the attacks against the data flow. First of all, let us consider the attacks against the data flow.
9.2.1. Access to Confidential Objects 9.2.1. Access to Confidential Objects
Access control to the object being transmitted is typically provided Access control to the object being transmitted is typically provided
by means of encryption. This encryption can be done over the whole by means of encryption. This encryption can be done over the whole
object (e.g., by the content provider, before the FEC encoding object (e.g., by the content provider, before the FEC encoding
process), or be done on a packet per packet basis (e.g., when IPSec/ process), or be done on a packet per-packet basis (e.g., when IPsec
ESP is used [RFC4303]). If access control is a concern, it is Encapsulating Security Payload (ESP) is used [RFC4303]). If access
RECOMMENDED that one of these solutions be used. Even if we mention control is a concern, it is RECOMMENDED that one of these solutions
these attacks here, they are not related nor facilitated by the use be used. Even if we mention these attacks here, they are not related
of FEC. nor facilitated by the use of FEC.
9.2.2. Content Corruption 9.2.2. Content Corruption
Protection against corruptions (e.g., after sending forged packets) Protection against corruptions (e.g., after sending forged packets)
is achieved by means of a content integrity verification/sender is achieved by means of a content integrity verification/sender
authentication scheme. This service can be provided at the object authentication scheme. This service can be provided at the object
level, but in that case a receiver has no way to identify which level, but in that case a receiver has no way to identify which
symbol(s) is(are) corrupted if the object is detected as corrupted. symbol(s) are corrupted if the object is detected as corrupted. This
This service can also be provided at the packet level. In this case, service can also be provided at the packet level. In this case,
after removing all forged packets, the object may be in some case after removing all forged packets, the object may be recovered
recovered. Several techniques can provide this source sometimes. Several techniques can provide this source
authentication/content integrity service: authentication/content integrity service:
o at the object level, the object MAY be digitally signed (with o At the object level, the object MAY be digitally signed (with
public key cryptography), for instance by using RSASSA-PKCS1-v1_5 public key cryptography), for instance by using RSASSA-PKCS1-v1_5
[RFC3447]. This signature enables a receiver to check the object [RFC3447]. This signature enables a receiver to check the object
integrity, once this latter has been fully decoded. Even if integrity, once the object has been fully decoded. Even if
digital signatures are computationally expensive, this calculation digital signatures are computationally expensive, this calculation
occurs only once per object, which is usually acceptable; occurs only once per object, which is usually acceptable.
o at the packet level, each packet can be digitally signed. A major o At the packet level, each packet can be digitally signed. A major
limitation is the high computational and transmission overheads limitation is the high computational and transmission overheads
that this solution requires (unless Elliptic Curve Cryptography that this solution requires (unless Elliptic Curve Cryptography
(ECC) is used, but ECC is the subject of proprietary patents). To (ECC) is used). To avoid this problem, the signature may span a
avoid this problem, the signature may span a set of symbols set of symbols (instead of a single one) in order to amortize the
(instead of a single one) in order to amortize the signature signature calculation. But if a single symbol is missing, the
calculation. But if a single symbol is missing, the integrity of integrity of the whole set cannot be checked.
the whole set cannot be checked;
o at the packet level, a Group Message Authentication Code (MAC) o At the packet level, a Group Message Authentication Code (MAC)
[RFC2104] scheme can be used, for instance by using HMAC-SHA-1 [RFC2104] scheme can be used; for instance, by using HMAC-SHA-256
with a secret key shared by all the group members, senders and with a secret key shared by all the group members (i.e., the
receivers. This technique creates a cryptographically secured sender(s) and receivers). Thanks to the secret key, this
(thanks to the secret key) digest of a packet that is sent along technique creates a cryptographically secured digest of a packet
with the packet. The Group MAC scheme does not create prohibitive that is sent along with the packet. The Group MAC scheme does not
processing load nor transmission overhead, but it has a major create prohibitive processing load nor transmission overhead, but
limitation: it only provides a group authentication/integrity it has a major limitation: it only provides a group
service since all group members share the same secret group key, authentication/integrity service since all group members share the
which means that each member can send a forged packet. It is same secret group key, which means that each member can send a
therefore restricted to situations where group members are fully forged packet. It is therefore restricted to situations where
trusted (or in association with another technique as a pre-check); group members are fully trusted (or in association with another
technique as a pre-check).
o at the packet level, TESLA [RFC4082] is a very attractive and o At the packet level, TESLA [RFC4082] is a very attractive and
efficient solution that is robust to losses, provides a true efficient solution that is robust to losses, provides a true
authentication/integrity service, and does not create any authentication/integrity service, and does not create any
prohibitive processing load or transmission overhead. Yet prohibitive processing load or transmission overhead. Yet
checking a packet requires a small delay (a second or more) after checking a packet requires a small delay (a second or more) after
its reception; its reception.
Techniques relying on public key cryptography (digital signatures and Techniques relying on public key cryptography (digital signatures and
TESLA during the bootstrap process, when used) require that public TESLA during the bootstrap process, when used) require that public
keys be securely associated to the entities. This can be achieved by keys be securely associated to the entities. This can be achieved by
a Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by a Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by
pre-distributing the public keys of each group member. pre-distributing the public keys of each group member.
Techniques relying on symmetric key cryptography (group MAC) require Techniques relying on symmetric key cryptography (group MAC) require
that a secret key be shared by all group members. This can be that a secret key be shared by all group members. This can be
achieved by means of a group key management protocol, or simply by achieved by means of a group key management protocol, or simply by
pre-distributing the secret key (but this manual solution has many pre-distributing the secret key (but this manual solution has many
limitations). limitations).
It is up to the developer and deployer, who know the security It is up to the developer and deployer, who know the security
requirements and features of the target application area, to define requirements and features of the target application area, to define
which solution is the most appropriate. Nonetheless, in case there which solution is the most appropriate. Nonetheless, in case there
is any concern of the threat of object corruption, it is RECOMMENDED is any concern of the threat of object corruption, it is RECOMMENDED
that at least one of these techniques be used. that at least one of these techniques be used.
9.3. Attacks Against the FEC Parameters 9.3. Attacks against the FEC Parameters
Let us now consider attacks against the FEC parameters (or FEC OTI). Let us now consider attacks against the FEC parameters (or FEC OTI).
The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an
FDT Instance containing FEC OTI for the object) or out-of-band (e.g., FDT Instance containing FEC OTI for the object) or out-of-band (e.g.,
in a session description). Attacks on these FEC parameters can in a session description). Attacks on these FEC parameters can
prevent the decoding of the associated object: for instance modifying prevent the decoding of the associated object: for instance,
the B parameter will lead to a different block partitioning at a modifying the B parameter will lead to a different block partitioning
receiver thereby compromising decoding; or setting the m parameter to at a receiver thereby compromising decoding; or setting the m
16 instead of 8 with FEC Encoding ID 2 will increase the processing parameter to 16 instead of 8 with FEC Encoding ID 2 will increase the
load while compromising decoding. processing load while compromising decoding.
It is therefore RECOMMENDED that security measures be taken to It is therefore RECOMMENDED that security measures be taken to
guarantee the FEC OTI integrity. To that purpose, the packets guarantee the FEC OTI integrity. To that purpose, the packets
carrying the FEC parameters sent in-band in an EXT_FTI header carrying the FEC parameters sent in-band in an EXT_FTI header
extension SHOULD be protected by one of the per-packet techniques extension SHOULD be protected by one of the per-packet techniques
described above: digital signature, group MAC, or TESLA. When FEC described above: digital signature, group MAC, or TESLA. When FEC
OTI is contained in an FDT Instance, this object SHOULD be protected, OTI is contained in an FDT Instance, this FDT Instance object SHOULD
for instance by digitally signing it with XML digital signatures be protected, for instance, by digitally signing it with XML digital
[RFC3275]. Finally, when FEC OTI is sent out-of-band (e.g., in a signatures [RFC3275]. Finally, when FEC OTI is sent out-of-band
session description) this latter SHOULD be protected, for instance by (e.g., in a session description), this FEC OTI SHOULD be protected,
digitally signing it. for instance, by digitally signing the object that includes this FEC
OTI.
The same considerations concerning the key management aspects apply The same considerations concerning the key management aspects apply
here also. here also.
10. IANA Considerations 10. IANA Considerations
Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA
registration. For general guidelines on IANA considerations as they registration. For general guidelines on IANA considerations as they
apply to this document, see [RFC5052]. apply to this document, see [RFC5052].
skipping to change at page 31, line 8 skipping to change at page 25, line 40
This document assigns the FEC Instance ID 0 scoped by the Under- This document assigns the FEC Instance ID 0 scoped by the Under-
Specified FEC Encoding ID 129 to "Reed-Solomon Codes over GF(2^^8)". Specified FEC Encoding ID 129 to "Reed-Solomon Codes over GF(2^^8)".
More specifically, under the "ietf:rmt:fec:encoding:instance" sub- More specifically, under the "ietf:rmt:fec:encoding:instance" sub-
name-space that is scoped by the "ietf:rmt:fec:encoding" called name-space that is scoped by the "ietf:rmt:fec:encoding" called
"Small Block Systematic FEC Codes", this document assigns FEC "Small Block Systematic FEC Codes", this document assigns FEC
Instance ID 0 to "Reed-Solomon Codes over GF(2^^8)". Instance ID 0 to "Reed-Solomon Codes over GF(2^^8)".
11. Acknowledgments 11. Acknowledgments
The authors want to thank Brian Adamson, Igor Slepchin, Stephen Kent, The authors want to thank Brian Adamson, Igor Slepchin, Stephen Kent,
Francis Dupont, Elwyn Davies, Magnus Westerlund and Alfred Hoenes for Francis Dupont, Elwyn Davies, Magnus Westerlund, and Alfred Hoenes
their valuable comments. The authors also want to thank Luigi Rizzo for their valuable comments. The authors also want to thank Luigi
for his comments and for the design of the reference Reed-Solomon Rizzo for his comments and for the design of the reference Reed-
codec. Solomon codec.
12. References 12. References
12.1. Normative References 12.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error
Correction (FEC) Building Block", RFC 5052, August 2007. Correction (FEC) Building Block", RFC 5052, August 2007.
[draft-ietf-rmt-bb-fec-basic-schemes-revised] [RFC5445] Watson, M., "Basic Forward Error Correction (FEC)
Watson, M., "Basic Forward Error Correction (FEC) Schemes", RFC 5445, March 2009.
Schemes",
draft-ietf-rmt-bb-fec-basic-schemes-revised-03.txt (work
in progress), February 2007.
12.2. Informative References 12.2. Informative References
[RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley,
M., and J. Crowcroft, "The Use of Forward Error Correction M., and J. Crowcroft, "The Use of Forward Error
(FEC) in Reliable Multicast", RFC 3453, December 2002. Correction (FEC) in Reliable Multicast", RFC 3453,
December 2002.
[RS-codec] [RS-codec] Rizzo, L., "Reed-Solomon FEC codec", available at
Rizzo, L., "Reed-Solomon FEC codec (revised version of
July 2nd, 1998), available at
http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz and http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz and
mirrored at http://planete-bcast.inrialpes.fr/", mirrored at http://planete-bcast.inrialpes.fr/, revised
July 1998. version of July 1998.
[Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable Computer [Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable Computer
Communication Protocols", ACM SIGCOMM Computer Communication Protocols", ACM SIGCOMM Computer
Communication Review Vol.27, No.2, pp.24-36, April 1997. Communication Review Vol.27, No.2, pp.24-36, April 1997.
[MWS77] Mac Williams, F. and N. Sloane, "The Theory of Error [MWS77] Mac Williams, F. and N. Sloane, "The Theory of Error
Correcting Codes", North Holland, 1977. Correcting Codes", North Holland, 1977.
[GO94] Gohberg, I. and V. Olshevsky, "Fast algorithms with [GO94] Gohberg, I. and V. Olshevsky, "Fast algorithms with
preprocessing for matrix-vector multiplication problems", preprocessing for matrix-vector multiplication problems",
Journal of Complexity, pp. 411-427, vol. 10, 1994. Journal of Complexity, pp. 411-427, vol. 10, 1994.
[draft-ietf-rmt-bb-fec-ldpc] [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density
Roca, V., Neumann, C., and D. Furodet, "Low Density Parity Parity Check (LDPC) Forward Error Correction", RFC 5170,
Check (LDPC) Forward Error Correction", June 2008.
draft-ietf-rmt-bb-fec-ldpc-07.txt (work in progress),
November 2007.
[RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T.
"Raptor Forward Error Correction Scheme", RFC 5053, Stockhammer, "Raptor Forward Error Correction Scheme",
June 2007. RFC 5053, October 2007.
[draft-ietf-rmt-pi-alc-revised] [ALC] Luby, M., Watson, M., and L. Vicisano, "Asynchronous
Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered Coding (ALC) Protocol Instantiation", Work
Layered Coding (ALC) Protocol Instantiation", in Progress, November 2008.
draft-ietf-rmt-pi-alc-revised-04.txt (work in progress),
February 2007.
[draft-ietf-rmt-pi-norm-revised] [NORM] Adamson, B., Bormann, C., Handley, M., and J. Macker,
Adamson, B., Bormann, C., Handley, M., and J. Macker, "NACK-Oriented Reliable Multicast Protocol", Work
"Negative-acknowledgment (NACK)-Oriented Reliable in Progress, March 2009.
Multicast (NORM) Protocol",
draft-ietf-rmt-pi-norm-revised-05.txt (work in progress),
March 2007.
[draft-ietf-rmt-flute-revised] [FLUTE] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V.
Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, Roca, "FLUTE - File Delivery over Unidirectional
"FLUTE - File Delivery over Unidirectional Transport", Transport", Work in Progress, September 2008.
draft-ietf-rmt-flute-revised-05.txt (work in progress),
October 2007.
[RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography
Standards (PKCS) #1: RSA Cryptography Specifications Standards (PKCS) #1: RSA Cryptography Specifications
Version 2.1", RFC 3447, February 2003. Version 2.1", RFC 3447, February 2003.
[RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)",
RFC 4303, December 2005. RFC 4303, December 2005.
[RFC2104] "HMAC: Keyed-Hashing for Message Authentication", [RFC2104] "HMAC: Keyed-Hashing for Message Authentication",
RFC 2104, February 1997. RFC 2104, February 1997.
[RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication [RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication
(TESLA): Multicast Source Authentication Transform (TESLA): Multicast Source Authentication Transform
Introduction", RFC 4082, June 2005. Introduction", RFC 4082, June 2005.
[RFC3275] Eastlake, D., Reagle, J., and D. Solo, "(Extensible Markup [RFC3275] Eastlake 3rd, D., Reagle, J., and D. Solo, "(Extensible
Language) XML-Signature Syntax and Processing", RFC 3275, Markup Language) XML-Signature Syntax and Processing",
March 2002. RFC 3275, March 2002.
Authors' Addresses Authors' Addresses
Jerome Lacan Jerome Lacan
ISAE/LAAS-CNRS ISAE/LAAS-CNRS
1, place Emile Blouin 1, place Emile Blouin
Toulouse 31056 Toulouse 31056
France France
Email: jerome.lacan@isae.fr EMail: jerome.lacan@isae.fr
URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5 URI: http://pagespro.isae.fr/jerome-lacan/
Vincent Roca Vincent Roca
INRIA INRIA
655, av. de l'Europe 655, av. de l'Europe
Inovallee; Montbonnot Inovallee; Montbonnot
ST ISMIER cedex 38334 ST ISMIER cedex 38334
France France
Email: vincent.roca@inria.fr EMail: vincent.roca@inria.fr
URI: http://planete.inrialpes.fr/people/roca/ URI: http://planete.inrialpes.fr/people/roca/
Jani Peltotalo Jani Peltotalo
Tampere University of Technology Tampere University of Technology
P.O. Box 553 (Korkeakoulunkatu 1) P.O. Box 553 (Korkeakoulunkatu 1)
Tampere FIN-33101 Tampere FIN-33101
Finland Finland
Email: jani.peltotalo@tut.fi EMail: jani.peltotalo@tut.fi
URI: http://atm.tut.fi/mad URI: http://mad.cs.tut.fi/
Sami Peltotalo Sami Peltotalo
Tampere University of Technology Tampere University of Technology
P.O. Box 553 (Korkeakoulunkatu 1) P.O. Box 553 (Korkeakoulunkatu 1)
Tampere FIN-33101 Tampere FIN-33101
Finland Finland
Email: sami.peltotalo@tut.fi EMail: sami.peltotalo@tut.fi
URI: http://atm.tut.fi/mad URI: http://mad.cs.tut.fi/
Full Copyright Statement
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
 End of changes. 136 change blocks. 
333 lines changed or deleted 314 lines changed or added

This html diff was produced by rfcdiff 1.35. The latest version is available from http://tools.ietf.org/tools/rfcdiff/