玩转KCP(4)-FEC(前向纠错)
版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 xtaci/kcp-go的作者，在KCP标准协议的基础上做了扩展，增加了加密和FEC（Forward error correction，前向纠错）那么前向纠错到底是干什么用的 2. reed-solomon算法概述 在xtaci/kcp-go中，FEC的实现使用的是reed-solomon编码(实现库为klauspost/reedsolomon)，这是一种诞生于上个世纪60年代的一种纠错码。详细的解释见参考资料1 原始数据如下图所示 它由4个piece组成, “ABCD” “EFGH” “IJKL” “MNOP”, 每行当做一个piece。 reed-solomon算法构造了一个编码矩阵(别问萌叔怎么构造，反正是挺深奥的数学问题)，使得这个矩阵与原始矩阵相乘以后，得到的新矩阵。可以观察出来，新矩阵的前4个piece与旧矩阵完全相同，剩余的2个piece，被叫做parity, 权且翻译为校验块吧。 即使新矩阵丢失了2个piece 在等式2边乘以编码矩阵的逆矩阵，就可以消去编码矩阵，重新恢复出原始数据 3. reed-solomon算法结论总结 包含有n个symbol的消息可以通过reed-solomon算法，得到包含 n + k 个 symbol的新消息。任意丢失至多k个symbol，原始消息仍然能够被恢复出来。这里symbol和piece的概念类同。 因为reed-solomon算法的这个特性，它被广泛的用于 1）DVD、CD、二维码 碟片即使有部分被刮花，仍然能够播放 二维码即使部分被遮挡，仍然能够识别 2）远距离空间传输 空间探测器在向地球发送数据包时，每个包的传输可能需要耗费几个小时，传输过程中，极有可能由于其他陨石遮挡等原因，造成丢包。有了reed-solomon算法，丢失的包可以被直接恢复出来，不需要再重传。 3）存储系统，比如 minio 甚至萌叔发现它在 minio/minio 一个支持Amazon S3协议的对象存储系统中也有使用 缺点 增加了额外的存储和传输量，另外在做数据恢复时，有额外的计算开销。 4. FEC KCP协议中前向纠错相关的字段是这样设定的，它和块加密一样，都是可选的 FEC TYPE: typeData = 0xF1 原始数据块 typeParity = 0xF2 校验数据块 FEC SEQID: 递增的计数器 +-----------------+ | SESSION | +-----------------+ | KCP(ARQ) | +-----------------+ | FEC(OPTIONAL) | +-----------------+ | CRYPTO(OPTIONAL)| +-----------------+ | UDP(PACKET) | +-----------------+ | IP | +-----------------+ | LINK | +-----------------+ | PHY | +-----------------+ (LAYER MODEL OF KCP-GO) 注意 和网络分层模型一样，FEC只对自己这层负责，FEC对自己的数据包中到底存的是什么并不感兴趣。因此校验数据块中的数据应该被理解为2进制数据，它们是不能按照ARQ被解析的。 ...