RFC 3453

The Use of Forward Error Correction (FEC) in Reliable Multicast

📅 published December 2002, from ietf

RFC 3453: The Use of Forward Error Correction (FEC) in Reliable Multicast 🎀

Okay bestie, this one is an Informational RFC from December 2002 💅, which means it's a memo for the Internet community and not a standard anyone has to follow. It came out of the Network Working Group and is written by six people: M. Luby (Digital Fountain), L. Vicisano (Cisco), J. Gemmell (Microsoft), L. Rizzo (Univ. Pisa), M. Handley (ICIR), and J. Crowcroft (Cambridge Univ.). It doesn't list anything it obsoletes or updates. 🦋

Status of this Memo

This memo gives info to the Internet community 🧚. It doesn't specify an Internet standard of any kind, and distribution of it is unlimited ✨.

Copyright (C) The Internet Society (2002). All Rights Reserved. 🌸

Abstract

This memo is all about using Forward Error Correction (FEC) codes to efficiently provide and/or augment reliability for one-to-many reliable data transport over IP multicast 📡. The main vibe 😭: the same packets carrying FEC data can simultaneously repair different packet loss patterns at multiple receivers, which is so iconic. It also covers the different classes of FEC codes and some of their basic properties, introduces terminology for implementing FEC in a reliable multicast protocol, and gives examples of possible abstract formats for packets that carry FEC. 🔥

Table of Contents

1. Rationale and Overview . . . . . . . . . . . . . . . . . . . .   2
  1.1. Application of FEC codes . . . . . . . . . . . . . . . . .   5
2. FEC Codes. . . . . . . . . . . . . . . . . . . . . . . . . . .   6
  2.1. Simple codes . . . . . . . . . . . . . . . . . . . . . . .   6
  2.2. Small block FEC codes. . . . . . . . . . . . . . . . . . .   8
  2.3. Large block FEC codes. . . . . . . . . . . . . . . . . . .  10
  2.4. Expandable FEC codes . . . . . . . . . . . . . . . . . . .  11
  2.5. Source blocks with variable length source symbols. . . . .  13
3. Security Considerations. . . . . . . . . . . . . . . . . . . . .  14
4. Intellectual Property Disclosure . . . . . . . . . . . . . . .  14
5. Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . .  15
6. References . . . . . . . . . . . . . . . . . . . . . . . . . .  15
7. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . .  17
8. Full Copyright Statement . . . . . . . . . . . . . . . . . . .  18

1. Rationale and Overview ✨

Okay so there are a bunch of ways to make transmission protocols reliable 🧚. A super common one is ARQ (automatic request for retransmission) 🔁. With ARQ, receivers use a back channel to the sender to request retransmission of lost packets. ARQ absolutely works for one-to-one reliable protocols, and TCP/IP is living proof of that 👑. It's also been an effective reliability tool for one-to-many protocols, and especially for some reliable IP multicast protocols.

BUT, for one-to-very-many reliability protocols, ARQ has limits 💀. One is the feedback implosion problem, because tons of receivers are all transmitting back to the sender at once. Another is that receivers need a back channel just to send those requests. Also, receivers can see different loss patterns, so a receiver might get held up by retransmissions of packets that other receivers lost, even though it already has them 😭. That can also waste bandwidth, since packets many receivers already got get resent anyway.

In places where ARQ is costly or impossible, like a very limited back channel or no back channel at all (satellite transmission is the classic example 🛰️), people sometimes use a Data Carousel approach [1]. With a Data Carousel, the sender splits the object into equal length pieces of data, which we call source symbols from here on 🍓. It puts those into packets and then keeps cycling through and sending them. Receivers keep receiving packets until they've got a copy of each one.

The big perk of a Data Carousel is that it needs no back channel, because no data flows from receivers to the sender 🙌. But it has downsides too. If a receiver loses a packet in one round, it has to wait an entire round before it gets another chance at that packet. This can also waste bandwidth, since the sender keeps cycling and transmitting packets until no receiver is missing one.

