喬冠杰，呂高鋒，譚 靖，莫露莎

(國防科技大學計算機學院，湖南 長沙 410073)

1 引言

隨著網(wǎng)絡的發(fā)展，流量規(guī)模的不斷增大，對大規(guī)模流量進行統(tǒng)計變得十分重要，早期的網(wǎng)絡管理功能，如流量統(tǒng)計，是固化在相應的網(wǎng)絡設備中的，基于端口對交換機或路由器連接不同網(wǎng)絡的流量進行統(tǒng)計。隨著網(wǎng)絡的發(fā)展，這種方式已經(jīng)不能滿足網(wǎng)絡管理的需求。

網(wǎng)絡可視化應運而生，對網(wǎng)絡的實時監(jiān)控越來越重要。網(wǎng)絡就像公路，需要實時掌握主干道信息，了解每條路是否堵塞，了解車流密度等等。車輛就相當于網(wǎng)絡中的流量，只有掌握道路信息，才能更好地調(diào)度交通，保證道路暢通。網(wǎng)絡也是一樣，只有實時去監(jiān)測流量，才能了解網(wǎng)絡狀態(tài)，進行流量調(diào)度、擁塞控制[1]和異常檢測等等。

為了應對大規(guī)模的流量統(tǒng)計[2]，各種測量結(jié)構(gòu)相繼產(chǎn)生，一種典型的網(wǎng)絡測量結(jié)構(gòu)是Sketch[3]。Sketch是一種基于哈希的緊湊的數(shù)據(jù)結(jié)構(gòu)，通過哈希減少流量的存儲空間，同時可以對流量進行統(tǒng)計。針對不同流量統(tǒng)計的問題，基于Sketch的統(tǒng)計算法不斷發(fā)生改變，流量統(tǒng)計中一個典型問題是對top-k流[4]進行統(tǒng)計，本質(zhì)是將大象流[5]和老鼠流[6]進行分離，實現(xiàn)對大象流的精確統(tǒng)計，同時對老鼠流實現(xiàn)粗略統(tǒng)計。Elastic Sketch[7]便是將老鼠流和大象流分離進行統(tǒng)計的典型。使用重部存儲大象流，輕部存儲老鼠流，實現(xiàn)大象流和老鼠流的分離。

但是，Elastic Sketch在計數(shù)器更新時也存在問題，在Elastic Sketch的替換策略中，當負投票和正投票比值大于一個閾值時，就會發(fā)生替換。如果這時來的一條流是冷流，則會把冷流插入到重部中去，并將標志位設置為true，此時便會將冷流誤判為熱流存到重部中。本文對這個問題進行了優(yōu)化，解決了冷流被誤判存入重部的問題。同時，針對被替換入重部的流不一定是最大流的問題，提出了一種基于最大值的替換策略，保證了重部中永遠記錄最大的流。

2 相關研究

網(wǎng)絡流主要根據(jù)五元組、包的大小來分類。在網(wǎng)絡中存在各種各樣的數(shù)據(jù)包，如果按照五元組或者包的大小分類的分類方法，對每一類數(shù)據(jù)包都分配一個計數(shù)器來存儲其數(shù)值，雖然測量結(jié)果準確，但是需要很大的空間來存放計數(shù)器。所以，研究人員采用哈希方法計算流的哈希值，根據(jù)哈希值的范圍來確定所需的存儲空間大小，各種數(shù)據(jù)包根據(jù)所得到的哈希值進行分類，可以在極大程度上減少存儲空間。

2.1 典型的Sketch結(jié)構(gòu)

2.1.1 Count-Min Sketch

