FEC - 前向纠错技术
Table of Contents
FEC：Forward Error Correction，前向纠错
FEC 是一种通过在网络传输中增加数据包的冗余信息，使得接收端能够在网络发生丢包后利用这些冗余信息直接恢复出丢失的数据包的一种方法。 https://zhuanlan.zhihu.com/p/104579290
##
Parity Check 奇偶校验
// 例如：求 10100001 中 1 的数量是奇数还是偶数
// 结果为 1 就是奇数个 1，结果为 0 就是偶数个 1
1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1
每个字节的数据都计算一个校验位，数据和校验位一起发送出去，这样接收方可以根据校验位粗略地判断接收到的数据是否有误。
##
基于 XOR 的 FEC
假设网络通信有 N 个 packet 需要发送，那么可以每 2 个 packet 生成一个 FEC packet，这样，连续的 3 个 packet 的任意一个 packet 丢失，都能通过另外 2 个恢复出来。
但考虑到每 2 个 packet 就产生 1 个 fec packet，冗余度可能有点高（比较浪费带宽），我们能否每 3 个或者每 N 个 packet 再产生一个 fec packet 呢？当然可以，我们以每 3 个 packet（A、B、C） 产生 1 个 fec packet（D）为例来推导一下：
d = a ^ b ^ c
a = a ^ (b ^ b) ^ (c ^ c) = (b ^ c) ^ (a ^ b ^ c) = b ^ c ^ d
b = (a ^ a) ^ b ^ (c ^ c) = (a ^ c) ^ (a ^ b ^ c) = a ^ c ^ d
c = (a ^ a) ^ (b ^ b) ^ c = (a ^ b) ^ (a ^ b ^ c) = a ^ b ^ d
由上述公式推导即可知道，这 4 个 packet，任意丢失 1 个 packet，均可以由其他 3 个 packet 恢复出来。
##
对象存储 - EC 纠删码
通过 K 个有效数据，产生 M 个 FEC 冗余包，这 K + M 个数据，任意丢失 M 个数据，都能把 K 个有效数据恢复出来。
#
Reed-Solomon Codes
##
RFC 草案 Payload Flexible FEC
#
1.1 奇偶校验码
##
1.1.1 一维 Parity FEC Protection
非交错，按行生成，一行里丢一个包可以，丢两个就没法恢复了（Burst Loss）
一维连续 FEC 保护
+---+ +---+ +===+
| 1 | X X | 4 | |R_1|
+---+ +---+ +===+
+---+ +---+ +---+ +---+ +===+
| 5 | | 6 | | 7 | | 8 | |R_2|
+---+ +---+ +---+ +---+ +===+
+---+ +---+ +---+ +---+ +===+
| 9 | | 10| | 11| | 12| |R_3|
+---+ +---+ +---+ +---+ +===+
非交错，按列生成，一列里丢一个包可以，丢两个就没法恢复了（Periodic Loss）
一维隔行 FEC 保护
+---+ +---+ +---+
| 1 | X | 3 | | 4 |
+---+ +---+ +---+
+---+ +---+ +---+
| 5 | X | 7 | | 8 |
+---+ +---+ +---+
+---+ +---+ +---+ +---+
| 9 | | 10| | 11| | 12|
+---+ +---+ +---+ +---+
+===+ +===+ +===+ +===+
|C_1| |C_2| |C_3| |C_4|
+===+ +===+ +===+ +===+
##
1.1.2 二维 Parity FEC Protection
互联网丢包是随机的、爆发式的，发送端应该生成 non-interleaved 和 interleaved 前项纠错包（FEC packets）
这种 FEC 保护被称作 二维奇偶校验前向纠错保护
但是如果发生特定的 loss pattern，这种保护模式依然会失效，比如：
+---+ +---+ +===+
| 1 | X X | 4 | |R_1|
+---+ +---+ +===+
+---+ +---+ +---+ +---+ +===+
| 5 | | 6 | | 7 | | 8 | |R_2|
+---+ +---+ +---+ +---+ +===+
+---+ +---+ +===+
| 9 | X X | 12| |R_3|
+---+ +---+ +===+
+===+ +===+ +===+ +===+
|C_1| |C_2| |C_3| |C_4|
+===+ +===+ +===+ +===+
+---+ +---+ +---+
| 1 | | 2 | X | 4 | X
+---+ +---+ +---+
+---+ +---+ +---+ +---+ +===+
| 5 | | 6 | | 7 | | 8 | |R_2|
+---+ +---+ +---+ +---+ +===+
+---+ +---+ +---+
| 9 | | 10| X | 12| X
+---+ +---+ +---+
+===+ +===+ +===+ +===+
|C_1| |C_2| |C_3| |C_4|
+===+ +===+ +===+ +===+
##
1.1.3 开销计算 Overhead Computation
开销（overhead）被定义为：
修复包大小 / 源包大小
单位：Bytes
通常来说，修复包比源包更大。
如果我们假设每一个修复包携带与源包等量的 bytes，我们可以计算出每一个不同的 FEC 保护策略的开销：
一维连续 FEC 保护：开销 = 1/L
一维隔行 FEC 保护：开销 = 1/D
二维 FEC 保护：开销 = 1/L + 1/D
where L and D are the number of columns and rows in the source block, respectively.
##
3. 定义
L：表示列
D：表示行
bitmask：由 FEC 包保护的包的运行长度编码。如果掩码中的位 i 被设置为 1，源数据包的编号 N + i 被这个 FEC 包保护。这里，N 是数基数，FEC 包中也有表示。
##
4. 包格式
这一小节定义了源包和修复包的格式
#
4.1 源包
#
4.2 修复包
修复包必须包含标识它们所属的源块的信息，以及包含的修复符号与原始源块之间的关系。为此，我们使用修复包的 RTP 报头以及 RTP 有效负载中的另一个报头，我们将其称为 FEC 报头，如图 9 所示。
（注意，受特定 FEC 包保护的所有源流包都需要在同一个 RTP 会话中。）
+------------------------------+
| IP Header |
+------------------------------+
| Transport Header |
+------------------------------+
| RTP Header | __
+------------------------------+ |
| FEC Header | \
+------------------------------+ > RTP Payload
| Repair Symbols | /
+------------------------------+ __|
Marker (M) Bit: 应该被设置成 0
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|R|F| P|X| CC |M| PT recovery | length recovery |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TS recovery |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRCCount | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRC_i |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SN base_i |k| Mask [0-14] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|k| Mask [15-45] (optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|k| |
+-+ Mask [46-108] (optional) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... next in SSRC_i ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
##
8. 拥塞控制考虑
in networks where the congestion is a major contributor to the packet loss, the potential impacts of using FEC SHOULD be considered carefully before injecting the repair flows into the network.
In particular, in bandwidth-limited networks, FEC repair flows may consume most or all of the available bandwidth and consequently may congest the network. In such cases, the applications MUST NOT arbitrarily increase the amount of FEC protection since doing so may lead to a congestion collapse. If desired, stronger FEC protection MAY be applied only after the source rate has been reduced.