潘有順 王開建

(1.茅臺學院公共基出部，貴州 遵義563000) (2.茅臺學院釀酒工程自動化系，貴州 遵義563000)

?

基于包性質的局域網(wǎng)冗余數(shù)據(jù)消除技術分析

潘有順1王開建2

(1.茅臺學院公共基出部，貴州 遵義563000) (2.茅臺學院釀酒工程自動化系，貴州 遵義563000)

局域網(wǎng)已經(jīng)在當前企事業(yè)單位信息化建設中扮演了一個重要的角色。但是在其通信過程中有大量的冗余數(shù)據(jù)存在，占用了帶寬，降低了效率。論文通過分析數(shù)據(jù)包的性質，針對局域網(wǎng)提出了一種基于包性質的冗余數(shù)據(jù)消除技術。它將獨立與共享緩存機制相結合，利用冗余閾值對低容量數(shù)據(jù)包進行過慮處理。

局域網(wǎng)；冗余數(shù)據(jù)；冗余消除；冗余數(shù)據(jù)消除技術

0 引言

在網(wǎng)絡通信過程中，學者們通過對通信數(shù)據(jù)的研究分析，發(fā)現(xiàn)用戶在使用網(wǎng)絡傳遞的信息中有大量的冗余數(shù)據(jù)存在。冗余數(shù)據(jù)不僅占用了網(wǎng)絡軟硬件資源，而且降低了整個網(wǎng)絡的通信性能。學者Breslau[1]等人提出網(wǎng)絡中 Web 對象數(shù)據(jù)被再次訪問的機率與其過去被訪問的次數(shù)成正比。如：代理緩存、Web 緩存、CDN、Ditto、CNF等。它們都屬于對象冗余消除技術范疇。其中Web 緩存是應用最廣泛的對象冗余消除技術。它采用訪問數(shù)據(jù)對象在時間方面的局部性原理，通常布置在離用戶終端較近區(qū)域，將用戶訪問過的數(shù)據(jù)對象進行緩存并對其設置一定的緩存期與替換算法。若有再次訪問這些對象的請求時，Web緩存會直接響應這一請求。雖然對象冗余消除技術在很大程度上減少了網(wǎng)絡中冗余數(shù)據(jù)無效傳輸，降低了網(wǎng)絡通信流量，實現(xiàn)了降低網(wǎng)絡訪問延遲，達到節(jié)省網(wǎng)絡資源的目的。但是它還是存在一定的局限性。首先它必須建立在特定網(wǎng)絡應用層協(xié)議基礎上，只能減少應用這些協(xié)議中的冗余數(shù)據(jù)；其次是冗余數(shù)據(jù)的粒度在KB之上，冗余精準度不高。包冗余消除技術主要工作在網(wǎng)絡的傳輸層或者網(wǎng)絡層。針對對象冗余消除技術不足，Spring 等學者在2000年首次提出包冗余消除技術[2]。它不依賴于網(wǎng)絡協(xié)議，更關注數(shù)據(jù)包中連續(xù)冗余字節(jié)流，冗余精度高，在一定程度上能夠消除網(wǎng)絡通信中字節(jié)級別的冗余數(shù)據(jù)，進一步提升了冗余消除能力。后來，Anand 等學者[3]改進了Spring 的冗余消除技術，使其應用到到互聯(lián)網(wǎng)中，冗余消除能力更強，在更大程度上減少網(wǎng)絡通信的冗余數(shù)據(jù)流量。Agarwal 等學者結合了Spring和Anand冗余消除技術的優(yōu)點，提出了基于靜態(tài)查找表的冗余數(shù)據(jù)消除技術[4]，更進一步提高了網(wǎng)絡冗余數(shù)據(jù)的消除水平。但是，包冗余消除技術使用共享緩存機制，無法區(qū)別冗余數(shù)據(jù)性質(如冗余數(shù)據(jù)用戶與數(shù)據(jù)功能)，冗余消除能力還有提升空間。

1 傳統(tǒng)包冗余消除技術

當前學者們的研究熱點主要關注包冗余消除技術?？偨Y學者們的研究成果，得出一個完整包冗余消除技術的工作過程中三個核心技術[5]，如圖1所示。

