适用于远距离高速网络的多层反馈系统LT码

张先国，张华

（1.中国电子科技集团公司第十五研究所，北京100083；2.战略支援部队航天系统部通信修理所，北京100083）

适用于远距离高速网络的多层反馈系统LT码

张先国1，张华2

（1.中国电子科技集团公司第十五研究所，北京100083；2.战略支援部队航天系统部通信修理所，北京100083）

针对LT码在远距离高速网络传输应用，研究发现LT码在提高通信效率的同时增加发送端和接收端的计算量，研究还发现LT码可显著增加数据包的平均到达时延。针对该问题，研究并提出一种多层反馈系统LT码。依据远距离高速网络中丢包率较小的特征，使用反馈系统码可以减少编解码的计算量；依据单个丢包均匀分布在较小码长内，突发丢包分布在较大码长内的特征，使用多层码分别覆盖单个丢包和突发丢包。仿真结果表明，多层反馈系统LT码在提高通信效率的同时，不仅减少发送端和接收端的编解码计算量，而且还减少数据包的平均到达时延。

多层码；时延；LT码；反馈；远距离高速网络

0 引言

因为光纤老化，错误的路由配置以及交换竞争等因素，在远距离高速网络的数据传输过程中存在一定的丢包。由于远距离高速网络中的往返时延（RTT）较长，使得自动重传请求（ARQ）机制效率低下[1]。LT码[2]和Raptor码[3]作为一种无速率码，非常适用于RTT较大并且存在丢包的网络。Raptor码是以LT码为核心的多层级联码。基于LT码和Raptor码的数据传输不需要接收端发送反馈信息。

文献[4]的编码器记录编码过程中每个原码包参与生成编码包的次数，在每次生成编码符号时，选择度数最小的编码包参与编码。文献[5-6]将规则变量节点度LT码应用于删除信道中。但是当码长变长，虽然规则变量节点度LT码能够显著地降低码的差错平台，但是每次生成编码包都需要对该表进行查找和更新，增加了编码器的复杂度，且每次生成编码包的计算复杂度也变高了。

文献[7]研究了LT码在码长固定情况下期望可译集大小ERS（Expected Ripple Size）函数的优化问题和增强置信传播译码的算法。文献[8]研究了可译集递减的度分布生成算法。

但是文献[9]通过引入反馈信息来优化后续编码包的度数，最大化每个编码包在接收端译码成功的概率，没有立即成功译码的编码包被直接丢弃，故其成功译码所需的编码包数量较大，只适用于接收端内存非常小的情况；文献[10]通过引入反馈信息来动态调整LT码的度数分布，降低成功译码所需的编码包数量；文献[11-12]引入滑动窗口机制来扩大码长，降低成功译码时冗余编码包的比例，提高传输效率；文献[13-15]在多次反馈转移LT码的基础上提出一种基于多次反馈的LT-AF码（Alternating Feedback Codes）。LT-AF码在降低反馈的次数的基础上根据编码符号度数波动变化重新修正转移鲁棒孤子分布；文献[16-17]在研究可译集递减的度分布生成算法基础上提出了可译集递减的反馈无速率码；然而原始包从发送端发出到接收端成功译码的时延较长，不适合那些对时效性要求较高的应用，例如视频点播和视频会议。

文献[18-19]把输入符号分成不同的区间，针对不同的区间使用不同的度分布，针对性的优化无速率码的ISRR。文献[20]提出了基于丢包率的系统码实现方法——RCSS（Rateless Coded Symbol Sorting）算法。算法预先假设一个丢包率，然后根据丢包率计算出需要生成的编码符号数量。文献[1]通过引入多层的前向纠错码，减少数据包的平均到达时延，但是其采用固定码率，故不能适应链路丢包率变化的场景。本文提出一种多层反馈系统LT码及其具体实现方案。由于远距离高速网络中丢包率较小，故直接传输原始包效率更高，然后由基于反馈信息生成的编码包以较小的冗余比例可靠的恢复出少量丢失的原始包；引入多层码保证丢失的原始包在尽可能小的码长内被成功译码，首先通过反馈信息分别统计出随机丢包和突发丢包的丢包率，然后针对不同的丢包类型，采用分层的LT码分别进行处理，每一层采用独立的编码空间生成编码包用于恢复该层丢失的原始包，保证得到较为满意的平均时延，最后给出仿真结果和分析。