Forward Error Correction (FEC) codes are a reliability method that can augment or replace other reliability methods, especially for one-to-many protocols like reliable IP multicast 🌈. We'll briefly go over some basic properties and types of FEC codes first, then look at how they're used in reliable IP multicast, and later we'll get into more detail on some of the codes.

In the general literature, FEC is about overcoming both erasures (losses) and bit-level corruption. In an IP multicast protocol, though, the network layers detect corrupted packets and discard them, or the transport layers can use packet authentication to discard them. So the main application of FEC codes to IP multicast protocols is as an erasure code 🧼. The payloads are generated and processed using an FEC erasure encoder, and objects are reassembled from received packets containing the generated encoding using the matching FEC erasure decoder.

The input to an FEC encoder is some number k of equal length source symbols. The encoder generates some number of encoding symbols that are the same length as the source symbols. The symbol length can change with each application of the encoder, or it can be fixed. These encoding symbols get placed into packets for transmission. The number of encoding symbols in each packet can vary from packet to packet, or a fixed number (often one) can go into each packet. Each packet also carries enough info to identify the particular encoding symbols it holds 🔍. When a receiver gets packets with encoding symbols, it feeds them into the matching FEC decoder to recreate an exact copy of the k source symbols. Ideally, the decoder can recreate that exact copy from any k of the encoding symbols 💖.

Later on, we'll describe a technique for using FEC codes like this to handle blocks with variable length source symbols 🎀.

Block FEC codes work like this. The input to a block FEC encoder is k source symbols and a number n. The encoder generates a total of n encoding symbols. The encoder is systematic if it generates n-k redundant symbols, which gives an encoding block of n encoding symbols in total, made up of the k source symbols and the n-k redundant symbols 🧩.

A block FEC decoder has the property that any k of the n encoding symbols in the encoding block is enough to reconstruct the original k source symbols 🪄.

Expandable FEC codes work like this. An expandable FEC encoder takes k source symbols as input and generates as many unique encoding symbols as requested, on demand. The time to generate each encoding symbol is the same no matter how many encoding symbols get generated ⏱️. An expandable FEC decoder has the property that any k of the unique encoding symbols is enough to reconstruct the original k source symbols.

The definitions above describe the ideal situation, where receiving any k encoding symbols is enough to recover the k source symbols. In that case the reception overhead is 0%. Some practical FEC codes need slightly more than k encoding symbols to recover the k source symbols. If k*(1+ep) encoding symbols are needed, we say the reception overhead is ep*100%. For example, if k*1.05 encoding symbols are needed, then the reception overhead is 5% 📈.

On a different axis, we loosely classify FEC codes as either small or large 🐣🐘. A small FEC code is efficient in terms of processing time for encoding and decoding when k is small, and a large FEC code is efficient for encoding and decoding when k is much larger. Some implementations of block FEC codes have encoding times proportional to n-k times the length of the k source symbols, and decoding times proportional to l times the length of the k source symbols. Here l is the number of missing source symbols among the k received encoding symbols, and l can be as large as k. Because encoding and decoding times grow as a product of k and n-k, these are typically considered small block FEC codes 🫠.

There are block FEC codes with a small reception overhead that can generate n encoding symbols and decode the k source symbols in time proportional to the length of the n encoding symbols. These are considered large block FEC codes 💜. There are also expandable FEC codes with a small reception overhead that can generate each encoding symbol in time roughly proportional to its length, and can decode all k source symbols in time roughly proportional to their length. These are considered large expandable FEC codes ✨. We'll describe examples of all of these types of codes later on 🦋.

Ideally, FEC codes in the context of IP multicast can generate encoding symbols that get transmitted in packets in such a way that each received packet is fully useful to a receiver for reassembling the object, no matter what previous packet reception patterns looked like 🌸. So if some packets are lost in transit between sender and receiver, the receiver doesn't have to ask for specific retransmission of the lost packets, and doesn't have to wait until they're resent by a Data Carousel. Instead, it can use any other equal number of packets that arrive afterward to reassemble the object 🙌. These packets can be proactively transmitted, or receivers can explicitly request them.

