可靠組播中基于ＦＥＣ的隨機(jī)化差錯(cuò)恢復(fù)算法

摘 要：隨機(jī)化差錯(cuò)恢復(fù)算法通過重傳機(jī)制來進(jìn)行消息恢復(fù)，本文提出了RRMF算法，用向前糾錯(cuò)和重傳技術(shù)相結(jié)合的方式為網(wǎng)絡(luò)提供可靠組播。FEC通過增加冗余信息的方式提高可靠性，當(dāng)接收到的信息不足以恢復(fù)原始數(shù)據(jù)時(shí)，使用ARQ進(jìn)行差錯(cuò)恢復(fù)。減少了重傳發(fā)生的次數(shù)，從而降低了差錯(cuò)反饋信息和重傳數(shù)據(jù)占用的帶寬，適合在大規(guī)模交互中使用。

關(guān)鍵詞：可靠組播；隨機(jī)化協(xié)議；自動(dòng)重傳；向前糾錯(cuò)

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)06-0318-03

近年來，可靠組播的應(yīng)用非常廣泛，在可靠的媒體流發(fā)布、經(jīng)衛(wèi)星信道的信息發(fā)布、股票行情的發(fā)布等，都有這一技術(shù)的應(yīng)用領(lǐng)域。為滿足大規(guī)模網(wǎng)絡(luò)的交互式應(yīng)用，建立有效的、可擴(kuò)展的可靠組播協(xié)議是研究的一個(gè)熱點(diǎn)。由于對(duì)可靠性的要求不同，很難設(shè)計(jì)出一個(gè)可以滿足所有應(yīng)用要求的協(xié)議模型，不同協(xié)議采用不同的差錯(cuò)控制機(jī)制。

1 可靠組播中的差錯(cuò)控制技術(shù)

1.1 ARQ（自動(dòng)重復(fù)請(qǐng)求）

ARQ［1］是一種按需重傳的機(jī)制，發(fā)送者通過接收者的反饋信息得知有報(bào)文在傳輸中丟失，就重傳該報(bào)文。ARQ機(jī)制分為基于發(fā)送者的肯定確認(rèn)(ACK)方式和基于接收者的否定確認(rèn)(NACK)方式。在ACK方式中，接收者成功接收到數(shù)據(jù)就向發(fā)送者發(fā)送ACK信息，如果發(fā)送者在規(guī)定的時(shí)間內(nèi)收到了所有組成員的ACK信息，表示傳輸成功；否則認(rèn)為該報(bào)文在某條鏈路上丟失，將重傳該報(bào)文。在NACK方式中，接收者根據(jù)數(shù)據(jù)報(bào)文中序列號(hào)的間隙確定報(bào)文的丟失，并向發(fā)送者發(fā)送NACK報(bào)文，發(fā)送者重傳該報(bào)文。在可靠組播中，NACK方式是最為常用的，它比ACK方式具有更好的可擴(kuò)展性，這是因?yàn)榻邮照咧辉趫?bào)文丟失時(shí)才會(huì)產(chǎn)生NACK報(bào)文，并且差錯(cuò)發(fā)現(xiàn)的任務(wù)分?jǐn)偨o每個(gè)接收者，減輕了發(fā)送者的負(fù)擔(dān)。

很多組播協(xié)議基于ARQ協(xié)議，如廣泛應(yīng)用的基于接收者的NACK方式的可擴(kuò)展可靠組播協(xié)議SRM［2］，它采用延時(shí)應(yīng)答機(jī)制阻止重復(fù)的請(qǐng)求重傳和應(yīng)答消息。RMTP［3］是基于發(fā)送者的ACK方式并通過局部恢復(fù)機(jī)制來避免反饋風(fēng)暴的樹型結(jié)構(gòu)協(xié)議。但是隨著組成員數(shù)的增多，丟失也會(huì)增多，這些協(xié)議都存在擴(kuò)展性的問題。

1.2 FEC（前向糾錯(cuò)）