一種典型的方法是使用Sketch數(shù)據(jù)結(jié)構(gòu)，其代表是Count-Min Sketch，如圖1所示。由于使用哈希函數(shù)產(chǎn)生哈希值可能會發(fā)生沖突[8,9]，多個不同種類數(shù)據(jù)包可能會哈希到同一個桶內(nèi)，這個桶的計數(shù)值就會偏大，為了減少哈希值沖突引起的誤差，研究人員設計了Count-Min Sketch。它通過設置多個哈希函數(shù)，用二維地址空間進行存儲，數(shù)據(jù)包經(jīng)過多個不同哈希函數(shù)的哈希后，得到對應的哈希值，這些哈希值有可能產(chǎn)生沖突，即不同種類的數(shù)據(jù)包可能在同一個哈希函數(shù)哈希之后有相同的哈希值，則根據(jù)哈希值來確定的數(shù)據(jù)包出現(xiàn)的次數(shù)則會偏大，所以建立多個哈希函數(shù)，取這其中最小的哈希值，這個值最接近實際數(shù)據(jù)包的數(shù)據(jù)。

Figure 1 Count-Min Sketch structure圖1 Count-Min Sketch結(jié)構(gòu)

在高速網(wǎng)絡流量下[10,11]，很難做到把所有信息都準確地記錄下來，而且會消耗大量存儲資源，計算開銷也很大，不能滿足實時性。并且在很多情況下，并不需要十分準確的數(shù)據(jù)，而是只需要滿足一定條件下的估計值。如果只設置了一個哈希函數(shù)，大量的數(shù)據(jù)流就會哈希到同一個桶中，產(chǎn)生沖突，誤差就會很大，而通過設置多個不同的哈希函數(shù)，取其中最小的哈希值會減少誤差，但也要合理地選取哈希函數(shù)數(shù)量，選取太多哈希函數(shù)顯然會加大計算開銷。

當可用帶寬很小時，發(fā)送大Sketch將導致長延遲并影響用戶流量。問題是如何使Sketch尺寸小于可用帶寬，尤其是當網(wǎng)絡不能正常工作時。一個解決方案是為相同的網(wǎng)絡流量構(gòu)建不同大小的Sketch。例如，構(gòu)建2個SketchS1和S2，其內(nèi)存大小為M和M/2，在可用帶寬很小時可以將S2發(fā)送到收集器。更好的解決方案是僅構(gòu)建S1，并將其快速壓縮為一半。

2.1.2 Elastic Sketch

(1)Elastic Sketch數(shù)據(jù)結(jié)構(gòu)。

Elastic Sketch是將冷流與熱流分離的典型結(jié)構(gòu)。由于數(shù)據(jù)量十分龐大，記錄下所有數(shù)據(jù)流的IP是十分困難的，而且這也將消耗大量的內(nèi)存資源，而遠端服務器受限于部署環(huán)境，很難提供如此龐大的內(nèi)存資源。對于所研究的某些任務，這些冷流并不必考慮，因而將熱流與冷流分離，并在后續(xù)任務中丟棄冷流，只考慮熱流會明顯節(jié)省內(nèi)存資源和傳輸帶寬。

文獻[7]提出將存儲空間劃分為2個部分，分別是重部和輕部，其中重部存儲熱流，輕部存儲冷流，如圖2所示。

Figure 2 Separate hot flow and cold flow圖2 分離熱流與冷流

重部劃分為N個桶，每個桶存儲4個字段，(key，vote+，flag，vote-)，分別是流ID、正投票、flag標志和負投票。其中流ID標識一條流，正投票記錄屬于此流的數(shù)據(jù)包數(shù)量，負投票記錄不屬于此流的數(shù)據(jù)包數(shù)量，flag標志表示輕部是否可能包含此流的正投票。當一條流數(shù)據(jù)f到來時，提取它的流ID，并調(diào)用mmh3哈希函數(shù)，得到哈希值h(f)(modN)的值value，根據(jù)value的值將流f與重部對應索引的桶中流F匹配。

Elastic Sketch將冷流和熱流分離，實現(xiàn)了對熱流較為精確的統(tǒng)計，對冷流的粗略統(tǒng)計，是一種經(jīng)典的對熱流進行統(tǒng)計的結(jié)構(gòu)，但也存在著一些問題，將在第3節(jié)進行詳細說明。

(2)準確度分析。

①重部沒有錯誤：對于標志為F(False)的流，記錄的正投票是沒有錯誤的流量大小;對于標志為T(True)的流，記錄的正投票是流量大小的一部分,仍然沒有錯誤，而另一部分記錄在錯誤的輕部下。

