端到端冗余流量消除技術(shù)的指紋選擇算法研究

陳靜怡， 馮 偉， 吳 杰

(復(fù)旦大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)系，上海200433)

0 引 言

由于互聯(lián)網(wǎng)上大量相同或相似的內(nèi)容被網(wǎng)絡(luò)邊緣的用戶多次請求，造成了數(shù)據(jù)在網(wǎng)絡(luò)上的重復(fù)傳輸，導(dǎo)致了大量的冗余流量，不但消耗網(wǎng)絡(luò)帶寬，而且降低了互聯(lián)網(wǎng)的效率。隨著存儲設(shè)備容量不斷擴(kuò)大，運(yùn)算設(shè)備性能不斷提高、價(jià)格不斷降低，在互聯(lián)網(wǎng)引入網(wǎng)內(nèi)存儲設(shè)施，使網(wǎng)絡(luò)具有記憶功能已經(jīng)成為可能，具有存儲功能的互聯(lián)網(wǎng)能夠?qū)崿F(xiàn)網(wǎng)絡(luò)冗余流量消除技術(shù)，它記錄網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)，識別被重復(fù)傳輸?shù)臄?shù)據(jù)，從而消除冗余傳輸，起到減少網(wǎng)絡(luò)流量、提高網(wǎng)絡(luò)性能的作用。代理緩存[1]、CDN[2]、CNF[3]等都屬于網(wǎng)絡(luò)冗余流量消除技術(shù)的范疇。其中，與協(xié)議無關(guān)的網(wǎng)絡(luò)冗余流量消除技術(shù)運(yùn)行在網(wǎng)絡(luò)層或傳輸層，存儲設(shè)備中的緩存對象為數(shù)據(jù)包。最早的協(xié)議無關(guān)網(wǎng)絡(luò)冗余流量消除技術(shù)由Spring等人于2000年提出，運(yùn)行于一對路由器之間，后常被用于消除ISP或局域網(wǎng)與商業(yè)網(wǎng)之間的連接鏈路或者數(shù)據(jù)中心與其備份數(shù)據(jù)庫之間的連接鏈路上的重復(fù)字節(jié)傳輸[4]。2008年，Anand等人提出了把Spring等人的方法整合到整個(gè)互聯(lián)網(wǎng)的所有路由器中[5]，這樣，協(xié)議無關(guān)的網(wǎng)絡(luò)冗余流量消除技術(shù)將被作為一項(xiàng)基礎(chǔ)服務(wù)而運(yùn)用到所有的點(diǎn)到點(diǎn)(即路由器到路由器)數(shù)據(jù)包傳輸中。此后，Anand等人又對其中的指紋運(yùn)算方法和解碼位置做了優(yōu)化[6-7]，使得運(yùn)用于全網(wǎng)的協(xié)議無關(guān)網(wǎng)絡(luò)冗余流量消除算法有更快的速度，而且更適合于全網(wǎng)范圍運(yùn)用。2010年，Anand等人發(fā)表了關(guān)于端到端冗余流量消除的論文[8]，這篇論文基于這樣一個(gè)理論：75%擁有相同片段的兩個(gè)數(shù)據(jù)包具有相同的源地址和目的地址，即來自同一對網(wǎng)絡(luò)上的端點(diǎn)。他們選擇 SAMPLEBYTE指紋選擇算法和最大匹配算法來實(shí)現(xiàn)端到端冗余流量消除，但是這樣會大量占用服務(wù)器端的內(nèi)存空間。在本篇論文中，論述了一種新的指紋選擇算法：貪婪指紋選擇算法，配合以塊匹配算法，能夠減少服務(wù)器端和用戶終端的內(nèi)存消耗，并且冗余消除的有效性與Anand等人的算法相近。

1 端到端冗余流量消除技術(shù)的目標(biāo)

端到端冗余流量消除技術(shù)與傳統(tǒng)的網(wǎng)絡(luò)層冗余流量消除技術(shù)相比，把一部分的計(jì)算量轉(zhuǎn)移到用戶終端，因此在設(shè)計(jì)算法時(shí)，要著重考慮用戶終端的性能限制，盡量減少用戶終端的計(jì)算量和空間占用。因此，端到端冗余流量消除技術(shù)的目標(biāo)為：

