【摘要】本文提出了一種基于內(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ò)。