②輕部不記錄流量ID，只記錄冷流量的大小，因此可以使用許多小型計數(shù)器(例如8位計數(shù)器)，而傳統(tǒng)Sketch需要使用幾個大型計數(shù)器(例如32位計數(shù)器)以適應熱流動。因此，本文的輕部可以非常準確?？傊?，熱和冷的精確度都很高。在最壞的情況下熱碰撞使準確性降低：當2個或更多的熱流被映射到同一個桶中時，一些熱流被驅(qū)逐到輕部和可能會使一些冷流量顯著高估。

(3)基于組相連的熱碰撞優(yōu)化。

熱碰撞的解決方案是：讓重部中的每個桶存儲多個流量，它允許在一個桶中記錄幾個熱流，因此熱碰撞率顯著下降。本文采用這種算法來降低熱碰撞率。

如果流f1替換流F，將流F驅(qū)逐到輕部，那么認定f1為熱流。假設大量的流f2到來，將流f1驅(qū)逐到輕部，然而f1是熱流，它被驅(qū)逐到輕部，被認定為了冷流，這就是熱碰撞。

為了解決這個問題，文獻[7]中提出了優(yōu)化方案，將原本每個桶只存儲一條流擴大為存儲多條流，如圖3所示。

Figure 3 Optimization scheme of hot flow collision圖3 熱流碰撞優(yōu)化方案

每個桶中存儲多條流，但是每個桶中的流共用一個負投票計數(shù)器，當一條流f到來時，將它哈希到其中一個桶中，如果桶沒有滿，將流插入到桶中；如果桶滿了，并且與桶中某一條流ID匹配，則這條流對應的vote+加1，如果都不匹配，那么將共用的負投票計數(shù)器加1。流f到來時，考慮是否驅(qū)逐桶中的某條流，將負投票vote-與桶中流對應最小正投票(vote+)min的比值與閾值λ作比較，如果vote-/(vote+)min<λ，則將流f驅(qū)逐到輕部，否則取出輕部中f的計數(shù)，其余操作與前一種方案相同。由于每次驅(qū)逐桶中流時，只會驅(qū)逐每個桶中正投票計數(shù)最小的，因此減少了熱流被驅(qū)逐的可能性。

2.2 Sketch應用

基于Sketch構(gòu)建測量解決方案：Sketch可用于許多測量任務，例如Heavy Hitter檢測[12]、流量變化檢測[13]和流量大小分布估計。例如，要計算通過端口80訪問Web服務器的唯一源的數(shù)量，可以簡單地根據(jù)端口80過濾流量，然后使用位圖來計算唯一源地址的數(shù)量。另一個例子是Heavy Hitter檢測，這對于數(shù)據(jù)中心的流量工程很重要。為了識別 Heavy Hitter，首先使用Count-Min Sketch來維護每個流的計數(shù)；然后，在可逆Sketch中識別哈希到重計數(shù)器的潛在流量，并使用Count-Min Sketch驗證它們的實際計數(shù)。

Sketch在進行數(shù)據(jù)處理之前，首先要根據(jù)研究內(nèi)容挑選合適的測量數(shù)據(jù)包，比如為了計算具有相同內(nèi)容的冗余數(shù)據(jù)包的數(shù)量，可以將數(shù)據(jù)包主體散列，而不是每次都存儲和比較整個數(shù)據(jù)包主體。對某些特定的流進行研究時，分類具有重要作用，例如，如果來自IP地址192.168.1.1的流量太多，可以過濾192.168.1.1/32的數(shù)據(jù)包，即使用一個計數(shù)器用于統(tǒng)計來自特定IP的流量，另一個計數(shù)器用于統(tǒng)計來自子網(wǎng)192.168.1.0/24的剩余流量。對于流分類，可以指定與流字段上的數(shù)據(jù)包匹配的通配符規(guī)則，并允許流字段中的某些位為通配位。例如，規(guī)則可以匹配源IP前綴192.168.1.0/24上的數(shù)據(jù)包，其中低8位是通配位。

