一種大象流兩級(jí)識(shí)別方法

（杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018）

一種大象流兩級(jí)識(shí)別方法

嚴(yán)軍榮，葉景暢，潘鵬

（杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018）

基于大象流的識(shí)別準(zhǔn)確度高且開銷低，對(duì)于解決SDN流量管理過程中控制器單點(diǎn)故障問題具有重要意義。針對(duì)現(xiàn)有大象流識(shí)別方法識(shí)別開銷大的問題，提出一種大象流兩級(jí)識(shí)別方法。該方法在第一階段提出基于TCP發(fā)送隊(duì)列的可疑大象流識(shí)別算法，在第二階段提出基于流持續(xù)時(shí)間的真實(shí)大象流識(shí)別算法；第一階段是在端系統(tǒng)中識(shí)別可疑大象流，用于降低第二階段真實(shí)大象流識(shí)別過程中SDN控制器所需監(jiān)測(cè)的網(wǎng)絡(luò)流數(shù)量。實(shí)驗(yàn)分析表明，在保證大象流識(shí)別的高準(zhǔn)確度前提下，大象流兩級(jí)識(shí)別方法較基于采樣的大象流識(shí)別方法可以降低約85%的控制器識(shí)別開銷。

大象流識(shí)別；TCP發(fā)送隊(duì)列；軟件定義網(wǎng)絡(luò)

1 引言

軟件定義網(wǎng)絡(luò)（software defined networking，SDN）是一種新型網(wǎng)絡(luò)架構(gòu)[1,2]，其通過剝離網(wǎng)絡(luò)設(shè)備的控制平面與數(shù)據(jù)轉(zhuǎn)發(fā)平面并將控制平面抽象為集中式控制器，為網(wǎng)絡(luò)提供了邏輯統(tǒng)一的轉(zhuǎn)發(fā)控制平臺(tái)，基于SDN特有的全網(wǎng)視圖可快速實(shí)現(xiàn)流量調(diào)度策略的制定以及交換機(jī)流表的配置。流量管理過程中，作為網(wǎng)絡(luò)大腦的SDN控制器需接收、處理海量數(shù)據(jù)以保證網(wǎng)絡(luò)的正常運(yùn)行，這對(duì)其性能提出巨大挑戰(zhàn)。為SDN控制器“減負(fù)”是避免控制器單點(diǎn)故障的有效方法，通過采用“抓大放小”的流量管理方式[3]，即精細(xì)管控大象流（傳輸數(shù)據(jù)量大、持續(xù)時(shí)間長(zhǎng)）、粗放管控老鼠流（傳輸數(shù)據(jù)量小、持續(xù)時(shí)間短）[4]，可有效減少控制器在大象流識(shí)別過程中的處理負(fù)載。因此，對(duì)SDN中的高準(zhǔn)確、低開銷的大象流識(shí)別方法進(jìn)行研究是很有必要的。

針對(duì)現(xiàn)有大象流識(shí)別算法識(shí)別開銷大的問題，本文考慮在端系統(tǒng)中預(yù)先識(shí)別并篩選出可疑大象流，以減少SDN控制器監(jiān)測(cè)網(wǎng)絡(luò)中大象流的開銷，從而提出一種大象流兩級(jí)識(shí)別方法。首先通過分析主機(jī)端數(shù)據(jù)流的尺寸特征實(shí)現(xiàn)第一階段可疑大象流的識(shí)別，然后通過SDN控制器監(jiān)測(cè)網(wǎng)絡(luò)中可疑大象流的持續(xù)時(shí)間特征實(shí)現(xiàn)第二階段真實(shí)大象流的識(shí)別，最后通過Mininet實(shí)驗(yàn)仿真驗(yàn)證大象流兩級(jí)識(shí)別方法性能。該方法包括在第一階段提出的基于TCP發(fā)送隊(duì)列的可疑大象流識(shí)別算法和在第二階段提出的基于流持續(xù)時(shí)間的真實(shí)大象流識(shí)別算法。其中，第一階段是在端系統(tǒng)中識(shí)別可疑大象流，用于降低第二階段真實(shí)大象流識(shí)別過程中SDN控制器所需監(jiān)測(cè)的網(wǎng)絡(luò)流數(shù)量。

2 相關(guān)工作