1 LT码和SLT码

LT码编码过程中的鲁棒孤子分布为[2]：

其中，d=1,2,∙∙∙,k为编码包的度数；详见文献[2]。LT码在整个传输过程中，度数分布保持不变。

SLT码基于收到的反馈信息动态的调整度数分布，从而提高效率，其度数分布为[10]：

其中，d=1,2,∙∙∙,k为鲁棒孤子分布中编码包的度数，d'为调整后编码包的度数，k为码长，n为已经收到的原始包的个数；详见文献[10]。

2 多层反馈系统LT码

2.1 单层反馈系统LT码

由于通过远距离高速网络进行数据传输时，只有少量的原始包丢失，故提出单层反馈系统LT码以提高传输效率。基本原理如下：首先估算链路的丢包率，然后根据公式（3）：

计算出要成功译码所有丢失的原始包所需编码包的数量m，其中常数c>0，为指定参数，δ为指定的译码失败概率；最后将编码包和原始包一起发送到接收端。单层反馈系统LT码用(k ,r,m )表示，其度数分布为：

2.2 多层反馈系统LT码

（ki,ri,mi）码的一个编码包的生成流程如下：

①按照公式4的度数分布随机生成度数d；

②从ki个原始包中随机选择d个原始包；

③d个原始包按位异或生成编码包。

为了保证单个丢包尽可能早的被恢复，突发丢包以最大的概率被恢复，因此合理的选择ki是非常重要的，定理1确定各个层的码长。

证明：假设丢包事件满足参数为λ的泊松分布，那么丢包事件的分布函数为：

为了保证编码包对恢复丢失原始包是有效的，那么需要保证码长范围内应该有丢包事件发生，故应保证发送ki个原始包后，丢包事件vi发生的次数大于1的概率为ρ，那么该概率满足：

图1 多层反馈系统LT码编码示意图

定理2假设丢包事件vi满足泊松分布，在编码包数量m相同的情况下，码长为ki的码的解码失败率要比码长为k的码的解码失败率低，其中(k>ki)。

定理3假设丢包事件V={v1,v2,...,vs}都分别满足泊松分布，在编码包数量m相同的情况下，多层反馈系统LT码比单层反馈系统LT码的解码失败概率低。

多层码一共有s层，把所有层的编码包数量加起来，定理4得证。

2.3 多层反馈系统LT码的算法

接收端的解码算法与LT码完全相同，本节主要介绍发送端的编码算法和发送策略。在发送端，编码包穿插在原始包中间发送给接收端，也就是每发送k m个原始包就发送一个编码包。多层反馈系统LT码中生成一个编码包的算法步骤如下：

步骤1从{1,2,…,k}中依照度数分布（根据丢包率r调整后的）选择一个度数d。

步骤2按照降序将{m1,m2,…,ms}进行排序，如果其中两个元素值相同，则按照最后一次被选择的时间Ti排序。

步骤3从排好序的{m1,m2,…,ms}第一个元素开始，寻找第一个ki≥d并且mi>1的元素mi。

步骤4在mi对应的层中生成一个编码包，由于mi对应的层有多个编码块，先从第一个编码块中生成编码包，当第一个编码块对应的编码包都生成完之后，从第二个编码块生成编码包，以此类推。

步骤5mi=mi-1，Ti=当前时间。

3 仿真结果

下面通过仿真实验检验多层反馈系统LT码的性能，程序使用标准C语言实现，发送端和接收端分别运行在Linux主机上，发送端和接收端通过1Gb/s的网络连接起来，并通过Linux的TC来控制丢包率和RTT时延。仿真实验的部分参数如表1所示：

表1 仿真实验参数

3.1 随机丢包

