基于聚合的FlowRadar網(wǎng)絡(luò)數(shù)據(jù)采集加速模型設(shè)計*

呂高鋒，王玉鵬，楊鎔嘉，唐 竹

(1.國防科技大學(xué)計算機學(xué)院，湖南 長沙 410073；2.78156部隊,甘肅 定西 748100)

1 引言

目前，已存在多種針對大規(guī)模網(wǎng)絡(luò)的狀態(tài)屬性采集方法，這些方法在流量覆蓋、軟硬件開銷和帶寬資源占用等方面各有優(yōu)缺點。例如，早期的數(shù)據(jù)采集主要基于簡單網(wǎng)絡(luò)管理協(xié)議SNMP(Simple Network Management Protocol)[1]，但由于SNMP通常采用輪詢的方式采集設(shè)備信息，在擁有很多設(shè)備的大型網(wǎng)絡(luò)中，輪詢流量容易導(dǎo)致網(wǎng)絡(luò)擁塞，并且其支持的信息量也很小。因此，Cisco推出了NetFlow協(xié)議[2,3]來實現(xiàn)流量監(jiān)控，但會導(dǎo)致較高的CPU開銷和內(nèi)存負擔(dān)。為了降低交換機或路由器的CPU開銷和內(nèi)存負擔(dān)，基于專用芯片支持的sFlow[4]技術(shù)應(yīng)運而生。隨著采集技術(shù)的發(fā)展，基于Sketch的數(shù)據(jù)采集方法(如SketchVisor[5]、CountMax[6]、Sketchlearn[7]和SpreadSketch[8]等)被提出，該類方法采用更緊湊的數(shù)據(jù)結(jié)構(gòu)，以固定大小的內(nèi)存匯總所有數(shù)據(jù)包的流量統(tǒng)計信息，具有更低的資源消耗，同時只產(chǎn)生有界的錯誤率。然而，現(xiàn)有基于Sketch的測量方案在高流量負載下會出現(xiàn)嚴(yán)重的性能下降，將其應(yīng)用于網(wǎng)絡(luò)測量時會不可避免地帶來巨大的計算開銷。

隨著數(shù)據(jù)平面可編程技術(shù)的不斷發(fā)展，由數(shù)據(jù)包內(nèi)嵌自定義統(tǒng)計信息的帶內(nèi)測量方法成為熱點，同時很多Sketch方法也可以基于數(shù)據(jù)平面可編程語言P4進行快速高效的實現(xiàn)，大大降低了軟件實現(xiàn)的資源開銷和芯片流片的代價成本。FlowRadar[9]測量方法即以P4語言為實現(xiàn)基礎(chǔ)，但與Sketch類方法對數(shù)據(jù)流進行概率采樣或近似估計不同，F(xiàn)lowRadar使用全采樣的方法提取流的五元組信息以及流、分組計數(shù)，可實現(xiàn)數(shù)據(jù)中心等大流量情況下的全局流分析。但是，由于在匹配流和更新計數(shù)器的過程中FlowRadar采用了Bloom Filter，導(dǎo)致該方法在哈希計算過程中存在較大的計算開銷和隨機內(nèi)存訪問開銷。

針對上述問題，本文結(jié)合Agg-Evict(聚合-逐出)[10]快速聚合思想，通過減少FlowRadar在匹配流和更新計數(shù)器過程中哈希計算所產(chǎn)生的開銷，減少網(wǎng)絡(luò)設(shè)備數(shù)據(jù)統(tǒng)計開銷，從而提高數(shù)據(jù)轉(zhuǎn)發(fā)的吞吐量，滿足網(wǎng)絡(luò)海量數(shù)據(jù)量采集需求。

2 背景技術(shù)

2.1 FlowRadar采集方法概述

