About Packet Loss Recovery
About Packet Loss Recovery
1、几种丢包恢复方法概述
目前基于发端的防丢包措施，除ARQ外，有交织和前向纠错（FEC）。
n 交织
交织的原理比较简单，但纯粹的交织只是将原来集中的信息丢失分散开来，使连续错误变成一种近似随机的错误，从比特流的角度来看，并没有改善，只适用于对随机比特错误不敏感的应用。而且包间交织（比特交织）需要进行缓冲，会引入端到端时延。
FEC是常用的另外一种方法，它以传输额外校验比特（牺牲带宽）为代价，换取可靠性的提升。FEC可分为内容无关和内容相关两种类型。
u 内容无关型FEC
内容无关型FEC对于业务数据来讲是透明的，它只是在原先包的基础上增加冗余，丢包后收端可根据冗余信息恢复。然而，它的保护能力直接决定于冗余的大小，以及其生成方法（决定了编译码的复杂程度）。常用的FEC有奇偶校验码（parity code）和里得-所罗门码（Reed-Solomon code）。奇偶校验码相对简单些，一般采用按帧（包）异或的方法。假设原数据为n-1包，对其进行模2加运算，生成第n包，当这n包数据中任意一包丢失时，都可以根据其它n-1包恢复出来。里得-所罗门码的数学模型比较复杂，但对突发丢包具有较好的效果。实现上，当丢包率大时，译码时的计算量非常大。
u 内容相关型FEC
内容相关型FEC利用对信源的了解来生成冗余，它的校验位不仅来自于各包的约束关系，而且直接与信源的内容相关。比如在语音传输中，每一帧的原始数据被分别存放在多个包中（可采取不同的压缩算法，降低备份的质量来减小整体带宽），当某一包丢失时，可以从含对应数据包中取出恢复（质量可能会降低）。
2、可采取的几种方案及性能分析
FEC理论上的上限推导比较复杂，并且在实际中它也是很难达到的。我们做了一些工作，就目前常用的几种方法的性能进行了分析。这里所采取的FEC都属于内容无关型。
n 交织
交织并没有纠错功能，它只是将原来的突发连续错误（丢包）转变为随机错误。它不增加带宽。假设采用完全随机交织，交织后各包等长，那么30%丢包率将带来收端30%的误比特率。如果再假设信源比特等概率分布，那么在收端可以全补’0’或’1’，之后误比特率可降为15%。
n 包间奇偶校验
每两包进行奇偶校验，可以满足1/3的冗余度要求。当编码后的三个包中的任意一个丢失时，可以由另外两个恢复。但实际上大多数丢包是连续发生的[1]，当连续两个以上包丢失时，这种方法失效。
n 比特奇偶校验
比特奇偶校验实现较为容易。先对原始数据流按比特进行异或运算，每2比特生成1比特校验位，之后对得到的2/3码率的数据流比特进行交织，重新分包后传输。如果采用随机交织且包长相等，则最终误码率与丢包是否连续无关。30%丢包率可近似为30%误比特率，收端根据比特间的奇偶校验规则进行译码，对于译码不成功的比特，可以随机填补以进一步降低最终误比特率。下图为比特奇偶校验的仿真结果：
可以看到在丢包率为30%时，经过比特奇偶校验译码及第二次随机填补后，最终的误比特率约为6%。
n 里得-所罗门码
里得-所罗门码有一个性能上限推导方法，就是纠正t个错误码元最多需要2t个校验码元。假设30%码元因为丢失而造成错误，那么要达到100%的纠正，同时传输的校验码元必须不少于60%，即效数据只能占40%，也就是说在30%的丢包率下要做到完全可靠传输，新增带宽至少为原来的150%。反过来说，在增加带宽为50%的情况下，校验码元占全部数据的33%，最多可以纠正约16%的码元错误，因此，这种情况下要做到可靠传输，丢包率应小于15%。
n 卷积码
卷积码通常用来纠正随机错误，因此我们将它与交织方法相结合。实验发现在原始误比特率高达30%的情况下，2/3码率的卷积码性能甚至比奇偶校验码还要差，并且约束长度越大，性能恶化越严重，1/2码率的卷积码虽然表现较好，但最终误码率仍在10-2级。
还考察了Turbo码+交织的方案，在1/3码率下，实验中所用的Turbo码可达到最终误码率小于10-9，代价是新增带宽250%。
3、结论
就视频传输来讲，对比特误码率的要求是比较高的，错误比特常造成最终解压缩时误码扩散。MPEG-4采用了抗比特误码的压缩编码，但要求比特误小于10-3，MPEG-1和MPEG-2对误码更加敏感。当丢包率为30%，在增加带宽不超过50%的情况下，纯粹采用与内容无关的FEC ，初步的实验表明最好的情况下误码率为10-2，远不能达到要求。
我们认为，比较有希望的解决之道应该是采用内容相关型的FEC，将视频压缩与FEC放在一起考虑。比如采取非平衡的错误保护，对那些关键帧进行高可靠性保护，而非键帧则用较少的冗余保护或者不保护，当其丢失时，根据相邻数据进行插值恢复。或者采用弹性的分层压缩编码，丢包时只降低恢复的质量，但整体上仍具可用性。
但是，如果考虑到压缩编码和纠错编码联合，就需要对原先所采用的压缩方法非常了解，并在此基础上设计方案，短时间内是做不到的。如果对于视频的连续性和平滑程度要求比较宽松，采用非平衡保护的方法比较容易实现。
参考资料
[1] Velibor Markovski, Fei Xue, and Ljiljana Trajkovi, “Simulation and analysis of packet loss in video transfers using User Datagram Protocol”, School of Engineering Science, Simon Fraser University, Vancouver, British Columbia,Canada E-mail: {vmarkovs, fxue, ljilja}@cs.sfu.ca.
[2] Nick Feamster and Hari Balakrishnan, “Packet Loss Recovery for Streaming Video”, M.I.T. Laboratory for Computer Science,Cambridge, MA 02139.
[3] Wenyu Jiang and Henning Schulzrinne, “Comparison and Optimization of Packet Loss Repair Methods on VoIP Perceived Quality under Bursty Loss”, Department of Computer Science, Columbia University 1214 Amsterdam Ave, Mail Code 0401,New York, NY 10027, USA,fwenyu,hgsg@cs.columbia.edu
[4] Colin Perkins, Orion Hodson, and Vicky Hardman, “A Survey of Packet Loss Recovery Techniques for Streaming Audio”, University College Lond