(1)在用戶終端處能夠方便的解碼數(shù)據(jù)包：用戶終端可能是智能手機(jī)、筆記本電腦、PAD等設(shè)備，這些設(shè)備受限于電池容量和計(jì)算能力。因此在設(shè)計(jì)算法時(shí)應(yīng)盡量把計(jì)算集中在高性能的服務(wù)器端，而使得用戶終端能夠方便的解碼被編碼的數(shù)據(jù)包。盡量少的占用用戶終端的計(jì)算資源。

(2)在服務(wù)器端能快速的編碼：服務(wù)器端需要把檢測出擁有重復(fù)傳輸片段的數(shù)據(jù)包經(jīng)行編碼：去除曾經(jīng)傳輸過的數(shù)據(jù)包片段，并以小的結(jié)構(gòu)體代替，用以告訴用戶終端從曾經(jīng)發(fā)送過的哪個(gè)數(shù)據(jù)包中恢復(fù)被去除的數(shù)據(jù)包片段。服務(wù)器端需要同時(shí)編碼和多個(gè)用戶終端之間傳輸?shù)臄?shù)據(jù)包，因此編碼算法需要足夠快速，以不至于造成數(shù)據(jù)包的延遲發(fā)送。

(3)在兩端都應(yīng)盡量減少內(nèi)存的占用：服務(wù)器端要分別記錄和大量用戶終端之間的數(shù)據(jù)，每一個(gè)用戶終端都要在服務(wù)器端的內(nèi)存中占有一定的空間，而在用戶終端，內(nèi)存受限于所使用的物理機(jī)器性能。因此在兩端都必須盡量減少內(nèi)存的使用，設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)和算法使得所占用的內(nèi)存盡量的小是端到端冗余流量消除技術(shù)必須考慮的一點(diǎn)。

2 算法設(shè)計(jì)

端到端冗余流量消除技術(shù)的算法設(shè)計(jì)包括服務(wù)器端算法設(shè)計(jì)和用戶終端算法設(shè)計(jì)。服務(wù)器端負(fù)責(zé)緩存曾經(jīng)發(fā)送過的數(shù)據(jù)包于數(shù)據(jù)包庫中，并對當(dāng)前要發(fā)送的數(shù)據(jù)包與數(shù)據(jù)包庫中的包進(jìn)行比對，檢測出其中的重復(fù)片段，并對數(shù)據(jù)包進(jìn)行編碼后發(fā)送，編碼后的數(shù)據(jù)包指出了哪一片段由于曾經(jīng)發(fā)送過而從數(shù)據(jù)包中去除。用戶終端收到數(shù)據(jù)包后對其進(jìn)行解碼，還原被去除的數(shù)據(jù)包片段，并緩存此數(shù)據(jù)包，用于下次可能的解碼操作。服務(wù)器端的編碼可能只是告訴用戶終端，從曾經(jīng)發(fā)送過的哪個(gè)數(shù)據(jù)包的哪個(gè)位置開始恢復(fù)當(dāng)前的數(shù)據(jù)包，所以客戶端只是簡單的解碼包和緩存包，而大量的比對運(yùn)算都發(fā)生在服務(wù)器端，這樣能滿足端到端冗余流量消除技術(shù)的設(shè)計(jì)要求。

在服務(wù)器端對數(shù)據(jù)包的編碼可以分為兩步：

(1)代表指紋選擇：在數(shù)據(jù)包的重復(fù)檢測中，每一個(gè)數(shù)據(jù)包都由多個(gè)指紋來代表，數(shù)據(jù)包之間的比對實(shí)際是能代表數(shù)據(jù)包的指紋之間的比對。每一個(gè)數(shù)據(jù)包可以由多個(gè)指紋來代表，每個(gè)指紋能代表數(shù)據(jù)包中的某一個(gè)固定長度的片段，所有數(shù)據(jù)包的代表指紋形成了代表指紋庫。然而，數(shù)據(jù)包的眾多片段每個(gè)都能產(chǎn)生一個(gè)指紋，顯然不可能把所有的指紋都存入代表指紋庫，如何從指紋中選擇一些來代表整個(gè)數(shù)據(jù)包，選出的指紋應(yīng)有代表性，這是代表指紋選擇算法的要求。下文中描述了5種指紋選擇算法，每個(gè)都在有效性和計(jì)算量上有所差別。

