基于聚合的FlowRadar網絡數據采集加速模型設計*

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

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

1 引言

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

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

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

2 背景技術

2.1 FlowRadar采集方法概述

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

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

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

Figure 2 Data structure of FlowRadar圖2 FlowRadar數據結構

2.2 Agg-Evict加速方法概述

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

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

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

3 網絡大數據采集優化相關研究

網絡大數據采集在許多方面都可以通過優化來滿足日益增長的數據采集需求，例如數據流的存儲檢索、負載分配優化和查詢優化等。

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

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

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

4 基于聚合的網絡大數據采集加速

4.1 基于聚合的網絡大數據采集加速模型

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

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

4.2 報文聚合模塊設計

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

Figure 5 Structure of 16-cell aggregator and P4 code圖5 聚合器結構及對應代碼

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

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

4.3 流逐出模塊設計

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

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

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

4.4 逐出流數據采集

被逐出的流將進入標準的FlowRadar采集結構進行流信息采集，它會將同一條流的信息通過多個哈希函數分散計入Bloom Filter的多個位置，但對于報文計數器而言，此時一次性計入的將不是單個報文，而是逐出流所包含的所有報文數目，大大減少了多個哈希函數重復計算帶來的計算開銷和帶寬消耗。最后，FlowRadar將采集的數據提交到后端采集器進行單流解碼和網絡解碼，后續操作與FlowRadar原始架構一致。

5 仿真實驗測試

5.1 測試環境與測試拓撲

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

Table 1 Software and hardware configuration of the prototype system

Figure 7 Topology of the test network圖7 測試網絡拓撲圖

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

5.2 網絡吞吐量對比

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

Figure 8 Comparison of network throughput圖8 網絡吞吐量對比

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

5.3 處理時延對比

同時，本文對比測試了FlowRadar和聚合加速FlowRadar的雙向網絡時延，測試方式為h1 pingh2，每隔0.01 s測量一次，測量1 000個報文取平均值，測試結果如圖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都存在少量的時延抖動。但是，從總體上看，在相同的網絡拓撲及相同的終端和交換機中，聚合加速FlowRadar的網絡時延要低于原始FlowRadar的。兩者的時延在數據量增加的過程中，由于單個的FlowRadar在全時段具有對流的恒定處理時間，前期時延數據有所波動，后期趨于穩定；而聚合加速的FlowRadar則由于報文逐出過程中數據量的處理會劇增，前期時延數據同樣有所波動，后期的時延還是存在波動狀況。兩者前期都存在數據量異常波動的原因是每次測試都要重啟網絡拓撲，軟件環境還不是很穩定。

測試時間間隔為0.1 s的結果如圖10所示?？梢钥闯觯诟蟮臅r間粒度和范圍下(0.1 s)，聚合加速的FlowRadar和原始的FlowRadar的延遲時間都存在較大波動。在粗粒度的時間間隔觀察下，兩者的數據波動差異不明顯。從總體上，在相同的網絡拓撲及相同的終端和交換機中，聚合加速的FlowRadar延遲要低于原始FlowRadar的延遲。

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

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

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

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

6 結束語

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