高速網(wǎng)絡(luò)UDP流超時策略研究

趙小歡， 夏靖波， 朱長虹

（1.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，陜西 西安 710077；2.中國人民解放軍95429部隊，云南 昆明 650200）

高速網(wǎng)絡(luò)UDP流超時策略研究

趙小歡1， 夏靖波1， 朱長虹2

（1.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，陜西 西安 710077；2.中國人民解放軍95429部隊，云南 昆明 650200）

隨著社交網(wǎng)絡(luò)、在線視頻、電子商務(wù)、即時通信及微博等新興業(yè)務(wù)的不斷涌現(xiàn)及迅速發(fā)展，網(wǎng)絡(luò)中UDP流量的比例及特性均發(fā)生了較大變化。文章通過對現(xiàn)有的流超時策略進(jìn)行分析，指出其適用于UDP流量時存在的局限及不足，針對實際UDP網(wǎng)絡(luò)流特性展開研究，并提出了一種UDP流區(qū)分更新的流超時策略（DUToS）。實驗結(jié)果證明，DUToS算法能夠更好地適用于UDP流量，有效改善了網(wǎng)絡(luò)流量測量的性能。

高速網(wǎng)絡(luò)；UDP數(shù)據(jù)流；流超時策略；區(qū)分更新超時策略（DUToS）

隨著網(wǎng)絡(luò)鏈路速率的提高，在流量測量系統(tǒng)中采集并分析全部的數(shù)據(jù)包信息變得不切實際，同時由于數(shù)據(jù)包級的流量測量缺乏高層業(yè)務(wù)信息，在許多情況下數(shù)據(jù)包級流量測量無法滿足網(wǎng)絡(luò)管理的需求?；诖?，文獻(xiàn)［1］提出了基于IP流的被動網(wǎng)絡(luò)測量方式，并將網(wǎng)絡(luò)IP流定義為符合特定流規(guī)范和超時約束的一系列數(shù)據(jù)包的集合。目前使用最廣泛的流規(guī)范是五元組（源IP、源端口、目的IP、目的端口、協(xié)議）規(guī)范，超時約束是將超過一定時間不活動的流定義為已終結(jié)流，以便更加有效地利用測量系統(tǒng)的資源。

隨著Internet的不斷發(fā)展，社交網(wǎng)絡(luò)、在線視頻、電子商務(wù)、即時通信及微博等多種新興業(yè)務(wù)不斷涌現(xiàn)，并迅速占據(jù)互聯(lián)網(wǎng)中主流應(yīng)用位置，同時一些傳統(tǒng)的主流應(yīng)用（如網(wǎng)絡(luò)新聞、電子郵件等）使用率不斷降低［2］，互聯(lián)網(wǎng)流量在組成和性質(zhì)上都有了較大的改變。通過對網(wǎng)絡(luò)中的IP流分析發(fā)現(xiàn)，Internet中TCP、UDP和ICMP 3種流量在包（packet）級別和流（flow）級別一直以來都占據(jù)著絕對優(yōu)勢，但由于UDP在實時性上優(yōu)于TCP，隨著網(wǎng)絡(luò)主流應(yīng)用的轉(zhuǎn)變，UDP流量在Internet中的作用越來越重要?；ヂ?lián)網(wǎng)數(shù)據(jù)分析合作組織（CAIDA）通過研究數(shù)條美國至瑞典間骨干鏈路在2002—2009年的流量數(shù)據(jù)后指出，隨著一些新興應(yīng)用趨于選擇UDP作為傳輸層協(xié)議，觀測到的鏈路中UDP流量相對于TCP流量在流、數(shù)據(jù)包和字節(jié)上的比例都有顯著增加［3］。

由于目前的流超時策略大部分是針對全部IP流或TCP流，較少有專門針對UDP流的超時策略，針對近年來網(wǎng)絡(luò)流量特別是UDP流量特性的變化，本文分析了現(xiàn)有的流超時策略適用于UDP流量時存在的局限和不足，結(jié)合MAWI提供的packet traces分析近年來網(wǎng)絡(luò)中UDP流的特性變化，并提出了一種UDP流區(qū)分更新的流超時策略，最后通過實驗進(jìn)行了分析及驗證。