3 冷熱流替換策略優(yōu)化

3.1 替換問題及原因分析

在Elastic Sketch中，重部的替換策略是當負投票與正投票的比值大于一個閾值時，新來的流會替換重部中保存的流，未考慮新流大小。如果新流是一條冷流，這條冷流會因為替換策略被存入重部，并將標志位設置為T，這樣會導致冷流占據(jù)重部，影響熱流的測量精度；另一方面，這種替換策略還可能會導致替換頻繁發(fā)生，當這條冷流因為替換策略要發(fā)生替換時，又來一條冷流，那么這時新的冷流又被記錄在重部，導致了替換的頻繁發(fā)生，并且熱流得不到記錄?，F(xiàn)有的替換策略無法確保存入重部的是一條絕對大流，只要滿足替換條件，剛來的流就會替換重部中的流，但無法保證這條流一定比之前的流大。

造成冷熱流替換的原因：

(1)單條冷流數(shù)量較少，但冷流總量很多；

(2)存儲熱流的空間有限，發(fā)生熱碰撞。

替換策略設計的原則：

(1)防止冷流被誤判為熱流進入重部；

(2)提高發(fā)生替換時的閾值，超過一定值再發(fā)生替換；

(3)增大重部的存儲空間，減少重部熱碰撞。

針對上述問題本文在3.2節(jié)提出了關于替換的優(yōu)化策略，保證了冷流在頻率較低的情況下不會替換重部中的熱流。3.3節(jié)提出了基于最大值替換策略，對熱流進行精確統(tǒng)計的同時，將最大流候選保存在countmax中，保證了發(fā)生替換后重部中存放的一定是最大的流，同時解決了冷流頻繁進入重部的問題。

3.2 優(yōu)化1 基于歷史值的冷熱替換策略

在Elastic Sketch中，流F是存儲在重部中的流，一條流f插入的過程分為以下4種情況：

(1)如果桶是空的，直接在桶中插入(f,1,F,0)；

(2)如果f=F，那么直接將vote+加1；

(3)如果f≠F，首先設定閾值λ，如果vote-/vote+<λ，那么將流f驅(qū)逐到輕部，vote-加1；

(4)如果f≠F，并且vote-/vote+≥λ，將桶中字段設置為(f,1,T,0)，將F驅(qū)逐到輕部。

在第4種情況下，如果流f是第1次進行匹配，那么就會把冷流f插入到重部，并且將flag設置為T，這時認定f為熱流，然而流f只出現(xiàn)過一次，本文對此進行以下優(yōu)化：

如果f≠F，并且vote-/vote+≥λ，這時從輕部取出流f的計數(shù)number，如果(number+1)/vote+≥1，那么將桶中字段設置為(f,1,T,0)，將F驅(qū)逐到輕部，否則將流f驅(qū)逐到輕部。如圖2所示，流f5插入重部，由于其中f5哈希之后是插入到重部的空處，在空處直接插入(f5,1,F,0)；流f1插入重部，哈希之后與重部中流ID字段匹配，將f1的vote+加1；流f8插入重部，哈希之后與流ID字段不匹配而且vote-/vote+小于閾值，將f3的vote-加1，將f8驅(qū)逐到輕部；流f9插入重部，哈希之后與流ID字段不匹配而且vote-/vote+大于閾值，將f4驅(qū)逐到輕部，f4所在桶更新為(f9,1,T,0)。

上述優(yōu)化解決了冷流第1次進入就會替換熱流的問題，很大程度上解決了頻繁替換的問題。

輕部是一個Count-Min Sketch，本文中設置了8個計數(shù)器，對于插入到輕部中的流，如果是原始數(shù)據(jù)的流f，經(jīng)過8個互不相同哈希函數(shù)哈希之后，在對應的計數(shù)器相應位置計數(shù)加1；如果是桶中的流F，那么在對應計數(shù)器的相應位置計數(shù)加上vote+的值。

3.3 優(yōu)化2 基于最大值的替換策略