在本次实验中，主要检测随机丢包情况下，多层反馈系统LT码的性能。从发送端发送4GB的文件到接收端，设置链路中单个丢包事件丢失的数据包占50%，连续丢2个数据包的丢包事件丢失的数据包占另外50%。实验发现在丢包率为0.05时，多层反馈系统LT码平均度数为3.7。而LT码在任何丢包率情况下的平均度数为13.5；在丢包率较小的情况下，系统LT码的平均度数远小于LT码，故反馈系统码能够有效降低编解码复杂度。

图2 不同丢包率的吞吐率

图3不同链路时延的吞吐率

图2 画出Maelstrom，多层反馈系统LT码以及单层反馈系统LT码在不同的丢包率情况下的吞吐率；图3则给出了三种方式在不同的链路时延情况下的吞吐率；可以看到LT码的吞吐率比Maelstrom高，这是因为Maelstrom采用固定的码率，不能有效地恢复所有的丢包，采用重传导致吞吐率下降。多层LT码比单层LT码吞吐率高，这是因为多层LT码的码长经过优化，每个编码包能够以很高的概率恢复出丢失的数据包。图4画出不同丢包率情况下的原始包到达接收端的平均时延；图5画出不同的链路时延的情况下原始包到达接收端的平均时延；可以看单层反馈系统LT码时延最大，因为丢失的原始包可能需要所有的其他原始包都已经收到后才能开始进行解码。

图4 不同丢包率的平均到达时延

图5 不同链路时延的平均到达时延

3.2 突发丢包

在本次实验中，主要检测突发丢包情况下，多层反馈系统LT码的性能。从发送端发送4GB的文件到接收端，设置链路中单个丢包事件丢失的数据包占30%，连续丢8个数据包的丢包事件丢失的数据包占20%，连续丢12个数据包的丢包事件丢失的数据包占50%。图6画出不同丢包率情况下的吞吐率；可以看出多层反馈系统LT码的吞吐率最高，并且随着丢包率的增加吞吐率下降的幅度不大。但是当丢包率越高时，单层和多层反馈系统LT码的吞吐率越接近，这是因为突发丢包率变高后，多层反馈系统LT码的平均码长变长，接近与单层反馈系统LT码的码长。

图6 不同丢包率的吞吐率

4 结语

基于前向纠错码的系统，吞吐率低和原始包平均到达时延长是视频点播、视频会议等系统中非常重要的问题。本文提出的多层反馈系统LT码可以快速地恢复出随机丢失的原始包，同时以很高的概率恢复出突发丢失的原始包。采用反馈系统码可以有效地降低发送端和接收端的编解码复杂度，提高系统地效率。仿真表明，多层反馈系统LT码在远距离高速网络中能够提高传输效率，降低数据包的平均到达时延。

[1]Balakrishnan M,Marian T,Birman K P,et al.Maelstrom:Transparent Error Correction for Communication Between Data Centers[J].IEEE Trans.on Networking,2011,19:617-629.

[2]Luby M.LT Codes[C].FOCS 2002,Vancouver:CA,2002:271-280.

[3]Shokrollahi A.Raptor Codes[J].Information Theory,2006,52:2551-2567.

[4]Hussain I,Xiao M,Rasmussen L.Error Floor Analysis of LT Codes over the Additive White Gaussian Noise Channel[J].Global Communications Conference,2011：1-5.

[5]Hussain I,Xiao M,Rasmussen L.Design of Spatially-Coupled Rateless Codes[J].Proceedings of IEEE 23rd International Symposium on Personal Indoor and Mobile Radio Communications,2012：1913-1918.

[6]Hussain I,Ming X,Rasmussen L K.Design of LT Codes with Equal and Unequal Erasure protection over binary erasure channels[J].IEEE Communications Letters,vol.17,no.2,2012,pp.261-264.

[7]朱宏杰.喷泉码编译码技术与应用研究[学位论文].北京,清华大学,2009,pp.33-35.

[8]Sorensen J H,Popovski P,Ostergaard J.Design and Analysis of LT Codes with Decreasing Ripple Size[J].Communications IEEE Trans⁃actions on,vol.60,no.11,2012,pp.3191-3197.