(2)匹配：匹配算法利用當(dāng)前數(shù)據(jù)包的代表指紋與代表指紋庫中的指紋做比對，如果在代表指紋庫中有相匹配的指紋，表示服務(wù)器端曾經(jīng)傳輸過相似數(shù)據(jù)包給客戶端，兩個(gè)數(shù)據(jù)包中的相同片段由匹配的代表指紋來表征。下文中的兩個(gè)匹配算法在內(nèi)存占用和有效性上有所差別。

2.1 指紋選擇算法

指紋選擇算法中參數(shù)w表示指紋算法的輸入字符串的字節(jié)數(shù)，w字節(jié)的字符串能產(chǎn)生一個(gè)指紋，如果一個(gè)數(shù)據(jù)包的負(fù)荷部分長度為L個(gè)字節(jié)，那么總共能產(chǎn)生L-w+1個(gè)指紋，數(shù)據(jù)包與數(shù)據(jù)包之間的比對實(shí)際是數(shù)據(jù)包的指紋與數(shù)據(jù)包的指紋之間的比對，w是數(shù)據(jù)包之間能被檢測到的重復(fù)字節(jié)的最小長度，通常w被定在12字節(jié)到64字節(jié)之間。一個(gè)數(shù)據(jù)包的L-w+1個(gè)指紋不能全部存儲在內(nèi)存中，否則，隨著數(shù)據(jù)包負(fù)荷部分的增大，指紋的數(shù)量也呈線性增長，所以必須要從L-w+1個(gè)備選指紋中選取1/p*(L-w+1)個(gè)指紋作為數(shù)據(jù)包的“代表指紋”，選出的代表指紋首先用于和指紋庫中的指紋做比對，然后被存入指紋庫，用于以后的指紋比對操作。服務(wù)器端的指紋庫(見圖1)中緩存的就是這些代表指紋，而對于那些沒有被選中的(p-1)/p*(L-w+1)個(gè)指紋則直接丟棄，其中p表示代表指紋的選擇率。一個(gè)數(shù)據(jù)包能有多個(gè)代表指紋，而一個(gè)代表指紋只代表一個(gè)數(shù)據(jù)包。代表指紋的選擇必須有代表性，能夠盡量多的檢測出兩個(gè)數(shù)據(jù)包之間的相同片段。

圖1 服務(wù)器端緩存結(jié)構(gòu)

2.1.1 MODP

早期的協(xié)議無關(guān)的網(wǎng)絡(luò)冗余消除算法中指紋的選擇都使用MODP算法，它基于Rabin移位指紋算法。MODP首先對數(shù)據(jù)包負(fù)荷中的所有w個(gè)連續(xù)的字節(jié)做移位指紋算法，即每w個(gè)連續(xù)的字節(jié)計(jì)算指紋之后右移一個(gè)字節(jié)繼續(xù)對w個(gè)連續(xù)的字節(jié)做移位指紋。對于最后得到的所有L-w+1個(gè)指紋，如果模p余0則被選為代表指紋，被選為代表指紋的概率為1/p。這樣選擇指紋的好處是當(dāng)一個(gè)內(nèi)容被少量的增加、刪除或修改之后，拆分成數(shù)據(jù)包在網(wǎng)絡(luò)上傳輸，路由器選擇的代表指紋總是相同的，不會因?yàn)閿?shù)據(jù)在整個(gè)內(nèi)容中位置的改變而改變。但是MODP算法也有3個(gè)缺點(diǎn)：①必須對每w個(gè)字節(jié)都計(jì)算一次指紋，即使是那些沒有被選為代表指紋的指紋。②代表指紋的選擇是基于參數(shù)p的，造成了數(shù)據(jù)包中被選中的代表指紋數(shù)量不平均，代表指紋在數(shù)據(jù)包中的位置分布不平均。③能被檢測出的重復(fù)字節(jié)集中于那些其指紋模p余0的字節(jié)，而對于其他重復(fù)字節(jié)則無法檢測。