FlowRadar作為一種全時段全采樣的數(shù)據(jù)流統(tǒng)計方法，解決了NetFlow無法處理海量數(shù)據(jù)流的不足。FlowRadar的設(shè)計關(guān)鍵點是如何在給定的有限流處理時間內(nèi)，在Hash表中維護流的五元組以及流計數(shù)和分組計數(shù)，同時保持較小的占用內(nèi)存和具有恒定的流處理時間。FlowRadar的流處理過程如圖1[9]所示，當(dāng)一個數(shù)據(jù)包到來時，F(xiàn)lowRadar首先提取數(shù)據(jù)包的五元組字段，同時檢查流過濾器判定該流是否已經(jīng)被存儲在流的集合中。如果該數(shù)據(jù)包來自一個新的流，F(xiàn)lowRadar首先更新計數(shù)器表，這包含流異或操作、增加流計數(shù)和報文計數(shù)。如果一個數(shù)據(jù)包是已經(jīng)存在的流，F(xiàn)lowRadar只增加報文計數(shù)。最后，F(xiàn)lowRadar在恒定的短時間內(nèi)，定期地將這些編碼后的數(shù)據(jù)信息發(fā)送到遠程采集器進行解碼。

Figure 1 Flow processing of FlowRadar圖1 FlowRadar流處理

FlowRadar的數(shù)據(jù)結(jié)構(gòu)由流過濾器和計數(shù)器表2部分組成[9]，具體如圖2所示。對于如何解決在Hash過程中產(chǎn)生的流沖突問題，F(xiàn)lowRadar首先將同一流散列到多個位置(如Bloom Filter)，這樣其中一個單元格中的一個流與另一個流碰撞的可能性就降低了。當(dāng)多個流落在同一個單元格中時，如果將它們存儲在一個鏈接表中開銷會很大，F(xiàn)lowRadar則使用異或函數(shù)來對同一個單元格產(chǎn)生沖突的流五元組信息以及計數(shù)器進行編碼。因此，F(xiàn)lowRadar可以在多個流共享的固定大小的內(nèi)存單元格中工作，并且對所有流都有固定的更新和插入時間。

Figure 2 Data structure of FlowRadar圖2 FlowRadar數(shù)據(jù)結(jié)構(gòu)

2.2 Agg-Evict加速方法概述

為了進行聚合更新以節(jié)省計算和內(nèi)存訪問，Agg-Evict設(shè)計了如圖3[10]所示的加速框架，其中聚合器包含k個KV(Key Value)數(shù)組，每個數(shù)組有l(wèi)個KV對，每個KV對的Key部分存儲流id，Value部分存儲相應(yīng)的聚合頻率。

Figure 3 Framework of Agg-Evict圖3 Agg-Evict加速框架示意圖

該框架將網(wǎng)絡(luò)測量分為2個階段：聚合和逐出。在聚合階段，框架主動針對所有入站數(shù)據(jù)包聚合流id，并將唯一的流id與其聚合頻率存儲在一個稱為聚合器的數(shù)據(jù)結(jié)構(gòu)中，同時使用一些連續(xù)的內(nèi)存訪問(高緩存位置)。在逐出階段，當(dāng)聚合器滿時，一次將存儲在其中的一些流id及其聚合頻率逐出到現(xiàn)有的測量解決方案中，進行聚合更新，從而獲得次線性處理時間[10]。但是，該方案以特定CPU的SSE2 SIMD指令進行KV查詢和匹配，提高了流id哈希值與KV對的匹配判定效率，不適合于通用交換芯片或P4處理器架構(gòu)。因此，本文基于協(xié)議無關(guān)交換架構(gòu)，采用P4語言重新設(shè)計實現(xiàn)了該加速框架，并進行了實驗驗證。

3 網(wǎng)絡(luò)大數(shù)據(jù)采集優(yōu)化相關(guān)研究

網(wǎng)絡(luò)大數(shù)據(jù)采集在許多方面都可以通過優(yōu)化來滿足日益增長的數(shù)據(jù)采集需求，例如數(shù)據(jù)流的存儲檢索、負載分配優(yōu)化和查詢優(yōu)化等。

在數(shù)據(jù)流的存儲優(yōu)化方面，由于數(shù)據(jù)流的存儲和分析需要高性能的硬件和軟件，針對集中式IP流收集的方法缺乏可擴展性，易遭受單點故障，并且隨著存儲的IP流記錄數(shù)的增加，流檢索性能不斷降低。DIPStorage(Distributed Storage of IP Flow records)[11]方法設(shè)計了一個可擴展的IP流記錄存儲平臺，其體系結(jié)構(gòu)建立在P2P概念之上，采用共享資源方式的分布式哈希表DHT(Distri- buted Hash Table)存儲IP流記錄的子集。原型系統(tǒng)評估顯示，該方法可有效存儲和檢索大量的IP流記錄。

