一種冗余流量消除算法

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

【關鍵詞】網絡流量；冗余消除；內容分塊；協議無關

1.協議無關的冗余流量消除

協議無關的冗余流量抑制技術是Spring教授首次提出來的[1]，他有別于基于應用層的協議相關的對象級別的冗余抑制技術，他的處理對象是單個的數據包，他能識別出數據包中已被傳輸的重復字節。

協議無關的RTE通常包括以下3個步驟[2]：

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

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

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

基于內容的冗余流量消除算法利用滑動窗口對窗口內的數據進行弱hash計算，當hash值滿足預先設置條件時，便標記一個分塊點，對二個分塊點間載荷定義的載荷分塊進行指紋計算。該算法提高分塊的穩固性。

2.基于內容的冗余消除算法

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

圖1 基于內容的冗余流量消除算法

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

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

3.實驗與仿真

3.1 實驗數據

為了準確對比不同冗余消除算法的效率和內存消耗，抓取了3種環境下的流量作為分析數據。抓取數據的總流量大小為39.12GB。數據A為多媒體發布，時長為1小時，共計12.32GB；數據B為學校接入網，時長為1小時，共計10.6GB；數據C為某實驗樓，時長為12小時，共計16.2GB。

3.2 冗余消除字節節省百分比

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

表1 冗余消除算法穩固性

4.結束語

針對當前協議無關的冗余流量消除算法穩固性不高的問題，提出了基于內容的冗余流量消除算法，該算法利用弱哈希計算數據塊的邊界點。實驗結果表明在數據集冗余度高的時候，RFECB冗余消除算法明顯優于FIXED算法和MAXP算法，即RFECB算法在不改變冗余消除效果的基礎上提高了冗余消除的效率，有效的提高了傳輸效率。

參考文獻

[1]唐海娜，林小拉，韓春靜.基于移動指針的數據流冗余消除算法[J].通信學報，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—），男，四川成都人，西南科技大學信息工程學院碩士研究生在讀，研究方向：計算機網絡。