傳統(tǒng)大象流識(shí)別方法主要包括基于采樣的大象流識(shí)別方法、基于計(jì)數(shù)的大象流識(shí)別方法以及基于LRU（least recently used）的大象流識(shí)別方法[5]3種?；诓蓸拥拇笙罅髯R(shí)別算法通過提取、分析網(wǎng)絡(luò)流樣本數(shù)據(jù)分組的特征推導(dǎo)得到網(wǎng)絡(luò)整體流量的特征。NetFlow技術(shù)和sFlow技術(shù)是目前常用的兩種流采樣方法，Bi C H等人[6]提出一種適用于數(shù)據(jù)中心的大象流兩級(jí)識(shí)別系統(tǒng)，通過sFlow篩選出可疑流并通過控制器從可疑流中分析、識(shí)別大象流；Mori等人[7]提出一種基于Bayes原理計(jì)算大象流閾值并利用分組采樣方法采樣、識(shí)別大象流的方法，具有較高的識(shí)別準(zhǔn)確率但其識(shí)別開銷較大。

Robert等人[8]最早提出基于計(jì)數(shù)的大象流識(shí)別方法，基于“匹配—計(jì)數(shù)”的原理，通過統(tǒng)計(jì)監(jiān)測(cè)設(shè)備中流數(shù)據(jù)分組的匹配結(jié)果以實(shí)現(xiàn)網(wǎng)絡(luò)大象流的識(shí)別。Bai L等人[9]提出一種基于超時(shí)計(jì)數(shù)的大象流識(shí)別方法，利用多級(jí)布隆過濾器（bloom filter，BF）對(duì)數(shù)據(jù)進(jìn)行計(jì)數(shù)，以實(shí)現(xiàn)老鼠流的過濾和大象流的識(shí)別，流識(shí)別可靠性較高但BF實(shí)現(xiàn)較復(fù)雜。趙小歡等人[10]提出一種基于CBF-SS（counting bloom filter-space saving）的大象流識(shí)別方法，利用CBF剔除老鼠流并依據(jù)SS算法識(shí)別大象流，時(shí)間復(fù)雜度較低但識(shí)別實(shí)時(shí)性較差。

Smitha等人[11]提出了基于LRU的大象流識(shí)別算法，通過在一個(gè)大小固定的流記錄緩存置換流記錄，實(shí)現(xiàn)了高頻大象流的識(shí)別。參考文獻(xiàn)[12，13]通過在LRU算法前增加流過濾步驟以剔除網(wǎng)絡(luò)老鼠流，提高了LRU算法的大象流識(shí)別準(zhǔn)確性。謝冬青等人[14]提出一種基于LRU和SCBF（space code bloom filter）的大象流識(shí)別方法，將新入網(wǎng)數(shù)據(jù)流記錄于SCBF中并將滿足條件的流記錄提升至LRU頂部，通過LRU與SCBF間的淘汰循環(huán)機(jī)制實(shí)現(xiàn)大象流的快速匯聚，識(shí)別準(zhǔn)確性較高但其較復(fù)雜且實(shí)時(shí)性欠缺。

伴隨SDN技術(shù)的發(fā)展，基于SDN的大象流識(shí)別技術(shù)應(yīng)運(yùn)而生，利用SDN特有的全網(wǎng)視圖及強(qiáng)大的流量監(jiān)測(cè)能力可快速實(shí)現(xiàn)大象流的識(shí)別。在SDN中的流量信息采集方法主要包括主動(dòng)式和被動(dòng)式[15,16]兩種，其中被動(dòng)式又包括基于事件觸發(fā)和基于時(shí)序觸發(fā)兩種。Lin C Y等人[17]提出一種基于區(qū)域鎖定的大象流識(shí)別方法，首先依據(jù)分層統(tǒng)計(jì)原理追溯并鎖定大象流產(chǎn)生區(qū)域，然后利用SDN控制器針主動(dòng)查詢?cè)搮^(qū)域內(nèi)設(shè)備記錄的流信息以實(shí)現(xiàn)大象流的識(shí)別，該方法通過鎖定大象流產(chǎn)生區(qū)域有效降低控制器的主動(dòng)查詢開銷但其實(shí)現(xiàn)較復(fù)雜。Curtis等人[18]提出一種基于套接字緩存監(jiān)測(cè)的大象流識(shí)別方法，其識(shí)別實(shí)時(shí)性較高但未對(duì)端系統(tǒng)識(shí)別結(jié)果進(jìn)行修正。Chao等人[19]提出一種基于霍夫丁決策樹的大象流識(shí)別算法，控制器首先依據(jù)數(shù)據(jù)流持續(xù)時(shí)間篩選潛在大象流，然后分析潛在大象流數(shù)據(jù)分組的大小特征識(shí)別大象流，有效提高了大象流識(shí)別的準(zhǔn)確性，但該方法的控制器識(shí)別開銷很大。