FEC［4，5］是一種編碼方法， 通過在傳輸中引入冗余信息來提高可靠性。在計(jì)算機(jī)通信中主要有兩種差錯(cuò)：錯(cuò)誤和丟失。錯(cuò)誤的數(shù)據(jù)是因?yàn)槟承┍忍財(cái)?shù)發(fā)生畸變，丟失是某些數(shù)據(jù)包沒有收到。底層協(xié)議通常要考慮兩種情況，如鏈路層FEC使用差錯(cuò)校正碼對(duì)既有丟包又有誤碼時(shí)依然能重建正確的數(shù)據(jù)，通常由硬件實(shí)現(xiàn)，采用漢明碼、RS編碼以及卷積碼等。而傳輸差錯(cuò)反映到通信協(xié)議高層只是數(shù)據(jù)包的丟失，因此工作在傳輸層或者應(yīng)用層的FEC可通過丟失校正碼和已知包數(shù)來處理丟失情況，通常由軟件實(shí)現(xiàn)。本文研究的協(xié)議中的差錯(cuò)就是指數(shù)據(jù)包的丟失。

純的FEC技術(shù)不必重傳數(shù)據(jù)，但是編碼解碼增加了計(jì)算的開銷和復(fù)雜性；用處理能力及帶寬來換取可靠性和較小的恢復(fù)延遲。在丟包率較高的情況下，性能明顯下降，整體性能取決于丟失情況最嚴(yán)重的接收者，不能保證數(shù)據(jù)傳輸?shù)耐耆煽浚虼撕苌偈褂谩?/p>

1.3 HEC（混合差錯(cuò)控制）

HEC［6］是基于前面兩種方式的優(yōu)點(diǎn)，把二者結(jié)合起來使用。通過FEC機(jī)制避免反饋風(fēng)暴，不能恢復(fù)的報(bào)文通過ARQ機(jī)制來完成，這種方式在近年來得到較廣泛的應(yīng)用。實(shí)現(xiàn)HEC的方法主要有兩種［5］：

(1)分層法。它是在基于ARQ可靠的組播下層加一個(gè)新層來負(fù)責(zé)FEC，它對(duì)ARQ而言是透明的，獨(dú)立的FEC層可以被多個(gè)應(yīng)用使用。但是對(duì)爆發(fā)性的丟包敏感，性能不穩(wěn)定。

(2)集成法。該方法注重效率，發(fā)送者不發(fā)送或者只傳送一部分校驗(yàn)包，當(dāng)接收者收到的包不足以恢復(fù)原始數(shù)據(jù)時(shí)才請(qǐng)求更多的冗余包。但是以延遲為代價(jià)，適合文件傳送?？煽拷M播數(shù)據(jù)分布協(xié)議RMDP［6］采用這種方法。

2 隨機(jī)化差錯(cuò)恢復(fù)算法

隨機(jī)化可靠組播協(xié)議RRMP［7］（Randomized Reliable Multicast Protocol）的差錯(cuò)恢復(fù)結(jié)構(gòu)建立在傳輸層。它結(jié)合Bimodal Multicast［8］協(xié)議中的隨機(jī)化差錯(cuò)恢復(fù)和樹協(xié)議中的分層結(jié)構(gòu)的差錯(cuò)恢復(fù)算法，采用一對(duì)多的組播方式，通過局部恢復(fù)提高擴(kuò)展性；而且只要檢測(cè)到消息丟失就請(qǐng)求重傳，把恢復(fù)消息的責(zé)任分?jǐn)偨o每個(gè)成員，減少反饋風(fēng)暴的發(fā)生。該協(xié)議采用基于閑談（Gossip）的隨機(jī)化理論，具有很好的擴(kuò)展性。

根據(jù)各個(gè)成員的地理位置不同分成層次結(jié)構(gòu)。發(fā)送者所在的域沒有父域，每個(gè)接收者包含所在區(qū)域成員的信息和它的直接上游區(qū)域即父域成員的信息。消息丟失可以通過序列號(hào)的間隙或交換會(huì)話(Session)消息發(fā)現(xiàn)，同時(shí)進(jìn)行局部恢復(fù)和全局恢復(fù)。接收者p收到一個(gè)消息就會(huì)檢測(cè)是否有消息丟失，如果消息m丟失了，在本區(qū)域隨機(jī)選擇成員請(qǐng)求重傳，并設(shè)置定時(shí)器。超時(shí)沒有得到應(yīng)答，隨機(jī)選擇另外的成員請(qǐng)求重傳。如果局部區(qū)域所有成員都沒有消息m，則以概率P向遠(yuǎn)程成員r請(qǐng)求，進(jìn)行全局恢復(fù)。r如果沒有消息m，不像局部恢復(fù)只是忽略請(qǐng)求，但要記錄p正等待消息m，一旦得到消息m就發(fā)給p，p在局部區(qū)域組播消息m。