1 網(wǎng)絡(luò)流超時策略分析

流超時設(shè)置是為了平衡海量流量和有限存儲之間的矛盾，盡快將已結(jié)束的流從有限緩存中刪除。理想情況下流超時設(shè)置得越短，過期流被淘汰得越快，但過短的超時設(shè)置可能會導(dǎo)致包間隔時間較長的流被截斷成為若干短流，造成包間關(guān)系及其更高層次信息分析的丟失，因此流超時研究需要根據(jù)具體的網(wǎng)絡(luò)流量特性，尋求性能與消耗的平衡。文獻(xiàn)［1］將流超時閥值分別設(shè)置為2is（i＝1，2，…，11）對觀測traces進(jìn)行組流實驗，得出主干網(wǎng)IP流超時閥值以64s為宜。該超時策略采用固定超時，未對不同種類、不同特性的IP流區(qū)分對待，在一些異常情況下必然會出現(xiàn)測量結(jié)果的偏差，另一方面，隨著網(wǎng)絡(luò)流量的不斷變化，64s的固定超時對于目前的網(wǎng)絡(luò)流是否合適值得懷疑，文獻(xiàn)［4］指出，目前的數(shù)據(jù)流超時間隔取值為16s可達(dá)到理想的效果。

文獻(xiàn)［5］基于TCP分組的應(yīng)用層協(xié)議分析流大小和最大報文間隔之間的關(guān)系得到流大小與報文間隔的經(jīng)驗條件概率分布，采用PGAT算法結(jié)合經(jīng)驗分布設(shè)置多個超時閥值。然而，實時網(wǎng)絡(luò)流應(yīng)用層協(xié)議識別本身就是一項非常困難的工作，PGAT算法只適用于少量可快速識別的業(yè)務(wù)流，同時PGAT算法主要適用于長流，不適用于包含大量短流的UDP流量。

文獻(xiàn)［6］通過分析流吞吐量和包間隔方差系數(shù)間的關(guān)系，提出一種自適應(yīng)的流超時算法MBET，MBET算法為每個流都維護(hù)一個獨立的超時，初始超時值設(shè)置為最大，隨著觀測值的變化，流超時值維持不變或以2的指數(shù)形式遞減。MBET算法能夠自適應(yīng)于流的變化，但主要針對長流，并且超時閥值一旦變小就不能再增加。

文獻(xiàn)［7－8］提出了2層自適應(yīng)超時策略TSAT和動態(tài)超時策略DToS，2種算法采用固定超時、協(xié)議分析、定期掃描及MBET等多種策略結(jié)合，極大地提高了系統(tǒng)資源利用率，但算法需要根據(jù)流的統(tǒng)計特性設(shè)置參數(shù)，并沒有專門針對UDP流量特性進(jìn)行優(yōu)化調(diào)整。文獻(xiàn)［9］針對UDP流的流超時策略，將流超時時限設(shè)置為6個值，通過支持向量機算法實現(xiàn)對UDP流超時閥值的分類，但由于UDP流中存在大量的短流，這些短流特別是單報文流的流量屬性特征嚴(yán)重不足，短流采用機器學(xué)習(xí)算法容易發(fā)生分類錯誤。

目前各種流超時策略研究的一個主要方向是在保證組流精度的前提下，根據(jù)流量的具體特性優(yōu)化流超時策略，以降低系統(tǒng)的資源消耗，但各種流超時策略大部分是以網(wǎng)絡(luò)中的全部流量作為研究對象，而不同協(xié)議產(chǎn)生的流量在流特性上具有較大的差異，這些流超時策略適用于UDP流時會導(dǎo)致性能下降；同時，不同于TCP流量具有明顯的協(xié)議標(biāo)識，可用來判斷流的開始和終結(jié)，無連接特性的UDP流量更需要通過流超時策略判斷流的起止，因此有必要結(jié)合UDP流的具體流量特性，進(jìn)一步優(yōu)化UDP流超時策略。

2 UDP流特性分析

MAWI提供的一條跨太平洋骨干鏈路2011年8月1日trace中流量分布情況［10］見表1所列。

表1 MAWI網(wǎng)絡(luò)流量

