張先國，張華

（1.中國電子科技集團公司第十五研究所，北京100083；2.戰(zhàn)略支援部隊航天系統(tǒng)部通信修理所，北京100083）

適用于遠距離高速網絡的多層反饋系統(tǒng)LT碼

張先國1，張華2

（1.中國電子科技集團公司第十五研究所，北京100083；2.戰(zhàn)略支援部隊航天系統(tǒng)部通信修理所，北京100083）

針對LT碼在遠距離高速網絡傳輸應用，研究發(fā)現LT碼在提高通信效率的同時增加發(fā)送端和接收端的計算量，研究還發(fā)現LT碼可顯著增加數據包的平均到達時延。針對該問題，研究并提出一種多層反饋系統(tǒng)LT碼。依據遠距離高速網絡中丟包率較小的特征，使用反饋系統(tǒng)碼可以減少編解碼的計算量；依據單個丟包均勻分布在較小碼長內，突發(fā)丟包分布在較大碼長內的特征，使用多層碼分別覆蓋單個丟包和突發(fā)丟包。仿真結果表明，多層反饋系統(tǒng)LT碼在提高通信效率的同時，不僅減少發(fā)送端和接收端的編解碼計算量，而且還減少數據包的平均到達時延。

多層碼；時延；LT碼；反饋；遠距離高速網絡

0 引言

因為光纖老化，錯誤的路由配置以及交換競爭等因素，在遠距離高速網絡的數據傳輸過程中存在一定的丟包。由于遠距離高速網絡中的往返時延（RTT）較長，使得自動重傳請求（ARQ）機制效率低下[1]。LT碼[2]和Raptor碼[3]作為一種無速率碼，非常適用于RTT較大并且存在丟包的網絡。Raptor碼是以LT碼為核心的多層級聯(lián)碼?；贚T碼和Raptor碼的數據傳輸不需要接收端發(fā)送反饋信息。

文獻[4]的編碼器記錄編碼過程中每個原碼包參與生成編碼包的次數，在每次生成編碼符號時，選擇度數最小的編碼包參與編碼。文獻[5-6]將規(guī)則變量節(jié)點度LT碼應用于刪除信道中。但是當碼長變長，雖然規(guī)則變量節(jié)點度LT碼能夠顯著地降低碼的差錯平臺，但是每次生成編碼包都需要對該表進行查找和更新，增加了編碼器的復雜度，且每次生成編碼包的計算復雜度也變高了。

文獻[7]研究了LT碼在碼長固定情況下期望可譯集大小ERS（Expected Ripple Size）函數的優(yōu)化問題和增強置信傳播譯碼的算法。文獻[8]研究了可譯集遞減的度分布生成算法。

但是文獻[9]通過引入反饋信息來優(yōu)化后續(xù)編碼包的度數，最大化每個編碼包在接收端譯碼成功的概率，沒有立即成功譯碼的編碼包被直接丟棄，故其成功譯碼所需的編碼包數量較大，只適用于接收端內存非常小的情況；文獻[10]通過引入反饋信息來動態(tài)調整LT碼的度數分布，降低成功譯碼所需的編碼包數量；文獻[11-12]引入滑動窗口機制來擴大碼長，降低成功譯碼時冗余編碼包的比例，提高傳輸效率；文獻[13-15]在多次反饋轉移LT碼的基礎上提出一種基于多次反饋的LT-AF碼（Alternating Feedback Codes）。LT-AF碼在降低反饋的次數的基礎上根據編碼符號度數波動變化重新修正轉移魯棒孤子分布；文獻[16-17]在研究可譯集遞減的度分布生成算法基礎上提出了可譯集遞減的反饋無速率碼；然而原始包從發(fā)送端發(fā)出到接收端成功譯碼的時延較長，不適合那些對時效性要求較高的應用，例如視頻點播和視頻會議。