針對熱流碰撞問題，以及冷流會替換重部中熱流的問題，本文進一步提出了基于最大值替換策略。引入countmax表，將結(jié)構(gòu)分為輕部和重部，重部每個桶包含3個位置，用于存儲熱流，每個位置分別記錄熱流ID和熱流數(shù)目。輕部包含2個獨立的哈希函數(shù)，第2個哈希函數(shù)對應一組計數(shù)器，用于存放冷流的哈希值，第1個哈希函數(shù)也對應一組計數(shù)器，用于存放第2個哈希函數(shù)對應的每組計數(shù)器值的最大值，并且第1個哈希函數(shù)對應的計數(shù)器包含一個countmax，用來存放第1個哈希函數(shù)對應所有計數(shù)器的最大值。

當流到達時，被哈希到重部的一個桶中，重部每個桶有3個位置可以存放3條熱流，若有空位置，并且流ID與桶中的流ID不同，將它插入到空位置中，并將計數(shù)器置1；若沒有空位置，流ID與桶中流ID相同，增加對應位置流的計數(shù)器；若沒有空位置，并且流ID與桶中流ID不同，將流通過hash1和hash2哈希到輕部的一個桶中。這個輕部桶只保存流的計數(shù)，之后將這個桶的計數(shù)和max進行比較，若桶計數(shù)值大于max，則將桶的計數(shù)值復制給max，再將max值與countmax進行比較；若大于countmax則將max值復制給countmax。若countmax值大于重部中某個位置的流計數(shù)，則將剛來的流與那個位置的流進行替換，用countmax的值作為這條流的計數(shù)值，被替換的流哈希到輕部中去，并用被替換的這條流的計數(shù)替代輕部中對應位置計數(shù)器的計數(shù)值。

如圖4所示，當流f23到達時，重部3個位置已滿，并且沒有流ID與其匹配，f23通過2次哈希函數(shù)到達輕部的計數(shù)器，更新計數(shù)值，并且計數(shù)值沒有大于max值，更新結(jié)束；當流f15到達時，重部3個位置已滿，并且沒有流ID與其匹配，f15通過2次哈希函數(shù)到達輕部的計數(shù)器，更新計數(shù)值，并且更新了max值和countmax值，由于countmax值沒有超過重部最小計數(shù)值，所以不發(fā)生替換，更新結(jié)束；當流f13到達時，重部3個位置已滿，并且沒有流ID與其匹配，f8經(jīng)過2次哈希函數(shù)到達輕部計數(shù)器，更新后max值變?yōu)?2，同時countmax值也改為12，這時，計數(shù)值大于f6流的計數(shù)值11，所以發(fā)生替換，將f6更新到輕部中，將(f13,12)插入到重部中，更新結(jié)束。

Figure 4 Replacement strategy based on maximum value and group connection圖4 基于最大值和組相連的替換策略

基于最大值和組相連的替換策略的優(yōu)勢在于將所有熱流的候選保存在了countmax中，通過3個不相關的哈希函數(shù)h1、h2、h3，將流分散在不同的位置進行存儲，很大程度上降低了哈希沖突帶來的影響，確保了一條冷流幾乎不可能更新countmax值，這樣冷流不會被記錄到重部，解決了冷流替換熱流的問題；同時，countmax表保存了h3對應的流的一個最大計數(shù)，countmax記錄了h2、h3映射區(qū)域的最大值，這樣在輕部重部發(fā)生替換的時候可以直接確定候選流計數(shù)值，避免了低頻冷流被記錄到重部中的情況。

4 實驗及結(jié)果分析

4.1 實驗平臺

基于Fast平臺進行算法測試，用戶可以選擇全定制功能開發(fā)模式，即基于平臺提供的FPGA開發(fā)接口(UM接口)和軟件開發(fā)接口(UA接口)開發(fā)自己的功能。統(tǒng)計模塊中的判斷模塊、重部在UM接口實現(xiàn)，統(tǒng)計模塊中的輕部在UA接口實現(xiàn)，為了加快實驗測試，流量感知的數(shù)據(jù)統(tǒng)計與分離算法在UA上實現(xiàn)。

4.2 統(tǒng)計模塊實現(xiàn)