This means the same packet is fully useful to all receivers for reassembling the object, even though the receivers may have experienced different packet loss patterns earlier 👑. This property can reduce or even eliminate the problems we mentioned above with ARQ and Data Carousel, and it can dramatically increase the scalability of the protocol to orders of magnitude more receivers 🚀💅

1.1. Application of FEC codes

Okay so FEC codes are lowkey the MVP of reliable IP multicast 💖 Some protocols pair them with ARQ, which is like the "resend if it got lost" move, and together they keep everything reliable 🦋 Picture a big object chopped into source blocks, each with a few source symbols. In round one, the sender blasts every source symbol for every block 🚀 Then receivers tell the sender how many symbols they're missing from each block. The sender finds the maximum number of missing symbols per block across all receivers, and uses a small block FEC encoder to make that many redundant symbols for each block 🧮 The catch: this only works as long as that maximum maximum for each block doesn't go over the number of redundant symbols that can be generated efficiently ⚠️ Round two is when the server sends all those redundant symbols for all blocks ✨ If nothing gets lost in round two, every receiver can rebuild an exact copy of each original block 🎉 Even if people are missing different symbols from different blocks, the redundant symbols for a block help every receiver who's missing something from that block in round two. That's the whole teamwork energy 🫶

Other reliable IP multicast protocols use FEC codes in a Data Carousel style, and the official name for this is an FEC Data Carousel 🎠 Say you use a large block FEC code. The large block FEC encoder spits out n encoding symbols, treating all k source symbols of an object as one block 💅 The sender loops through those n encoding symbols and sends them in packets, in the same order, every single round 🔁 An FEC Data Carousel can protect you from packet loss way better than a plain Data Carousel does 🔥 A receiver can jump in at any moment. As long as it gets at least k encoding symbols during the next n encoding symbols, it can fully recover the object 🙌 And this still works even if the receiver starts catching packets right in the middle of a pass through the encoding symbols 🧚 This method can also work when the object is split into blocks and a short block FEC code is applied to each block on its own. In that case it's useful to interleave the symbols from the different blocks when they're sent, and we'll get into the details of why below 👀

Because an expandable FEC encoder can make any number of encoding symbols, reliable IP multicast protocols using expandable FEC codes usually depend only on those codes for reliability 🌈 For example, when an expandable FEC code runs in an FEC Data Carousel, the encoding packets never repeat. So any k of the potentially unbounded pile of encoding symbols are enough to recover the original k source symbols 💜

Other reliable IP multicast protocols get reliability by generating just enough encoding symbols so that each one is sent only once (at most) 🍓 For example, the sender can decide ahead of time how many encoding symbols it's going to send, use an FEC code to generate that many from the object, and then send them all to every receiver 📦 This suits streaming protocols really well. The stream gets split into objects, the source symbols for each object are encoded into encoding symbols with an FEC code, and then each object's set of encoding symbols goes out one after the other over IP multicast 🎀

2. FEC Codes ✨

2.1. Simple codes

There are some super simple codes that fix packet loss really well when the loss rate is very low 🌸 For example, to protect against a single loss, you chop the object into fixed-size source symbols and then add one redundant symbol that's the parity (XOR) of all the source symbols 🧁 A source symbol's size gets picked so it fits perfectly into a packet's payload. So if the packet payload is 512 bytes, every source symbol is 512 bytes 📏 Each packet's header has enough info to identify its payload, and that's an example of an encoding symbol ID 🪪 In this example, the encoding symbol ID has two parts. The first part is an encoding flag: it's 1 if the encoding symbol is a source symbol, and 0 if it's a redundant symbol 🚩 The second part is a source symbol ID when the encoding flag is 1, and a redundant symbol ID when the encoding flag is 0 🔢 Source symbol IDs go from 0 to k-1, and the redundant symbol ID can just be 0 💖 Let's say the object has four source symbols with values a, b, c and d. Then the redundant symbol's value is e = a XOR b XOR c XOR d 🧮 So the packets end up looking like this:

(1, 0: a), (1, 1: b), (1, 2: c), (1, 3: d), (0, 0: e).