文獻[18-19]把輸入符號分成不同的區(qū)間，針對不同的區(qū)間使用不同的度分布，針對性的優(yōu)化無速率碼的ISRR。文獻[20]提出了基于丟包率的系統(tǒng)碼實現方法——RCSS（Rateless Coded Symbol Sorting）算法。算法預先假設一個丟包率，然后根據丟包率計算出需要生成的編碼符號數量。文獻[1]通過引入多層的前向糾錯碼，減少數據包的平均到達時延，但是其采用固定碼率，故不能適應鏈路丟包率變化的場景。本文提出一種多層反饋系統(tǒng)LT碼及其具體實現方案。由于遠距離高速網絡中丟包率較小，故直接傳輸原始包效率更高，然后由基于反饋信息生成的編碼包以較小的冗余比例可靠的恢復出少量丟失的原始包；引入多層碼保證丟失的原始包在盡可能小的碼長內被成功譯碼，首先通過反饋信息分別統(tǒng)計出隨機丟包和突發(fā)丟包的丟包率，然后針對不同的丟包類型，采用分層的LT碼分別進行處理，每一層采用獨立的編碼空間生成編碼包用于恢復該層丟失的原始包，保證得到較為滿意的平均時延，最后給出仿真結果和分析。

1 LT碼和SLT碼

LT碼編碼過程中的魯棒孤子分布為[2]：

其中，d=1,2,???,k為編碼包的度數；詳見文獻[2]。LT碼在整個傳輸過程中，度數分布保持不變。

SLT碼基于收到的反饋信息動態(tài)的調整度數分布，從而提高效率，其度數分布為[10]：

其中，d=1,2,???,k為魯棒孤子分布中編碼包的度數，d'為調整后編碼包的度數，k為碼長，n為已經收到的原始包的個數；詳見文獻[10]。

2 多層反饋系統(tǒng)LT碼

2.1 單層反饋系統(tǒng)LT碼

由于通過遠距離高速網絡進行數據傳輸時，只有少量的原始包丟失，故提出單層反饋系統(tǒng)LT碼以提高傳輸效率?；驹砣缦拢菏紫裙浪沔溌返膩G包率，然后根據公式（3）：

計算出要成功譯碼所有丟失的原始包所需編碼包的數量m，其中常數c>0，為指定參數，δ為指定的譯碼失敗概率；最后將編碼包和原始包一起發(fā)送到接收端。單層反饋系統(tǒng)LT碼用(k ,r,m )表示，其度數分布為：

2.2 多層反饋系統(tǒng)LT碼

（ki,ri,mi）碼的一個編碼包的生成流程如下：

①按照公式4的度數分布隨機生成度數d；

②從ki個原始包中隨機選擇d個原始包；

③d個原始包按位異或生成編碼包。

為了保證單個丟包盡可能早的被恢復，突發(fā)丟包以最大的概率被恢復，因此合理的選擇ki是非常重要的，定理1確定各個層的碼長。

證明：假設丟包事件滿足參數為λ的泊松分布，那么丟包事件的分布函數為：

為了保證編碼包對恢復丟失原始包是有效的，那么需要保證碼長范圍內應該有丟包事件發(fā)生，故應保證發(fā)送ki個原始包后，丟包事件vi發(fā)生的次數大于1的概率為ρ，那么該概率滿足：

圖1 多層反饋系統(tǒng)LT碼編碼示意圖

定理2假設丟包事件vi滿足泊松分布，在編碼包數量m相同的情況下，碼長為ki的碼的解碼失敗率要比碼長為k的碼的解碼失敗率低，其中(k>ki)。

定理3假設丟包事件V={v1,v2,...,vs}都分別滿足泊松分布，在編碼包數量m相同的情況下，多層反饋系統(tǒng)LT碼比單層反饋系統(tǒng)LT碼的解碼失敗概率低。

多層碼一共有s層，把所有層的編碼包數量加起來，定理4得證。

2.3 多層反饋系統(tǒng)LT碼的算法