1.1 建立備份庫與指紋庫。服務器從自己的緩存中劃出兩個空間建立備份庫與指紋庫。備份庫用于將以往發(fā)送出的數(shù)據(jù)塊進行緩存。服務器首先將待發(fā)送數(shù)據(jù)包的數(shù)據(jù)載荷進行分塊處理，按一定算法計算出每一數(shù)據(jù)塊所對應的指紋，然后再按指紋采樣算法從這些指紋抽取出有代表性指紋緩存到指紋庫中，使得每一個數(shù)據(jù)塊都有一個代表性指紋與其對應。用戶端緩存中備份庫，它通過同步機制與服務器端備份庫內容保持一致。

1.2 指紋采樣。服務器對當前將要發(fā)送給用戶的數(shù)據(jù)包按第一步驟中的指紋計算算法與指紋采樣算法計算出數(shù)據(jù)塊的代表指紋。

1.3 指紋匹配。將當前數(shù)據(jù)塊的代表指紋與服務器端指紋庫中的代表指紋按一定匹配算法進行匹配比較。若匹配成功，也就是服務器端的備份庫中存在與相同當前數(shù)據(jù)塊，從而識別出這一冗余數(shù)據(jù)。服務器對這一冗余數(shù)據(jù)塊編碼為簡易冗余標識，最后將帶有冗余標識載荷的簡易數(shù)據(jù)包并發(fā)送給用戶端。若匹配不成功，則把當前代表指紋和與其對應的數(shù)據(jù)塊依次緩存到服務器端備份庫與指紋庫中，并發(fā)送。

圖1 包冗余消除技術工作過程圖

有大量冗余數(shù)據(jù)存在主要原因是在通信過程中，傳遞的數(shù)據(jù)包中有若干相同的數(shù)據(jù)塊[6]。這些冗余數(shù)據(jù)塊就其本身來說有如下兩個重要的性質：一是數(shù)據(jù)包用戶性質。二是數(shù)據(jù)包功能性質。

因此，論文在此基礎上，針對應用廣泛局域網(wǎng)提出了一種基于包性質的冗余數(shù)據(jù)消除技術。通過實驗，證明了該技術能夠減少了CPU的占用時間，提高了網(wǎng)絡數(shù)據(jù)冗余消除效率。

2 數(shù)據(jù)包性質分析與建模

2.1 數(shù)據(jù)包性質分析

在局域網(wǎng)里，服務器與用戶通信的數(shù)據(jù)包中除了滿載荷外，還有近50%的數(shù)據(jù)包僅有很少數(shù)據(jù)，甚至有的沒有數(shù)據(jù)。比如：TCP 確認信息、ICPM控制信息及SSL和TLS安全協(xié)議等。這部分數(shù)據(jù)包中數(shù)據(jù)部分占整個數(shù)據(jù)包比例非常小，冗余數(shù)據(jù)也很少，包的大小在20字節(jié)至100字節(jié)不等。如果在服務器端對其進行同樣的冗余消除過程，這樣不但占用了服務器CPU的處理時間，而且冗余數(shù)據(jù)貢獻量也很低，總體收益率很低。在論文中，對于這部分冗余收益率低的低容量數(shù)據(jù)包采取直接發(fā)送方式，無需進行冗余處理處理。

2.2 基于數(shù)據(jù)性質冗余消除技術的系統(tǒng)模型

在上述數(shù)據(jù)包性質分析的基礎上，針對應用廣泛的局域網(wǎng)，論文提出了一種基于包性質的冗余數(shù)據(jù)消除技術，其結構如圖2所示：

圖2 基于包性質的冗余數(shù)據(jù)消除技術結構圖

服務器端緩存中分別建立三類空間——公共指紋庫、用戶指紋庫和編碼庫，并根據(jù)冗余收益值動態(tài)調整每個用戶指紋庫與公共指紋庫的空間大小。服務器端ROM程序存儲器中存放一個判斷程序。公共指紋庫中存放多個用戶共同使用的數(shù)據(jù)塊指紋，用戶指紋庫中存放僅供此用戶單獨使用的數(shù)據(jù)塊指紋。編碼庫用于存放數(shù)據(jù)塊在用戶數(shù)據(jù)塊庫中的位置編碼。每個用戶端緩存中分別建立數(shù)據(jù)塊庫。這些數(shù)據(jù)塊庫存放了用戶請求訪問過的以數(shù)據(jù)塊為單位的信息。用戶端定期將數(shù)據(jù)塊庫中數(shù)據(jù)塊位置信息同步給服務器端的編碼庫。

