基于自適應(yīng)閾值的大象流檢測方法

劉 奕，李建華，陳 玉

1.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安 710077

2.空軍工程大學(xué) 研究生院，西安 710038

數(shù)據(jù)中心網(wǎng)絡(luò)[1]作為聯(lián)合裝備網(wǎng)絡(luò)的核心，對戰(zhàn)場信息進(jìn)行存儲和處理，實(shí)現(xiàn)各軍種裝備信息實(shí)時共享。隨著武器裝備和信息技術(shù)的發(fā)展，數(shù)據(jù)中心網(wǎng)絡(luò)通信量迅速增加，容易導(dǎo)致鏈路擁塞甚至中斷，此時需要對網(wǎng)絡(luò)中的異常流量進(jìn)行準(zhǔn)確檢測，實(shí)現(xiàn)數(shù)據(jù)中心網(wǎng)絡(luò)流量的實(shí)時監(jiān)控和有效調(diào)度，從而提高鏈路傳輸?shù)姆€(wěn)定性和可靠性。

目前，針對數(shù)據(jù)中心網(wǎng)絡(luò)流量研究顯示[2-4]，數(shù)據(jù)中心的流量呈現(xiàn)“大小流”特性：9%的流發(fā)送的視頻或語音等數(shù)據(jù)占網(wǎng)絡(luò)總數(shù)據(jù)量的90%，此類流被稱為“大象流”，而數(shù)量巨大但字節(jié)小于10 KB的文本或命令字等數(shù)據(jù)流被稱為“老鼠流”。大象流具有數(shù)量少、持續(xù)時間長、帶寬需求大的特點(diǎn)；老鼠流具有數(shù)量大、持續(xù)時間短、帶寬需求小的特點(diǎn)。而且流的到達(dá)和離開非常快，使得SDN[5]（software defined network）控制器很難為每個新流均能分配資源。同時，大量的異常流量會導(dǎo)致控制器被頻繁調(diào)用，從而降低了控制器的工作性能和可擴(kuò)展性。常用大象流檢測方法包括基于用戶終端的檢測方法和基于網(wǎng)絡(luò)鏈路的檢測方法兩種，文獻(xiàn)[6]通過統(tǒng)計終端主機(jī)的套接字緩沖區(qū)來檢測大象流，并通過帶內(nèi)信令的方式向網(wǎng)絡(luò)控制器發(fā)送檢測信號。文獻(xiàn)[7-8]提出了一種基于OpenFlow[9]協(xié)議的分層統(tǒng)計提取機(jī)制來檢測大象流，通過控制器實(shí)時統(tǒng)計流表信息，根據(jù)IP地址計算出單個流的大小。文獻(xiàn)[6-8]方法均屬于基于用戶終端的檢測方法，該類方法能夠有效減少網(wǎng)絡(luò)帶寬資源消耗，但在大象流檢測過程中采用了靜態(tài)閾值的方式，沒有考慮數(shù)據(jù)中心網(wǎng)絡(luò)特性變化，當(dāng)閾值設(shè)置過高，會出現(xiàn)較高的漏報率，從而導(dǎo)致大量的大象流無法被準(zhǔn)確檢測，當(dāng)閾值設(shè)置過低，會檢測到過多的老鼠流，容易導(dǎo)致路徑擁塞。文獻(xiàn)[10]利用控制器以輪詢的方式統(tǒng)計當(dāng)前各鏈路網(wǎng)絡(luò)的流量信息，當(dāng)數(shù)據(jù)流量超過10%的鏈路帶寬時，即可看作是大象流。由于數(shù)據(jù)中心的流量傳輸速率越來越快，導(dǎo)致該方法較高的丟包率和漏檢率，容易造成鏈路擁塞。文獻(xiàn)[11]提出一種流量采樣的檢測方法，通過計算采樣數(shù)據(jù)的統(tǒng)計特征來判斷鏈路的網(wǎng)絡(luò)流量，該方法通過增加流量采樣率可以有效提高檢測正確率，但是會降低鏈路利用率。文獻(xiàn)[12]利用最久未用（least recent used，LRU）機(jī)制，首先利用第一級的LRU過濾大部分老鼠流，然后通過第二級的LRU對大象流進(jìn)行計數(shù)和檢測，該方法可以降低老鼠流置換LRU緩存中大象流的概率，有效降低了大象流的漏檢率。文獻(xiàn)[13-14]將LRU機(jī)制和布魯姆過濾器（bloom filter，BF）機(jī)制相結(jié)合，提出一種基于LRU.BF策略的大象流檢測方法，首先利用BF方法來檢測是否存在大象流，然后結(jié)合LRU方法對大象流進(jìn)行過濾，通過將大象流的過濾和判斷相分離方式，降低了大象流的漏檢率。