2.1.2 MAXP

MAXP指紋選擇算法把數(shù)據(jù)包負(fù)荷中的每p個(gè)字節(jié)分為一段，p個(gè)字節(jié)中數(shù)值最大的一個(gè)字節(jié)被選出，對由這個(gè)字節(jié)起始的w個(gè)字節(jié)做指紋算法(指紋算法可能是SHA-1、RSA算法、Jenkins哈希算法等)。MAXP算法克服了MODP算法的3個(gè)缺點(diǎn)：首先MAXP算法不必對每w個(gè)字節(jié)進(jìn)行一次指紋算法，而只需對那些被選擇的w個(gè)字節(jié)做指紋算法，減少了運(yùn)算量；其次，MAXP算法平均在每p個(gè)字節(jié)中選擇一個(gè)代表指紋，使得代表指紋在整個(gè)數(shù)據(jù)包負(fù)荷中基本是均勻分布的，而且每個(gè)數(shù)據(jù)包負(fù)荷都根據(jù)自己的字節(jié)長度擁有相應(yīng)數(shù)量的代表指紋；最后，代表指紋的選擇依據(jù)具有一定的相對性，與絕對的值p無關(guān)，因此能檢測出的重復(fù)片段并不局限于某些字節(jié)。實(shí)驗(yàn)表明MAXP算法不但克服了MODP算法的一些缺點(diǎn)，而且其對冗余流量檢測的有效性卻并不差于MODP。

2.1.3 FIXED

MODP和MAXP算法的共同缺點(diǎn)是它們的計(jì)算量都相對較大：MODP算法需要對每w字節(jié)都計(jì)算指紋，MAXP算法需要在每p字節(jié)長度中計(jì)算數(shù)值最大的字節(jié)，但他們的優(yōu)點(diǎn)是都根據(jù)一定長度數(shù)據(jù)塊片段的數(shù)值來選擇其代表指紋。FIXED算法彌補(bǔ)了MODP和MAXP的缺點(diǎn)：選擇數(shù)據(jù)包負(fù)荷中的第p個(gè)字節(jié)，第2p個(gè)字節(jié)，第3p個(gè)字節(jié)…作為指紋運(yùn)算的起始字節(jié)，指紋的選擇只和位置有關(guān)，而和數(shù)值無關(guān)。盡管FIXED方法速度快，但是由于代表指紋的選擇與數(shù)據(jù)包的內(nèi)容(數(shù)值)無關(guān)，所以對于文件細(xì)微的插入、刪除和修改，它都無法檢測出重復(fù)數(shù)據(jù)，使得其有效性不如MODP和MAXP。

2.1.4 SAMPLEBYTE

上述3種代表指紋選擇算法，其中MAXP和MODP算法對于傳輸內(nèi)容的細(xì)微修改有很好的健壯性，但是運(yùn)算量較大，而FIXED算法與傳輸內(nèi)容無關(guān)，但是運(yùn)算量小。SIMPLEBYTE算法結(jié)合了上述3種方法各自的優(yōu)點(diǎn)。SIMPLEBYTE算法事先有一張256項(xiàng)的查找表，每個(gè)不同的字節(jié)對應(yīng)一項(xiàng)，查找的結(jié)果或?yàn)?，或?yàn)?，表中值為1的項(xiàng)的數(shù)量應(yīng)為256/p。算法依次把數(shù)據(jù)包負(fù)荷中的字節(jié)在查找表中查找，如果當(dāng)前字節(jié)的值為1，那么從這個(gè)字節(jié)起始的w個(gè)字節(jié)將作為指紋運(yùn)算的輸入，其結(jié)果為一個(gè)代表指紋，然后從此字節(jié)開始跳過p/2個(gè)字節(jié)繼續(xù)依次把字節(jié)按查找表中查找，直到數(shù)據(jù)包末尾。SIMPLEBYTE運(yùn)算量小，只需做線性的查找工作，而根據(jù)實(shí)驗(yàn)可知其有效性與MAXP和MODP相當(dāng)。