3 FEC理論及基于FEC的隨機(jī)化差錯(cuò)恢復(fù)算法

3.1 數(shù)據(jù)包層FEC編碼的軟件實(shí)現(xiàn)

FEC的主要思想是：k個(gè)數(shù)據(jù)包在發(fā)送端經(jīng)過冗余編碼后生成ｎ個(gè)數(shù)據(jù)包，將n個(gè)包發(fā)給接收端；接收端收到至少任意k個(gè)數(shù)據(jù)包就可以通過譯碼使原始數(shù)據(jù)還原，n-k為冗余校驗(yàn)信息的數(shù)量。編碼/譯碼過程如圖1所示。

圖1 FEC編碼/譯碼過程

在計(jì)算機(jī)通信中一個(gè)數(shù)據(jù)包經(jīng)常包括成百上千個(gè)比特，如果數(shù)據(jù)包不加處理地作為輸入進(jìn)行FEC運(yùn)算，將會(huì)過多地耗費(fèi)存儲(chǔ)器和處理器資源，影響編碼效率。因此可以把大數(shù)據(jù)包分成多個(gè)小數(shù)據(jù)塊。根據(jù)協(xié)議規(guī)范［9］的描述，編碼數(shù)據(jù)塊的大小分為三類：小塊FEC編碼、大塊FEC編碼和可擴(kuò)展的FEC編碼。小塊編碼適合對(duì)較小的數(shù)據(jù)塊編碼（要求k＜256），因?yàn)樵趯?shí)際應(yīng)用中，太大的k值會(huì)嚴(yán)重影響編碼/譯碼的速度。后兩種編碼屬于Digital Fountain［10］的專利，其冗余數(shù)據(jù)個(gè)數(shù)要多于k個(gè)才能恢復(fù)原始數(shù)據(jù)，接收開銷比小塊編碼大些。Rizzo［11］ 的實(shí)驗(yàn)已經(jīng)表明用軟件實(shí)現(xiàn)編碼的速度可以達(dá)到Mbps，現(xiàn)有機(jī)器的配置足夠容忍這樣的開銷。

3.2 基于FEC的隨機(jī)化差錯(cuò)恢復(fù)算法

由于可靠組播中重要的問題之一就是減少ARQ機(jī)制的反饋信息，這是影響可擴(kuò)展性的主要問題。RRMP使用隨機(jī)化理論后擴(kuò)展性大大提高，但是每丟失一個(gè)數(shù)據(jù)包都要請(qǐng)求重傳，而基于FEC的隨機(jī)化差錯(cuò)恢復(fù)算法RRMF引入了FEC機(jī)制能夠容忍一定數(shù)量的數(shù)據(jù)丟失。RRMF的差錯(cuò)恢復(fù)算法分為兩個(gè)階段：

(1)局部恢復(fù)。在發(fā)送端，發(fā)送k個(gè)數(shù)據(jù)包和n－k個(gè)校驗(yàn)包，接著發(fā)送下一個(gè)FEC塊，每個(gè)FEC塊后面包含結(jié)束標(biāo)志，用于接收方檢查丟包的情況。 

在接收端，

①收到FEC結(jié)束標(biāo)志或者根據(jù)塊序號(hào)判斷哪個(gè)FEC塊結(jié)束標(biāo)志丟失了，檢查該FEC塊中接收到的包的個(gè)數(shù)m。

·k≤m≤n，如果數(shù)據(jù)包的個(gè)數(shù)等于k，不必譯碼，否則進(jìn)行譯碼。

·m＜k，在本區(qū)域隨機(jī)選擇成員q并發(fā)送請(qǐng)求NACK(g，c，s)。其中，g表示所屬塊，c表示請(qǐng)求個(gè)數(shù)，s表示請(qǐng)求序列號(hào)隊(duì)列。只需要能恢復(fù)s中的任意c個(gè)包即可。譯碼開銷取決于實(shí)際丟失的原始數(shù)據(jù)塊l≤min(k，n-k)。若超時(shí)則隨機(jī)選擇另外的成員恢復(fù)。若收到的恢復(fù)數(shù)據(jù)包個(gè)數(shù)少于c個(gè)，則重復(fù)此過程直到滿足要求。