綜上所述，本文提出一種自適應(yīng)閾值的大象流量檢測方法，采用動態(tài)流量學(xué)習(xí)（dynamic traffic learning，DTL）方法實(shí)時計算更新閾值，從而完成數(shù)據(jù)中心網(wǎng)絡(luò)中低延遲、低開銷的大象流檢測識別。首先通過控制器發(fā)送一組流量統(tǒng)計請求來獲取交換機(jī)的流量統(tǒng)計信息，然后分析流量特征與大象流之間的關(guān)系，通過基于高斯分布加權(quán)優(yōu)化的DTL方法動態(tài)學(xué)習(xí)快速變化的數(shù)據(jù)中心流量來預(yù)測檢測閾值，為了提高大象流檢測的準(zhǔn)確性，防止流表發(fā)生抖動，采用差分估計的閾值平滑機(jī)制，降低檢測閾值配置更新頻率。最后利用控制器將檢測閾值配置至觸發(fā)器，當(dāng)流量的測量值（如流量的大小和持續(xù)時間）超過設(shè)置的檢測閾值時，觸發(fā)器將其判斷為大象流，從而實(shí)現(xiàn)大象流實(shí)時自適應(yīng)檢測分類。

1 算法原理

1.1 系統(tǒng)架構(gòu)

針對數(shù)據(jù)中心網(wǎng)絡(luò)靜態(tài)閾值檢測錯誤率高的問題，提出了一種基于DTL自適應(yīng)閾值的大象流檢測系統(tǒng)，利用DTL方法對流量進(jìn)行檢測，并對閾值進(jìn)行實(shí)時動態(tài)自適應(yīng)配置，不需要對OpenFlow協(xié)議進(jìn)行額外的修改，控制平面幾乎沒有增加工作量，保證了方法的實(shí)用性，大象流檢測系統(tǒng)架構(gòu)如圖1所示。

圖1中給出本文大象流檢測系統(tǒng)由流量統(tǒng)計分析模塊和閾值計算配置模塊組成，其中流量統(tǒng)計分析模塊為了能夠動態(tài)地滿足數(shù)據(jù)中心流量特性要求，定期從交換機(jī)收集流量統(tǒng)計信息并在流量收集器中更新，分析器從流量收集器中收集合適的特征作為后續(xù)處理的訓(xùn)練數(shù)據(jù)。閾值計算配置模塊首先將分析器發(fā)送的流量統(tǒng)計信息作為訓(xùn)練數(shù)據(jù)，根據(jù)流量特征建立合適的數(shù)學(xué)模型，然后利用加權(quán)優(yōu)化方法對閾值進(jìn)行預(yù)測，最后采用平滑機(jī)制將預(yù)測的檢測閾值與已配置的檢測閾值進(jìn)行比較，判斷是否在大象流分類的觸發(fā)器中配置預(yù)測閾值。該系統(tǒng)的控制器不再收集流量統(tǒng)計信息來對大象流進(jìn)行分類，而是通過分析器定期收集流量統(tǒng)計信息，使訓(xùn)練數(shù)據(jù)滿足流量特性的要求，同時利用加權(quán)優(yōu)化和平滑機(jī)制使預(yù)測閾值更加準(zhǔn)確，進(jìn)一步防止流表的波動，降低檢測錯誤率。