2.1.5 貪婪指紋選擇算法

貪婪指紋選擇算法在SAMPLEBYTE算法的基礎(chǔ)之上做了改進(jìn)：當(dāng)由SAMPLEBYTE算法選出的代表指紋在指紋庫中有匹配的指紋時(shí)(如圖2所示)，即指紋p1與指紋庫中已經(jīng)存在的某個(gè)指紋相同，表示片段1在曾將的某個(gè)數(shù)據(jù)包中已經(jīng)被傳送過，則把數(shù)據(jù)包中匹配片段的下一片段(片段2)也做指紋算法，其得到的指紋p2也作為代表指紋(見圖2)。

圖2 貪婪指紋選擇算法

如果p2也和指紋庫中的某個(gè)指紋匹配，則片段3也將被做指紋運(yùn)算，并被選為代表指紋，以此類推(如圖3所示)。貪婪指紋選擇算法基于這樣一個(gè)思想：兩個(gè)數(shù)據(jù)包中的某一片段是相同的，那么他們各自的下一片段也很有可能是相同的。這樣選擇出來的代表指紋能更大限度的檢測出重復(fù)，而且使得代表指紋不局限于SAMPLEBYTE查找表，代表指紋的選擇更具有平均性。在貪婪指紋選擇算法中，指紋選擇率p可能小于其實(shí)際值。

圖3 貪婪指紋選擇算法偽代碼

2.2 匹配算法

2.2.1 最大匹配算法

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

在最大匹配算法中，服務(wù)器端需要緩存每個(gè)完整的數(shù)據(jù)包，用以指紋匹配成功時(shí)能向左右拓展相同數(shù)據(jù)片段的長度，因此稱為最大匹配算法。服務(wù)器端的內(nèi)存分為兩部分，一部分用以存儲代表指紋，稱為代表指紋庫，另一部分用以存儲數(shù)據(jù)包，稱為數(shù)據(jù)包庫。用戶終端只需要緩存數(shù)據(jù)包，而不需要緩存指紋，服務(wù)器端的數(shù)據(jù)包庫與用戶終端的數(shù)據(jù)包庫高度一致，因此服務(wù)器端只需要告訴用戶終端被去除的數(shù)據(jù)片段在數(shù)據(jù)包庫中的起始位置和長度，就能在用戶終端還原數(shù)據(jù)包，大部分的計(jì)算量都在服務(wù)器端完成，簡化了用戶終端的操作。

2.2.2 塊配算法

在塊匹配算法中，檢測出兩個(gè)數(shù)據(jù)包中的相同數(shù)據(jù)片段后不需要向左右拓展相同部分的長度。指紋所代表的數(shù)據(jù)片段就被認(rèn)為是檢測出的一個(gè)完整的重復(fù)片段。因此，在服務(wù)器端不需要數(shù)據(jù)包庫，只需要指紋庫，而在用戶終端也不需要數(shù)據(jù)包庫，取而代之的是數(shù)據(jù)塊庫。服務(wù)器端需要知道每一個(gè)數(shù)據(jù)塊在用戶終端的數(shù)據(jù)塊庫中的什么位置，當(dāng)檢測到匹配的指紋時(shí)，只需要告訴用戶終端從數(shù)據(jù)塊庫的什么位置還原數(shù)據(jù)包，每一個(gè)數(shù)據(jù)塊的長度總是固定的w字節(jié)。

與最大匹配算法相比，塊匹配算法大大減少了在服務(wù)器端和客戶端的內(nèi)存占用，但是重復(fù)檢測的效果顯然不如最大匹配算法。

