本站小編為你精心準備了資源評估論文：網絡流量能源消耗評估參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

作者：脫立恒倪宏劉學單位：中國科學院研究生院中國科學院聲學研究所國家網絡新媒體工程技術研究中心

冗余流量消除

RTE通常包括以下4個步驟。

（1）冗余數據探測。加速器使用數據塊選擇算法選出數據包中的數據塊，通過指紋算法計算每個數據塊的指紋，然后進行指紋匹配。

（2）指紋匹配。將計算出的指紋與加速器緩存中已經存儲的歷史指紋進行比對，比對成功，對數據片段編碼；未比對成功，將指紋、數據塊或數據包存入加速器緩存中，供下次指紋匹配使用。

（3）編碼。使用短的元數據編碼冗余數據塊，如：<O,P>，其中O表示冗余塊在緩存中的偏移位置，P表示該數據塊在數據包中的起始位置。

（4）解碼。接收端加速器根據發送端插入的元數據，對元數據進行解碼。

在RTE算法過程中，塊選擇算法決定冗余數據塊的選取效率，以下對比不同塊選擇算法的特點：FIXED算法固定每p（p為目標抽樣周期）個字節從數據包中選取一個數據塊，對于數據包內容的微小變化不健壯，通常不被使用；MODP算法使用哈希函數（rabinhash）計算Rabin指紋（RabinFingerprint，RF）計算連續w字節長數據塊的指紋f，選擇f=0modp的數據塊作為檢測片段，該算法可能導致選出的數據塊過疏或過密分布，如字節連續相同的數據片段；MAXP算法選擇每p個字節中，單個字節數值最大的字節為起點的w字節長的數據塊，具有穩定抽樣率，但該算法傾向選擇第一字節值較大的數據塊，當該類型數據塊的冗余率較低時，算法將無法獲得冗余率高的數據塊；SAMPLEBYTE算法使用一個256項查找表，256項索引分別與字節的256個值對應，每一項的查找結果r∈{0,1}，1代表該索引對應的字節值被選中為標識，0代表該索引對應的字節值不被選中，查找表中固定k個字節值被選為標識。

SAMPLEBYTE算法分析數據包時，逐個字節掃描，如果掃描到的字節對應字節值的查找結果為1，則以該字節所在位置為起點，選出數據塊，該字節稱為該塊的標識。計算選中數據塊的指紋，按照RTE的處理步驟繼續處理。一旦選中某個數據塊，則以標識所在位置為起點，跳過p/2個字節重新開始SAMPLEBYTE算法。

SAMPLEBYTE使用離線算法統計訓練數據，得到固定k=8個標識，分別為0、32、48、101、105、115、116、255。文獻[2]指出，在p=32時，系統可獲得吞吐量和字節節省間更好的平衡，之后的研究[7-8]多以該抽樣率作為理論抽樣目標。如果網絡數據包中所有字節值均勻分布，則SAMPLEBYTE對數據塊抽樣率為8/256，但網絡數據包中字節值非均勻分布，導致SAMPLEBYTE過抽樣或低抽樣。

基于動態查找表的網絡冗余流量消除算法

1動態查找表更新算法

由以上分析得出，抽樣率與標識個數以及標識在數據包中出現概率有關，RTE效率與選擇哪些標識有關，為了動態跟蹤抽樣率，同時選擇合適的標識，需要實時跟蹤網絡數據變化。為了獲得精確的抽樣率，實時統計網絡數據包中不同字節值的出現概率，以便調整查找表Llpt中標識的個數；為了獲得高的冗余數據檢測效率，實時統計以不同字節值為標識的數據段的冗余頻率，以數據塊冗余出現頻率高的字節值為基礎，預測下階段哪些標識對于提取冗余數據塊更加有效。式(1)表示，選中的所有標識的抽樣率小于等于1/p，式(2)表示，在式(1)限制條件下，選擇使得不同字節值開頭的數據段的冗余概率和最大的字節值作為查找表的標識。冗余概率和最大的標識，選擇出的數據塊的冗余率越高，RTE效率越高。該選擇標識的過程轉化為背包問題，本文使用貪心算法（greedy）求解該問題。按照不同字節值的冗余概率降序排列，選擇使得總的抽樣率接近1/p的字節值作為標識。

2以不同字節值開頭的數據塊的修正冗余頻率計算方法

DYNATABLE統計不同字節值在數據包中出現概率，方法是，在使用RF算法計算指紋的過程中，實時記錄不同字節值A出現的次數MA，用該次數比該段時間數據總長度，即為出現概率。

以不同字節值開頭的數據塊的冗余頻率，統計上比較難，如果按每字節滑動統計所有數據塊，可以獲得以不同字節值開頭的數據塊的冗余頻率，但在進行RTE時，每次選中數據塊后，需要跳過S長數據片段，以防止數據塊的過抽樣，此時，按每字節滑動統計的數據塊冗余頻率將不再準確。所以需要對按每字節滑動統計的冗余數據塊的冗余頻率統計方法進行修正。假設在按字節滑動統計的過程中，以字節A開頭的前后2個冗余數據塊的距離為L，后一個數據塊能否被選出，與距離前一個以A開頭的數據塊的距離有關，前后2個數據塊的距離L<S時，如果前一個數據塊被選中，在跳過S的過程中，后一個數據塊將被跳過，該重復數據塊處理流程如圖1所示。