In this example, the encoding symbol ID is the first two values in each tuple, where the first value is the encoding flag and the second is either a source symbol ID or the redundant symbol ID 💅 Whatever comes after the colon is the value of the encoding symbol 🦋 Here's the iconic part: any single source symbol can be recovered as the parity of all the other symbols 👑 For example, say these packets arrive:

(1, 0: a), (1, 1: b), (1, 3: d), (0, 0: e)

Then the missing source symbol with source symbol ID = 2 can be rebuilt by computing a XOR b XOR d XOR e = c 🙈 Literally just math, but make it cute 🎀

Another way to form the encoding symbol ID is to let the values 0,...,k-1 match the k source symbols, and let the value k match the redundant symbol, which is the XOR of the k source symbols 🌈

When the object has a lot of source symbols, a simple block code version of the above can save the day 🫶 Here, the source symbols get grouped into source blocks, each made of some number k of consecutive symbols. The k can be different for different blocks 🧩 If a block has k source symbols, you add one redundant symbol to make an encoding block of k+1 encoding symbols. Then a source block of k source symbols can be recovered from any k of the k+1 encoding symbols in its encoding block 💜

There are also slightly fancier ways to add redundant symbols using parity ✨ For example, you can arrange a block of k source symbols in an object into a p x p square matrix, where p = sqrt(k) 🧠 Then, for each row, you add a redundant symbol that's the parity of all the source symbols in that row. Same deal for each column: add a redundant symbol that's the parity of all the source symbols in that column 🪄 That means any row of the matrix can be recovered from any p of the p+1 symbols in that row, and the same goes for any column 🥹 Higher-dimensional product codes built with this technique are also an option. But you have to be wary of using these constructions without thinking hard about the possible loss patterns of symbols ⚠️ Ideally, you'd want this property: if k source symbols get encoded into n encoding symbols (the encoding symbols are the source symbols plus the redundant symbols), then the k source symbols can be recovered from any k of the n encoding symbols 🌟 The simple constructions described above don't come close to that ideal behavior, bestie 😭

2.2. Small block FEC codes ✨

Okay so, reliable IP multicast protocols may use a block (n, k) FEC code [2] 🎀. The idea is that k source symbols get encoded into n > k encoding symbols, and any k of those encoding symbols can be used to rebuild the original k source symbols 🔥. Because of that, these codes have no reception overhead when you encode the entire object directly 😭✨. Block codes are usually systematic, which means the n encoding symbols are made of the k source symbols plus n-k redundant symbols generated from those k source symbols. A redundant symbol is the same size as a source symbol 💅. The first simple code (XOR) from the last section is a (k+1, k) code 🍓. Honestly though, choosing n bigger than k+1 is a total power move, because it gives way better protection against losses 🛡️💜.

The big popular example here is the Reed-Solomon family, which runs on algebraic methods using finite fields 🧚. Implementations of (n, k) FEC erasure codes are efficient enough for personal computers to use [16]. For example, [15] describes an implementation where the encoding and decoding speeds decay as C/j. The constant C is on the order of 10 to 80 Mbytes/second for Pentium class machines of various vintages, and j is upper bounded by min(k, n-k) 🌈.

In practice, k and n have to stay small (for example, below 256), because large values make encoding and decoding prohibitively expensive 💀. Most objects are longer than k symbols for reasonable values of k and symbol length. For example, with k = 16 and 1 kilobyte symbols, anything bigger than 16 kilobytes is already too long 🙈. So objects get split into a bunch of source blocks. Each source block has some number k of source symbols, and that k can vary between source blocks 🦋. The FEC encoder turns each k-symbol source block into an n-symbol encoding block, and n can vary per source block too ✨.

For a receiver to fully recover the object, it needs k distinct encoding symbols (meaning different encoding symbol IDs) from the matching encoding block, for every source block 🫶. Sometimes a block gets more encoding symbols than it has source symbols. When that happens, the extra encoding symbols get thrown away 🗑️. Here's how the encoding structure looks, with Figure 1 showing it 👑:

       |   source symbol IDs   |   source symbols IDs  |
       |   of source block 0   |   of source block 1   |
                    |                          |
                    v                          v
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
       |0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                               |
                           FEC encoder
                               |
                               v
   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
   |0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                  ^                             ^
                  |                             |
   |  encoding symbol IDs        | encoding symbol IDs         |
   |  of encoding block 0        | of encoding block 1         |