3 研究?jī)?nèi)容

本文提出的大象流兩級(jí)識(shí)別方法如圖1所示。第一階段基于端系統(tǒng)的TCP發(fā)送隊(duì)列監(jiān)測(cè)實(shí)現(xiàn)可疑大象流識(shí)別，認(rèn)定發(fā)送隊(duì)列中數(shù)據(jù)量超過可疑流閾值的流為可疑大象流并對(duì)其標(biāo)記；第二階段基于SDN控制器的流量監(jiān)測(cè)功能實(shí)現(xiàn)真實(shí)大象流的識(shí)別，認(rèn)定網(wǎng)絡(luò)中持續(xù)時(shí)間超過特定值的可疑大象流為真實(shí)大象流。

3.1 第一階段識(shí)別

圖1 大象流兩級(jí)識(shí)別算法示意

該階段通過監(jiān)測(cè)端系統(tǒng)TCP發(fā)送隊(duì)列中數(shù)據(jù)流的尺寸特征實(shí)現(xiàn)可疑大象流的識(shí)別，為此提出一種基于TCP發(fā)送隊(duì)列的可疑大象流識(shí)別（suspicious elephant detection based on write queue，SED-WQ）算法。在數(shù)據(jù)發(fā)送初始階段（數(shù)據(jù)仍在主機(jī)緩存中），SED-WQ算法通過傳輸控制塊（transport control block,TCB）[20]啟用TCP_CORK選項(xiàng)暫時(shí)阻塞 TCP發(fā)送隊(duì)列，T0時(shí)間（T0值可設(shè)置）后遍歷 TCP發(fā)送隊(duì)列并統(tǒng)計(jì)其保存的總數(shù)據(jù)量，據(jù)此判斷該流是否為可疑大象流，標(biāo)記并發(fā)送識(shí)別出的可疑大象流。SED-WQ算法流程如圖2所示，具體步驟如下。

步驟1 本地主機(jī)與對(duì)端主機(jī)通過3次握手建立TCP連接并讀取elephant_detection值（該值初始值為0，表示未處理該流），如其值等于0，則調(diào)用sys_setsocketopt()函數(shù)開啟TCB的TCP_CORK選項(xiàng)，然后將elephant_detection值加1，進(jìn)入步驟2；如大于0，則表示該流類型已確定，直接進(jìn)入步驟8。

步驟2 定時(shí)調(diào)用skb_queue_empty()函數(shù)以監(jiān)測(cè)發(fā)送隊(duì)列是否為空，如函數(shù)返回true，表明發(fā)送隊(duì)列為空，繼續(xù)等待數(shù)據(jù)存入；如返回false，表明應(yīng)用程序開始產(chǎn)生數(shù)據(jù)并存入套接字緩存（SKB）[20]中，進(jìn)入步驟3。

步驟3 啟動(dòng)計(jì)時(shí)器1記錄時(shí)間t1，數(shù)據(jù)持續(xù)存入發(fā)送隊(duì)列SKB中直到t1＞T0，終止計(jì)時(shí)，進(jìn)入步驟5。

步驟4 讀取發(fā)送隊(duì)列鏈表頭 sk_buff_head保存的qlen值，從頭開始遍歷發(fā)送隊(duì)列中的qlen個(gè)SKB，依次讀取第i個(gè)SKB保存的len值并累加得到發(fā)送隊(duì)列中保存的總數(shù)據(jù)量queue_data，其中0＜i≤qlen。

步驟5 將queue_data與可疑流閾值M進(jìn)行比較，如果queue_data≥M，則認(rèn)定該流為可疑大象流，進(jìn)入步驟6；如果queue_data＜M，則認(rèn)定該流為老鼠流，進(jìn)入步驟7。

步驟6 通過 ipv4_change_dsfield()函數(shù)設(shè)置該流IP分組頭DSCP位為可疑流標(biāo)識(shí)符，本文定義可疑流標(biāo)識(shí)符為48（0x30），與之對(duì)應(yīng)的ToS值為192（0xC0）。

步驟7 調(diào)用 sys_setsocketopt()函數(shù)關(guān)閉 TCB的TCP_CORK選項(xiàng)，解除TCP發(fā)送隊(duì)列的阻塞狀態(tài)。