②收到其它成員的請(qǐng)求，如果有該數(shù)據(jù)包，就給予應(yīng)答，否則忽略。

③收到了請(qǐng)求的應(yīng)答數(shù)據(jù)包，如果是全局恢復(fù)的應(yīng)答，在局部區(qū)域組播。

(2)全局恢復(fù)。由于網(wǎng)絡(luò)擁塞可能導(dǎo)致有些局部區(qū)域都沒有得到某些報(bào)文，需要進(jìn)行全局恢復(fù)。在局部區(qū)域恢復(fù)數(shù)據(jù)超時(shí)后仍未成功，則認(rèn)為該區(qū)域所有成員都丟失了數(shù)據(jù)。在父域中隨機(jī)選擇一個(gè)成員以概率P發(fā)送請(qǐng)求，設(shè)置定時(shí)器，超時(shí)則隨機(jī)選擇另外一個(gè)成員進(jìn)行恢復(fù)。收到請(qǐng)求的成員如果沒有該數(shù)據(jù)包，進(jìn)入本地局部恢復(fù)階段，得到數(shù)據(jù)包后立即給予應(yīng)答。

4 性能分析

假設(shè)每個(gè)數(shù)據(jù)包丟失相互獨(dú)立，設(shè)p為網(wǎng)絡(luò)包丟失概率，在沒有采用FEC編碼的RRMP算法中，發(fā)送者發(fā)送某數(shù)據(jù)包M′次后，才能使某接收者正確得到，則M′的概率分布服從幾何分布：

使用FEC的冗余開銷為(n-k)/k，冗余越大越可靠，但是會(huì)降低效率。圖3說明了當(dāng)n=128、32、16，冗余為8時(shí)的平均傳輸次數(shù)，設(shè)丟失率為5%?？梢钥闯霎?dāng)結(jié)點(diǎn)數(shù)很小時(shí)的時(shí)候，EFEC[M]≈n/k，額外的開銷使性能比沒有引入FEC算法差；然而節(jié)點(diǎn)數(shù)很大的時(shí)候，引入FEC算法后性能提高，這時(shí)候冗余開銷可以被抵消，因?yàn)橥粋€(gè)校驗(yàn)包可以被不同的接收者用來恢復(fù)不同的丟包。根據(jù)圖中曲線描述進(jìn)行n和k值的正確選擇，n和k太大或者太小都不適合，可以取n=32，k=24。

圖4列出了n=32，k=24時(shí)在丟失率不同的時(shí)候一個(gè)數(shù)據(jù)包的平均傳輸次數(shù)。丟失率越小，曲線越平穩(wěn);隨著網(wǎng)絡(luò)丟失率增大，性能開始下降。曲線也說明隨著節(jié)點(diǎn)數(shù)的增多，平均傳輸次數(shù)是按著對(duì)數(shù)增長的。通常丟失率超過25%將嚴(yán)重影響正常的通信，這里不考慮。因此在網(wǎng)絡(luò)環(huán)境不是很惡劣的情況下，采用改進(jìn)后的算法RRMF可以降低每個(gè)數(shù)據(jù)包的平均傳輸次數(shù)， 減小重傳的時(shí)間， 從而提高應(yīng)用的吞吐量。

圖3 丟失率為5%時(shí)noFEC和FEC比較圖4 n=32 k=24時(shí)不同丟失率的FEC比較

4 結(jié)束語

RRMF算法結(jié)合了重傳和向前糾錯(cuò)技術(shù)，實(shí)現(xiàn)組播差錯(cuò)恢復(fù)機(jī)制，不需要底層拓?fù)浣Y(jié)構(gòu)的支持，擴(kuò)展性好。FEC的引入，在一定條件下可以降低重傳的數(shù)據(jù)量，提高系統(tǒng)的吞吐量。只要選擇合適的參數(shù)，基于FEC編碼的隨機(jī)化可靠組播協(xié)議能夠改善RRMP協(xié)議中可能出現(xiàn)過多的重傳帶來反饋風(fēng)暴以及對(duì)重復(fù)包的處理，既節(jié)省帶寬又減少恢復(fù)丟失數(shù)據(jù)包的時(shí)間。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。