接收端的解碼算法與LT碼完全相同，本節(jié)主要介紹發(fā)送端的編碼算法和發(fā)送策略。在發(fā)送端，編碼包穿插在原始包中間發(fā)送給接收端，也就是每發(fā)送k m個原始包就發(fā)送一個編碼包。多層反饋系統(tǒng)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 仿真結果

下面通過仿真實驗檢驗多層反饋系統(tǒng)LT碼的性能，程序使用標準C語言實現，發(fā)送端和接收端分別運行在Linux主機上，發(fā)送端和接收端通過1Gb/s的網絡連接起來，并通過Linux的TC來控制丟包率和RTT時延。仿真實驗的部分參數如表1所示：

表1 仿真實驗參數

3.1 隨機丟包

在本次實驗中，主要檢測隨機丟包情況下，多層反饋系統(tǒng)LT碼的性能。從發(fā)送端發(fā)送4GB的文件到接收端，設置鏈路中單個丟包事件丟失的數據包占50%，連續(xù)丟2個數據包的丟包事件丟失的數據包占另外50%。實驗發(fā)現在丟包率為0.05時，多層反饋系統(tǒng)LT碼平均度數為3.7。而LT碼在任何丟包率情況下的平均度數為13.5；在丟包率較小的情況下，系統(tǒng)LT碼的平均度數遠小于LT碼，故反饋系統(tǒng)碼能夠有效降低編解碼復雜度。

圖2 不同丟包率的吞吐率

圖3不同鏈路時延的吞吐率

圖2 畫出Maelstrom，多層反饋系統(tǒng)LT碼以及單層反饋系統(tǒng)LT碼在不同的丟包率情況下的吞吐率；圖3則給出了三種方式在不同的鏈路時延情況下的吞吐率；可以看到LT碼的吞吐率比Maelstrom高，這是因為Maelstrom采用固定的碼率，不能有效地恢復所有的丟包，采用重傳導致吞吐率下降。多層LT碼比單層LT碼吞吐率高，這是因為多層LT碼的碼長經過優(yōu)化，每個編碼包能夠以很高的概率恢復出丟失的數據包。圖4畫出不同丟包率情況下的原始包到達接收端的平均時延；圖5畫出不同的鏈路時延的情況下原始包到達接收端的平均時延；可以看單層反饋系統(tǒng)LT碼時延最大，因為丟失的原始包可能需要所有的其他原始包都已經收到后才能開始進行解碼。

圖4 不同丟包率的平均到達時延

圖5 不同鏈路時延的平均到達時延

3.2 突發(fā)丟包

在本次實驗中，主要檢測突發(fā)丟包情況下，多層反饋系統(tǒng)LT碼的性能。從發(fā)送端發(fā)送4GB的文件到接收端，設置鏈路中單個丟包事件丟失的數據包占30%，連續(xù)丟8個數據包的丟包事件丟失的數據包占20%，連續(xù)丟12個數據包的丟包事件丟失的數據包占50%。圖6畫出不同丟包率情況下的吞吐率；可以看出多層反饋系統(tǒng)LT碼的吞吐率最高，并且隨著丟包率的增加吞吐率下降的幅度不大。但是當丟包率越高時，單層和多層反饋系統(tǒng)LT碼的吞吐率越接近，這是因為突發(fā)丟包率變高后，多層反饋系統(tǒng)LT碼的平均碼長變長，接近與單層反饋系統(tǒng)LT碼的碼長。

圖6 不同丟包率的吞吐率

4 結語

基于前向糾錯碼的系統(tǒng)，吞吐率低和原始包平均到達時延長是視頻點播、視頻會議等系統(tǒng)中非常重要的問題。本文提出的多層反饋系統(tǒng)LT碼可以快速地恢復出隨機丟失的原始包，同時以很高的概率恢復出突發(fā)丟失的原始包。采用反饋系統(tǒng)碼可以有效地降低發(fā)送端和接收端的編解碼復雜度，提高系統(tǒng)地效率。仿真表明，多層反饋系統(tǒng)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-），女，碩士，高級工程師，研究方向為網絡安全