```
' and
'
``````
' lines.
Checking references for intended status: Proposed Standard
----------------------------------------------------------------------------
(See RFCs 3967 and 4897 for information about using normative references
to lower-maturity documents in RFCs)
-- Looks like a reference, but probably isn't: '0' on line 739
** Downref: Normative reference to an Informational RFC: RFC 3453
-- Obsolete informational reference (is this intentional?): RFC 3447
(Obsoleted by RFC 8017)
-- Obsolete informational reference (is this intentional?): RFC 3852
(Obsoleted by RFC 5652)
Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 11 comments (--).
Run idnits with the --verbose option for more detailed information about
the items above.
--------------------------------------------------------------------------------
2 RMT V. Roca
3 Internet-Draft INRIA
4 Intended status: Standards Track C. Neumann
5 Expires: July 26, 2008 Thomson
6 D. Furodet
7 STMicroelectronics
8 January 23, 2008
10 Low Density Parity Check (LDPC) Staircase and Triangle Forward Error
11 Correction (FEC) Schemes
12 draft-ietf-rmt-bb-fec-ldpc-08.txt
14 Status of this Memo
16 By submitting this Internet-Draft, each author represents that any
17 applicable patent or other IPR claims of which he or she is aware
18 have been or will be disclosed, and any of which he or she becomes
19 aware will be disclosed, in accordance with Section 6 of BCP 79.
21 Internet-Drafts are working documents of the Internet Engineering
22 Task Force (IETF), its areas, and its working groups. Note that
23 other groups may also distribute working documents as Internet-
24 Drafts.
26 Internet-Drafts are draft documents valid for a maximum of six months
27 and may be updated, replaced, or obsoleted by other documents at any
28 time. It is inappropriate to use Internet-Drafts as reference
29 material or to cite them other than as "work in progress."
31 The list of current Internet-Drafts can be accessed at
32 http://www.ietf.org/ietf/1id-abstracts.txt.
34 The list of Internet-Draft Shadow Directories can be accessed at
35 http://www.ietf.org/shadow.html.
37 This Internet-Draft will expire on July 26, 2008.
39 Copyright Notice
41 Copyright (C) The IETF Trust (2008).
43 Abstract
45 This document describes two Fully-Specified FEC Schemes, LDPC-
46 Staircase and LDPC-Triangle, and their application to the reliable
47 delivery of data objects on the packet erasure channel (i.e., a
48 communication path where packets are either received without any
49 corruption or discarded during transmission). These systematic FEC
50 codes belong to the well known class of ``Low Density Parity Check''
51 (LDPC) codes, and are large block FEC codes in the sense of RFC3453.
53 Table of Contents
55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5
56 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 6
57 3. Definitions, Notations and Abbreviations . . . . . . . . . . . 7
58 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 7
59 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 7
60 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 8
61 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 9
62 4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 9
63 4.2. FEC Object Transmission Information . . . . . . . . . . . 9
64 4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 9
65 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 9
66 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 10
67 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 10
68 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 13
69 5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 13
70 5.2. Determining the Maximum Source Block Length (B) . . . . . 14
71 5.3. Determining the Encoding Symbol Length (E) and Number
72 of Encoding Symbols per Group (G) . . . . . . . . . . . . 15
73 5.4. Determining the Maximum Number of Encoding Symbols
74 Generated for Any Source Block (max_n) . . . . . . . . . . 16
75 5.5. Determining the Number of Encoding Symbols of a Block
76 (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
77 5.6. Identifying the G Symbols of an Encoding Symbol Group . . 17
78 5.7. Pseudo Random Number Generator . . . . . . . . . . . . . . 21
79 6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 23
80 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 23
81 6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 23
82 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 25
83 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25
84 7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 27
85 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 27
86 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 27
87 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 28
88 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 28
89 8. Security Considerations . . . . . . . . . . . . . . . . . . . 29
90 8.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 29
91 8.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 29
92 8.2.1. Access to Confidential Objects . . . . . . . . . . . . 29
93 8.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 30
94 8.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 31
95 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 32
96 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 33
97 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 34
98 11.1. Normative References . . . . . . . . . . . . . . . . . . . 34
99 11.2. Informative References . . . . . . . . . . . . . . . . . . 34
100 Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 37
101 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 39
102 Intellectual Property and Copyright Statements . . . . . . . . . . 40
104 1. Introduction
106 [RFC3453] introduces large block FEC codes as an alternative to small
107 block FEC codes like Reed-Solomon. The main advantage of such large
108 block codes is the possibility to operate efficiently on source
109 blocks of size several tens of thousands (or more) source symbols.
110 The present document introduces the Fully-Specified FEC Encoding ID 3
111 that is intended to be used with the LDPC-Staircase FEC codes, and
112 the Fully-Specified FEC Encoding ID 4 that is intended to be used
113 with the LDPC-Triangle FEC codes [RN04][MK03]. Both schemes belong
114 to the broad class of large block codes. For a definition of the
115 term Fully-Specified Scheme, see [RFC5052], section 4.
117 LDPC codes rely on a dedicated matrix, called a "Parity Check
118 Matrix", at the encoding and decoding ends. The parity check matrix
119 defines relationships (or constraints) between the various encoding
120 symbols (i.e., source symbols and repair symbols), that are later
121 used by the decoder to reconstruct the original k source symbols if
122 some of them are missing. These codes are systematic, in the sense
123 that the encoding symbols include the source symbols in addition to
124 the repair symbols.
126 Since the encoder and decoder must operate on the same parity check
127 matrix, information must be communicated between them as part of the
128 FEC Object Transmission Information.
130 A publicly available reference implementation of these codes is
131 available and distributed under a GNU/LGPL license [LDPC-codec].
132 Besides, the code extracts included in this document are directly
133 contributed to the IETF process by the authors of this document and
134 by Radford M. Neal.
136 2. Requirements notation
138 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
139 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
140 document are to be interpreted as described in [RFC2119].
142 3. Definitions, Notations and Abbreviations
144 3.1. Definitions
146 This document uses the same terms and definitions as those specified
147 in [RFC5052]. Additionally, it uses the following definitions:
149 Source symbol: unit of data used during the encoding process
151 Encoding symbol: unit of data generated by the encoding process
153 Repair symbol: encoding symbol that is not a source symbol
155 Code rate: the k/n ratio, i.e., the ratio between the number of
156 source symbols and the number of encoding symbols. The code rate
157 belongs to a ]0; 1] interval. A code rate close to 1 indicates
158 that a small number of repair symbols have been produced during
159 the encoding process
161 Systematic code: FEC code in which the source symbols are part of
162 the encoding symbols
164 Source block: a block of k source symbols that are considered
165 together for the encoding
167 Encoding Symbol Group: a group of encoding symbols that are sent
168 together, within the same packet, and whose relationships to the
169 source object can be derived from a single Encoding Symbol ID
171 Source Packet: a data packet containing only source symbols
173 Repair Packet: a data packet containing only repair symbols
175 Packet Erasure Channel: a communication path where packets are
176 either dropped (e.g., by a congested router, or because the number
177 of transmission errors exceeds the correction capabilities of the
178 physical layer codes) or received. When a packet is received, it
179 is assumed that this packet is not corrupted
181 3.2. Notations
183 This document uses the following notations:
185 L denotes the object transfer length in bytes
187 k denotes the source block length in symbols, i.e., the number of
188 source symbols of a source block
189 n denotes the encoding block length, i.e., the number of encoding
190 symbols generated for a source block
192 E denotes the encoding symbol length in bytes
194 B denotes the maximum source block length in symbols, i.e., the
195 maximum number of source symbols per source block
197 N denotes the number of source blocks into which the object shall
198 be partitioned
200 G denotes the number of encoding symbols per group, i.e., the
201 number of symbols sent in the same packet
203 CR denotes the "code rate", i.e., the k/n ratio
205 max_n denotes the maximum number of encoding symbols generated for
206 any source block. This is in particular the number of encoding
207 symbols generated for a source block of size B
209 H denotes the parity check matrix
211 pmms_rand(m) denotes the pseudo-random number generator defined in
212 Section 5.7 that returns a new random integer in [0; m-1] each
213 time it is called
215 3.3. Abbreviations
217 This document uses the following abbreviations:
219 ESI: Encoding Symbol ID
221 FEC OTI: FEC Object Transmission Information
223 FPI: FEC Payload ID
225 LDPC: Low Density Parity Check
227 PRNG: Pseudo Random Number Generator
229 4. Formats and Codes
231 4.1. FEC Payload IDs
233 The FEC Payload ID is composed of the Source Block Number and the
234 Encoding Symbol ID:
236 The Source Block Number (12 bit field) identifies from which
237 source block of the object the encoding symbol(s) in the packet
238 payload is(are) generated. There are a maximum of 2^^12 blocks
239 per object. Source block numbering starts at 0.
241 The Encoding Symbol ID (20 bit field) identifies which encoding
242 symbol(s) generated from the source block is(are) carried in the
243 packet payload. There are a maximum of 2^^20 encoding symbols per
244 block. The first k values (0 to k-1) identify source symbols, the
245 remaining n-k values (k to n-k-1) identify repair symbols.
247 There MUST be exactly one FEC Payload ID per packet. In case of an
248 Encoding Symbol Group, when multiple encoding symbols are sent in the
249 same packet, the FEC Payload ID refers to the first symbol of the
250 packet. The other symbols can be deduced from the ESI of the first
251 symbol thanks to a dedicated function, as explained in Section 5.6
253 0 1 2 3
254 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
255 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
256 | Source Block Number | Encoding Symbol ID (20 bits) |
257 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
259 Figure 1: FEC Payload ID encoding format for FEC Encoding ID 3 and 4
261 4.2. FEC Object Transmission Information
263 4.2.1. Mandatory Element
265 o FEC Encoding ID: the LDPC-Staircase and LDPC-Triangle Fully-
266 Specified FEC Schemes use respectively the FEC Encoding ID 3
267 (Staircase) and 4 (Triangle).
269 4.2.2. Common Elements
271 The following elements MUST be defined with the present FEC Schemes:
273 o Transfer-Length (L): a non-negative integer indicating the length
274 of the object in bytes. There are some restrictions on the
275 maximum Transfer-Length that can be supported:
277 maximum transfer length = 2^^12 * B * E
279 For instance, if B=2^^19 (because of a code rate of 1/2,
280 Section 5.2), and if E=1024 bytes, then the maximum transfer
281 length is 2^^41 bytes (or 2 TB). The upper limit, with symbols of
282 size 2^^16-1 bytes and a code rate larger or equal to 1/2, amounts
283 to 2^^47 bytes (or 128 TB).
285 o Encoding-Symbol-Length (E): a non-negative integer indicating the
286 length of each encoding symbol in bytes.
288 o Maximum-Source-Block-Length (B): a non-negative integer indicating
289 the maximum number of source symbols in a source block. There are
290 some restrictions on the maximum B value, as explained in
291 Section 5.2.
293 o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer
294 indicating the maximum number of encoding symbols generated for
295 any source block. There are some restrictions on the maximum
296 max_n value. In particular max_n is at most equal to 2^^20.
298 Section 5 explains how to define the values of each of these
299 elements.
301 4.2.3. Scheme-Specific Elements
303 The following elements MUST be defined with the present FEC Scheme:
305 o G: a non-negative integer indicating the number of encoding
306 symbols per group (i.e., per packet). The default value is 1,
307 meaning that each packet contains exactly one symbol. Values
308 greater than 1 can also be defined, as explained in Section 5.3.
310 o PRNG seed: the seed is a 32 bit unsigned integer between 1 and
311 0x7FFFFFFE (i.e., 2^^31-2) inclusive. This value is used to
312 initialize the Pseudo Random Number Generator (Section 5.7).
314 4.2.4. Encoding Format
316 This section shows two possible encoding formats of the above FEC
317 OTI. The present document does not specify when or how these
318 encoding formats should be used.
320 4.2.4.1. Using the General EXT_FTI Format
322 The FEC OTI binary format is the following, when the EXT_FTI
323 mechanism is used (e.g., within the ALC
324 [draft-ietf-rmt-pi-alc-revised] or NORM
326 [draft-ietf-rmt-pi-norm-revised] protocols).
328 0 1 2 3
329 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
330 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
331 | HET = 64 | HEL = 5 | |
332 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
333 | Transfer-Length (L) |
334 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
335 | Encoding Symbol Length (E) | G | B (MSB) |
336 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
337 | B (LSB) | Max Nb of Enc. Symbols (max_n) |
338 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
339 | PRNG seed |
340 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
342 Figure 2: EXT_FTI Header for FEC Encoding ID 3 and 4.
344 In particular:
346 o The Transfer-Length (L) field size (48 bits) is larger than the
347 size required to store the maximum transfer length (Section 4.2.2)
348 for field alignment purposes.
350 o The Maximum-Source-Block-Length (B) field (20 bits) is split into
351 two parts: the 8 most significant bits (MSB) are in the third 32-
352 bit word of the EXT_FTI, and the remaining 12 least significant
353 bits (LSB) are in the fourth 32-bit word.
355 4.2.4.2. Using the FDT Instance (FLUTE specific)
357 When it is desired that the FEC OTI be carried in the FDT Instance of
358 a FLUTE session [draft-ietf-rmt-flute-revised], the following XML
359 attributes must be described for the associated object:
361 o FEC-OTI-FEC-Encoding-ID
363 o FEC-OTI-Transfer-length
365 o FEC-OTI-Encoding-Symbol-Length
367 o FEC-OTI-Maximum-Source-Block-Length
369 o FEC-OTI-Max-Number-of-Encoding-Symbols
371 o FEC-OTI-Scheme-Specific-Info
373 The FEC-OTI-Scheme-Specific-Info contains the string resulting from
374 the Base64 encoding (in the XML Schema xs:base64Binary sense)
375 [RFC4648] of the following value:
377 0 1 2 3
378 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
379 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
380 | PRNG seed |
381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
382 | G |
383 +-+-+-+-+-+-+-+-+
385 Figure 3: FEC OTI Scheme Specific Information to be Included in the
386 FDT Instance for FEC Encoding ID 3 and 4.
388 During Base64 encoding, the 5 bytes of the FEC OTI Scheme Specific
389 Information are transformed into a string of 8 printable characters
390 (in the 64-character alphabet) that is added to the FEC-OTI-Scheme-
391 Specific-Info attribute.
393 5. Procedures
395 This section defines procedures that are common to FEC Encoding IDs 3
396 and 4.
398 5.1. General
400 The B (maximum source block length in symbols), E (encoding symbol
401 length in bytes) and G (number of encoding symbols per group)
402 parameters are first determined. The algorithms of Section 5.2 and
403 Section 5.3 MAY be used to that purpose. Using other algorithms is
404 possible without compromising interoperability since the B, E and G
405 parameters are communicated to the receiver by means of the FEC OTI.
407 Then, the source object MUST be partitioned using the block
408 partitioning algorithm specified in [RFC5052]. To that purpose, the
409 B, L (object transfer length in bytes), and E arguments are provided.
410 As a result, the object is partitioned into N source blocks. These
411 blocks are numbered consecutively from 0 to N-1. The first I source
412 blocks consist of A_large source symbols, the remaining N-I source
413 blocks consist of A_small source symbols. Each source symbol is E
414 bytes in length, except perhaps the last symbol which may be shorter.
416 Then, the max_n (maximum number of encoding symbols generated for any
417 source block) parameter is determined. The algorithm of Section 5.4
418 MAY be used to that purpose. Using another algorithm is possible
419 without compromising interoperability since the max_n parameter is
420 communicated to the receiver by means of the FEC OTI.
422 For each block, the actual number of encoding symbols, n, MUST then
423 be determined using the "n-algorithm" detailed in Section 5.5.
425 Then, FEC encoding and decoding can be done block per block,
426 independently. To that purpose, a parity check matrix is created,
427 that forms a system of linear equations between the source and repair
428 symbols of a given block, where the basic operator is XOR.
430 This parity check matrix is logically divided into two parts: the
431 left side (from column 0 to k-1) describes the occurrences of each
432 source symbol in the system of linear equations; the right side (from
433 column k to n-1) describes the occurrences of each repair symbol in
434 the system of linear equations. The only difference between the
435 LDPC-Staircase and LDPC-Triangle schemes is the construction of this
436 right sub-matrix. An entry (a "1") in the matrix at position (i,j)
437 (i.e., at row i and column j) means that the symbol with ESI j
438 appears in equation i of the system.
440 When the parity symbols have been created, the sender transmits
441 source and parity symbols. The way this transmission occurs can
442 largely impact the erasure recovery capabilities of the LDPC-* FEC.
443 In particular, sending parity symbols in sequence is suboptimal.
444 Instead it is usually recommended the shuffle these symbols. The
445 interested reader will find more details in [NRFF05].
447 The following sections detail how the B, E, G, max_nand n parameters
448 are determined (respectively in Section 5.2, Section 5.3, Section 5.4
449 and Section 5.5), how encoding symbol groups are created
450 (Section 5.6), and finally Section 5.7 details the PRNG.
452 5.2. Determining the Maximum Source Block Length (B)
454 The B parameter (maximum source block length in symbols) depends on
455 several parameters: the code rate (CR), the Encoding Symbol ID field
456 length of the FEC Payload ID (20 bits), as well as possible internal
457 codec limitations.
459 The B parameter cannot be larger than the following values, derived
460 from the FEC Payload ID limitations, for a given code rate:
462 max1_B = 2^^(20 - ceil(Log2(1/CR)))
464 Some common max1_B values are:
466 o CR == 1 (no repair symbol): max1_B = 2^^20 = 1,048,576
468 o 1/2 <= CR < 1: max1_B = 2^^19 = 524,288 symbols
470 o 1/4 <= CR < 1/2: max1_B = 2^^18 = 262,144 symbols
472 o 1/8 <= CR < 1/4: max1_B = 2^^17 = 131,072 symbols
474 Additionally, a codec MAY impose other limitations on the maximum
475 block size. For instance, this is the case when the codec uses
476 internally 16 bit unsigned integers to store the Encoding Symbol ID,
477 since it does not enable to store all the possible values of a 20 bit
478 field. In that case, if for instance 1/2 <= CR < 1, then the maximum
479 source block length is 2^^15. Other limitations may also apply, for
480 instance because of a limited working memory size. This decision
481 MUST be clarified at implementation time, when the target use case is
482 known. This results in a max2_B limitation.
484 Then, B is given by:
486 B = min(max1_B, max2_B)
488 Note that this calculation is only required at the coder, since the B
489 parameter is communicated to the decoder through the FEC OTI.
491 5.3. Determining the Encoding Symbol Length (E) and Number of Encoding
492 Symbols per Group (G)
494 The E parameter usually depends on the maximum transmission unit on
495 the path (PMTU) from the source to each receiver. In order to
496 minimize the protocol header overhead (e.g., the LCT/UDP/IPv4 or IPv6
497 headers in case of ALC), E is chosen as large as possible. In that
498 case, E is chosen so that the size of a packet composed of a single
499 symbol (G=1) remains below but close to the PMTU.
501 However other considerations can exist. For instance, the E
502 parameter can be made a function of the object transfer length.
503 Indeed, LDPC codes are known to offer better protection for large
504 blocks. In case of small objects, it can be advantageous to reduce
505 the encoding symbol length (E) in order to artificially increase the
506 number of symbols, and therefore the block size.
508 In order to minimize the protocol header overhead, several symbols
509 can be grouped in the same Encoding Symbol Group (i.e., G > 1).
510 Depending on how many symbols are grouped (G) and on the packet loss
511 rate (G symbols are lost for each packet erasure), this strategy
512 might or might not be appropriate. A balance must therefore be
513 found.
515 The current specification does not mandate any value for either E or
516 G. The current specification only provides an example of possible
517 choices for E and G. Note that this choice is done by the sender, and
518 the E and G parameters are then communicated to the receiver thanks
519 to the FEC OTI. Note also that the decoding algorithm used
520 influences the choice of the E and G parameters. Indeed, increasing
521 the number of symbols will negatively impact the processing load when
522 decoding is based (in part or totally) on Gaussian elimination,
523 whereas the impacts will be rather low when decoding is based on the
524 trivial algorithm sketched in Section 6.4.
526 Example:
528 Let us assume that the trivial decoding algorithm sketched in
529 Section 6.4 is used. First define the target packet payload size,
530 pkt_sz (at most equal to the PMTU minus the size of the various
531 protocol headers). The pkt_sz must be chosen in such a way that the
532 symbol size is an integer. This can require that pkt_sz be a
533 multiple of 4, 8 or 16 (see the table below). Then calculate the
534 number of packets in the object: nb_pkts = ceil(L / pkt_sz).
535 Finally, thanks to nb_pkts, use the following table to find a
536 possible G value.
538 +------------------------+----+-------------+-------------------+
539 | Number of packets | G | Symbol size | k |
540 +------------------------+----+-------------+-------------------+
541 | 4000 <= nb_pkts | 1 | pkt_sz | 4000 <= k |
542 | | | | |
543 | 1000 <= nb_pkts < 4000 | 4 | pkt_sz / 4 | 4000 <= k < 16000 |
544 | | | | |
545 | 500 <= nb_pkts < 1000 | 8 | pkt_sz / 8 | 4000 <= k < 8000 |
546 | | | | |
547 | 1 <= nb_pkts < 500 | 16 | pkt_sz / 16 | 16 <= k < 8000 |
548 +------------------------+----+-------------+-------------------+
550 5.4. Determining the Maximum Number of Encoding Symbols Generated for
551 Any Source Block (max_n)
553 The following algorithm MAY be used by a sender to determine the
554 maximum number of encoding symbols generated for any source block
555 (max_n) as a function of B and the target code rate. Since the max_n
556 parameter is communicated to the decoder by means of the FEC OTI,
557 another method MAY be used to determine max_n.
559 Input:
561 B: Maximum source block length, for any source block. Section 5.2
562 MAY be used to determine its value.
564 CR: FEC code rate, which is provided by the user (e.g., when
565 starting a FLUTE sending application). It is expressed as a
566 floating point value. The CR value must be such that the
567 resulting number of encoding symbols per block is at most equal to
568 2^^20 (Section 4.1).
570 Output:
572 max_n: Maximum number of encoding symbols generated for any source
573 block.
575 Algorithm:
577 max_n = ceil(B / CR);
579 if (max_n > 2^^20) then return an error ("invalid code rate");
581 (NB: if B has been defined as explained in Section 5.2, this error
582 should never happen)
584 5.5. Determining the Number of Encoding Symbols of a Block (n)
586 The following algorithm, also called "n-algorithm", MUST be used by
587 the sender and the receiver to determine the number of encoding
588 symbols for a given block (n) as a function of B, k, and max_n.
590 Input:
592 B: Maximum source block length, for any source block. At a
593 sender, Section 5.2 MAY be used to determine its value. At a
594 receiver, this value MUST be extracted from the received FEC OTI.
596 k: Current source block length. At a sender or receiver, the
597 block partitioning algorithm MUST be used to determine its value.
599 max_n: Maximum number of encoding symbols generated for any source
600 block. At a sender, Section 5.4 MAY be used to determine its
601 value. At a receiver, this value MUST be extracted from the
602 received FEC OTI.
604 Output:
606 n: Number of encoding symbols generated for this source block.
608 Algorithm:
610 n = floor(k * max_n / B);
612 5.6. Identifying the G Symbols of an Encoding Symbol Group
614 When multiple encoding symbols are sent in the same packet, the FEC
615 Payload ID information of the packet MUST refer to the first encoding
616 symbol. It MUST then be possible to identify each symbol from this
617 single FEC Payload ID. To that purpose, the symbols of an Encoding
618 Symbol Group (i.e., packet):
620 o MUST all be either source symbols, or repair symbols. Therefore
621 only source packets and repair packets are permitted, not mixed
622 ones.
624 o are identified by a function, sender(resp.
625 receiver)_find_ESIs_of_group(), that takes as argument:
627 * for a sender, the index of the Encoding Symbol Group (i.e.,
628 packet) that the application wants to create,
630 * for a receiver, the ESI information contained in the FEC
631 Payload ID.
633 and returns a list of G Encoding Symbol IDs. In case of a source
634 packet, the G Encoding Symbol IDs are chosen consecutively, by
635 incrementing the ESI. In case of a repair packet, the G repair
636 symbols are chosen randomly, as explained below.
638 o are stored in sequence in the packet, without any padding. In
639 other words, the last byte of the i-th symbol is immediately
640 followed by the first byte of (i+1)-th symbol.
642 The system must first be initialized by creating a random permutation
643 of the n-k indexes. This initialization function MUST be called
644 immediately after creating the parity check matrix. More precisely,
645 since the PRNG seed is not re-initialized, no call to the PRNG
646 function must have happened between the time the parity check matrix
647 has been initialized and the time the following initialization
648 function is called. This is true both at a sender and at a receiver.
650 int *txseqToID;
651 int *IDtoTxseq;
653 /*
654 * Initialization function.
655 * Warning: use only when G > 1.
656 */
657 void
658 initialize_tables ()
659 {
660 int i;
661 int randInd;
662 int backup;
664 txseqToID = malloc((n-k) * sizeof(int));
665 IDtoTxseq = malloc((n-k) * sizeof(int));
666 if (txseqToID == NULL || IDtoTxseq == NULL)
667 handle the malloc failures as appropriate...
668 /* initialize the two tables that map ID
669 * (i.e., ESI-k) to/from TxSequence. */
670 for (i = 0; i < n - k; i++) {
671 IDtoTxseq[i] = i;
672 txseqToID[i] = i;
673 }
674 /* now randomize everything */
675 for (i = 0; i < n - k; i++) {
676 randInd = pmms_rand(n - k);
677 backup = IDtoTxseq[i];
678 IDtoTxseq[i] = IDtoTxseq[randInd];
679 IDtoTxseq[randInd] = backup;
680 txseqToID[IDtoTxseq[i]] = i;
681 txseqToID[IDtoTxseq[randInd]] = randInd;
682 }
683 return;
684 }
686 It is then possible, at the sender, to determine the sequence of G
687 Encoding Symbol IDs that will be part of the group.
689 /*
690 * Determine the sequence of ESIs for the packet under construction
691 * at a sender.
692 * Warning: use only when G > 1.
693 * PktIdx (IN): index of the packet, in
694 * {0..ceil(k/G)+ceil((n-k)/G)} range
695 * ESIs[] (OUT): list of ESIs for the packet
696 */
697 void
698 sender_find_ESIs_of_group (int PktIdx,
699 ESI_t ESIs[])
700 {
701 int i;
703 if (PktIdx < nbSourcePkts) {
704 /* this is a source packet */
705 ESIs[0] = PktIdx * G;
706 for (i = 1; i < G; i++) {
707 ESIs[i] = (ESIs[0] + i) % k;
708 }
709 } else {
710 /* this is a repair packet */
711 for (i = 0; i < G; i++) {
712 ESIs[i] =
713 k +
714 txseqToID[(i + (PktIdx - nbSourcePkts) * G)
715 % (n - k)];
716 }
717 }
718 return;
719 }
721 Similarly, upon receiving an Encoding Symbol Group (i.e., packet), a
722 receiver can determine the sequence of G Encoding Symbol IDs from the
723 first ESI, esi0, that is contained in the FEC Payload ID.
725 /*
726 * Determine the sequence of ESIs for the packet received.
727 * Warning: use only when G > 1.
728 * esi0 (IN): : ESI contained in the FEC Payload ID
729 * ESIs[] (OUT): list of ESIs for the packet
730 */
731 void
732 receiver_find_ESIs_of_group (ESI_t esi0,
733 ESI_t ESIs[])
734 {
735 int i;
737 if (esi0 < k) {
738 /* this is a source packet */
739 ESIs[0] = esi0;
740 for (i = 1; i < G; i++) {
741 ESIs[i] = (esi0 + i) % k;
742 }
743 } else {
744 /* this is a repair packet */
745 for (i = 0; i < G; i++) {
746 ESIs[i] =
747 k +
748 txseqToID[(i + IDtoTxseq[esi0 - k])
749 % (n - k)];
750 }
751 }
752 }
754 5.7. Pseudo Random Number Generator
756 The FEC Encoding IDs 3 and 4 rely on a pseudo-random number generator
757 (PRNG) that must be fully specified, in particular in order to enable
758 the receivers and the senders to build the same parity check matrix.
760 The Park-Miler "minimal standard" PRNG [PM88] MUST be used. It
761 defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij
762 (modulo M), with the following choices: A = 7^^5 = 16807 and M =
763 2^^31 - 1 = 2147483647. A validation criteria of such a PRNG is the
764 following: if seed = 1, then the 10,000th value returned MUST be
765 equal to 1043618065.
767 Several implementations of this PRNG are known and discussed in the
768 literature. An optimized implementation of this algorithm, using
769 only 32 bit mathematics and which does not require any division, can
770 be found in [rand31pmc]. It uses the Park and Miller algorithm
771 [PM88] with the optimization suggested by D. Carta in [CA90]. The
772 history behind this algorithm is detailed in [WI08]. Yet any other
773 implementation of the PRNG algorithm that matches the above
774 validation criteria, like the ones detailed in [PM88], is
775 appropriate.
777 This PRNG produces natively a 31 bit value between 1 and 0x7FFFFFFE
778 (2^^31-2) inclusive. Since it is desired to scale the pseudo random
779 number between 0 and maxv-1 inclusive, one must keep the most
780 significant bits of the value returned by the PRNG (the least
781 significant bits are known to be less random and modulo based
782 solutions should be avoided [PTVF92]). The following algorithm MUST
783 be used:
785 Input:
787 raw_value: random integer generated by the inner PRNG algorithm,
788 between 1 and 0x7FFFFFFE (2^^31-2) inclusive.
790 maxv: upper bound used during the scaling operation.
792 Output:
794 scaled_value: random integer between 0 and maxv-1 inclusive.
796 Algorithm:
798 scaled_value = (unsigned long) ((double)maxv * (double)raw_value /
799 (double)0x7FFFFFFF);
801 (NB: the above C type casting to unsigned long is equivalent to
802 using floor() with positive floating point values)
804 In this document, pmms_rand(maxv) denotes the PRNG function that
805 implements the Park-Miller "minimal standard" algorithm defined above
806 and that scales the raw value between 1 and maxv-1 inclusive, using
807 the above scaling algorithm. Additionally, a function should be
808 provided to enable the initialization of the PRNG with a seed (i.e.,
809 a 31 bit interger between 1 and 0x7FFFFFFE inclusive) before calling
810 pmms_rand(maxv) the first time.
812 6. Full Specification of the LDPC-Staircase Scheme
814 6.1. General
816 The LDPC-Staircase scheme is identified by the Fully-Specified FEC
817 Encoding ID 3.
819 The PRNG used by the LDPC-Staircase scheme must be initialized by a
820 seed. This PRNG seed is an instance-specific FEC OTI attribute
821 (Section 4.2.3).
823 6.2. Parity Check Matrix Creation
825 The LDPC-Staircase matrix can be divided into two parts: the left
826 side of the matrix defines in which equations the source symbols are
827 involved; the right side of the matrix defines in which equations the
828 repair symbols are involved.
830 The left side MUST be generated by using the following function:
832 /*
833 * Initialize the left side of the parity check matrix.
834 * This function assumes that an empty matrix of size n-k * k has
835 * previously been allocated/reset and that the matrix_has_entry(),
836 * matrix_insert_entry() and degree_of_row() functions can access it.
837 * (IN): the k and n parameters.
838 */
839 void left_matrix_init (int k, int n)
840 {
841 int i; /* row index or temporary variable */
842 int j; /* column index */
843 int h;
844 int t; /* left limit within the list of possible choices u[] */
845 int u[3*MAX_K]; /* table used to have a homogeneous 1 distrib. */
847 /* Initialize a list of all possible choices in order to
848 * guarantee a homogeneous "1" distribution */
849 for (h = 3*k-1; h >= 0; h--) {
850 u[h] = h % (n-k);
851 }
853 /* Initialize the matrix with 3 "1s" per column, homogeneously */
854 t = 0;
855 for (j = 0; j < k; j++) { /* for each source symbol column */
856 for (h = 0; h < 3; h++) { /* add 3 "1s" */
857 /* check that valid available choices remain */
858 for (i = t; i < 3*k && matrix_has_entry(u[i], j); i++);
859 if (i < 3*k) {
860 /* choose one index within the list of possible
861 * choices */
862 do {
863 i = t + pmms_rand(3*k-t);
864 } while (matrix_has_entry(u[i], j));
865 matrix_insert_entry(u[i], j);
867 /* replace with u[t] which has never been chosen */
868 u[i] = u[t];
869 t++;
870 } else {
871 /* no choice left, choose one randomly */
872 do {
873 i = pmms_rand(n-k);
874 } while (matrix_has_entry(i, j));
875 matrix_insert_entry(i, j);
876 }
877 }
878 }
880 /* Add extra bits to avoid rows with less than two "1s".
881 * This is needed when the code rate is smaller than 2/5. */
882 for (i = 0; i < n-k; i++) { /* for each row */
883 if (degree_of_row(i) == 0) {
884 j = pmms_rand(k);
885 matrix_insert_entry(i, j);
886 }
887 if (degree_of_row(i) == 1) {
888 do {
889 j = pmms_rand(k);
890 } while (matrix_has_entry(i, j));
891 matrix_insert_entry(i, j);
892 }
893 }
894 }
896 The right side (the staircase) MUST be generated by using the
897 following function:
899 /*
900 * Initialize the right side of the parity check matrix with a
901 * staircase structure.
902 * (IN): the k and n parameters.
903 */
904 void right_matrix_staircase_init (int k, int n)
905 {
906 int i; /* row index */
908 matrix_insert_entry(0, k); /* first row */
909 for (i = 1; i < n-k; i++) { /* for the following rows */
910 matrix_insert_entry(i, k+i); /* identity */
911 matrix_insert_entry(i, k+i-1); /* staircase */
912 }
913 }
915 Note that just after creating this parity check matrix, when encoding
916 symbol groups are used (i.e., G > 1), the function initializing the
917 two random permutation tables (Section 5.6) MUST be called. This is
918 true both at a sender and at a receiver.
920 6.3. Encoding
922 Thanks to the staircase matrix, repair symbol creation is
923 straightforward: each repair symbol is equal to the sum of all source
924 symbols in the associated equation, plus the previous repair symbol
925 (except for the first repair symbol). Therefore encoding MUST follow
926 the natural repair symbol order: start with the first repair symbol,
927 and generate repair symbol with ESI i before symbol with ESI i+1.
929 6.4. Decoding
931 Decoding basically consists in solving a system of n-k linear
932 equations whose variables are the n source and repair symbols. Of
933 course, the final goal is to recover the value of the k source
934 symbols only.
936 To that purpose, many techniques are possible. One of them is the
937 following trivial algorithm [ZP74]: given a set of linear equations,
938 if one of them has only one remaining unknown variable, then the
939 value of this variable is that of the constant term. So, replace
940 this variable by its value in all the remaining linear equations and
941 reiterate. The value of several variables can therefore be found
942 recursively. Applied to LDPC FEC codes working over an erasure
943 channel, the parity check matrix defines a set of linear equations
944 whose variables are the source symbols and repair symbols. Receiving
945 or decoding a symbol is equivalent to having the value of a variable.
946 Appendix A sketches a possible implementation of this algorithm.
948 A Gaussian elimination (or any optimized derivative) is another
949 possible decoding technique. Hybrid solutions that start by using
950 the trivial algorithm above and finish with a Gaussian elimination
951 are also possible.
953 Because interoperability does not depend on the decoding algorithm
954 used, the current document does not recommend any particular
955 technique. This choice is left to the codec developer.
957 However choosing a decoding technique will have great practical
958 impacts. It will impact the erasure capabilities: a Gaussian
959 elimination enables to solve the system with a smaller number of
960 known symbols compared to the trivial technique. It will also impact
961 the CPU load: a Gaussian elimination requires more processing than
962 the above trivial algorithm. Depending on the target use case, the
963 codec developer will favor one feature or the other.
965 7. Full Specification of the LDPC-Triangle Scheme
967 7.1. General
969 LDPC-Triangle is identified by the Fully-Specified FEC Encoding ID 4.
971 The PRNG used by the LDPC-Triangle scheme must be initialized by a
972 seed. This PRNG seed is an instance-specific FEC OTI attribute
973 (Section 4.2.3).
975 7.2. Parity Check Matrix Creation
977 The LDPC-Triangle matrix can be divided into two parts: the left side
978 of the matrix defines in which equations the source symbols are
979 involved; the right side of the matrix defines in which equations the
980 repair symbols are involved.
982 The left side MUST be generated by using the same left_matrix_init()
983 function as with LDPC-Staircase (Section 6.2).
985 The right side (the triangle) MUST be generated by using the
986 following function:
988 /*
989 * Initialize the right side of the parity check matrix with a
990 * triangle structure.
991 * (IN): the k and n parameters.
992 */
993 void right_matrix_staircase_init (int k, int n)
994 {
995 int i; /* row index */
996 int j; /* randomly chosen column indexes in 0..n-k-2 */
997 int l; /* limitation of the # of "1s" added per row */
999 matrix_insert_entry(0, k); /* first row */
1000 for (i = 1; i < n-k; i++) { /* for the following rows */
1001 matrix_insert_entry(i, k+i); /* identity */
1002 matrix_insert_entry(i, k+i-1); /* staircase */
1003 /* now fill the triangle */
1004 j = i-1;
1005 for (l = 0; l < j; l++) { /* limit the # of "1s" added */
1006 j = pmms_rand(j);
1007 matrix_insert_entry(i, k+j);
1008 }
1009 }
1010 }
1012 Note that just after creating this parity check matrix, when encoding
1013 symbol groups are used (i.e., G > 1), the function initializing the
1014 two random permutation tables (Section 5.6) MUST be called. This is
1015 true both at a sender and at a receiver.
1017 7.3. Encoding
1019 Here also repair symbol creation is straightforward: each repair
1020 symbol of ESI i is equal to the sum of all source and repair symbols
1021 (with ESI lower than i) in the associated equation. Therefore
1022 encoding MUST follow the natural repair symbol order: start with the
1023 first repair symbol, and generate repair symbol with ESI i before
1024 symbol with ESI i+1.
1026 7.4. Decoding
1028 Decoding basically consists in solving a system of n-k linear
1029 equations, whose variables are the n source and repair symbols. Of
1030 course, the final goal is to recover the value of the k source
1031 symbols only. To that purpose, many techniques are possible, as
1032 explained in Section 6.4.
1034 Because interoperability does not depend on the decoding algorithm
1035 used, the current document does not recommend any particular
1036 technique. This choice is left to the codec implementer.
1038 8. Security Considerations
1040 8.1. Problem Statement
1042 A content delivery system is potentially subject to many attacks:
1043 some of them target the network (e.g., to compromise the routing
1044 infrastructure, by compromising the congestion control component),
1045 others target the Content Delivery Protocol (CDP) (e.g., to
1046 compromise its normal behavior), and finally some attacks target the
1047 content itself. Since this document focuses on a FEC building block
1048 independently of any particular CDP (even if ALC and NORM are two
1049 natural candidates), this section only discusses the additional
1050 threats that an arbitrary CDP may be exposed to when using this
1051 building block.
1053 More specifically, several kinds of attacks exist:
1055 o those that are meant to give access to a confidential content
1056 (e.g., in case of a non-free content),
1058 o those that try to corrupt the object being transmitted (e.g., to
1059 inject malicious code within an object, or to prevent a receiver
1060 from using an object),
1062 o and those that try to compromise the receiver's behavior (e.g., by
1063 making the decoding of an object computationally expensive).
1065 These attacks can be launched either against the data flow itself
1066 (e.g., by sending forged symbols) or against the FEC parameters that
1067 are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out-
1068 of-band (e.g., in a session description).
1070 8.2. Attacks Against the Data Flow
1072 First of all, let us consider the attacks against the data flow.
1074 8.2.1. Access to Confidential Objects
1076 Access control to a confidential object being transmitted is
1077 typically provided by means of encryption. This encryption can be
1078 done over the whole object (e.g., by the content provider, before the
1079 FEC encoding process), or be done on a packet per packet basis (e.g.,
1080 when IPsec/ESP is used [RFC4303]). If confidentiality is a concern,
1081 it is RECOMMENDED that one of these solutions be used. Even if we
1082 mention these attacks here, they are not related nor facilitated by
1083 the use of FEC.
1085 8.2.2. Content Corruption
1087 Protection against corruptions (e.g., after sending forged packets)
1088 is achieved by means of a content integrity verification/sender
1089 authentication scheme. This service can be provided at the object
1090 level, but in that case a receiver has no way to identify which
1091 symbol(s) is(are) corrupted if the object is detected as corrupted.
1092 This service can also be provided at the packet level. In this case,
1093 after removing all forged packets, the object may be in some case
1094 recovered. Several techniques can provide this source
1095 authentication/content integrity service:
1097 o at the object level, the object MAY be digitally signed (with
1098 public key cryptography), for instance by using RSASSA-PKCS1-v1_5
1099 [RFC3447]. This signature enables a receiver to check the object
1100 integrity, once this latter has been fully decoded. Even if
1101 digital signatures are computationally expensive, this calculation
1102 occurs only once per object, which is usually acceptable;
1104 o at the packet level, each packet can be digitally signed. A major
1105 limitation is the high computational and transmission overheads
1106 that this solution requires (unless perhaps if Elliptic Curve
1107 Cryptography (ECC) is used). To avoid this problem, the signature
1108 may span a set of symbols (instead of a single one) in order to
1109 amortize the signature calculation. But if a single symbol is
1110 missing, the integrity of the whole set cannot be checked;
1112 o at the packet level, a Group Message Authentication Code (MAC)
1113 [RFC2104] scheme can be used, for instance by using HMAC-SHA-1
1114 with a secret key shared by all the group members, senders and
1115 receivers. This technique creates a cryptographically secured
1116 (thanks to the secret key) digest of a packet that is sent along
1117 with the packet. The Group MAC scheme does not create prohibitive
1118 processing load nor transmission overhead, but it has a major
1119 limitation: it only provides a group authentication/integrity
1120 service since all group members share the same secret group key,
1121 which means that each member can send a forged packet. It is
1122 therefore restricted to situations where group members are fully
1123 trusted (or in association with another technique as a pre-check);
1125 o at the packet level, TESLA [RFC4082] is an attractive solution
1126 that is robust to losses, provides a true authentication/integrity
1127 service, and does not create any prohibitive processing load or
1128 transmission overhead. Yet checking a packet requires a small
1129 delay (a second or more) after its reception;
1131 Techniques relying on public key cryptography (digital signatures and
1132 TESLA during the bootstrap process, when used) require that public
1133 keys be securely associated to the entities. This can be achieved by
1134 a Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by
1135 pre-distributing the public keys of each group member.
1137 Techniques relying on symmetric key cryptography (group MAC) require
1138 that a secret key be shared by all group members. This can be
1139 achieved by means of a group key management protocol, or simply by
1140 pre-distributing the secret key (but this manual solution has many
1141 limitations).
1143 It is up to the CDP developer, who knows the security requirements
1144 and features of the target application area, to define which solution
1145 is the most appropriate. Nonetheless, in case there is any concern
1146 of the threat of object corruption, it is RECOMMENDED that at least
1147 one of these techniques be used.
1149 8.3. Attacks Against the FEC Parameters
1151 Let us now consider attacks against the FEC parameters (or FEC OTI).
1152 The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an
1153 FDT Instance containing FEC OTI for the object) or out-of-band (e.g.,
1154 in a session description). Attacks on these FEC parameters can
1155 prevent the decoding of the associated object: for instance modifying
1156 the B parameter will lead to a different block partitioning.
1158 It is therefore RECOMMENDED that security measures be taken to
1159 guarantee the FEC OTI integrity. To that purpose, the packets
1160 carrying the FEC parameters sent in-band in an EXT_FTI header
1161 extension SHOULD be protected by one of the per-packet techniques
1162 described above: digital signature, group MAC, or TESLA. When FEC
1163 OTI is contained in an FDT Instance, this object SHOULD be protected,
1164 for instance by digitally signing it with XML digital signatures
1165 [RFC3275]. Finally, when FEC OTI is sent out-of-band (e.g., in a
1166 session description) this latter SHOULD be protected, for instance by
1167 digitally signing it with [RFC3852].
1169 The same considerations concerning the key management aspects apply
1170 here also.
1172 9. IANA Considerations
1174 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA
1175 registration. For general guidelines on IANA considerations as they
1176 apply to this document, see [RFC5052].
1178 This document assigns the Fully-Specified FEC Encoding ID 3 under the
1179 "ietf:rmt:fec:encoding" name-space to "LDPC Staircase Codes".
1181 This document assigns the Fully-Specified FEC Encoding ID 4 under the
1182 "ietf:rmt:fec:encoding" name-space to "LDPC Triangle Codes".
1184 10. Acknowledgments
1186 Section 5.5 is derived from a previous Internet-Draft, and we would
1187 like to thank S. Peltotalo and J. Peltotalo for their contribution.
1188 We would also like to thank Pascal Moniot, Laurent Fazio, Aurelien
1189 Francillon, Shao Wenjian, Magnus Westerlund, Brian Carpenter, Tim
1190 Polk, Jari Arkko, Chris Newman, Robin Whittle and Alfred Hoenes for
1191 their comments.
1193 Last but not least, the authors are grateful to Radford M. Neal
1194 (University of Toronto) whose LDPC software
1195 (http://www.cs.toronto.edu/~radford/ldpc.software.html) inspired this
1196 work.
1198 11. References
1200 11.1. Normative References
1202 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
1203 Requirement Levels", RFC 2119, BCP 14, March 1997.
1205 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error
1206 Correction (FEC) Building Block", RFC 5052, August 2007.
1208 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley,
1209 M., and J. Crowcroft, "The Use of Forward Error Correction
1210 (FEC) in Reliable Multicast", RFC 3453, December 2002.
1212 11.2. Informative References
1214 [ZP74] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-
1215 Density Codes for Transmission in a Channel with
1216 Erasures", Translated from Problemy Peredachi
1217 Informatsii, Vol.10, No. 1, pp.15-28, January-March 1974.
1219 [RN04] Roca, V. and C. Neumann, "Design, Evaluation and
1220 Comparison of Four Large Block FEC Codecs: LDPC, LDGM,
1221 LDGM-Staircase and LDGM-Triangle, Plus a Reed-Solomon
1222 Small Block FEC Codec", INRIA Research Report RR-5225,
1223 June 2004.
1225 [NRFF05] Neumann, C., Roca, V., Francillon, A., and D. Furodet,
1226 "Impacts of Packet Scheduling and Packet Loss Distribution
1227 on FEC Performances: Observations and Recommendations",
1228 ACM CoNEXT'05 Conference, Toulouse, France (an extended
1229 version is available as INRIA Research Report RR-5578),
1230 October 2005.
1232 [LDPC-codec]
1233 Roca, V., Neumann, C., Cunche, M., and J. Laboure, "LDPC-
1234 Staircase/LDPC-Triangle Codec Reference Implementation",
1235 INRIA Rhone-Alpes and STMicroelectronics,
1236 http://planete-bcast.inrialpes.fr/.
1238 [MK03] MacKay, D., "Information Theory, Inference and Learning
1239 Algorithms", Cambridge University Press, ISBN: 0-521-
1240 64298-1, 2003.
1242 [PM88] Park, S. and K. Miller, "Random Number Generators: Good
1243 Ones are Hard to Find", Communications of the ACM, Vol.
1244 31, No. 10, pp.1192-1201, 1988.
1246 [CA90] Carta, D., "Two Fast Implementations of the Minimal
1247 Standard Random Number Generator", Communications of the
1248 ACM, Vol. 33, No. 1, pp.87-88, January 1990.
1250 [WI08] Whittle, R., "Park-Miller-Carta Pseudo-Random Number
1251 Generator", http://www.firstpr.com.au/dsp/rand31/,
1252 January 2008.
1254 [rand31pmc]
1255 Whittle, R., "31 bit pseudo-random number generator", htt
1256 p://www.firstpr.com.au/dsp/rand31/
1257 rand31-park-miller-carta.cc.txt, September 2005.
1259 [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery,
1260 "Numerical Recipies in C; Second Edition", Cambridge
1261 University Press, ISBN: 0-521-43108-5, 1992.
1263 [draft-ietf-rmt-pi-alc-revised]
1264 Luby, M., Watson, M., and L. Vicisano, "Asynchronous
1265 Layered Coding (ALC) Protocol Instantiation",
1266 draft-ietf-rmt-pi-alc-revised-04.txt (work in progress),
1267 February 2007.
1269 [draft-ietf-rmt-pi-norm-revised]
1270 Adamson, B., Bormann, C., Handley, M., and J. Macker,
1271 "Negative-acknowledgment (NACK)-Oriented Reliable
1272 Multicast (NORM) Protocol",
1273 draft-ietf-rmt-pi-norm-revised-05.txt (work in progress),
1274 March 2007.
1276 [draft-ietf-rmt-flute-revised]
1277 Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca,
1278 "FLUTE - File Delivery over Unidirectional Transport",
1279 draft-ietf-rmt-flute-revised-05.txt (work in progress),
1280 October 2007.
1282 [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography
1283 Standards (PKCS) #1: RSA Cryptography Specifications
1284 Version 2.1", RFC 3447, February 2003.
1286 [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)",
1287 RFC 4303, December 2005.
1289 [RFC2104] "HMAC: Keyed-Hashing for Message Authentication",
1290 RFC 2104, February 1997.
1292 [RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication
1293 (TESLA): Multicast Source Authentication Transform
1294 Introduction", RFC 4082, June 2005.
1296 [RFC3275] Eastlake, D., Reagle, J., and D. Solo, "(Extensible Markup
1297 Language) XML-Signature Syntax and Processing", RFC 3275,
1298 March 2002.
1300 [RFC3852] Housley, R., "Cryptographic Message Syntax (CMS)",
1301 RFC 3852, July 2004.
1303 [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data
1304 Encodings", RFC 4648, October 2006.
1306 Appendix A. Trivial Decoding Algorithm (Informative Only)
1308 A trivial decoding algorithm is sketched below (please see
1309 [LDPC-codec] for the details omitted here):
1311 Initialization: allocate a table partial_sum[n-k] of buffers, each
1312 buffer being of size the symbol size. There's one
1313 entry per equation since the buffers are meant to
1314 store the partial sum of each equation; Reset all
1315 the buffers to zero;
1317 /*
1318 * For each newly received or decoded symbol, try to make progress
1319 * in the decoding of the associated source block.
1320 * NB: in case of a symbol group (G>1), this function is called for
1321 * each symbol of the received packet.
1322 * NB: a callback function indicates to the caller that new symbol(s)
1323 * has(have) been decoded.
1324 * new_esi (IN): ESI of the new symbol received or decoded
1325 * new_symb (IN): Buffer of the new symbol received or decoded
1326 */
1327 void
1328 decoding_step(ESI_t new_esi,
1329 symbol_t *new_symb)
1330 {
1331 If (new_symb is an already decoded or received symbol) {
1332 Return; /* don't waste time with this symbol */
1333 }
1335 If (new_symb is the last missing source symbol) {
1336 Remember that decoding is finished;
1337 Return; /* work is over now... */
1338 }
1340 Create an empty list of equations having symbols decoded
1341 during this decoding step;
1343 /*
1344 * First add this new symbol to the partial sum of all the
1345 * equations where the symbol appears.
1346 */
1347 For (each equation eq in which new_symb is a variable and
1348 having more than one unknown variable) {
1350 Add new_symb to partial_sum[eq];
1352 Remove entry(eq, new_esi) from the H matrix;
1353 If (the new degree of equation eq == 1) {
1354 /* a new symbol can be decoded, remember the
1355 * equation */
1356 Append eq to the list of equations having symbols
1357 decoded during this decoding step;
1358 }
1359 }
1361 /*
1362 * Then finish with recursive calls to decoding_step() for each
1363 * newly decoded symbol.
1364 */
1365 For (each equation eq in the list of equations having symbols
1366 decoded during this decoding step) {
1368 /*
1369 * Because of the recursion below, we need to check that
1370 * decoding is not finished, and that the equation is
1371 * __still__ of degree 1
1372 */
1373 If (decoding is finished) {
1374 break; /* exit from the loop */
1375 }
1377 If ((degree of equation eq == 1) {
1378 Let dec_esi be the ESI of the newly decoded symbol in
1379 equation eq;
1381 Remove entry(eq, dec_esi);
1383 Allocate a buffer, dec_symb, for this symbol and
1384 copy partial_sum[eq] to dec_symb;
1386 Inform the caller that a new symbol has been
1387 decoded via a callback function;
1389 /* finally, call this function recursively */
1390 decoding_step(dec_esi, dec_symb);
1391 }
1392 }
1394 Free the list of equations having symbols decoded;
1395 Return;
1396 }
1398 Authors' Addresses
1400 Vincent Roca
1401 INRIA
1402 655, av. de l'Europe
1403 Inovallee; Montbonnot
1404 ST ISMIER cedex 38334
1405 France
1407 Email: vincent.roca@inria.fr
1408 URI: http://planete.inrialpes.fr/people/roca/
1410 Christoph Neumann
1411 Thomson
1412 12, bd de Metz
1413 Rennes 35700
1414 France
1416 Email: christoph.neumann@thomson.net
1417 URI: http://planete.inrialpes.fr/people/chneuman/
1419 David Furodet
1420 STMicroelectronics
1421 12, Rue Jules Horowitz
1422 BP217
1423 Grenoble Cedex 38019
1424 France
1426 Email: david.furodet@st.com
1427 URI: http://www.st.com/
1429 Full Copyright Statement
1431 Copyright (C) The IETF Trust (2008).
1433 This document is subject to the rights, licenses and restrictions
1434 contained in BCP 78, and except as set forth therein, the authors
1435 retain all their rights.
1437 This document and the information contained herein are provided on an
1438 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
1439 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
1440 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
1441 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
1442 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
1443 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
1445 Intellectual Property
1447 The IETF takes no position regarding the validity or scope of any
1448 Intellectual Property Rights or other rights that might be claimed to
1449 pertain to the implementation or use of the technology described in
1450 this document or the extent to which any license under such rights
1451 might or might not be available; nor does it represent that it has
1452 made any independent effort to identify any such rights. Information
1453 on the procedures with respect to rights in RFC documents can be
1454 found in BCP 78 and BCP 79.
1456 Copies of IPR disclosures made to the IETF Secretariat and any
1457 assurances of licenses to be made available, or the result of an
1458 attempt made to obtain a general license or permission for the use of
1459 such proprietary rights by implementers or users of this
1460 specification can be obtained from the IETF on-line IPR repository at
1461 http://www.ietf.org/ipr.
1463 The IETF invites any interested party to bring to its attention any
1464 copyrights, patents or patent applications, or other proprietary
1465 rights that may cover technology that may be required to implement
1466 this standard. Please address the information to the IETF at
1467 ietf-ipr@ietf.org.
1469 Acknowledgment
1471 Funding for the RFC Editor function is provided by the IETF
1472 Administrative Support Activity (IASA).
```