2.3 指紋庫中指紋位置動態(tài)調整

權值函數(shù)F(X)可以對服務器端指紋庫中的代表指紋匹配情況進行一次綜合評估。其評估原則要主要考慮兩個因素——最近24小時匹配次數(shù)LSUM和累計匹配次數(shù)SUM。該權值被稱作冗余收益值R(Z) ，其用來表征該代表指紋將來被再次匹配的機率。冗余收益值R(Z)是我們進行指紋位置動態(tài)調整的唯一依據(jù)。在理論上，冗余收益值R(Z)的模型如下：

R(Z)=F(LSUM/SUM)

(1)

其中，Z表示指紋庫中的一個代表指紋。 從表達式(1)中，冗余收益值R(Z)最終結果取決于一個合適的權值函數(shù)F(X)。因此，選取正確權值函數(shù)F(X)顯得十分重要。其實，考慮了指紋的匹配過程與LRFU算法的基本思想是一致的，所以采用的權值函數(shù)F(X)模型如下：

F(X)=(1/P)tX(P=5)

(2)

2.4 包性質的冗余數(shù)據(jù)消除技術工作過程

論文針對局域網(wǎng)通信提出的一種基于包性質的冗余數(shù)據(jù)消除技術。此技術主要包括如下四個步驟，如圖3所示。

圖3 基于包性質的冗余數(shù)據(jù)消除技術工作過程流程圖

1)包容量判斷。服務器端的判斷程序比對將要發(fā)送給用戶端的數(shù)據(jù)包容量與判斷程序中冗余閾值R(論文結合局域網(wǎng)的通信流量分析，將R設置為640字節(jié)。管理員也可以根據(jù)需要進行調整。)。如果大于R，則進行下一步驟2)。反之，說明此數(shù)據(jù)包為冗余數(shù)據(jù)量低的數(shù)據(jù)包，服務器直接發(fā)送，無需進行冗余消除處理。

2)指紋采樣。服務器端根據(jù)數(shù)據(jù)包的目的地址來識別對應的用戶端。然后對這些數(shù)據(jù)包的載荷部分分塊，并按一定的指紋計算算法和指紋采樣算法計算出代表性指紋。論文比較關注指紋采樣命中率，所以采用Winnowing算法采樣數(shù)據(jù)塊的代表指紋。

3)冗余識別。按一定指紋匹配算法，將步驟2)得到的用戶數(shù)據(jù)塊代表指紋分別與服務器端公共指紋庫和該用戶指紋庫中的指紋進行比較匹配。如果匹配成功，則識別出這一冗余數(shù)據(jù)。服務器調用編碼庫對此數(shù)據(jù)塊進行簡易地冗余編碼，最后將帶有冗余編碼數(shù)據(jù)包發(fā)送給用戶端。同時根據(jù)冗余收益值R(Z)調整該指紋在用戶指紋庫中的排序。反之，則是將當前代表指紋存入服務器端的用戶指紋庫或者公共指紋庫中。論文中采用的是塊匹配算法。相對于最大匹配算法，它大大減少了在服務器端和用戶端的緩存空間的占用。

4)冗余解碼。當用戶端收到帶有簡易冗余編碼的數(shù)據(jù)包時，對其中冗余標識進行解碼，獲得冗余數(shù)據(jù)塊的位置信息，并根據(jù)此位置信息從自己的數(shù)據(jù)塊庫中還原出對應的數(shù)據(jù)塊。完成了一次網(wǎng)絡通信，最終達到網(wǎng)絡通信過程包冗余消除的目的。

3 實驗證明

實驗環(huán)境選擇了貴州省某高校的萬兆主干鏈路互連網(wǎng)絡，實驗設備為三臺DELL xeonE5-2600V3資源服務器與近1200用戶終端節(jié)點。

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

為了準確對比不同冗余消除技術在服務器端CPU占用時間和字節(jié)節(jié)約率兩個方面差異， 我們抓取了某一天中三個時間段的用戶對服務器訪問的數(shù)據(jù)流量作為分析依據(jù)，如表1所示。

表1 實驗數(shù)據(jù)統(tǒng)計