[9]Beimel A,Dolev S,Singer N.RT Oblivious Erasure Correcting[J].IEEE Trans.on Networking,2007,15:1321-1332.

[10]Hagedorn A,Agarwal S,Starobinski D,et al.Rateless Coding with Feedback[C].INFOCOM 2009,Rio de Janeiro:Brazil,2009:1791-1799.

[11]Bogino M,Cataldi P,Grangetto M,et al.Sliding-Window Digital Fountain Codes for Streaming of Multimedia Applications[C].SCAS 2007,New Orleans:USA,2007:3467-3470.

[12]Cataldi P,Grangetto M,Tillo T,et al.Sliding-window Raptor Codes for Efficient Scalable Wireless Video Broadcasting with UnequalLoss Protection[J].IEEE Transactions on Image Processing,2010,19:1491-1503.

[13]Talari A,Rahnavard N.LT-AF Codes:LT Codes with Alternating Feedback[C].Proceedings of IEEE International Symposium on Information Theory,2013：2646-2650.

[14]Talari A,Rahnavard N.Robust LT Codes with Alternating Feedback[J].Computer Communications,2014，49（1）：60-68.

[15]Sorensen J H,Popovski P,Ostergaard J.Feedback in LT Codes for Prioritized and Non-Prioritized Data[C].Proceedings of IEEE Vehicular Technology Conference,2012：1-5.

[16]Lei Zhang,Jian-xin Liao,Jing-yu Wang,Tong-hong Li,QiQi.Design of Improved Luby Transform Codes with Decreasing Ripple Size and Feedback.IET Communications,2014（8）：1409-1416.

[17]Lei Zhang,Jian-xin Liao,Jing-yu Wang,Qi Qi,Tong Xu,Sheng-wen Tian,Min-yan Liao.Diversified SLT Codes Based on Feedback for Communication Over Wireless Networks.in Global Information Infrastructure Symposium(GIIS),2013：1-6.

[18]Kim S,Lee S.Improved Intermediate Performance of Rateless Codes[C].International Conference on Advanced Communication Technology,2009：1682-1686.

[19]Talari A,Rahnavard N.Rateless Codes with Optimum Intermediate Performance[J].Global Communications Conference,2009：1-6.

[20]Talari A,Rahnavard N.On the Intermediate Symbol Recovery Rate of Rateless Codes[J].IEEE Transactions on Communications,2012，60（5）：1237-1242.

Abstract：

LT codes have been used for improving throughput of communication over high-speed long-distance networks.However,the latency be⁃tween the arrival of a packet at the sender and receiver and the complexity of computing is considerable.Thus,proposes the new fountain codes named multi-layered systematic LT codes with feedback.For loss rate is in low level,systematic LT codes with feedback decrease the average degree of encoded packets compared with LT codes.Several LT codes with different code length are running simultaneously.Singleton loss is recovered as quickly as possible by LT codes with smaller code length.Burst loss is recovered by LT codes with larger code length at the cost of increased recovery latency.Simulations result show that the proposed method using multi-layered LT codes with feedback have better performance in term of throughput and delivery latency compared with Maelstrom and single layered systematic LT codes with feedback.

Keywords：

Multi-Layered Codes;Latency;LT Codes;Feedback;High-Speed Long-Distance Networks

Multi-Layered Systematic LT Codes with Feedback for Communication over High-Speed Long-Distance Networks

ZHANG Xian-guo1，ZHANG Hua2
（1.The Fifteenth Institute of Electronics Science and Technology Company of China，Beijing 100083；2.Space Systems Department Communications Repair Office,Strategic Support Force,Beijing 100083）

2017-06-02

2017-06-18

1007-1423（2017）18-0003-06

10.3969/j.issn.1007-1423.2017.18.001

张先国（1981-），男，安徽合肥人，硕士，工程师，研究方向为网络信息安全、情报信息处理

张华（1972-），女，硕士，高级工程师，研究方向为网络安全