資源評估論文：網(wǎng)絡流量能源消耗評估范文

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

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

冗余流量消除

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

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

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

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

（4）解碼。接收端加速器根據(jù)發(fā)送端插入的元數(shù)據(jù)，對元數(shù)據(jù)進行解碼。

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

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

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

基于動態(tài)查找表的網(wǎng)絡冗余流量消除算法

1動態(tài)查找表更新算法

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

2以不同字節(jié)值開頭的數(shù)據(jù)塊的修正冗余頻率計算方法

DYNATABLE統(tǒng)計不同字節(jié)值在數(shù)據(jù)包中出現(xiàn)概率，方法是，在使用RF算法計算指紋的過程中，實時記錄不同字節(jié)值A出現(xiàn)的次數(shù)MA，用該次數(shù)比該段時間數(shù)據(jù)總長度，即為出現(xiàn)概率。

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

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

3DYNATABLE算法流程

綜上，DYNATABLE算法如下：輸入?yún)?shù)：tpkt為數(shù)據(jù)包指針，w為數(shù)據(jù)段長度，N為數(shù)據(jù)總長度，且N>w，i為臨時變量

4布隆濾波器設計

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

5256-LSA緩存替換算法

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

實驗與仿真

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

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

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

2緩存替換算法

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

3抽樣率

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

4字節(jié)節(jié)省

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

5運行時間

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

結論

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