對于收集到的實驗數(shù)據(jù)，我們經(jīng)過分析研究發(fā)現(xiàn)在校園網(wǎng)中的不同類型服務數(shù)據(jù)產(chǎn)生的冗余貢獻率(冗余貢獻率=此服務類型的冗余數(shù)據(jù)量/所有服務類型的冗余數(shù)據(jù)總量)是不一樣的。數(shù)據(jù)總量中近75%為下行數(shù)據(jù)量，其冗余消除貢獻率較高，大約為85%。 在網(wǎng)絡提供的應用服務中，數(shù)據(jù)量所占比例最大的是HTTP服務，其冗余消除貢獻率也達到76%。具體分布情況如表2所示。

表2 冗余數(shù)據(jù)分布

3.2 CPU占用時間

在局域網(wǎng)中冗余數(shù)據(jù)處理過程中，起決定性作用的是服務器端。其CPU執(zhí)行某一冗余數(shù)據(jù)消除技術進行通信過程的數(shù)據(jù)冗余處理。這一處理過程中的指紋計算、指紋采樣、指紋編碼、查找指紋和插入指紋等方面操作都要占用CPU處理時間。論文提出的基于包性質的冗余數(shù)據(jù)消除技術與冗余除技術分別運行于本實驗環(huán)境，得出如下結果，如表3所示。

表3 三種冗余消除技術的CPU占用時間

從表3可以看出，論文提出的基于包性質的冗余數(shù)據(jù)消除技術在CPU占用時間方面表現(xiàn)出的優(yōu)勢是比較明顯的。就其主要原因是論文的技術對于容量小于640B以下的數(shù)據(jù)包不進行冗余處理。

結語

目前冗余數(shù)據(jù)在網(wǎng)絡中特別是在局域網(wǎng)中大量存在，嚴重影響了網(wǎng)絡的通信效率。論文在研究當前協(xié)議無關的冗余數(shù)據(jù)消除技術的基礎上，提出了一種基于包性質的冗余數(shù)據(jù)消除技術。該技術充分考慮局域網(wǎng)通信過程中數(shù)據(jù)包的用戶性質與容量性質，設置了多用戶的獨立與共享緩存機制，建立了數(shù)據(jù)包容量的過濾閾值。這樣不僅節(jié)約了緩存空間，而且還降低了網(wǎng)絡設備處理能耗。實驗結果表明，相對于現(xiàn)有的冗余消除技術，論文技術的冗余消除率比較好，改善了局域網(wǎng)通信效率，節(jié)約了帶寬資源，在局域網(wǎng)中發(fā)揮了很大價值。

[1]Breslau L, Cao P, et al. Web caching and Zipf-like distributions: Evidence and implications. In: Proc. of the IEEE INFOCOM.1999.

[2]Spring N, Wetherall D. A protocal-independent technique for eliminating redundant network traffic. ACM SIGCOMM Computer Communication Review, 2000.

[3]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 communicatio,2009:87-98.

[4]Aggarwal B,Akella A,Anand A,et al.EndRE:An end-system redundancy elimination service for enterprises[C].San Jos:USENIX Symposium on Networked Systems Design and Implementation,2010.

[5]AGARWALB， AKELLA A， ANAND A， et al． EndRE: an endsystem redundancy elimination service for enterprises[C].//NSDI 2010: Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation． Berkeley: USENIX Association， 2010: 419-432.

[6]唐海娜,林小拉,韓春靜. 基于移動指針的數(shù)據(jù)流冗余消除算法[J].通信學報,2012(2)：7-14.

(責任編輯：王德紅)

The Technique to Eliminate Redundant Data in LANs

Pan Youshun1Wang Kaijian2

(1.Department of pubic Fourdation,Moutai University, Zunyi 563000,Guizhou, China) (2.Department of Brewing Engineering Automation,Moutai University,Zunyi563000,Guizhou,China)

LAN has played an important role in the information construction of current enterprises. However there are always a lot of redundant data in the communication process occupying the bandwidth, resulting in efficiency reduction. A packet nature-based technique to eliminate redundant data in LANs is proposed in the paper by analyzing the nature of data packets. It could independently combine with the buffer sharing mechanism to filter low-capacity packets by means of redundancy threshold.

LAN， redundant data， redundancy elimination，redundant data eliminating technique

2016-09-10

1.潘有順(1977.02～)，男，江蘇淮安人，茅臺學院公共基礎部高級工程師，碩士。研究方向：計算機網(wǎng)絡技術。 2.王開建(1955.08～)，女，天津人，茅臺學院釀酒工程自動化系教授。研究方向：微電子技術、無線傳感技術。

TP393.01

A

1673-9507(2016)06-0121-03