步驟8 正常發(fā)送數(shù)據(jù)。

其中，步驟1中提到的setsocketopt()函數(shù)用于獲取或設(shè)置相關(guān)聯(lián)的套接口選項(xiàng)（通過設(shè)置套接口選項(xiàng)可實(shí)現(xiàn)數(shù)據(jù)處理過程相關(guān)參數(shù)或行為的配置），函數(shù)參數(shù)包括socket、level、option_name、option_value以及 option_len這 5個(gè)，socket表示數(shù)據(jù)流的套接字描述符，level指表示調(diào)用的具體函數(shù)類型 （包括SOL_Socket類、SOL_TCP、Ipproto_IP類等），option_name表示待配置套接口選項(xiàng)名稱，option_value表示下發(fā)至內(nèi)核的數(shù)據(jù)，option_len表示下發(fā)的數(shù)據(jù)長(zhǎng)度。

3.2 第二階段識(shí)別

該階段通過對(duì)網(wǎng)絡(luò)中可疑大象流持續(xù)時(shí)間特征的分析實(shí)現(xiàn)真實(shí)大象流的識(shí)別，提出一種基于流持續(xù)時(shí)間的大象流識(shí)別（real elephant detection based on duration time，RED-DT）算法。RED-DT算法基于流持續(xù)時(shí)間特征在第一階段識(shí)別的基礎(chǔ)上對(duì)網(wǎng)絡(luò)中的可疑大象流進(jìn)行二次篩選，認(rèn)定持續(xù)時(shí)間大于T1（T1可設(shè)置）的可疑大象流為真實(shí)大象流，快速剔除了第一階段的誤識(shí)別大象流，保證了大象流識(shí)別算法的準(zhǔn)確性和實(shí)時(shí)性。該階段可通過控制器編寫識(shí)別應(yīng)用實(shí)現(xiàn)，利用SDN主動(dòng)向交換機(jī)請(qǐng)求可疑大象流的統(tǒng)計(jì)信息如命中流表項(xiàng)的累計(jì)字節(jié)數(shù)、命中該流表項(xiàng)的累計(jì)分組數(shù)，如兩次請(qǐng)求所得統(tǒng)計(jì)量發(fā)生改變則可認(rèn)定該可疑大象流仍存在，可認(rèn)定其為真實(shí)大象流。RED-DT算法流程如圖3所示，具體步驟如下。

圖2 第一階段SED-WQ算法流程

步驟1 通過packet_in_handler()函數(shù)解析packet_in消息[21]，然后利用get_protocol()方法獲取該流數(shù)據(jù) IP數(shù)據(jù)分組頭TOS值。

步驟2 將所得TOS值與192進(jìn)行比較（可疑大象流標(biāo)識(shí)符為192），如TOS=192，則認(rèn)定該流為第一階段識(shí)別出的可疑流并將該流相關(guān)信息包括 datapath、table_id、match以及status（默認(rèn)值為suspicious）等記錄在大象流列表中，進(jìn)入步驟3；如TOS≠192，則認(rèn)定該流為老鼠流。

步驟3 啟動(dòng)計(jì)時(shí)器2用于記錄時(shí)間t，在t=T1與t= T1+T這兩個(gè)時(shí)刻，Ryu控制器通過 ofp_flow_stats_request流請(qǐng)求消息向交換機(jī)查詢可疑流相關(guān)信息。

步驟4 Ryu解析交換機(jī)返回的兩個(gè)ofp_flow_stats_reply消息，獲取T1與T1+T時(shí)刻計(jì)數(shù)器統(tǒng)計(jì)的累積命中字節(jié)數(shù)并記為b1、b2。如b1=b2，則認(rèn)定該可疑大象流為老鼠流，將其從大象流列表中刪除；如 b1≠b2，則認(rèn)定該可疑大象流為真實(shí)大象流，修改大象流列表中該流status屬性為real，表明該流為大象流。其中大象流列表見表1。

圖3 第二階段識(shí)別RED-DT算法流程

表1 大象流列表

3.3 性能分析

首先對(duì)大象流兩級(jí)識(shí)別算法兩個(gè)階段的識(shí)別過程進(jìn)行分析，然后通過仿真將大象流兩級(jí)識(shí)別算法與基于采樣的大象流識(shí)別算法進(jìn)行對(duì)比和分析。

3.3.1 第一階段識(shí)別驗(yàn)證

