一種冗余流量消除算法

【摘要】本文提出了一種基于內(nèi)容的冗余流量消除算法（RFECB）。算法利用滑動窗口計算數(shù)據(jù)塊的邊界點，對二個邊界點的數(shù)據(jù)塊計算其指紋并進行指紋匹配。RFECB能夠提高冗余消除字節(jié)節(jié)省百分比，減少了冗余流量在網(wǎng)絡(luò)中的傳輸。

【關(guān)鍵詞】網(wǎng)絡(luò)流量；冗余消除；內(nèi)容分塊；協(xié)議無關(guān)

1.協(xié)議無關(guān)的冗余流量消除

協(xié)議無關(guān)的冗余流量抑制技術(shù)是Spring教授首次提出來的[1]，他有別于基于應(yīng)用層的協(xié)議相關(guān)的對象級別的冗余抑制技術(shù)，他的處理對象是單個的數(shù)據(jù)包，他能識別出數(shù)據(jù)包中已被傳輸?shù)闹貜?fù)字節(jié)。

協(xié)議無關(guān)的RTE通常包括以下3個步驟[2]：

冗余流量探測：在源端服務(wù)器對于特定方向的每一個數(shù)據(jù)包，DRE算法首先對數(shù)據(jù)包對每個數(shù)據(jù)包進行分塊，通過指紋算法計算每個數(shù)據(jù)塊的指紋，然后進行指紋匹配。

指紋匹配：將計算出的指紋和源端服務(wù)器的指紋庫中的歷史指紋進行比對，比對成功，對數(shù)據(jù)塊進行編碼；未比對成功，將指紋和數(shù)據(jù)包或數(shù)據(jù)塊分布存入指紋庫和數(shù)據(jù)包庫中，供下次指紋匹配使用。

匹配算法：選出代表指紋后，服務(wù)器端把每一個代表指紋都和指紋庫中的指紋做比對，如果有相同的指紋存在于指紋庫中，表示最近發(fā)送的數(shù)據(jù)包與當(dāng)前數(shù)據(jù)包有相同的數(shù)據(jù)片段，相同部分的長度至少為w字節(jié)。把相同部分逐字節(jié)的往左和往右拓展，最終相同部分的數(shù)據(jù)被從當(dāng)前數(shù)據(jù)包中去除，并以{相同數(shù)據(jù)起始位置，相同數(shù)據(jù)長度}2個屬性組成的短記號代替。

基于內(nèi)容的冗余流量消除算法利用滑動窗口對窗口內(nèi)的數(shù)據(jù)進行弱hash計算，當(dāng)hash值滿足預(yù)先設(shè)置條件時，便標(biāo)記一個分塊點，對二個分塊點間載荷定義的載荷分塊進行指紋計算。該算法提高分塊的穩(wěn)固性。

2.基于內(nèi)容的冗余消除算法

冗余流量探測是冗余消除算法的關(guān)鍵[3]，指紋算法中的參數(shù)W表示指紋算法的輸入字符串的字節(jié)數(shù)，w字節(jié)的字符串能產(chǎn)生一個指紋，如果數(shù)據(jù)包的載荷部分長度是L個字節(jié)，那么總共能產(chǎn)生L-W+1個指紋。由于受到指紋庫大小的限制[4]，要么在選取所有指紋的一個子集作為代表指紋；要么在分塊前就對選出代表的數(shù)據(jù)塊，再計算得到的指紋即為代表指紋。無論采用那種方法，塊選擇算法決定冗余數(shù)據(jù)塊的選取效率，以下對比不同的塊選擇算法的特點：

圖1 基于內(nèi)容的冗余流量消除算法