Figure 1 is giving "two source blocks, each with 8 source symbols", and the FEC encoder makes 2 extra redundant symbols per block (10 encoding symbols total for each of the two blocks) 🎀.

Most of the time an object is split into equal-length source blocks, and each one has k contiguous source symbols from the object. So block c holds the range of source symbols [ck, (c+1)k-1] 🌸. This is great because the FEC encoder can be optimized for one particular k, and memory references stay local when the sender reads source symbols to encode and when the receiver reads encoding symbols to decode 🧠. Locality matters a LOT when the object lives on disk, since it cuts down on disk seeks 💿. The block number plus the source symbol ID inside that block can be used to uniquely pin down a source symbol in the object 📍. If the object size isn't a multiple of k source symbols, the last source block just ends up with fewer than k symbols 🥲.

Block numbers can be counted consecutively from zero 🔢. Encoding symbols inside a block can be uniquely identified with an encoding symbol ID 🪪. One way to do that is to pair an encoding flag (which says whether the symbol is a source symbol or a redundant symbol) with either a source symbol ID or a redundant symbol ID 💜. For example, an encoding flag value of 1 means source symbol, and 0 means redundant symbol. Source symbol IDs can run from 0 to k-1, and redundant symbol IDs can run from 0 to n-k-1 ✨.

Let's do an example, because examples are my love language 💖. Say the object has 10 source symbols, a through j, with k = 5 and n = 8. That gives two source blocks of 5 symbols each, and two encoding blocks of 8 symbols each. Let p, q and r be the redundant symbol values for the first encoding block, and let x, y and z be the redundant symbol values for the second one. The encoding symbols and their identifiers are:

(0, 1, 0: a), (0, 1, 1: b), (0, 1, 2: c), (0, 1, 3: d), (0, 1, 4: e),
(0, 0, 0: p), (0, 0, 1: q), (0, 0, 2: r),
(1, 1, 0: f), (1, 1, 1: g), (1, 1, 2: h), (1, 1, 3: i), (1, 1, 4: j),
(1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z).

In that notation, the first value is the block number, and the next two values together identify the encoding symbol inside the block. So the encoding symbol ID is the encoding flag plus either the source symbol ID or the redundant symbol ID, depending on the flag 🧩. The symbol's value comes after the colon 🎁. Each block can be recovered from any 5 of its 8 encoding symbols 🙌. For instance, receiving

 (0, 1, 1: b), (0, 1, 2: c), (0, 1, 3: d), (0, 0, 0: p), (0, 0, 1: q)

is enough to recover the first source block, and receiving

 (1, 1, 0: f), (1, 1, 1: g), (1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z)

is enough to recover the second source block 🫠✨.

There's also another way to uniquely identify encoding symbols inside a block. You let the encoding symbol IDs for source symbols be 0,...,k-1, and the encoding symbol IDs for redundant symbols be k,...,n-1 🦋.

2.3. Large block FEC codes 🌊

Tornado codes [12], [13], [10], [11], [9] are large block FEC codes, and they're the alternative to small block FEC codes 💫. An (n, k) Tornado code needs slightly more than k out of n encoding symbols to recover k source symbols. In other words, there's a small reception overhead 🥹. The trade is that the non-zero reception overhead buys you a value of k in the tens of thousands while encoding and decoding stay efficient 🚀. Because of memory considerations, n is usually restricted to a small multiple of k in practice, for example n = 2k 🧸. [4] describes an implementation of Tornado codes where encoding and decoding speeds are tens of megabytes per second for Pentium class machines of various vintages, when k is in the tens of thousands and n = 2k 🔥. The reception overhead for those values of k and n sits in the 5-10% range 📈. Tornado codes also need a big pile of out-of-band information communicated to all senders and receivers for each different object length 📦. On top of that, they need memory on the encoder and decoder that is proportional to the object length times 2n/k 🧮.