在Anand等人的論文中他們考慮到算法的效果選擇了最大匹配算法，但是這樣服務(wù)器端為每個(gè)用戶終端都需要建立一個(gè)數(shù)據(jù)包庫，當(dāng)用戶數(shù)量巨大的時(shí)候，會大量的占用服務(wù)器端的內(nèi)存。同樣的，在用戶終端，數(shù)據(jù)包庫比數(shù)據(jù)塊庫占用更多的內(nèi)存，當(dāng)一個(gè)用戶與多個(gè)服務(wù)器端建立連接，那么采用最大匹配算法的話會消耗更多的內(nèi)存。

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

在實(shí)驗(yàn)中共模擬了2種指紋選擇算法：SAMPLEBYTE和貪婪指紋選擇算法，以及2種匹配算法：最大匹配算法和塊匹配算法。其他 3種指紋選擇算法由于已經(jīng)被證明效果差于SAMPLEBYTE而不在實(shí)驗(yàn)考慮范圍內(nèi)。在本次實(shí)驗(yàn)中，我模擬并比較了3種端到端冗余流量消除算法：第1個(gè)采用SAMPLEBYTE作為指紋選擇算法以及最大匹配作為匹配算法，第2個(gè)采用 SAMPLEBYTE作為指紋選擇算法以及塊匹配作為匹配算法，最后一個(gè)采用貪婪指紋選擇算法以及塊匹配算法。Anand等人在論文中采用了第4個(gè)算法，盡管第一個(gè)算法會在服務(wù)器端和用戶終端占用大量的內(nèi)存，而第2個(gè)算法由于其冗余消除的效果不理想而沒有被采用。第3個(gè)算法用于和前兩個(gè)算法做對比，以證明貪婪指紋選擇算法的運(yùn)用能夠一定程度的彌補(bǔ)前兩個(gè)算法的各自缺點(diǎn)。

實(shí)驗(yàn)參數(shù)選擇：w為32字節(jié)；p為64；指紋算法選擇Jenkins哈希算法，它可以產(chǎn)生很好的分布，輸出為32個(gè)bit；SAMPLEBYTE查找表中第0、42、48、104項(xiàng)設(shè)為1，根據(jù)對實(shí)際數(shù)據(jù)包的分析，這4項(xiàng)在所有255個(gè)字符中出現(xiàn)的概率約為1/64，符合參數(shù)p的要求。在最大匹配算法中，預(yù)留給數(shù)據(jù)包庫的內(nèi)存大小為16MB，由于指紋選擇率p為64(如果采用貪婪指紋選擇算法，p會略小于其實(shí)際值，但為了實(shí)驗(yàn)的方便，在貪婪指紋選擇算法中，仍然按照p=64來計(jì)算指紋庫中代表指紋的大約個(gè)數(shù))，16M/64=262144，所以整個(gè)數(shù)據(jù)包庫產(chǎn)生的代表指紋約有262144個(gè)。如果把指紋庫的內(nèi)存大小預(yù)設(shè)為1.25M，那么每個(gè)指紋結(jié)構(gòu)占用5字節(jié)，其中3個(gè)字節(jié)用以指向所代表的數(shù)據(jù)片段在數(shù)據(jù)包庫中的位置(2^24=16M)，另外兩個(gè)字節(jié)由于不足以表示一個(gè)完整的指紋，所以把指紋庫的索引也作為指紋表示的一部分，索引用以表示指紋的前18位，后14位由剩下的2個(gè)字節(jié)表示，當(dāng)兩個(gè)指紋的前18位沖突時(shí)，則原來的指紋結(jié)構(gòu)將被新的覆蓋。在塊匹配算法中，只留下了指紋庫而不再需要數(shù)據(jù)包庫，同時(shí)指紋庫中的數(shù)據(jù)包偏移量字段也不再需要，因此指紋庫的大小縮減到0.5MB，相比于最大匹配算法，服務(wù)器端為每個(gè)用戶終端消耗的內(nèi)存由65.25MB下降為0.5MB。

4 實(shí)驗(yàn)結(jié)果

總共分析了從4個(gè)網(wǎng)站采集的TCP數(shù)據(jù)包，稱為數(shù)據(jù)1到數(shù)據(jù)4。

(1)內(nèi)存消耗