trace中共包含1 680 971條IP流，其中TCP、UDP、ICMP 3種流分別占到總流數(shù)量的31.32%、51.88%、16.27%，其他流僅占到總流數(shù)量的0.53%；共有數(shù)據(jù)報文15 214 334個，其中TCP、UDP、ICMP報文分別占到總報文數(shù)量的80.43%、15.89%、3.38%，其 他 報 文 數(shù) 比 例 為0.3%。由表1可以看出，相對于文獻(xiàn)［11］，隨著網(wǎng)絡(luò)的不斷發(fā)展變化，骨干鏈路中UDP流量的流數(shù)量和報文數(shù)量都有了明顯的增長。

網(wǎng)絡(luò)IP流流長分布和流持續(xù)時間分布都具有比較明顯的重尾現(xiàn)象，文獻(xiàn)［1］提出的64s固定超時基本上能夠滿足全部IP流的流超時需要，但對于大多數(shù)流長較小、流持續(xù)時間較短的流來說，64s的超時設(shè)置浪費了較多的時間和空間資源。為了進(jìn)一步優(yōu)化流超時策略的資源配置，有必要根據(jù)IP流的不同特性動態(tài)調(diào)整超時策略。

trace－20110801的流長和流持續(xù)時間的累積分布函數(shù)如圖1所示。

圖1 流長與流持續(xù)時間CDF分布圖

由圖1可以看出，盡管4種流分布都表現(xiàn)出明顯的重尾現(xiàn)象，但不同流的流長和流持續(xù)時間的重尾程度并不相同。流長在10以內(nèi)的流分別占到總流數(shù)、TCP流數(shù)、UDP流數(shù)、ICMP流數(shù)的95.79%、94.37%、98.84%、98.91%，而流持續(xù)時間在1s以內(nèi)的流分別占到總流數(shù)、TCP流數(shù)、UDP 流 數(shù)、ICMP 流 數(shù) 的 51.71%、36.12%、86.44%、70.77%。

對于UDP流而言，短流的比例特別高，流長在1、2、3、6、10以內(nèi)的流分別占到 UDP總流數(shù)的 84.41%、92.12%、94.94%、98.05%、98.84%，當(dāng)發(fā)生DDoS等網(wǎng)絡(luò)攻擊時，網(wǎng)絡(luò)中的單報文流的比例會進(jìn)一步增加［12］，對于單報文流超時閥值的優(yōu)化能夠極大地節(jié)約系統(tǒng)資源消耗。在識別單報文UDP流的基礎(chǔ)上，單報文流超時閥值越小越好，單報文流超時策略可以等價于單報文UDP流的識別問題。同時，在整個UDP流持續(xù)周期內(nèi)，流持續(xù)時間在1、2、4、8、16、32、64s以內(nèi)的流分別占到總流數(shù)的86.44%、86.87%、88.82%、92.87%、95.20%、96.54%、98.39%，顯然，絕大部分 UDP流的持續(xù)時間都遠(yuǎn)小于64s，64s的超時閥值為大部分UDP流流持續(xù)時間的數(shù)十到數(shù)千倍，UDP流超時閥值具有較大的優(yōu)化空間。

trace－20110801中不同長度UDP流的平均流持續(xù)時間和平均報文間隔時間如圖2所示。

從圖2可以看出，對于平均流持續(xù)時間而言，UDP短流的持續(xù)時間較短，而不同長度UDP長流的持續(xù)時間波動較大；就UDP流平均報文間隔時間而言，流長處于2～100中的流平均報文間隔時間及波動較大，如在UDP流長為24處，大約平均每隔15s才傳輸1個報文，長流的平均報文間隔時間較小，特別是對于流長為103～105的流速率更為穩(wěn)定。

圖2 UDP流持續(xù)時間分布圖

3 區(qū)分更新超時策略（DUToS）設(shè)計