在負載分配優(yōu)化方面，基于Sketch的測量面臨的關(guān)鍵挑戰(zhàn)是如何以最少的資源利用率接受更多的并發(fā)測量任務(wù)，COSTA(Cross-layer Optimization for Sketch-based Software difined measurement Task Assignment)[12]方法設(shè)計了基于Sketch的跨層優(yōu)化測量系統(tǒng)，在測量應(yīng)用精度和資源使用之間達到了不同程度的平衡和優(yōu)化。該系統(tǒng)利用應(yīng)用層和任務(wù)分配層之間的跨層信息，估計應(yīng)用層和資源使用情況，在管理層中查找具有足夠可用資源的設(shè)備以分配這些應(yīng)用程序。該方法將分配問題描述為一個混合整數(shù)非線性規(guī)劃問題，并開發(fā)了一個兩階段啟發(fā)式算法來有效地分配任務(wù)。通過對真實數(shù)據(jù)包跟蹤的大量實驗，證明了COSTA可以減少40%的資源使用，并可額外接受30%以上的任務(wù)，同時只有很小的準(zhǔn)確度損失。

在查詢優(yōu)化方面，ShBF(Shift Bloom Filter)[13]設(shè)計了一種用于表示和查詢集合的框架，可以使用少量內(nèi)存快速進行3種常見的集合查詢(成員查詢、關(guān)聯(lián)查詢和多重查詢)。ShBF提出在位置偏移量中對集合元素的輔助信息進行編碼，而不是對集合數(shù)據(jù)結(jié)構(gòu)分配額外的內(nèi)存來存儲輔助信息，通過對3種查詢類型的ShBF進行分析建模，計算出最優(yōu)系統(tǒng)參數(shù)。測試結(jié)果表明，ShBF在3種類型的集合查詢上都有顯著的性能提升。

4 基于聚合的網(wǎng)絡(luò)大數(shù)據(jù)采集加速

4.1 基于聚合的網(wǎng)絡(luò)大數(shù)據(jù)采集加速模型

基于聚合的網(wǎng)絡(luò)大數(shù)據(jù)采集加速模型如圖4所示，所有報文依據(jù)五元組信息歸類為不同的數(shù)據(jù)流，聚合器根據(jù)報文所屬的數(shù)據(jù)流進行歸類統(tǒng)計。該聚合器的處理過程主要包括聚合和逐出2部分，通過將多次更新聚合為一次更新來降低傳統(tǒng)大數(shù)據(jù)采集方法的計算開銷。聚合后的報文再進入FlowRadar進行信息采集，最后發(fā)送到后端控制器進行解碼分析。

Figure 4 Overall process of aggregation-based acceleration for FlowRadar圖4 聚合加速FlowRadar總流程

4.2 報文聚合模塊設(shè)計

為了減少每個報文都進行哈希計算所導(dǎo)致的巨大計算開銷和隨機內(nèi)存訪問開銷，本文參考Agg-Evict框架設(shè)計了聚合器數(shù)據(jù)結(jié)構(gòu)來主動聚合數(shù)據(jù)報文，從而更有效地處理聚合流，并且不依賴同一批數(shù)據(jù)中的數(shù)據(jù)報文訪問同一條目的概率。圖5展示了包含16個單元格的聚合器結(jié)構(gòu)，該聚合器包含4個KV數(shù)組對，每個KV數(shù)組對包含4個單元格，每個單元格中記錄了K值(報文五元組信息)和V值(分組計數(shù)器)。

Figure 5 Structure of 16-cell aggregator and P4 code圖5 聚合器結(jié)構(gòu)及對應(yīng)代碼

具體處理流程如圖6中報文聚合部分所示。當(dāng)數(shù)據(jù)流到達時，聚合器首先將數(shù)據(jù)流解析后的五元組通過一個快速哈希函數(shù)映射到4個KV數(shù)組對的任意一個，然后與KV數(shù)組對的4個單元格中的K值進行匹配。若匹配，則分組計數(shù)器V值增加；若不匹配，則查找空的單元格插入流的五元組K值，并將V值置1；若不匹配且無空的單元格時，則執(zhí)行相應(yīng)的逐出策略產(chǎn)生新的空KV數(shù)組對后插入。通常每次逐出的流id包含1個以上的報文數(shù)量，而傳統(tǒng)FlowRadar方案每次只處理1個報文，因此采用聚合更新方式可減少大量計算和隨機內(nèi)存訪問開銷。