第一階段的可疑大象流識(shí)別利用SED-WQ算法實(shí)現(xiàn)了可疑大象流的識(shí)別與標(biāo)記。為簡(jiǎn)化實(shí)驗(yàn)，利用文件傳輸協(xié)議（file transferprotocol，F(xiàn)TP）服務(wù)發(fā)送數(shù)據(jù)并使用wireshark抓取網(wǎng)卡上的數(shù)據(jù)分組，分析分組頭DSCP位驗(yàn)證第一階段可疑大象流識(shí)別結(jié)果。FTP是基于TCP的應(yīng)用層協(xié)議，數(shù)據(jù)發(fā)送較快且傳輸數(shù)據(jù)量可設(shè)置 （通過改變傳輸文件的大小實(shí)現(xiàn)），分析該階段識(shí)別結(jié)果與傳輸文件的大小可快速實(shí)現(xiàn)SED-WQ算法識(shí)別結(jié)果的分析與驗(yàn)證。

數(shù)據(jù)中心網(wǎng)絡(luò)中90%左右的數(shù)據(jù)流其承載的數(shù)據(jù)量不超過1 MB[22]，因此本文設(shè)置可疑大象流閾值為1 MB。為模擬實(shí)際網(wǎng)絡(luò)環(huán)境中的流類型比例，本次實(shí)驗(yàn)生成1～100 KB大小的文件75個(gè)，100 KB～1 MB大小的文件16個(gè)，1 MB以上文件9個(gè)。在數(shù)據(jù)發(fā)送前，需對(duì)Linux主機(jī)發(fā)送緩存區(qū)的默認(rèn)值和最大值進(jìn)行修改，利用sysctlwnet.core.wmem_default=1048576指令修改主機(jī)默認(rèn)發(fā)送緩存大小為 1 MB，利用 sysctl-wnet.core.wmem_max= 10485760指令修改主機(jī)最大發(fā)送緩存大小為10 MB。

發(fā)送上述文件并抓取數(shù)據(jù)分組，圖 4和圖5是 wireshark抓取的兩個(gè)FTP數(shù)據(jù)分組，分析其DSCP值可知，圖4被識(shí)別為可疑大象流，對(duì)照傳輸記錄發(fā)現(xiàn)本次傳輸文件大小為115 MB，識(shí)別結(jié)果符合實(shí)際；圖5被識(shí)別為老鼠流，對(duì)照傳輸記錄發(fā)現(xiàn)本次傳輸文件大小為3.5 KB，識(shí)別結(jié)果符合實(shí)際。

3.3.2 第二階段識(shí)別驗(yàn)證

第二階段的真實(shí)大象流識(shí)別利用RED-DT算法實(shí)現(xiàn)了對(duì)第一階段誤檢可疑大象流的快速剔除，該階段驗(yàn)證的網(wǎng)絡(luò)拓?fù)淙鐖D6所示。

Host1發(fā)出的FTP流通過OVS時(shí)會(huì)被發(fā)送至控制器，Ryu讀取數(shù)據(jù)分組TOS位識(shí)別出第一階段的可疑大象流并將其信息記錄在大象流列表，依據(jù)可疑大象流的持續(xù)時(shí)間特征實(shí)現(xiàn)真實(shí)大象流的識(shí)別，部分代碼如下。

@set_ev_cls（ofp_event．EventOFPPacketIn,MAIN_ DISPATCHER）

def_packet_in_handl er(self，ev)：

msg=ev．msg

datapath=msg．datapath

