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

潘有順 王開建

(1.茅臺(tái)學(xué)院公共基出部，貴州 遵義563000) (2.茅臺(tái)學(xué)院釀酒工程自動(dòng)化系，貴州 遵義563000)

?

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

潘有順1王開建2

(1.茅臺(tái)學(xué)院公共基出部，貴州 遵義563000) (2.茅臺(tái)學(xué)院釀酒工程自動(dòng)化系，貴州 遵義563000)

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

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

0 引言

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

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

當(dāng)前學(xué)者們的研究熱點(diǎn)主要關(guān)注包冗余消除技術(shù)?？偨Y(jié)學(xué)者們的研究成果，得出一個(gè)完整包冗余消除技術(shù)的工作過程中三個(gè)核心技術(shù)[5]，如圖1所示。

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

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

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

圖1 包冗余消除技術(shù)工作過程圖

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

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

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

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

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

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

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

圖2 基于包性質(zhì)的冗余數(shù)據(jù)消除技術(shù)結(jié)構(gòu)圖

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

2.3 指紋庫中指紋位置動(dòng)態(tài)調(diào)整

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

R(Z)=F(LSUM/SUM)

(1)

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

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

(2)

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

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

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

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

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

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

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

3 實(shí)驗(yàn)證明

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

3.1 實(shí)驗(yàn)數(shù)據(jù)分析

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

表1 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)

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

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

3.2 CPU占用時(shí)間

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

表3 三種冗余消除技術(shù)的CPU占用時(shí)間

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

結(jié)語

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

[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]唐海娜,林小拉,韓春靜. 基于移動(dòng)指針的數(shù)據(jù)流冗余消除算法[J].通信學(xué)報(bào),2012(2)：7-14.

(責(zé)任編輯：王德紅)

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～)，男，江蘇淮安人，茅臺(tái)學(xué)院公共基礎(chǔ)部高級(jí)工程師，碩士。研究方向：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)。 2.王開建(1955.08～)，女，天津人，茅臺(tái)學(xué)院釀酒工程自動(dòng)化系教授。研究方向：微電子技術(shù)、無線傳感技術(shù)。

TP393.01

A

1673-9507(2016)06-0121-03