圖1 自適應(yīng)閾值大象流檢測系統(tǒng)Fig.1 Adaptive threshold elephant flow detection system

1.2 DTL算法

首先定義p i為流量收集器每秒收集流量大小的流量統(tǒng)計數(shù)據(jù)（以字節(jié)為單位）。在Δt秒的時間內(nèi)，將合適的流量特征q j定義為式（1）：

如果在Δt秒內(nèi)的流量大小占總流量的比例遠(yuǎn)大于θ，就將該流量視為大象流。因此，可用q j來預(yù)測觸發(fā)器的閾值Th k。為了滿足數(shù)據(jù)中心流量特性要求，預(yù)測閾值Th k定義如式（2）所示：

其中，α表示連接Th k和q j的協(xié)同參數(shù)，k表示當(dāng)前時刻，N表示選擇q j的移動窗口，ψ表示預(yù)測閾值函數(shù)。在式（2）中，關(guān)鍵是如何找到協(xié)同參數(shù)α，為了解決此問題，本文將[qk-1,q k-2,…,q k-N] 視為數(shù)據(jù)組[Xn,Yn]，n=k-1,k-2,…,k-N，可假設(shè)在函數(shù)ψ中能夠找到類似ψ(X,α)∈ψ的解來使得E2最小，從而得到Thk=ψ(X k,α)，其中E2可表示為：

因此，可以將問題轉(zhuǎn)化為用N個數(shù)據(jù)估計使得E2最小的最優(yōu)化問題。采用最小二乘法對式（4）進(jìn)行求解，如式（5）所示：

其中，M表示ψ(X,α)的階數(shù)。為了提高預(yù)測閾值Th k的準(zhǔn)確性，利用加權(quán)優(yōu)化方法來優(yōu)化機(jī)器學(xué)習(xí)過程。引入?yún)?shù)ω來表示不同時間的重要性，ωk-1＞ωk-2＞…＞ωk-N，ω服從高斯分布?？蓪⑹剑?）的最小化問題轉(zhuǎn)化為式（9）形式：

為了降低機(jī)器學(xué)習(xí)方法的復(fù)雜度，采用正交三角（QR）分解法對其進(jìn)行分解簡化，QR分解定義如式（10）所示：

考慮到數(shù)據(jù)中心網(wǎng)絡(luò)信息流轉(zhuǎn)過程中流量特性要求，需要頻繁地更新預(yù)測閾值來實(shí)時、自適應(yīng)地識別大象流。當(dāng)控制器配置一個新的閾值觸發(fā)器時，將到達(dá)的流識別為大象流，并請求控制器計算非擁塞路徑。在控制器完成調(diào)度之后，交換器會分配一個新的流表來對該大象流進(jìn)行重新路由分配。下一時刻，如果最新的閾值將這個大象流識別為老鼠流，會立即刪除新分配的流表。這種情況不僅會導(dǎo)致大量的虛報率、漏報率和誤報率，而且會使流表產(chǎn)生劇烈抖動。

針對這一問題，本文引入流量檢測平滑機(jī)制。當(dāng)模塊接收到新的預(yù)測閾值時，首先根據(jù)差分估計來決定是否替換之前的閾值。

定義振幅比β如式（13）所示：

設(shè)置ε為平滑參數(shù)，τ為平滑時間。如果β≤ε，則認(rèn)為預(yù)測閾值將使流表產(chǎn)生抖動，以阻止控制器配置交換機(jī)。直到β＞ε的時間為τ時，預(yù)測閾值才被配置到交換機(jī)中。

根據(jù)上述分析，本文提出的DTL算法具體流程如下所示：

其中Thpre表示當(dāng)前配置的閾值，q表示式（1）中收集的訓(xùn)練值，Updata_threshold表示閾值更新主函數(shù)，Least_square_method表示本文簡化的最小二乘函數(shù)，Smooth_mechanism表示平滑機(jī)制函數(shù)。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)環(huán)境設(shè)置