Tornado codes are designed to have low reception overhead on average, when receiving a random portion of the encoding packets 🎲. So, to make sure a receiver can reassemble the object with low reception overhead, the packets get permuted into a random order before transmission 🔀💖.

2.4. Expandable FEC codes ✨

Okay so, everything we've looked at so far is block codes 📦. But there's a whole other flavour called expandable FEC codes 🦋. Like block codes, an expandable FEC encoder works on an object of known size that's been chopped into equal-length source symbols 🍓. The difference is that there's no predetermined number of encoding symbols. The encoder can make as few or as many unique encoding symbols as you need, on demand 💅.

LT codes [6], [7], [8], [5] are an example of large expandable FEC codes with a small reception overhead 👑. An LT encoder uses randomization to generate each encoding symbol randomly and independently of all the other encoding symbols 🎲. Like Tornado codes, the number of source symbols k can be super huge for LT codes, on the order of tens to hundreds of thousands 😭, and the encoder and decoder run efficiently in software 💻. For example, the encoding and decoding speeds for LT codes are in the range 3-20 megabytes per second on Pentium class machines of various vintages when k is in the high tens of thousands 🔥. An LT encoder can generate as few or as many encoding symbols as required on demand ✨.

When an LT encoder needs to make a new encoding symbol, it's based on a randomly chosen encoding symbol ID that uniquely describes how that symbol is generated from the source symbols 🧚. In general, each encoding symbol ID value corresponds to one unique encoding symbol. So the space of possible encoding symbols is approximately four billion if, for example, the encoding symbol ID is 4 bytes 🤯. That means the chance that a particular encoding symbol is the same as any other particular encoding symbol is inversely proportional to the number of possible encoding symbol IDs 🧮.

An LT decoder has the property that, with very high probability, receiving any set of slightly more than k randomly and independently generated encoding symbols is enough to reassemble the k source symbols 🫶. For example, when k is on the order of tens to hundreds of thousands, the reception overhead is less than 5% with no failures in hundreds of millions of trials under any loss conditions 🌈.

Because encoding symbols are generated randomly and independently by choosing random encoding symbol IDs, LT codes have a really cool property 😍. Encoding symbols for the same k source symbols can be generated and transmitted from multiple senders and received by one receiver. The reception overhead and the decoding time are the same as if all the encoding symbols had come from a single sender 🙌. The only requirement is that the senders choose their encoding symbol IDs randomly and independently of one another 🎀.

There's a weak tradeoff between the number of source symbols and the reception overhead for LT codes. The larger the number of source symbols, the smaller the reception overhead 📉. So for shorter objects, it's sometimes a good move to partition the object into many short source symbols and include multiple encoding symbols in each packet 📦✨. In that case, a single encoding symbol ID is used to identify the multiple encoding symbols contained in one packet 🍭.

There are a couple of factors to weigh when choosing the symbol length and number of source symbols. The main one is that there's a fixed overhead per symbol in the overall processing for encoding and decoding, no matter how many source symbols there are 🧠. So shorter symbols mean that this fixed per-symbol processing becomes a bigger chunk of the total work, which leads to larger overall processing requirements 🐢. A second, much less important consideration is that there's a part of the per-symbol processing that depends logarithmically on the number of source symbols. For that reason, there's a slight preference towards fewer source symbols 💜.

Like small block codes, there's a point where the object is big enough that it makes sense to partition it into blocks when using LT codes 🧩. Generally, the object is partitioned into blocks whenever the number of source symbols times the packet payload length is less than the size of the object. So if the packet payload is 1024 bytes and the maximum number of source symbols is 128,000, then any object over 128 megabytes gets partitioned into more than one block 🌸. You can choose the maximum number of source symbols depending on the encoding and decoding speed versus reception overhead tradeoff you want 🎯.

Encoding symbols can be uniquely identified by a block number, when the object is big enough to be partitioned into more than one block, and by an encoding symbol ID 🪪. If block numbers are used, they're generally numbered consecutively, starting from zero within the object 🔢. The block number and the encoding symbol ID are both chosen uniformly and randomly from their range when an encoding symbol is about to be transmitted 🎰.