實際選擇中，前一個數據塊被選中也存在一定概率，其與更前面的數據塊的選擇有關，但針對后一個數據塊，其距離前一個數據塊的距離L越大，意味著離更前面的數據塊距離越大，被選中的概率越大；前后2個以A開頭的數據塊距離L≥S時，后一數據塊肯定能被選中，即后一個數據塊對以A開頭的數據塊冗余頻率貢獻為（此函數記為contribute）：累加各個冗余頻率貢獻得到以不同字節值開頭的數據塊的修正冗余頻率CA。利用布隆濾波器（BloomFilter，BF)能快速判斷某個元素是否屬于集合特點，在統計以不同字節值A開頭的數據塊的修正冗余頻率時，將指紋放入布隆濾波器實現的集合GA中。

3DYNATABLE算法流程

綜上，DYNATABLE算法如下：輸入參數：tpkt為數據包指針，w為數據段長度，N為數據總長度，且N>w，i為臨時變量

4布隆濾波器設計

BF的參數設計對統計的效率至關重要。BF由一個長度m的二進制向量和q個隨機映射函數組成，它將輸入元素通過映射，映射到二進制向量的q個比特位上，并將比特位置1，檢測某輸入元素是否已經存在的過程是計算該元素的映射，如果q個映射比特位全部置1，說明元素已經存在，否則，元素不存在。BF可以保證所有已經插入過的元素肯定能被檢測出，但存在一定的誤識別率p(FalsePositiveRate,FPR)。設存入元素個數為n，則p與m、q、n關系為:為保證計算高效性，選q=2，BF存儲的最大元素個數為6n=10。為使FPR控制在p≤1%，由公式(4)得出，二進制向量長度m應取20Mb。

5256-LSA緩存替換算法

SAMPLEBYTE中使用FIFO（FirstInFirstOut)的緩存替換算法，Halepovic等提出使用LSA（LeastSavingswithAging）緩存替換策略。由于DYNABYTE算法實時動態更新查找表，當查找表中標識發生變化時，已被替換出的標識對應的數據塊將不可能再命中，LSA算法無法迅速替換出該部分數據塊。DYNABYTE將緩存拆分成256份，每份緩存對應一個字節值，不同數據塊存入其標識對應的緩存中，當查找表發生變化時，被替換出的標識的緩存將不被再次訪問。

實驗與仿真

本節討論DYNATABLE的實驗及仿真結果。實驗設備為DELLR710服務器，配置為16核CPU、4G內存、500G硬盤，操作系統為CentOS5.5。雖然DYNATABLE為RTE提供動態的查找表，對查找表更新與塊選擇算法是相互獨立的，DYNATABLE的查找表更新算法和塊選擇算法分別采用2個獨立進程完成。DYNATABLE查找表更新進程更新查找表后，將其更新到共享內存區，同時通知塊選擇算法進程實時更新查找表。

1實驗數據

為了準確對比不同塊選擇算法的效率，抓取表1中4種情況的流量作為分析數據。抓取數據總流量大小為130.6GB。

2緩存替換算法

實驗中分別使用LSA和256-LSA這2種緩存替換策略，對4段跟蹤數據進行分析，結果如表2所示。由表2可見，256-LSA緩存替換方法比LSA替換方法的字節節省率R提高約20%。以下實驗中，均使用256-LSA緩存替換策略。

3抽樣率

用DT代表DYNATABLE算法，FX代表FIXED算法，MX代表MAXP算法，MD代表MODP算法，SB代表SAMPLEBYTE算法，圖2顯示了5種算法的實際抽樣率變化情況，其中FIXED和MAXP的抽樣率相對比較穩定，MODP抽樣率過高，SAMPLEBYTE的抽樣率較低。DYNATABLE算法能夠動態調整抽樣率，使抽樣率在目標抽樣率附近波動。

4字節節省

表3和圖3對比了5種算法的字節節省率，字節節省率定義為冗余消除后傳輸字節數與冗余消除前的字節數的比值。DYNATABLE算法帶來了更高的字節節省率，對于A、B、D，DYNATABLE比MAXP平均提高16.1%，對于C，DYNATABLE比SAMPLEBYTE提高38.8%。

5運行時間

表4同時統計了5種算法處理每Gb數據的CPU運行時間。DYNATABLE的查找表更新算法和塊選擇算法分別獨立運行，表中DYNATABLE算法的CPU時間乘以2表示取查找表更新算法的CPU運行時間和塊選擇算法的CPU運行時間中的較大值，再對CPU運行時間加倍。CPU時間消耗包括，計算指紋、緩存查找和插入等操作開銷。塊選擇算法的計算量主要集中在對緩存的查找和插入操作；DYNATABLE的查找表更新算法，計算量集中在數據塊的查找或插入BF集合，通過實驗，DYNATABLE的查找表更新算法和塊選擇算法的運行時間基本相當。DYNATABLE增加計算量，但并未減小處理數據的吞吐量。

結論

本文提出了一種基于動態查找表的RTE算法（DYNATABLE），該算法實時統計網絡數據中以不同標識開頭的數據塊冗余率，選取冗余率高的標識，動態更新查找表，以選取更多的冗余數據塊，在網絡數據傳輸時，獲得高的字節節省；在統計以不同標識開頭的數據塊冗余率時，使用布隆濾波器存儲已出現的數據塊的指紋，縮短算法運行時間；DYNATABLE算法中使用256-LSA緩存替換算法更新緩存，提高緩存命中率。通過仿真實驗，DYNATABLE在不減少數據處理吞吐量的條件下，有效提高網絡數據傳輸中的字節節省，提高廣域網傳輸效率。