為了有效檢驗(yàn)本文大象流檢測算法的可行性和有效性，實(shí)驗(yàn)采用OMnet++網(wǎng)絡(luò)仿真軟件，主要包括客戶端、交換機(jī)和與SDN兼容的控制器。在性能模擬中生成的TCP流的持續(xù)時間和大小的依據(jù)是在2018年9月16日從CAIDA網(wǎng)站（https：//www.caida.org/data）下載的第一級鏈路的2個路由器中收集的真實(shí)數(shù)據(jù)軌跡，使用分布式網(wǎng)絡(luò)流量生成器生成流量，OMnet++中配置的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)錇閒at-tree結(jié)構(gòu)。

實(shí)驗(yàn)運(yùn)行平臺的操作系統(tǒng)版本：Windows 2012 R2，CPU：Quad 3.47 GHz Intel Xeon?X5690，內(nèi)存：16 GB。

2.2 系統(tǒng)性能分析

首先分析檢測錯誤率與預(yù)測閾值函數(shù)階數(shù)M之間的關(guān)系，如圖2所示，錯誤率定義由式（14）所示：

其中，Thpredict表示預(yù)測閾值，Thstatistic表示統(tǒng)計的最優(yōu)閾值。由圖2可知，當(dāng)階數(shù)M≤2時，移動窗口數(shù)量對錯誤率影響較小，錯誤率小于20%。當(dāng)階數(shù)M＞2時，移動窗口數(shù)量對錯誤率影響較大。當(dāng)移動窗口數(shù)量N≤7時，錯誤率較高，隨著N繼續(xù)增加，錯誤率逐漸降低。當(dāng)移動窗口數(shù)N=7時，與M=3和M=4相比，M=2的錯誤率分別小于4.71%和15.34%，因此本文選取的預(yù)測閾值函數(shù)階數(shù)M=2。

圖2 基于不同M值的錯誤率Fig.2 Error rate based on different M values

圖3 是在M=2時，不同移動窗口數(shù)量條件下加權(quán)優(yōu)化的檢測錯誤率情況。由圖3可知，本文的加權(quán)優(yōu)化算法可以有效降低檢測錯誤率。隨著移動窗口數(shù)量N增加，檢測錯誤率逐漸降低，當(dāng)N≥7時，檢測錯誤率基本保持不變，相比N=2時最高檢測錯誤率相差大約5.62%，從圖2和3可以看出，設(shè)置M=2和N=7進(jìn)行加權(quán)優(yōu)化可以顯著降低錯誤率。

圖3 加權(quán)優(yōu)化后的錯誤率Fig.3 Error rate after weighted optimization

圖4 是不同計算方式下，四種閾值結(jié)果隨流量變化情況。由圖4可知，統(tǒng)計結(jié)果與訓(xùn)練結(jié)果相差不大，當(dāng)分析周期T=100和T=260時，網(wǎng)絡(luò)流量變化較快，與訓(xùn)練結(jié)果相比，固定閾值下滿足流量特性要求的結(jié)果相差較多?？紤]到如果控制器將每個訓(xùn)練結(jié)果均配置為觸發(fā)器來識別大象流，可能會增加控制平面上的開銷，同時頻繁的閾值配置會導(dǎo)致流表抖動。而經(jīng)過本文平滑處理之后的閾值不僅滿足了網(wǎng)絡(luò)中流量特征要求，而且也相應(yīng)地保持了閾值的不變性，有效減少了流表抖動。

圖4 平滑前后的動態(tài)閾值結(jié)果Fig.4 Dynamic threshold results before and after smoothing

圖5 是不同閾值計算方式下，錯誤率隨流量變化情況。由圖5可知，訓(xùn)練結(jié)果的錯誤率最低。在T≤100時平滑結(jié)果和固定值的錯誤率相同，在T≥100時由于流量的變化，固定閾值造成的錯誤率迅速增加，而平滑結(jié)果的錯誤率仍然保持在較低水平，訓(xùn)練結(jié)果與平滑結(jié)果之間的差異較小。