dpid=datapath．id，/*獲得交換機(jī)設(shè)備號(hào)*／

parser=datapath．pfproto_parser

table_id=msg，/*獲得流表號(hào)*／

in_port=msg．match[’in_port’]

/*解析packet_in消息攜帶的數(shù)據(jù)分組或報(bào)頭*／

pkt=packet．Packet(msg．data)

ip_tos=pkt．get_protocol(ipv4．ipv4．tos)，/*獲得TOS值*／

ip_src=pkt．get_protocol(ipv4．ipv4．src)，/*獲得源 IP

地址*／

圖4 抓取的可疑大象流數(shù)據(jù)分組

圖5 抓取的老鼠流數(shù)據(jù)分組

圖6 第二階段識(shí)別驗(yàn)證網(wǎng)絡(luò)拓?fù)?/p>

ip_dst=pkt．get_protocol(ipv4．ipv4．dst)，/*獲得目的IP地址*／

tcp_src_port=pkt．get_protocol(tcp．tcp．src_port)，/*獲得源端口*／

tcp_dst_port=pkt．get_protocol(tcp．tcp．dst_．port)，/*獲得目的端口*／

利用Mininet進(jìn)行仿真并查看Ryu維護(hù)的大象流列表，其內(nèi)容見表2。

分析表2中數(shù)據(jù)可以發(fā)現(xiàn)，第二階段識(shí)別通過RED-DT算法能夠?qū)崿F(xiàn)真實(shí)大象流的識(shí)別，兩次識(shí)別過程剔除了不滿足條件的大象流，并將真實(shí)大象流狀態(tài)標(biāo)記為real。

3.3.3 大象流兩級(jí)識(shí)別算法性能分析

首先分析大象流兩級(jí)識(shí)別算法的識(shí)別準(zhǔn)確性，然后在大象流識(shí)別開銷方面與基于采樣的大象流識(shí)別算法進(jìn)行對(duì)比和分析。

（1）兩級(jí)識(shí)別算法的識(shí)別準(zhǔn)確性分析

改變 M值進(jìn)行重復(fù)試驗(yàn)，統(tǒng)計(jì)分析網(wǎng)絡(luò)大象流的比例、大象流的識(shí)別準(zhǔn)確性以及大象流誤識(shí)別率，結(jié)果如圖 7所示。由圖 7可知，大象流兩級(jí)識(shí)別算法的識(shí)別結(jié)果與測(cè)試數(shù)據(jù)文件基本吻合，具有較高的識(shí)別準(zhǔn)確性。

（2）控制器識(shí)別開銷分析

在保證大象流兩級(jí)識(shí)別方法識(shí)別準(zhǔn)確性的同時(shí)下，從算法識(shí)別開銷角度將大象流兩級(jí)識(shí)別算法與基于采樣的大象流識(shí)別方法進(jìn)行比較分析，假定網(wǎng)絡(luò)環(huán)境見表3。

表2 大象流列表記錄信息

圖7 不同閾值下大象流的識(shí)別性能

表3 模擬環(huán)境配置

①基于采樣的大象流識(shí)別

該方法利用分組采樣的方式采樣數(shù)據(jù)流并統(tǒng)計(jì)，依據(jù)樣本特征推導(dǎo)采樣流的特征以此實(shí)現(xiàn)網(wǎng)絡(luò)大象流的識(shí)別。在該識(shí)別算法中，識(shí)別開銷可定義為所有交換機(jī)上每秒采樣的數(shù)據(jù)總和，該值可由式（1）計(jì)算得到。

采樣方法僅需發(fā)送數(shù)據(jù)分組頭至控制器即可，故Ds取值為54 byte（MAC分組頭、IP分組頭及TCP分組頭之和），則可計(jì)算出基于采樣的大象流識(shí)別方法理論上每秒需處理337.5 KB的數(shù)據(jù)。

②大象流兩級(jí)識(shí)別方法

大象流兩級(jí)識(shí)別方法的控制器識(shí)別開銷為第二階段的可疑大象流監(jiān)測(cè)開銷。針對(duì)特定可疑大象流控制器需處理1條packet-in消息、2條流統(tǒng)計(jì)請(qǐng)求消息以及2條應(yīng)答

消息，則該方法的識(shí)別開銷可由式（2）計(jì)算得到。

其中，E為網(wǎng)絡(luò)中可疑大象流的比例，可疑大象流閾值為 1 MB時(shí) E值為 12%，packet-in消息 Bpcket-in為128 byte，ofp_flow_stats_request請(qǐng)求消息Brequest為48 byte（分組頭8 byte，消息主體40 byte），ofp_flow_stats_reply消息Breply為64 byte（分組頭8 byte，消息主體 56 byte），則可計(jì)算大象流兩級(jí)識(shí)別方法控制器每秒需處理52.8 KB的數(shù)據(jù)。

為更直觀地比較上述兩種大象流識(shí)別方法的開銷，現(xiàn)將式（1）與式（2）的右邊相除得到兩種識(shí)別算法開銷比值r的式（3）。其中，E與可疑大象流閾值有關(guān)。由此可以得出，r值與大象流閾值的關(guān)系，如圖8所示。

圖8 大象流兩級(jí)識(shí)別算與采樣識(shí)別算法開銷比較

從圖8可看出，可疑大象流閾值M越大，大象流兩級(jí)識(shí)別算法相較于采樣識(shí)別算法開銷越小，表明大象流兩級(jí)識(shí)別算法通過兩階段的大象流可有效識(shí)別SDN控制器的識(shí)別開銷，保證系統(tǒng)運(yùn)行的可靠、穩(wěn)定，但在M值選取過程中也考慮端系統(tǒng)內(nèi)存利用率情況。

綜合來說，本文提出的SDN中的一種大象流兩級(jí)識(shí)別方法，在保證大象流識(shí)別準(zhǔn)確性的同時(shí)可有效降低SDN控制器的識(shí)別開銷，在避免控制器單點(diǎn)故障問題上較基于采樣的大象流識(shí)別方法具有明顯優(yōu)勢(shì)。當(dāng)可疑大象流閾值M=1 MB時(shí)，大象流兩級(jí)識(shí)別算法的大象流識(shí)別準(zhǔn)確性為92%且其控制器識(shí)別開銷較基于采樣的大象流識(shí)別算法降低了約85%。

4 結(jié)束語

本文針對(duì)現(xiàn)有基于SDN的大象流識(shí)別方法存在的控制器開銷較大的問題，提出一種大象流兩級(jí)識(shí)別方法，在第一階段采用基于TCP發(fā)送隊(duì)列的識(shí)別算法檢測(cè)可疑大象流，在第二階段采用基于流持續(xù)時(shí)間的識(shí)別算法檢測(cè)真實(shí)大象流。端系統(tǒng)中的第一階段可疑大象流識(shí)別剔除了大部分老鼠流，可有效降低第二階段SDN控制器所需監(jiān)測(cè)的網(wǎng)絡(luò)流數(shù)量，以實(shí)現(xiàn)控制器識(shí)別開銷的“減負(fù)”，仿真結(jié)果表明本文提出的大象流兩級(jí)識(shí)別算法在保證較高大象流識(shí)別準(zhǔn)確性的同時(shí)，可有效降低SDN控制器的識(shí)別開銷。

[1]ZUO Q Y,CHEN M,ZHAO G S,et al.OpenFlow-based SDN technologies [J].Journal of Software (Chinese),2013(5): 1078-1097.

[2]MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al. OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.

[3]CRISTIAN E,VARGHESE G.New directions in traffic measurement and accounting:focusing on the elephants, ignoring the mice [J].ACM Transactions on Computer Systems (TOCS),2003,21(3):270-313.

[4]BENSON T,AKELLA A,MALTZ D A.Network traffic characteristics of data centers in the wild [C]//The 10th ACM SIGCOMM Conference on Internet Measurement,November 1-30,2010,Melbourne,Australia.New York:ACM Press,2010: 267-280.

[5]XIA J B,REN G M.Survey on elephant flow identifying methods[J].Control and Decision,2013,28(6):801-807.

[6]BI C H,LUO X,YE T,et al.On precision and scalability of elephant flow detection in data center with SDN[C]//2013 IEEE Globecom Workshops(GC Wkshps),December 9-13,2013, Atlanta,Georgia,USA.New Jersey:IEEE Press,2013:1227-1232.

[7]MORI T,UCHIDA M,GOTO S.Identifying elephant flows through periodically sampled packets [C]//The 4th ACM SIGCOMM Conference on Internet Measurement,Oct25-27,2004, Taormina,Sicily,Italy.New York:ACM Press,2004:115-120.

[8]ROBERT B,STROTHE R M.MJRTY—a fast majority vote algorithm[M].Amsterdam:Springer Netherlands,1991.

[9]BAI L,LIU W J.Algorithm based on multiple filters for elephant flows identification [C] // 2011 International Conference on Transportation,Mechanical,and Electrical Engineering (TMEE),December 16-18,2011,Changchun, China.New Jersey:IEEE Press,2011:1084-1087.

[10]ZHAO X H,LI M H.Large flow identification based on counting bloom filter and space saving[J].Journal of University of Chinese Academy of Sciences,2015,32(3):391-397.

[11]SMITHA,KIM I,NARASIMHAREDDY A L.Identifying long-term high-bandwidth flows at a router[C]//The 8th International Conference on High Performance Computing, December 17-20,2001,Hyderabad,India.Heidelberg:Springer, 2001:361-371.

[12]LIU X L,LIU Y,WANG C L.An identification algorithm of network elephant flow based on FEFS and CBF [J].Computer Engineering,2015,41(9):68-73.

[13]BAI L,TIAN L Q,CHEN C.Elephant flow detection algorithm for high speed networks based on flow sampling and LRU[J]. Computer Application and Software,2016,33(4):111-115.

[14]XIE D Q,ZHOU Z H,LUO J W.An algorithm based on LRU and SCBF for elephant flows identification and its application in DDoS defense[J].Journal of Computer Research and Development, 2011,48(8):1517-1523.

[15]TOOTOONCHIAN A,GHOBADI M,GANJALI Y.OpenTM: traffic matrix estimator for OpenFlow networks[C]//2010 International Conference on Passive and Active Network Measurement,April 7-9,2010,Zurich,Switzerland.Heidelberg: Springer,2010:201-210.

[16]BENSON T,ANAND A,AKELLA A,et al.MicroTE:fine grained traffic engineering for data centers[C]//The Seventh Conference on Emerging Networking Experiments and Technologies,December 6-9,Tokyo,Japan.New York:ACM Press,2011:8.

[17]LIN C Y,CHIEN C,CHANG J W,et al.Elephant flow detection in datacenters using openflow-based hierarchical statistics pulling [C]//2014 IEEE Global Communications Conference,December 8-12,2014,Austin,Texas,USA.New Jersey:IEEE Press,2014:2264-2269.

[18]CURTIS A R,KIM W,YALAGANDULA P.Mahout:low-overhead datacenter traffic management using end-host-based elephant detection[C]//2011 IEEE INFOCOM,April 10-15,Shanghai, China.New Jersey:IEEE Press,2011:1629-1637.

[19]CHAO S C,LIN K C J,CHEN M S.Flow classification for software-defined data centers using stream mining[J].IEEE Transactions on Services Computing.doi:10.1109/TSC. 2016.2597846.

[20]FAN D D,MO L.Analysis of Linux kernel[M].Beijing:China Machine Press,2010.

[21]OpenFlowSwitch Specification.Open networking foundation, version 1.3.0(wire protocol 0x04)[S].2012.

[22]KANDULA S,SENGUPTA S,GREENBERG A,et al.The nature of data center traffic:measurements&analysis[C]//The 9th ACM SIGCOMM Conference on Internet Measurement Conference,November 4-6,2009,Chicago,Illinois,USA.New York:ACM Press,2009:202-208.

A two-level method for elephant flow identification

YAN Junrong,YE Jingchang,PAN Peng
School of Communication Engineering,Hangzhou Dianzi University,Hangzhou 310018,China

The high accuracy and low overhead of elephant flows identification have a great meaning on solving the controller’s single pointoffailure problem in SDN traffic management.Aiming atthe problem ofhigh overhead of the existing elephant flows identification method,a two-levelmethod for elephant flows identification was proposed which included a suspicious elephantdetection algorithm based on TCP write-queue in the firststage and arealelephantdetection algorithm based on flow duration in the second stage.During the firststage,the suspicious elephant flows were identified in the end systemsto reduce the amountofflowsmonitored by the SDN controlleratthe second stage.Analysisand simulation prove that, under the premise of ensuring the accuracy of elephant flow identification,the two-level method for elephant flows identification reducesabout85%overhead ofidentification compared with sampling identification method.

elephant flow identification,TCP sending queue,SDN

TP393

：A

10.11959/j.issn.1000-0801.2017076

嚴(yán)軍榮（1974-），男，博士，杭州電子科技大學(xué)講師，主要研究方向?yàn)闊o線通信與軟件定義網(wǎng)絡(luò)。

葉景暢（1992-），男，杭州電子科技大學(xué)碩士生，主要研究方向?yàn)檐浖x網(wǎng)絡(luò)。

潘鵬（1983-），男，博士，杭州電子科技大學(xué)副教授，主要研究方向?yàn)槎嘤脩魴z測(cè)技術(shù)、協(xié)作通信理論與技術(shù)。

2016-11-28；

2017-02-21

浙江省公益技術(shù)應(yīng)用研究計(jì)劃基金資助項(xiàng)目(No.2016C31G2041123)；第56批中國博士后科學(xué)基金面上資助項(xiàng)目(No.2014M561693)；國家自然科學(xué)基金青年科學(xué)基金資助項(xiàng)目(No.61401130)

Foundation Item s:Zhejiang Provincial Public Technology Application Research Program(No.2016C31G2041123),The 56th China Postdoctoral Science Foundation(No.2014M561693),The National Natural Science Foundation of Youth Science Foundation(No.61401130)