Here's an example to make it click 👀. Suppose the number of source symbols is 128,000 and the number of blocks is 2. Then each packet generated by the LT encoder could be of the form (b, x: y). In this example, the first value identifies the block number, and the second value identifies the encoding symbol within the block. The block number b is either 0 or 1, and the encoding symbol ID x might be a 32-bit value. The value y after the colon is the value of the encoding symbol 💖.

2.5. Source blocks with variable length source symbols 🎀

For all the FEC codes described above, all the source symbols in the same source block are the same length 📏. In this section, we describe a general technique for when it's useful to use source symbols of varying lengths in a single source block 🌈. This technique works for block FEC codes 🧱.

Let l_1, l_2, ... , l_k be the lengths in bytes of k varying length source symbols that are considered part of the same source block 📐. Let lmax be the maximum over i = 1, ... , k of l_i 🔝. To prepare the source block for the FEC encoder, pad each source symbol i out to length lmax with a suffix of lmax-l_i zeroes 0️⃣. Then prepend the value l_i to the beginning of that 🧁. Each padded source symbol is therefore of length x+lmax, assuming it takes x bytes to store an integer with possible values 0,...,lmax. Here, x is a protocol constant that's known to both the encoder and the decoder 🤝. These padded source symbols, each of length x+lmax, are the input to the encoder, together with the value n. The encoder then generates n-k redundant symbols, each of length x+lmax ✨.

The encoding symbols that go into packets are made up of the original k varying length source symbols and the n-k redundant symbols, each of length x+lmax 📦. From any k of the received encoding symbols, the FEC decoder recreates the k original source symbols as follows 🔍. If all k original source symbols are received, no decoding is necessary 🥳. Otherwise, at least one redundant symbol is received. From that, the receiver can easily tell whether the block is made up of variable-length source symbols. If the redundant symbol(s) are longer than the source symbols, then the source symbols are variable-length 🕵️‍♀️. Note that in a variable-length block, the redundant symbols are always longer than the longest source symbol, because of the prepended symbol-length 🧠. The receiver can work out the value of lmax by subtracting x from the length of a received redundant symbol 🧮. For each of the received original source symbols, the receiver can generate the corresponding padded source symbol as described above 🔁. Then the input to the FEC decoder is the set of received redundant symbols, together with the set of padded source symbols built from the received original symbols. The FEC decoder then produces the set of k padded source symbols 🎁. Once the k padded source symbols have been recovered, the length l_i of original source symbol i can be recovered from the first x bytes of the ith padded source symbol. Then original source symbol i is obtained by taking the next l_i bytes following the x bytes of the length field 💅.

3. Security Considerations 🚨

Okay, this part is serious bestie 😤. The use of FEC, all by itself, adds no additional security considerations compared with sending the same information without FEC 🙏. BUT, just like for any transmission system, a malicious sender may try to inject packets that carry corrupted encoding symbols 😈. If a receiver accepts one or more corrupted encoding symbols in place of authentic ones, then that receiver may reconstruct a corrupted object 💀.

Yikes! Application-level transmission object authentication can detect the corrupted transfer, but the receiver must discard the transferred object 🚫. Injecting corrupted encoding symbols means they get accepted as valid encoding symbols by a receiver, which is, at the very least, an effective denial of service attack 😭🔥.

In light of this possibility, FEC receivers may screen the source address of a received symbol against a list of authentic transmitter addresses 🛡️. Since source addresses can be spoofed, transport protocols using FEC may provide mechanisms for robust source authentication of each encoding symbol 🔐. Multicast routers along the path of a FEC transfer may provide the capability of discarding multicast packets that originated on that subnet and whose source IP address doesn't match that subnet 🚧.

It is recommended that a packet authentication scheme such as TESLA [14] be used in conjunction with FEC codes 💜. Then, packets that can't be authenticated can be discarded, and the object can be reliably recovered from the received authenticated packets 🎀.

4. Intellectual Property Disclosure ⚖️