圖5 基于不同結(jié)果的錯誤率分析Fig.5 Error rate analysis based on different results

圖6 是不同檢測方法下，發(fā)送給控制器流轉(zhuǎn)信息流的最大數(shù)量情況。由圖6可知，由于OpenFlow協(xié)議需要每個信息流的狀態(tài)，所以發(fā)送的信息流數(shù)量最高。當(dāng)T=50時，流量變化較小，Mahout、Deveflow[15]和本文檢測系統(tǒng)發(fā)送給控制器的流轉(zhuǎn)信息流數(shù)量大約均為100，隨著網(wǎng)絡(luò)流量增加，Mahout和Deveflow兩種方法的流轉(zhuǎn)信息流數(shù)量迅速增加，而本文檢測系統(tǒng)的流轉(zhuǎn)信息流數(shù)量變化相對較少，幾乎保持不變。

圖6 流轉(zhuǎn)信息流的最大值Fig.6 Maximum value of information flow

2.3 系統(tǒng)開銷分析

針對數(shù)據(jù)中心網(wǎng)絡(luò)的流量特性要求，本文采用動態(tài)配置預(yù)測閾值的機(jī)器學(xué)習(xí)方法，并通過差分平滑機(jī)制減少閾值更新次數(shù)，降低了流表抖動，但該方法是否會增加控制平面的工作量及檢測時延決定了其可行性和實(shí)用性。

表1是三種方法在控制平面上更新觸發(fā)器的配置信息數(shù)量。由表1可知，隨著流量的快速變化，固定閾值方法更新的配置信息數(shù)量增長較為緩慢。在沒有平滑機(jī)制的條件下，使用訓(xùn)練結(jié)果會導(dǎo)致配置信息數(shù)量迅速增長，此時控制平面的開銷也會明顯增加，而在本文的平滑機(jī)制作用下，配置信息數(shù)量下降明顯，雖然略高于固定閾值的配置信息數(shù)量，但在可接受范圍內(nèi)。

表1 配置信息Table 1 Configuration information

圖7是三種方法的大象流檢測平均時間。其中檢測時延包括檢測器中的流分類時延、數(shù)據(jù)庫中的數(shù)據(jù)匹配時延和系統(tǒng)中的訓(xùn)練學(xué)習(xí)時延。由圖7可知，Mahout方法大約6 ms時延，主要是由于該檢測方法是在終端主機(jī)上運(yùn)行的。Deveflow方法采用隨機(jī)抽樣的方法，用大約25 ms的時間識別收集器中的大象流。本文流量檢測系統(tǒng)可以在35 ms內(nèi)檢測到大象流，而大象流的平均持續(xù)時間約為幾秒，本文流量檢測系統(tǒng)的檢測時延所占大象流總生存時間的比例較小。因此，本文提出的大象流檢測系統(tǒng)具有實(shí)際可行性，并且檢測的開銷和時延相對較低。

圖7 大象流檢測的平均時間Fig.7 Average time for elephant flow detection

3 結(jié)語

針對數(shù)據(jù)中心網(wǎng)絡(luò)大象流的檢測問題，提出一種基于動態(tài)流量學(xué)習(xí)自適應(yīng)閾值的大象流檢測系統(tǒng)，首先利用加權(quán)優(yōu)化方法對訓(xùn)練數(shù)據(jù)進(jìn)行閾值預(yù)測，然后通過差分估計的平滑機(jī)制減少閾值配置次數(shù)，降低了流表抖動。通過仿真實(shí)驗(yàn)表明：本系統(tǒng)能夠有效捕獲數(shù)據(jù)中心網(wǎng)絡(luò)信息流轉(zhuǎn)中快速變化的大象流，顯著降低了控制平面開銷，具有一定的可行性和有效性。