此外，在計算開銷和隨機內(nèi)存訪問開銷降低方面，本文舉例說明。假設(shè)網(wǎng)絡(luò)有9個流id為f1、f2、f3、f1、f3、f1、f2、f1和f1的傳入數(shù)據(jù)包。通常情況下，需要更新FlowRadar的計數(shù)器9次，即需要進行9次哈希計算和9次隨機內(nèi)存訪問。使用聚合方法之后，首先將9個報文聚合為3個具有相同流id的報文集合：f1*5、f2*2和f3*2，然后將聚合結(jié)果導(dǎo)出到FlowRadar中。這樣只需進行3次更新(即3次哈希計算和3次隨機內(nèi)存訪問)。通過這種方式，在不考慮聚合操作所引入額外開銷的前提下，F(xiàn)lowRadar的處理速度理論上可以提高3倍。

4.3 流逐出模塊設(shè)計

逐出策略決定當(dāng)KV數(shù)組已滿時應(yīng)逐出哪一條流，它決定了聚合器的聚合級別，對聚合性能具有重要影響。常見的選擇策略是LRU(Least Recently Used)，它為每個KV對維護一個時間戳，記錄上一次更新該KV對的時間。一旦需要逐出一個KV對時，需要找到擁有最小時間戳的KV對并逐出。由于LRU每次逐出需要掃描各個時間戳，其實現(xiàn)開銷相對較高。