通過對UDP流量特性分析可知，UDP流中單報文流的比例極高，若按照64s的固定流超時設(shè)置，這些單報文流將極大地浪費系統(tǒng)資源；同時由于長流的平均報文間隔時間及波動均較小，對于這些長流，可以通過觀測前期報文間隔值預(yù)測以后報文間隔值來設(shè)置UDP流超時閥值。為了精確設(shè)置各種UDP流的超時閥值，首先需要初步統(tǒng)計新出現(xiàn)UDP流的信息，為此系統(tǒng)創(chuàng)建一個新流特性統(tǒng)計空間（New Flow Statistics Extraction Module，簡稱NFSEM）來提取 UDP流長信息，NFSEM采用雙鏈表數(shù)據(jù)結(jié)構(gòu)，鏈表數(shù)目固定，采用LRU淘汰策略更新流，同時為了防止NFSEM被長流占滿及部分流占用NFSEM過長時間，對于流長大于10的UDP流將會強制被淘汰到流超時空間（Timeout Module，簡稱TM）。

TM統(tǒng)計UDP流的信息，對不同長度的流采用3種不同的流超時策略，分別在3個子空間long－flow－space、short－flow－space和singlepacket－flow－space中實現(xiàn)。

DUToS原理如圖3所示，算法描述為：

（1）當(dāng)一個UDP報文到來時，通過哈希方式查找UDP報文對應(yīng)的流地址，若UDP流位于NFSEM中，則進(jìn)入步驟（2）；若UDP流位于TM中，則進(jìn)入步驟（3）；否則進(jìn)入步驟（4）。

（2）更新NFSEM 中對應(yīng)UDP流信息，將UDP流放入鏈表頭部，若UDP流長大于10，則將該UDP流從NFSEM中淘汰至TM中，進(jìn)入步驟（5）。

（3）更新TM中對應(yīng)的UDP流信息，進(jìn)入步驟（5）。

（4）判斷NFSEM中鏈表是否已被占滿，若鏈表未滿，則將新到UDP流放入鏈表頭部，否則，將鏈表尾部UDP流淘汰至TM中，并將新到UDP流放入鏈表頭部，進(jìn)入步驟（5）。

（5）判斷UDP流長，若UDP流長為1，將UDP流放入 TM 的single－packet－flow－space區(qū)間，按照先入先出FIFO策略淘汰過期流；若UDP流長處于［2，L）區(qū)間，將流放入 TM 的short－flow－space區(qū)間，按照MBET策略淘汰過期流；若UDP流長處于L［，＋∞）區(qū)間，將流放入TM的long－flow－space區(qū)間，通過SVM預(yù)測設(shè)置流超時閥值。

圖3 DUToS原理

對于單報文UDP流，DUToS并沒有固定時間以淘汰舊流，而是通過空間受限的FIFO緩存不斷更新過期流，這樣做具有以下優(yōu)點：①FIFO策略巧妙地將流識別與流淘汰結(jié)合，每次淘汰的流是最可能終結(jié)的單報文流，具有較高的準(zhǔn)確率；②FIFO策略能夠自適應(yīng)于網(wǎng)絡(luò)中單報文流速率的變化，以每秒產(chǎn)生上萬個UDP單報文流為例，若FIFO包含10 000個表項，則平均每個單報文流被淘汰的時間不到1s，在DDoS攻擊等網(wǎng)絡(luò)異常情況下，F(xiàn)IFO緩存能夠更快地淘汰過期單報文流，算法具有較高的魯棒性。

對于UDP長流的超時設(shè)置，為便于實現(xiàn)，將長流超時閥值分別設(shè)置為｛｛2｝，｛4｝，｛8｝，｛16｝，｛32｝，｛64｝｝，則 UDP流報文間隔時間被劃分為6個區(qū)間｛（0，2），［2，4），［4，8），［8，16），［16，32），［32，64）｝，此時長流超時閥值設(shè)置問題就轉(zhuǎn)換為多類分類問題。不同于傳統(tǒng)的支持向量機需要尋求最優(yōu)分類面來最小化分類誤差，網(wǎng)絡(luò)流超時閥值的設(shè)置是有偏的（即流超時閥值大于報文間隔值能夠接受，流超時閥值小于報文間隔值，即使是略小于報文間隔值都是不能接受的）。