The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document 📜. For more information, consult the online list of claimed rights 🔗.

5. Acknowledgments 🫶

Thanks to Vincent Roca and Hayder Radha for their detailed comments on this document 🌸💖.

6. References 📚✨

okay bestie, the reference list is where all the receipts live 🧾💅 these are the papers and patents the whole spec is built on, so don't skip any of them 🫶

  • [1] Acharya, S., Franklin, M. and S. Zdonik, "Dissemination - Based Data Delivery Using Broadcast Disks", IEEE Personal Communications, pp.50-60, Dec 1995. 📡
  • [2] Blahut, R.E., "Theory and Practice of Error Control Codes", Addison Wesley, MA, 1984. 📘
  • [3] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996. 📜
  • [4] Byers, J.W., Luby, M., Mitzenmacher, M. and A. Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data", Proceedings ACM SIGCOMM '98, Vancouver, Canada, Sept 1998. 🌊
  • [5] Haken, A., Luby, M., Horn, G., Hernek, D., Byers, J. and M. Mitzenmacher, "Generating high weight encoding symbols using a basis", U.S. Patent No. 6,411,223, June 25, 2002. 🔖
  • [6] Luby, M., "Information Additive Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,307,487, October 23, 2001. 🔖
  • [7] Luby, M., "Information Additive Group Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,320,520, November 20, 2001. 🔖
  • [8] Luby, M., "Information Additive Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,373,406, April 16, 2002. 🔖
  • [9] Luby, M. and M. Mitzenmacher, "Loss resilient code with double heavy tailed series of redundant layers", U.S. Patent No. 6,195,777, February 27, 2001. 🔖
  • [10] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D. and V. Stemann, "Message encoding with irregular graphing", U.S. Patent No. 6,163,870, December 19, 2000. 🔖
  • [11] Luby, M., Mitzenmacher, M., Shokrollahi, A. and D. Spielman, "Efficient Erasure Correcting Codes", IEEE Transactions on Information Theory, Special Issue: Codes on Graphs and Iterative Algorithms, pp. 569-584, Vol. 47, No. 2, February 2001. 🧠
  • [12] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D. Spielman, "Loss resilient decoding technique", U.S. Patent No. 6,073,250, June 6, 2000. 🔖
  • [13] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D. Spielman, "Irregularly graphed encoding technique", U.S. Patent No. 6,081,909, June 27, 2000. 🔖
  • [14] Perrig, A., Canetti, R., Song, D. and J.D. Tygar, "Efficient and Secure Source Authentication for Multicast", Network and Distributed System Security Symposium, NDSS 2001, pp. 35-46, February 2001. 🔐
  • [15] Rizzo, L., "Effective Erasure Codes for Reliable Computer Communication Protocols", ACM SIGCOMM Computer Communication Review, Vol.27, No.2, pp.24-36, Apr 1997. 🌟
  • [16] Rizzo, L., "On the Feasibility of Software FEC", DEIT Tech Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997. 💻

7. Authors' Addresses 💌

these are the brilliant humans who wrote this thing, so here's where to find them 🥰

Michael Luby Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538

EMail: luby@digitalfountain.com

Lorenzo Vicisano Cisco Systems, Inc. 170 West Tasman Dr., San Jose, CA, USA, 95134

EMail: lorenzo@cisco.com

Jim Gemmell Microsoft Research 455 Market St. #1690 San Francisco, CA, 94105

EMail: jgemmell@microsoft.com

Luigi Rizzo Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy

EMail:luigi@iet.unipi.it

Mark Handley ICSI Center for Internet Research 1947 Center St. Berkeley CA, USA, 94704

EMail: mjh@icir.org

Jon Crowcroft Marconi Professor of Communications Systems University of Cambridge Computer Laboratory William Gates Building J J Thomson Avenue Cambridge CB3 0FD

EMail: Jon.Crowcroft@cl.cam.ac.uk

Copyright (C) The Internet Society (2002). All Rights Reserved.

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.

The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS 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.

Acknowledgement 🌷

Funding for the RFC Editor function is currently provided by the Internet Society. 💖

📦 where this page comes from