為了減少操作開銷，本文采用了GRR(Global Round Robin)逐出策略。該策略對于k個KV陣列，保持一個從0到m-1(m

總體而言，不同的逐出策略不影響測量方案的精度，而只影響測量方案所看到的分組輸入順序。

4.4 逐出流數(shù)據(jù)采集

被逐出的流將進入標(biāo)準(zhǔn)的FlowRadar采集結(jié)構(gòu)進行流信息采集，它會將同一條流的信息通過多個哈希函數(shù)分散計入Bloom Filter的多個位置，但對于報文計數(shù)器而言，此時一次性計入的將不是單個報文，而是逐出流所包含的所有報文數(shù)目，大大減少了多個哈希函數(shù)重復(fù)計算帶來的計算開銷和帶寬消耗。最后，F(xiàn)lowRadar將采集的數(shù)據(jù)提交到后端采集器進行單流解碼和網(wǎng)絡(luò)解碼，后續(xù)操作與FlowRadar原始架構(gòu)一致。

5 仿真實驗測試

5.1 測試環(huán)境與測試拓撲

原型系統(tǒng)采用Ubuntu 14.04虛擬機進行搭建，虛擬機軟硬件配置如表1所示，搭建的簡單網(wǎng)絡(luò)環(huán)境如圖7所示。系統(tǒng)基于Mininet構(gòu)建2個bmv2交換機，每個交換機接入2個終端，交換機上運行修改后的FlowRadar P4程序以實現(xiàn)聚合加速采集功能。

Table 1 Software and hardware configuration of the prototype system

Figure 7 Topology of the test network圖7 測試網(wǎng)絡(luò)拓撲圖

聚合加速模型通過降低計算開銷和訪存次數(shù)來提升采集性能，但上述2個指標(biāo)并不能說明加速方法的有效性，因為在計算開銷和訪存次數(shù)減少的同時，本文所提方法在報文聚合和流逐出階段會帶來額外的開銷，因此仿真實驗以系統(tǒng)總體的吞吐量和處理延時作為評價指標(biāo)。

5.2 網(wǎng)絡(luò)吞吐量對比

本文在6個節(jié)點的網(wǎng)絡(luò)拓撲中，對比測試了原始FlowRadar和聚合加速FlowRadar的網(wǎng)絡(luò)性能，即終端h1、h2之間的網(wǎng)絡(luò)吞吐量。實驗通過iperf發(fā)送TCP流量，每隔0.5 s測量一次，測量時間為300 s，具體結(jié)果如圖8所示。

Figure 8 Comparison of network throughput圖8 網(wǎng)絡(luò)吞吐量對比

由圖8可知，在更大的時間尺度范圍內(nèi)單個的FlowRadar的測試帶寬平均值為72.28 Mb/s，基于聚合的FlowRadar的測試帶寬的平均值為108.87 Mb/s。從總體上看，聚合加速的FlowRadar仍比單個的FlowRadar的帶寬提高36 Mb/s左右，吞吐量性能提升約50.63%。同樣地，單個的FlowRadar帶寬波動幅度比較小，聚合加速的FlowRadar帶寬在某些時刻，由于聚合模塊報文逐出時處理數(shù)據(jù)流較大的原因會有驟降的現(xiàn)象，但在其余時刻其帶寬更加趨于穩(wěn)定。

5.3 處理時延對比

同時，本文對比測試了FlowRadar和聚合加速FlowRadar的雙向網(wǎng)絡(luò)時延，測試方式為h1 pingh2，每隔0.01 s測量一次，測量1 000個報文取平均值，測試結(jié)果如圖9所示。

Figure 9 Comparison of bidirectional network delay when the time interval is 0.01 s圖9 時間間隔為0.01 s時的雙向時延對比

由圖9可知，在0.01 s的時間間隔下，聚合加速的FlowRadar和原始的FlowRadar都存在少量的時延抖動。但是，從總體上看，在相同的網(wǎng)絡(luò)拓撲及相同的終端和交換機中，聚合加速FlowRadar的網(wǎng)絡(luò)時延要低于原始FlowRadar的。兩者的時延在數(shù)據(jù)量增加的過程中，由于單個的FlowRadar在全時段具有對流的恒定處理時間，前期時延數(shù)據(jù)有所波動，后期趨于穩(wěn)定；而聚合加速的FlowRadar則由于報文逐出過程中數(shù)據(jù)量的處理會劇增，前期時延數(shù)據(jù)同樣有所波動，后期的時延還是存在波動狀況。兩者前期都存在數(shù)據(jù)量異常波動的原因是每次測試都要重啟網(wǎng)絡(luò)拓撲，軟件環(huán)境還不是很穩(wěn)定。

測試時間間隔為0.1 s的結(jié)果如圖10所示。可以看出，在更大的時間粒度和范圍下(0.1 s)，聚合加速的FlowRadar和原始的FlowRadar的延遲時間都存在較大波動。在粗粒度的時間間隔觀察下，兩者的數(shù)據(jù)波動差異不明顯。從總體上，在相同的網(wǎng)絡(luò)拓撲及相同的終端和交換機中，聚合加速的FlowRadar延遲要低于原始FlowRadar的延遲。

Figure 10 Comparison of bidirectional network delay when the time interval is 0.1 s圖10 當(dāng)時間間隔為0.1 s時的雙向時延對比

測試時間間隔為1 s的結(jié)果如圖11所示，在最大的時間粒度和范圍下(1 s)測試1 000個數(shù)據(jù)包的延遲，除去兩者都有的個別異常劇增的延遲數(shù)據(jù)，在相同的網(wǎng)絡(luò)拓撲及相同的終端和交換機中，聚合加速FlowRadar的延遲總體上要低于原始FlowRadar的延遲，并且兩者異常波動的數(shù)據(jù)相差無幾，其原因可以歸結(jié)于軟件環(huán)境的影響。

Figure 11 Comparison of bidirectional network delay when the time interval is 1 s圖11 當(dāng)時間間隔為1 s時的雙向時延對比

綜合以上3組測試結(jié)果來看，采用聚合加速FlowRadar的交換機處理時延總體上要低于原始FlowRadar的。但是，在時延抖動方面，在細粒度的時間維度下，基于聚合加速的FlowRadar由于采用報文聚合和逐出機制會造成較大的時延抖動；在粗粒度的時間維度下，兩者的時延抖動相差不大。

6 結(jié)束語

本文對網(wǎng)絡(luò)大數(shù)據(jù)采集優(yōu)化方案進行了研究，基于協(xié)議無關(guān)交換架構(gòu)PISA(Protocol Independent SwitchArch)，采用P4語言設(shè)計實現(xiàn)了面向報文聚合的FlowRadar數(shù)據(jù)采集加速模型，將屬于同一流的報文進行聚合，降低FlowRadar中使用多次哈希操作所導(dǎo)致的計算開銷和內(nèi)存訪問次數(shù)。最后，本文基于Mininet搭建原型系統(tǒng)進行功能驗證與性能測試，實驗結(jié)果表明，聚合加速的FlowRadar在網(wǎng)絡(luò)吞吐量和處理時延等方面的性能要優(yōu)于原始FlowRadar模型。