在服務(wù)器端，采用最大匹配所需的內(nèi)存消耗是采用塊匹配的130.5陪，在用戶終端也達(dá)到了8倍(見表1)。最大匹配所需的內(nèi)存遠(yuǎn)遠(yuǎn)大于塊匹配算法，在服務(wù)器端如果用戶數(shù)量增加，那么所消耗的內(nèi)存也會急劇增加。

表1 冗余消除算法內(nèi)存消耗

(2)冗余消除效果

3個(gè)端到端冗余流量消除算法各自的效果見表2。除了數(shù)據(jù)4外，其他3個(gè)數(shù)據(jù)中算法3結(jié)果都與算法1相接近。究其原因，從表2中可以看出，數(shù)據(jù)4的冗余消除量遠(yuǎn)遠(yuǎn)小于其他3個(gè)數(shù)據(jù)，當(dāng)數(shù)據(jù)集中的冗余量較小時(shí)，可能大部分的冗余都高度分散，造成了貪婪指紋選擇算法的設(shè)想前提不存在，因此引起效果下降，所以對于數(shù)據(jù)4，算法3的效果與算法2相接近。當(dāng)數(shù)據(jù)包中的冗余量越大時(shí)，貪婪指紋選擇算法的效果就越好。

表2 冗余消除算法

在實(shí)驗(yàn)中，算法3的服務(wù)器端內(nèi)存消耗只有算法1的約1/130，其指紋庫內(nèi)存消耗也只有算法2/5，相信如果加大算法3的指紋庫內(nèi)存，使其與算法1的指紋庫所消耗內(nèi)存相同，那么算法3的效果應(yīng)該會更好。

5 結(jié)束語

端到端冗余流量消除技術(shù)是當(dāng)前的新興研究領(lǐng)域，其屬于協(xié)議無關(guān)的冗余流量消除技術(shù)，但是與以往的技術(shù)不同，其工作在傳輸層，并且把所有的運(yùn)算量都放置在網(wǎng)絡(luò)的邊緣(服務(wù)器和用戶終端)。

本文針對當(dāng)前服務(wù)器端內(nèi)存消耗巨大這一問題，提出了一種新的指紋選擇算法：貪婪指紋選擇算法。它認(rèn)為兩個(gè)數(shù)據(jù)包中相同片段的下一片段很有可能也是相同的，基于這一原理，下一片段的指紋也將被選為代表指紋。根據(jù)實(shí)驗(yàn)結(jié)果，貪婪指紋選擇算法使得服務(wù)器端的內(nèi)存消耗減少了約130倍，客戶端的內(nèi)存消耗也僅為原來的1/8，同時(shí)當(dāng)數(shù)據(jù)集中的冗余量較大時(shí)，冗余消除的效果能達(dá)到原來的85%-88%，數(shù)據(jù)集中的冗余量越大，貪婪指紋算法帶來的效果越好。如果加大服務(wù)器端的指紋庫，則貪婪指紋選擇算法的效果能更加接近于現(xiàn)有的端到端冗余流量消除算法。

[1]Squid.Squid web proxy cache[EB/OL].http://www.squid-cache.org/,2010.

[2]Pallis G,Vakali A.Insight and perspectives for content delivery networks[J].Communications of the ACM,2006,49(1):101-106.

[3]Liu H,Zhang Y,Raychaudhuri D.Performance evaluation of the"cache-and-forward(CNF)"networkformobile content delivery services[C].Dresden:International Conference on Communications Workshops,2009:1-5.

[4]IT Facts.WAN optimization revenues grow 16%[EB/OL].www.itfacts.biz/wan-optimization-market-to-grow-16/1205/,2004.

[5]Anand A,Gupta A,Akella A,et al.Packet caches on routers:the implications of universal redundant traffic elimination[J].ACM SIGCOMM Computer Communication Review,2008,38(4):219-230.

[6]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.

[7]Anand A,Muthukrishnan C,Akella A,et al.Redundant in network traffic:Findings and implications[C].New York,NY,USA:ACM Sigmetrics,2009:37-48.

[8]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.