統(tǒng)計模塊主要分為3個部分：重部、判斷模塊和輕部。重部是一個哈希表，它可以卸載到硬件實現(xiàn)，本文考慮實際情況，由軟件進行實現(xiàn)。它存儲4個字段的信息，存儲空間大小是可擴展的，只需要將原重部復制并合并，刪除其中的一半流，其中原有的h()%t轉(zhuǎn)變?yōu)閔()%(2t)，比如假設原重部大小為4 KB，它劃分為4塊1 KB的存儲空間，流f1存儲位置為h(f1)%4=1,擴展后，h(f1)%8=5,則刪除原重部中的流f1。其中，h()表示一條流鍵進行哈希運算之后的結(jié)果，t表示重部計劃分的塊數(shù)。判斷模塊主要由哈希函數(shù)和判斷語句組成。輕部是Count-Min Sketch，由軟件實現(xiàn)。它存儲從重部中被驅(qū)逐流的計數(shù)，它共由8個計數(shù)器組成，計數(shù)器的存儲空間大小也是可變的。

mmh3哈希函數(shù)由C語言實現(xiàn)，是一種非加密散列函數(shù)，適用于一般的基于散列的查找。它產(chǎn)生一個32位或128位散列值。使用128位時，x86和x64版本不會生成相同的值，因為算法針對各自的平臺進行了優(yōu)化，因而本文調(diào)用該哈希函數(shù)不會產(chǎn)生沖突。

4.3 誤差分析

數(shù)據(jù)量為2 000 000條流，Sketch和桶大小為32,64,128時的誤差統(tǒng)計結(jié)果如圖5a～圖5c所示，數(shù)據(jù)量為5 000 000條流，Sketch和桶大小為32，64,128時的誤差統(tǒng)計結(jié)果如圖5d～圖5f所示,數(shù)據(jù)量為10 000 000條流，Sketch和桶大小為32,64,128時的誤差統(tǒng)計結(jié)果如圖5g～圖5i所示。

Figure 5 Statistical results圖5 統(tǒng)計結(jié)果

將統(tǒng)計計數(shù)量與實際計數(shù)量作為誤差值，其中基礎版統(tǒng)計結(jié)果和優(yōu)化版統(tǒng)計結(jié)果如圖5所示，橫坐標x表示誤差值為2x-1～2x的數(shù)據(jù)，縱坐標表示具有該誤差數(shù)據(jù)的總量，將誤差不超過2的統(tǒng)計認定為準確的,準確率=準確數(shù)/過濾數(shù)據(jù)種類數(shù)。

當Sketch和桶大小比較小時，結(jié)果會出現(xiàn)誤差，但是總體上準確率也比較高，并且在Sketch和桶大小一定時，統(tǒng)計數(shù)據(jù)量越大，相對準確率越高，這是由于減小了由于數(shù)據(jù)統(tǒng)計量小帶來的偶然誤差。

對于熱流和冷流的分離，組相連優(yōu)化版本也減小了對熱碰撞以及冷流冒充熱流的誤差，并且在分離過程中數(shù)據(jù)量準確率高，丟失數(shù)據(jù)的概率比較低。隨著Sketch的增大，準確率也隨之提升，但是存儲空間也增大，因而在保證準確率的同時，取合適大小的Sketch也比較關鍵。隨著數(shù)據(jù)量的增大，準確率也隨之提升，減小了由于數(shù)據(jù)量過小帶來的偶然誤差。

5 結(jié)束語

本文針對大規(guī)模數(shù)據(jù)流統(tǒng)計中的典型結(jié)構(gòu)Elastic Sketch中冷熱流替換策略進行優(yōu)化，針對冷流第1次進入重部就替換熱流的問題進行了優(yōu)化，同時提出了基于最大值和組相連的替換策略，保證了重部中存儲的都是最大的流，解決了冷流頻繁替換熱流的問題，同時大大降低了熱流碰撞的概率。相比于傳統(tǒng)的測量統(tǒng)計方法，提高了統(tǒng)計精度，同時減少了內(nèi)存占用。