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

張先國(guó)，張華

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

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

張先國(guó)1，張華2

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

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

多層碼；時(shí)延；LT碼；反饋；遠(yuǎn)距離高速網(wǎng)絡(luò)

0 引言

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

文獻(xiàn)[4]的編碼器記錄編碼過(guò)程中每個(gè)原碼包參與生成編碼包的次數(shù)，在每次生成編碼符號(hào)時(shí)，選擇度數(shù)最小的編碼包參與編碼。文獻(xiàn)[5-6]將規(guī)則變量節(jié)點(diǎn)度LT碼應(yīng)用于刪除信道中。但是當(dāng)碼長(zhǎng)變長(zhǎng)，雖然規(guī)則變量節(jié)點(diǎn)度LT碼能夠顯著地降低碼的差錯(cuò)平臺(tái)，但是每次生成編碼包都需要對(duì)該表進(jìn)行查找和更新，增加了編碼器的復(fù)雜度，且每次生成編碼包的計(jì)算復(fù)雜度也變高了。

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

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

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

1 LT碼和SLT碼

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

其中，d=1,2,???,k為編碼包的度數(shù)；詳見(jiàn)文獻(xiàn)[2]。LT碼在整個(gè)傳輸過(guò)程中，度數(shù)分布保持不變。

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

其中，d=1,2,???,k為魯棒孤子分布中編碼包的度數(shù)，d'為調(diào)整后編碼包的度數(shù)，k為碼長(zhǎng)，n為已經(jīng)收到的原始包的個(gè)數(shù)；詳見(jiàn)文獻(xiàn)[10]。

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

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

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

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

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

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

①按照公式4的度數(shù)分布隨機(jī)生成度數(shù)d；

②從ki個(gè)原始包中隨機(jī)選擇d個(gè)原始包；

③d個(gè)原始包按位異或生成編碼包。

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

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

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

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

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

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

多層碼一共有s層，把所有層的編碼包數(shù)量加起來(lái)，定理4得證。

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

接收端的解碼算法與LT碼完全相同，本節(jié)主要介紹發(fā)送端的編碼算法和發(fā)送策略。在發(fā)送端，編碼包穿插在原始包中間發(fā)送給接收端，也就是每發(fā)送k m個(gè)原始包就發(fā)送一個(gè)編碼包。多層反饋系統(tǒng)LT碼中生成一個(gè)編碼包的算法步驟如下：

步驟1從{1,2,…,k}中依照度數(shù)分布（根據(jù)丟包率r調(diào)整后的）選擇一個(gè)度數(shù)d。

步驟2按照降序?qū)m1,m2,…,ms}進(jìn)行排序，如果其中兩個(gè)元素值相同，則按照最后一次被選擇的時(shí)間Ti排序。

步驟3從排好序的{m1,m2,…,ms}第一個(gè)元素開(kāi)始，尋找第一個(gè)ki≥d并且mi>1的元素mi。

步驟4在mi對(duì)應(yīng)的層中生成一個(gè)編碼包，由于mi對(duì)應(yīng)的層有多個(gè)編碼塊，先從第一個(gè)編碼塊中生成編碼包，當(dāng)?shù)谝粋€(gè)編碼塊對(duì)應(yīng)的編碼包都生成完之后，從第二個(gè)編碼塊生成編碼包，以此類推。

步驟5mi=mi-1，Ti=當(dāng)前時(shí)間。

3 仿真結(jié)果

下面通過(guò)仿真實(shí)驗(yàn)檢驗(yàn)多層反饋系統(tǒng)LT碼的性能，程序使用標(biāo)準(zhǔn)C語(yǔ)言實(shí)現(xiàn)，發(fā)送端和接收端分別運(yùn)行在Linux主機(jī)上，發(fā)送端和接收端通過(guò)1Gb/s的網(wǎng)絡(luò)連接起來(lái)，并通過(guò)Linux的TC來(lái)控制丟包率和RTT時(shí)延。仿真實(shí)驗(yàn)的部分參數(shù)如表1所示：

表1 仿真實(shí)驗(yàn)參數(shù)

3.1 隨機(jī)丟包

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

圖2 不同丟包率的吞吐率

圖3不同鏈路時(shí)延的吞吐率

圖2 畫(huà)出Maelstrom，多層反饋系統(tǒng)LT碼以及單層反饋系統(tǒng)LT碼在不同的丟包率情況下的吞吐率；圖3則給出了三種方式在不同的鏈路時(shí)延情況下的吞吐率；可以看到LT碼的吞吐率比Maelstrom高，這是因?yàn)镸aelstrom采用固定的碼率，不能有效地恢復(fù)所有的丟包，采用重傳導(dǎo)致吞吐率下降。多層LT碼比單層LT碼吞吐率高，這是因?yàn)槎鄬覮T碼的碼長(zhǎng)經(jīng)過(guò)優(yōu)化，每個(gè)編碼包能夠以很高的概率恢復(fù)出丟失的數(shù)據(jù)包。圖4畫(huà)出不同丟包率情況下的原始包到達(dá)接收端的平均時(shí)延；圖5畫(huà)出不同的鏈路時(shí)延的情況下原始包到達(dá)接收端的平均時(shí)延；可以看單層反饋系統(tǒng)LT碼時(shí)延最大，因?yàn)閬G失的原始包可能需要所有的其他原始包都已經(jīng)收到后才能開(kāi)始進(jìn)行解碼。

圖4 不同丟包率的平均到達(dá)時(shí)延

圖5 不同鏈路時(shí)延的平均到達(dá)時(shí)延

3.2 突發(fā)丟包

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

圖6 不同丟包率的吞吐率

4 結(jié)語(yǔ)

基于前向糾錯(cuò)碼的系統(tǒng)，吞吐率低和原始包平均到達(dá)時(shí)延長(zhǎng)是視頻點(diǎn)播、視頻會(huì)議等系統(tǒng)中非常重要的問(wèn)題。本文提出的多層反饋系統(tǒng)LT碼可以快速地恢復(fù)出隨機(jī)丟失的原始包，同時(shí)以很高的概率恢復(fù)出突發(fā)丟失的原始包。采用反饋系統(tǒng)碼可以有效地降低發(fā)送端和接收端的編解碼復(fù)雜度，提高系統(tǒng)地效率。仿真表明，多層反饋系統(tǒng)LT碼在遠(yuǎn)距離高速網(wǎng)絡(luò)中能夠提高傳輸效率，降低數(shù)據(jù)包的平均到達(dá)時(shí)延。

[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]朱宏杰.噴泉碼編譯碼技術(shù)與應(yīng)用研究[學(xué)位論文].北京,清華大學(xué),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

張先國(guó)（1981-），男，安徽合肥人，碩士，工程師，研究方向?yàn)榫W(wǎng)絡(luò)信息安全、情報(bào)信息處理

張華（1972-），女，碩士，高級(jí)工程師，研究方向?yàn)榫W(wǎng)絡(luò)安全