為了確保UDP流不被截斷，將流超時閥值｛｛2｝，｛4｝，｛8｝，｛16｝，｛32｝，｛64｝｝對應(yīng)的報文間隔區(qū)間重新調(diào)整為（0，2－ε1），［2－ε1，4－ε2），［4－ε2，8－ε3），［8－ε3，16－ε4），［16－ε4，32－ε5），［32－ε5，64）。同時，基于實時性的考慮，DUToS算法并不對長流中的每個UDP報文時間間隔進(jìn)行預(yù)測，而是每隔T個報文預(yù)測1次，或者當(dāng)上次預(yù)測值α與當(dāng)前報文間隔值β的絕對差大于t1，或者當(dāng)前超時閥值To與報文間隔值β的差值小于t2時，DUToS算法重新預(yù)測并更新預(yù)測值α和UDP流超時閥值To。

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

為了驗證DUToS的性能，將本文提出的DUToS與 PGAT 算法［5］、TSAT 算法［7］與 MSVM算法［9］進(jìn)行比較，定義評價指標(biāo)為：

其中，true－count為trace中真實包含的流數(shù)；generated－count為采用各種超時算法測得的流數(shù)；unshorten－count為采用各種超時策略后真實的流數(shù)中未被截斷的流數(shù)；extra－time為UDP流最后一個報文到來至流被淘汰期間持續(xù)的時間。

為了增加對比性，選用MAWI提供的同一條鏈路1999年3月21日、2009年3月30日和2011年8月1日3組trace作為測試數(shù)據(jù)，DUToS算法參數(shù)ε1＝ε2＝ε3＝ε4＝ε5＝1，L＝20，T＝50，t1＝t2＝0.2，短流采用的 MBET淘汰方式參數(shù)見文獻(xiàn)［7］，實驗結(jié)果見表2所列。

表2 各種流超時策略效果對比

從表2可以看出，PGAT算法適用于UDP流量時在gr、ir、mft 3個指標(biāo)上表現(xiàn)均不理想，主要是因為PGAT算法通過識別流對應(yīng)的應(yīng)用協(xié)議來判斷流超時閥值，而通過分析3組trace發(fā)現(xiàn)，UDP流量的端口分布在0～65 535整個區(qū)間上具有較高的隨機性，難以簡單地識別出UDP流對應(yīng)的應(yīng)用層協(xié)議。MSVM算法對于trace－2009和trace－2011的gr和ir的準(zhǔn)確率較低，這是由于trace－2009和trace－2011中UDP短流特別是單報文流的比率很高，MSVM算法在預(yù)測流量屬性特征不足的單報文流時，誤差必然增加。

相對而言，TSAT和DUToS在流產(chǎn)生率gr和流完整率ir的準(zhǔn)確率較高，但DUToS算法的流超時均值mft要明顯低于TSAT算法，這意味著DUToS算法對于已終結(jié)流的淘汰速度高于TSAT算法。

對trace－2011采用不同流超時策略時系統(tǒng)需要維護(hù)的活躍UDP流數(shù)量隨時間的變化情況如圖4所示，從圖4可以看出，由于對比例占到UDP流總數(shù)84.41%的單報文流采用了優(yōu)化處理，在整個測量周期內(nèi)，DUToS需要維護(hù)的活躍UDP流數(shù)量明顯低于其他算法，由于系統(tǒng)占用系統(tǒng)資源與活躍流數(shù)量成正比，因此DUToS需要的計算和存儲資源是最少的。

圖4 不同超時策略維護(hù)活躍UDP流數(shù)

5 結(jié)束語

隨著骨干網(wǎng)絡(luò)鏈路速率的進(jìn)一步提升，提高組流效率已經(jīng)成為基于粒度的網(wǎng)絡(luò)行為分析亟待解決的問題之一。針對網(wǎng)絡(luò)中UDP流量的增長變化，本文詳細(xì)分析了UDP流的流量特性，在此基礎(chǔ)上提出了針對不同長度的流采用不同更新方式的區(qū)分更新流超時策略（DUToS），該策略對單報文流采用空間受限方式淘汰過期流，對于短流采用MBET策略淘汰過期流，對于長流采用SVM方法預(yù)測包間隔來設(shè)置流超時值。實驗結(jié)果驗證了DUToS更加適合于UDP流量，策略在流產(chǎn)生率、流完整率、流超時均值3個指標(biāo)上均有較好的表現(xiàn)，并且在對同一組UDP流量進(jìn)行組流時，DUToS占用的系統(tǒng)資源遠(yuǎn)低于其他方法需要占用的資源。