FIXED算法固定每P個字節(jié)從數(shù)據(jù)包中選擇一個數(shù)據(jù)塊，然后計算數(shù)據(jù)塊的指紋即為代表指紋，但是這種識別算法對數(shù)據(jù)包的微小變化不健壯；MODP算法中的每一個塊是數(shù)據(jù)包載荷的子字符串，然后使用哈希函數(shù)計算Rabin指紋計算數(shù)據(jù)塊的指紋F，選擇FmodP=0的數(shù)據(jù)塊做為代表指紋對應(yīng)的數(shù)據(jù)塊，該算法可能導(dǎo)致選出的數(shù)據(jù)塊過疏或過密分布，如字節(jié)連續(xù)相同的數(shù)據(jù)片段；MAXP算法選擇每P個字節(jié)中單個字節(jié)數(shù)值最大的字節(jié)為起點的w字節(jié)長的數(shù)據(jù)塊，具有穩(wěn)定抽樣率，但該算法傾向選擇第一個字節(jié)值較大的數(shù)據(jù)塊，當(dāng)該類型數(shù)據(jù)塊的冗余率較低時，算法將無法獲得冗余率高的數(shù)據(jù)塊。上述3種代表指紋選擇算法，其中MAXP和MODP算法對于傳輸內(nèi)容的細(xì)微修改有很好的健壯性，但是運算量較大，而FIXED算法與傳輸內(nèi)容無關(guān)，但是運算量小。

在本文提出的基于內(nèi)容的冗余消除算法中（如圖1所示），利用滑動窗口對窗口內(nèi)的數(shù)據(jù)進行弱hash計算，當(dāng)hash值滿足預(yù)先設(shè)置條件時，便標(biāo)記一個分塊點，對二個分塊點間載荷定義的載荷分塊進行指紋計算。這樣不僅減少了冗余消除的運算量，同時也保證了冗余消除的穩(wěn)固性。

3.實驗與仿真

3.1 實驗數(shù)據(jù)

為了準(zhǔn)確對比不同冗余消除算法的效率和內(nèi)存消耗，抓取了3種環(huán)境下的流量作為分析數(shù)據(jù)。抓取數(shù)據(jù)的總流量大小為39.12GB。數(shù)據(jù)A為多媒體發(fā)布，時長為1小時，共計12.32GB；數(shù)據(jù)B為學(xué)校接入網(wǎng)，時長為1小時，共計10.6GB；數(shù)據(jù)C為某實驗樓，時長為12小時，共計16.2GB。

3.2 冗余消除字節(jié)節(jié)省百分比

表1對比了三種算法對3種數(shù)據(jù)的字節(jié)節(jié)省率，字節(jié)節(jié)省率定義為冗余消除后傳輸字節(jié)數(shù)與冗余前的字節(jié)數(shù)的比值。從表1可以看出，數(shù)據(jù)A的冗余消除量遠遠大于其他2個數(shù)據(jù)，當(dāng)數(shù)據(jù)集中的冗余量較大時，RFECB算法的字節(jié)節(jié)省率和FIXED算法字節(jié)節(jié)省率最為接近。

表1 冗余消除算法穩(wěn)固性

4.結(jié)束語

針對當(dāng)前協(xié)議無關(guān)的冗余流量消除算法穩(wěn)固性不高的問題，提出了基于內(nèi)容的冗余流量消除算法，該算法利用弱哈希計算數(shù)據(jù)塊的邊界點。實驗結(jié)果表明在數(shù)據(jù)集冗余度高的時候，RFECB冗余消除算法明顯優(yōu)于FIXED算法和MAXP算法，即RFECB算法在不改變?nèi)哂嘞Ч幕A(chǔ)上提高了冗余消除的效率，有效的提高了傳輸效率。

參考文獻

[1]唐海娜，林小拉，韓春靜.基于移動指針的數(shù)據(jù)流冗余消除算法[J].通信學(xué)報，2012（2）.

[2]Anand A，Gupta A，Akella A，et al.Packet caches on routers：the implications of universal redundant traffic elimination[J].ACMSIGCOMM Computer Communication Review，2008，38（4）.

[3]SPRING N T，WETHERALL D.A protocol-independent technique for eliminating redundant network traffic[J].ACM SIGCOMM Computer Communication Review，2000， 30（4）：87-95.

[4]Anand A，Sekar V，Akella A.SmartRE：An architecture for coordinated network-wide redundancy elimination[C].New York，NY，USA.Proceedings of the ACM SIGCOMM conference on Data communication，2009：87-98.

作者簡介：鄭鴻（1987—），男，四川成都人，西南科技大學(xué)信息工程學(xué)院碩士研究生在讀，研究方向：計算機網(wǎng)絡(luò)。