［1］Claffy K C，Braun H W，Polyzos G C.A parameterizable methodology for Internet traffic flow profiling［J］.IEEE Journal on Selected Areas in Communications，1995，12（8）：1481－1494.

［2］中國互聯(lián)網(wǎng)絡(luò)信息中心（CNNIC）.第30次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)?況 調(diào) 查 統(tǒng) 計 報 告 ［EB／OL］.［2012－07－23］.http：／／www.cnnic.cn／.

［3］CAIDA.Analyzing UDP usage in Internet traffic［EB／OL］.［2010－01－14］.http：／／www.caida.org／rersearch／traffic－analysis／tcpudpratio／.

［4］王 遠(yuǎn)，丁 偉，龔 儉.TCP數(shù)據(jù)流超時研究［J］.廈門大學(xué)學(xué)報：自然科學(xué)版，2007，46（2）：192－195.

［5］Wang Junfeng，Li Lei，Sun Fuchun，et al.A probabilityguaranteed adaptive timeout algorithm for high－speed network flow detection［J］.Computer Networks，2005，48（2）：215－233.

［6］Ryu B，Cheney D，Braun H W.Internet flow characterization：adaptive timeout strategy and statistical modeling［C］／／Workshop on Passive and Active Measurement（PAM），2001：95－105.

［7］周明中，龔 儉，丁 偉.網(wǎng)絡(luò)流超時策略研究［J］.通信學(xué)報，2005，26（4）：88－93.

［8］周明中，龔 儉，丁 偉.高速網(wǎng)絡(luò)中基于流速測度的動態(tài)超時策略［J］.軟件學(xué)報，2006，17（10）：2141－2151.

［9］Cai Jing，Zhang Zhibin，Zhang Peng.An adaptive timeout strategy for profiling UDP flows［C］／／2010First International Conference on Network and Computing，2010：44－48.

［10］MAWI Working Group.WIDE traffic archive［EB／OL］.［2011－09－03］.http：／／mawi.wide.ad.jp／.

［11］Zhang Y，Breslau L，Paxson V，et al.On the characteristics and origins of Internet flow rates［C］／／Proc of the ACM SIGCOMM 2002，2002：309－322.

［12］葉 震，施偉偉.基于TCP＿IP報頭分析和主動測試的DDoS攻擊響應(yīng)機制［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2010，33（3）：363－367.

Research on UDP flow timeout strategy in high－speed network

ZHAO Xiao－h(huán)uan1， XIA Jing－bo1， ZHU Chang－h(huán)ong2

（1.College of Information and Navigation，Air Force Engineering University，Xi’an 710077，China；2.Troop 95429of The People’s Liberation Army，Kunming 650200，China）

With the continuous emergence and rapid development of social network，online video，e－commerce，instant message，micro－blogging，etc.，great changes have taken place in the percentage and property of UDP traffic on the Internet.By the analysis of the state－of－the－art flow timeout strategies，their deficiencies and shortcomings are pointed out when applied in UDP traffic.Then，a differentiated updating timeout strategy（DUToS）for profiling UDP flows is proposed based on the analysis of the property of real UDP flows.Experimental results show that the algorithm of DUToS is more suitable for UDP traffic and can effectively improve the performance of network traffic measurement system.

high－speed network；UDP flow；flow timeout strategy；differentiated updating timeout strategy（DUToS）

TP393

A

1003－5060（2013）02－0176－06

10.3969／j.issn.1003－5060.2013.02.011

2012－08－24；

2012－10－16

陜西省自然科學(xué)基金重點資助項目（2012JZ8005）；全軍軍事學(xué)研究生課題資助項目（2010XXXX－488）

趙小歡（1984－），男，湖北棗陽人，空軍工程大學(xué)博士生；

夏靖波（1963－），男，河北秦皇島人，博士，空軍工程大學(xué)教授，博士生導(dǎo)師.

（責(zé)任編輯 閆杏麗）