李川，李岷

（綿陽職業(yè)技術(shù)學(xué)院，四川綿陽621000）

一種基于Netflow機(jī)制的大流抽樣算法設(shè)計(jì)*

李川，李岷

（綿陽職業(yè)技術(shù)學(xué)院，四川綿陽621000）

在網(wǎng)絡(luò)測(cè)量中，如何在快速存儲(chǔ)器容量一定的條件下提高對(duì)大流的測(cè)量精度是目前研究的一個(gè)熱點(diǎn)問題。首先在不影響應(yīng)用需求的前提下，提出了對(duì)雙向流進(jìn)行抽樣測(cè)量的思想。然后對(duì)流抽樣算法進(jìn)行了一定的數(shù)學(xué)分析，證明了測(cè)量雙向流能有效提高流表的利用率，較好地提高大流測(cè)量精度。為實(shí)現(xiàn)基于Netflow機(jī)制的抽樣算法，詳細(xì)設(shè)計(jì)了哈希函數(shù)，流表表項(xiàng)結(jié)構(gòu)，重點(diǎn)解決了將雙向流映射到同一個(gè)流表表項(xiàng)的問題。最后利用網(wǎng)絡(luò)實(shí)測(cè)數(shù)據(jù)對(duì)該算法進(jìn)行了仿真驗(yàn)證，結(jié)果表明，當(dāng)存儲(chǔ)資源一定時(shí)，該算法的大流測(cè)量精度要優(yōu)于單向流測(cè)量算法。

大流抽樣，雙向流，Netflow，測(cè)量精度

0　引言

網(wǎng)絡(luò)流量測(cè)量對(duì)網(wǎng)絡(luò)計(jì)費(fèi)、網(wǎng)絡(luò)性能評(píng)估和異常檢測(cè)等網(wǎng)絡(luò)功能的實(shí)現(xiàn)具有重要的意義。網(wǎng)絡(luò)流量測(cè)量的對(duì)象主要有報(bào)文測(cè)量和流測(cè)量?jī)煞N類型，由于流可以反映網(wǎng)絡(luò)端到端的應(yīng)用狀況，因此，流測(cè)量研究已經(jīng)成為目前網(wǎng)絡(luò)測(cè)量研究最主要的方向之一［1-2］。

IETF推薦的流測(cè)量方法是在測(cè)量設(shè)備中維護(hù)一個(gè)流表,為每個(gè)流保存一個(gè)流記錄，但是現(xiàn)在網(wǎng)絡(luò)中流的數(shù)量十分巨大，而目前的半導(dǎo)體技術(shù)無法提供容量足夠大的快速存儲(chǔ)器SRAM用來記錄每個(gè)流的信息［3］，因此，實(shí)現(xiàn)起來十分困難。大量的研究表明，互聯(lián)網(wǎng)中的流大小呈重尾分布［4-5］,即少量的大流占據(jù)了網(wǎng)絡(luò)中大部分的流量。文獻(xiàn)［6］對(duì)AS之間的流量測(cè)量結(jié)果顯示，9%的大流產(chǎn)生了90%的流量。對(duì)于一些網(wǎng)絡(luò)應(yīng)用，例如網(wǎng)絡(luò)計(jì)費(fèi)，網(wǎng)絡(luò)流量分布測(cè)量而言，大流能提供足夠準(zhǔn)確的信息，因此，對(duì)于這些應(yīng)用，只測(cè)量大流能較好地解決快速存儲(chǔ)器SRAM容量不足的問題。

目前大流的抽樣測(cè)量方法主要有Multistage Filters［7］,Sample and Hold［8］、Smart Sampling［9］和LRU［10］4種，這些方法都是根據(jù)大流字節(jié)數(shù)多，持續(xù)時(shí)間長(zhǎng)等特點(diǎn)來設(shè)計(jì)算法對(duì)單方向上的大流進(jìn)行測(cè)量。考慮網(wǎng)絡(luò)流量的產(chǎn)生是用戶與網(wǎng)絡(luò)服務(wù)交互的結(jié)果，即網(wǎng)絡(luò)中既有用戶至網(wǎng)絡(luò)服務(wù)方向的上行流，又有網(wǎng)絡(luò)服務(wù)至用戶方向的下行流，從流測(cè)量的目的是反映端到端的應(yīng)用狀況來看，可以將該上行流和其對(duì)應(yīng)的下行流歸為一個(gè)雙向流處理。上述幾種方法測(cè)量的都是單向大流，如果在某個(gè)雙向流中的任一方向上均是小流，而該雙向流卻是一大流，上述幾種方法將無從檢測(cè)。

因此，本文將首先證明測(cè)量雙向流能有效提高大流測(cè)量的精度，然后結(jié)合廣泛使用的Netflow［11-12］技術(shù)設(shè)計(jì)一種對(duì)雙向流的采樣算法，最后利用網(wǎng)絡(luò)實(shí)測(cè)數(shù)據(jù)進(jìn)行仿真驗(yàn)證。

1　流抽樣算法分析

為了提高抽樣設(shè)備的處理速度以適應(yīng)高速網(wǎng)絡(luò)環(huán)境，大多數(shù)流抽樣方法都是利用報(bào)文經(jīng)過哈希映射得到的哈希值作為流表中相應(yīng)表項(xiàng)的索引。屬于某個(gè)流的所有報(bào)文都將被映射到同一個(gè)流表表項(xiàng)中以記錄該流的信息。但是由于流表的表項(xiàng)數(shù)小于網(wǎng)絡(luò)中流的數(shù)量，將會(huì)有不同的流映射到同一個(gè)表項(xiàng)中，可能造成以下3個(gè)不良影響：

①不同的大流映射在同一個(gè)表項(xiàng)中，導(dǎo)致分析測(cè)量結(jié)果時(shí)得到的大流數(shù)偏低，影響了流量分布的測(cè)量，對(duì)某個(gè)大流流量大小估計(jì)的準(zhǔn)確度也將大大降低。

②一些小流和某個(gè)大流映射在同一個(gè)表項(xiàng)中，分析測(cè)量結(jié)果時(shí)這些小流會(huì)被當(dāng)作大流流量的一部分，導(dǎo)致對(duì)該大流的流量大小估計(jì)的準(zhǔn)確度降低。

③某些小流映射在同一表項(xiàng)中，匯聚的結(jié)果導(dǎo)致抽樣設(shè)備誤以為檢測(cè)到一條大流，從而影響了網(wǎng)絡(luò)流量分布的測(cè)量結(jié)果。

由于網(wǎng)絡(luò)中的流大小服從重尾分布，大流的數(shù)量很少，而小流的數(shù)量極多，因此，情形①發(fā)生的概率較低，而情形②、③卻經(jīng)常發(fā)生。要提高對(duì)大流流量、分布的測(cè)量精度，就必須降低這些不良事件發(fā)生的概率。

假設(shè)某抽樣設(shè)備的流表共有m項(xiàng)表項(xiàng)，所使用的哈希映射函數(shù)也完全隨機(jī)。如果在一定的時(shí)間Δt內(nèi)，經(jīng)過該抽樣設(shè)備的流總數(shù)為n，滿足1≤n≤m，那么在Δt時(shí)間內(nèi)至少有兩個(gè)流映射到同一表項(xiàng)的概率為

由式（1）知

其中，1≤n+1≤m，因此可以推知h

即P是n的單調(diào)遞增函數(shù)。當(dāng)由單向流的測(cè)量改為雙向流的測(cè)量時(shí)，某些端點(diǎn)之間的上行流和下行流將被合并為一條流處理，流的總數(shù)n將會(huì)降低，不同流映射到同一表項(xiàng)的概率P將隨之減少。因此，上述不良事件發(fā)生的概率會(huì)降低，大流的測(cè)量精度將得到提高。

2　流抽樣算法設(shè)計(jì)

2.1大流的定義

目前在測(cè)量領(lǐng)域廣泛使用的是基于五元組的流定義，即具有相同的源IP地址、目的IP地址、源端口、目的端口和協(xié)議類型的數(shù)據(jù)報(bào)文組成一個(gè)流。雙向流是將使用相同的協(xié)議類型，來往于對(duì)應(yīng)源宿端點(diǎn)之間數(shù)據(jù)報(bào)文看作一個(gè)流。

NetFlow機(jī)制使用以下規(guī)則來判斷一個(gè)流是否結(jié)束：①新到達(dá)TCP報(bào)文首部的FIN或RST標(biāo)志位被置位，則對(duì)應(yīng)的流結(jié)束。②一定的時(shí)間內(nèi)沒有屬于某一流的數(shù)據(jù)報(bào)文到達(dá)，則該流結(jié)束。該時(shí)間間隔稱為流超時(shí)時(shí)間。③流的持續(xù)時(shí)間超過閾值，則認(rèn)為該流結(jié)束。該時(shí)間稱為流持續(xù)時(shí)間。

如果在一定的時(shí)間內(nèi)，某條流的流量大小超過了閾值，則該流被認(rèn)為是大流。

2.2哈希函數(shù)的選擇

為了提高流表中表項(xiàng)的利用率，降低上述不良事件發(fā)生的概率，用作映射的哈希函數(shù)應(yīng)具有較好的隨機(jī)性。目前公認(rèn)能產(chǎn)生隨機(jī)序列最好的哈希函數(shù)是MD5、SHA1等加密性哈希函數(shù)，但是這些哈希函數(shù)進(jìn)行運(yùn)算的時(shí)間復(fù)雜度高，很難適應(yīng)于高速的網(wǎng)絡(luò)測(cè)量環(huán)境?，F(xiàn)在許多研究都傾向于使用H3函數(shù)來進(jìn)行哈希映射［13-14］。文獻(xiàn)［15］也對(duì)H3、Bob、CRC32生成的哈希值分布的均勻性進(jìn)行了卡方檢驗(yàn)，H3函數(shù)被證明隨機(jī)性最好。

H3哈希函數(shù)是通過如下的線性變換：

將一個(gè)n位的二進(jìn)制串映射為一個(gè)m位的二進(jìn)制串，矩陣R=（rij）m×n是一個(gè)二進(jìn)制隨機(jī)矩陣。運(yùn)算中的乘法和加法相當(dāng)于與邏輯和或邏輯，用計(jì)算機(jī)很容易實(shí)現(xiàn)，因此，H3哈希函數(shù)的運(yùn)算速度很快，適用于高速的網(wǎng)絡(luò)測(cè)量環(huán)境。

將IP報(bào)文中32位的源IP串記為a1，目的IP串記為a2，16位的源端口串記為a3，目的端口串記為a4，8位的協(xié)議類型串記為a5，本文哈希值h的計(jì)算公式如下：

2.3流表表項(xiàng)結(jié)構(gòu)設(shè)計(jì)

為了實(shí)現(xiàn)基于NetFlow機(jī)制的流抽樣算法，流表表項(xiàng)中記錄的流信息，至少應(yīng)包含以下幾項(xiàng)：

①流的首個(gè)報(bào)文到達(dá)時(shí)間，該項(xiàng)可以用于幫助判斷流是否超出持續(xù)時(shí)間，共8 Byte。

②流的最新報(bào)文到達(dá)時(shí)間，該項(xiàng)可用于幫助判斷流是否超時(shí)。由于某些時(shí)間信息在①中已經(jīng)存儲(chǔ)，所以該項(xiàng)只需4 Byte。

③流，該項(xiàng)用于標(biāo)示出特定的流。采用五元組后，共13個(gè)Byte。

④到達(dá)報(bào)文標(biāo)識(shí)符，該項(xiàng)可用于判斷一個(gè)TCP流是否結(jié)束，共1個(gè)Byte。

⑤流的總字節(jié)數(shù)，用于記錄流量的大小，共4 Byte，可以記錄流量的最大值為4 G的流。

一個(gè)表項(xiàng)總共需要30個(gè)Byte的存儲(chǔ)空間。報(bào)文經(jīng)H3函數(shù)映射后得到的哈希值是一個(gè)m位的二進(jìn)制串，將其作為流表中表項(xiàng)的索引，一共可以表示2m項(xiàng)，所以流表的大小為30×2m個(gè)字節(jié)。目前的半導(dǎo)體工藝能提供的最大SRAM為64 M，可以提供大約2 M個(gè)表項(xiàng)。

2.4算法流程

采用NetFlow機(jī)制的大流抽樣算法的具體流程如圖1所示，處理流記錄流程圖如圖2所示。

雙向流測(cè)量要將上行流和下行流映射到同一個(gè)表項(xiàng)中，為了實(shí)現(xiàn)這一點(diǎn)，每到達(dá)一個(gè)報(bào)文，先將它的源IP地址和目的IP地址串，源端口和目的端口串互換位置再計(jì)算它的哈希值。計(jì)算公式如下：

圖1　大流抽樣流程圖

圖2　處理流記錄流程圖

然后判斷該報(bào)文是否屬于對(duì)應(yīng)h'表項(xiàng)記錄的流中。判斷的條件有：①該流記錄是否存在；②若流記錄存在，其表示的流是否結(jié)束。如果未結(jié)束，則說明該報(bào)文是屬于該表項(xiàng)對(duì)應(yīng)的流中，此時(shí)，更新該流記錄。如果表項(xiàng)表示的流結(jié)束，則對(duì)其進(jìn)行處理，處理的流程如圖2所示。然后利用式（5）重新計(jì)算哈希值h，判斷報(bào)文是否屬于新的哈希值對(duì)應(yīng)表項(xiàng)記錄的流中，是的話更新流記錄，否則處理該流記錄。這樣，可以保證雙向流兩個(gè)方向的報(bào)文均映射到同一個(gè)流表表項(xiàng)中。

當(dāng)報(bào)文是第1次進(jìn)入流記錄的處理過程中時(shí)，將首先判斷該表項(xiàng)對(duì)應(yīng)的流是否為大流。如果是，則保存該流信息至外存中供以后分析使用，然后置空該表項(xiàng)供以后的流使用。如果該表項(xiàng)對(duì)應(yīng)的是小流則不必保存流信息，直接將其置空即可。當(dāng)該報(bào)文是第2次進(jìn)入流記錄處理過程中時(shí)，說明該報(bào)文來自一個(gè)新流，此時(shí)判斷完是否保存以前的流信息后，直接覆蓋該表項(xiàng)以記錄新的流信息即可。

3　仿真驗(yàn)證

本文仿真驗(yàn)證中所使用的數(shù)據(jù)是由MAWI工作組在互聯(lián)網(wǎng)上采集得到的。設(shè)在一定的時(shí)間內(nèi)網(wǎng)絡(luò)中共有大流的數(shù)量為l條，總的字節(jié)數(shù)為b1；小流的數(shù)量為x條，總的字節(jié)數(shù)為b2。采用流抽樣算法進(jìn)行測(cè)量后，測(cè)得的大流字節(jié)數(shù)為，相對(duì)誤差，由上述情形②、③造成的被誤測(cè)的小流數(shù)為，占小流總數(shù)的比例，用指標(biāo)來衡量流抽樣算法的好壞。

將字節(jié)數(shù)超過鏈路容量0.01%的流認(rèn)為是大流，流的超時(shí)時(shí)間設(shè)為Netflow默認(rèn)的15 s，流的持續(xù)時(shí)間設(shè)為默認(rèn)的30 min。仿真所使用的數(shù)據(jù)由MAWI工作組在互聯(lián)網(wǎng)上采集得到，共有單向流11 500條，其中，大流所占比例為11.59%，大流字節(jié)數(shù)所占比例為86.12%；雙向流9 588條，其中大流所占比例14.08%，大流字節(jié)數(shù)所占比例87.66%。顯然，該實(shí)驗(yàn)數(shù)據(jù)服從重尾分布。SRAM存儲(chǔ)器作為流表共有2m個(gè)表項(xiàng)，由于目前存儲(chǔ)器的最大值為64 M，故m≤12。

分別采用單向流和雙向流算法對(duì)大流進(jìn)行測(cè)量，所得結(jié)果如表1所示。

表1　實(shí)驗(yàn)結(jié)果對(duì)比表

不同索引位數(shù)條件下單雙向流測(cè)量誤測(cè)小流相對(duì)值、絕對(duì)值比較見圖3、圖4。

圖3　不同索引位數(shù)條件下單雙向流測(cè)量誤測(cè)小流相對(duì)值比較

圖4　不同索引位數(shù)條件下單雙向流測(cè)量誤測(cè)小流相對(duì)值比較

從表1及圖3、圖4可以看出，當(dāng)SRAM容量一定時(shí)，雖然大多數(shù)情況下采用雙向流抽樣算法得到的誤測(cè)小流相對(duì)值Δ要略高于單向流抽樣算法（超出幅度小于1%），但是其誤測(cè)小流的絕對(duì)值x'卻明顯低于單向流抽樣。這說明，雙向流測(cè)量能更有效地提高流表的利用率，減少小流被誤檢的概率。大流相對(duì)誤差的測(cè)量結(jié)果表明，雙向流對(duì)大流測(cè)量的精度要優(yōu)于單向流，充分證明了算法分析中的結(jié)論。如果在一定的時(shí)間內(nèi)，網(wǎng)絡(luò)中的任一單向流都有其對(duì)應(yīng)的反向流，那么使用雙向流測(cè)量可以使這段時(shí)間內(nèi)流的數(shù)量減少一半，所測(cè)得大流相對(duì)誤差將明顯低于單向流測(cè)量的結(jié)果。

4　結(jié)束語

隨著高速網(wǎng)絡(luò)的不斷發(fā)展，網(wǎng)絡(luò)流量測(cè)量的應(yīng)用變得越來越普遍。本文提出的雙向流抽樣算法能在SRAM容量一定的前提下提高大流的測(cè)量精度。由于抽樣算法采用的是目前已在路由器中廣泛使用的Netflow技術(shù)，因此實(shí)現(xiàn)和應(yīng)用方便。對(duì)雙向流進(jìn)行抽樣的思想也能推廣至其他的網(wǎng)絡(luò)流量抽樣算法中。

雖然兩個(gè)大流映射至同一表項(xiàng)的概率很低，但一旦發(fā)生，造成的后果很嚴(yán)重，因此，本文下一步的工作是繼續(xù)研究如何以較小的時(shí)空代價(jià)完全避免這種情況的發(fā)生。

［1］程光，龔儉，互聯(lián)網(wǎng)流測(cè)量［M］.南京：東南大學(xué)出版社，2008.

［2］劉瓊，劉珍，黃敏.基于機(jī)器學(xué)習(xí)的IP流量分類研究［J］.計(jì)算機(jī)科學(xué)，2010，37（12）：35-40.

［3］裴育杰，王洪波，程時(shí)端.基于兩級(jí)LRU機(jī)制的大流檢測(cè)算法［J］.電子學(xué)報(bào)，2009，37（4）：684-685.

［4］Feldmann A，Greenberg A，Lund C，etal.Deriving Traffic Demands for Operational IP Networks:Methodology and Experience［J］.IEEE/ACM Transactions on Networking，2001，9（3）：265-280.

［5］Zhang Y，Breslau L，Paxson V，etal.On the Characteristics and Origins of Internet Flow Rates［C］//In Proceedings of the 2002 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.New York:ACM，2002：309-322.

［6］Fang W，Peterson L.Inter-AS Traffic Patterns and Their Implications［C］//In Global Telecommunications Conference（GLOBECOM'99），Piscataway:IEEE，1999：1859-1868.

［7］Cristian E，George V.New Directions in Traffic Measurement and Accounting［J］.SIGCOMM Computer CommunicationReview，2002，32（4）：323-336.

［8］Broder A，Mitzenmacher M.Network Applications of Bloom Filters:A Survey［J］.Internet Mathematics，2002，1（4）：485-509.

［9］Duffield N G，Lund C，Thorup M.Flow Sampling under Hard Resource Constraints［C］//Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems,New York,ACM Press，2004：85-96.

［10］Smitha，KimI，Reddy A.Identifyinglong-termhigh-band-width Flows at a Router［C］//In Proceedings of the 8th International Conference on High Performance Computing,Berlin，Springer-Verlag，2001：361-371.

［11］Chio B Y，Bhattacharyya S.Observations on Cisco Sampled NetFlow［J］.Special Issue on the First ACM SIGMETRICS Workshop on Large Scale Network Inference，2005，33（3）：18-23.

［12］陳亮，龔儉.基于NetFlow記錄的高速應(yīng)用流量分類方法［J］.通信學(xué)報(bào)，2012，33（1）：145-152.

［13］Keys K,Moore D，Estan C.A Robust System for Accurate Real-time Summaries of Internet Traffic［C］//In Proceedings of the 2005 ACM SIGMETRICS International Conference,Banff，Alberta，Canada，2005：85-96.

［14］Zhao Q，Kumar A，Xu J.Joint data Streaming and Sampling Techniques for Detection of Super Sources and Destinations［C］//In Proceedings of Internet Measurement Conference 2005，Berkeley，CA，2005：77-90.

［15］王洪波.互聯(lián)網(wǎng)測(cè)量系統(tǒng)可擴(kuò)展性問題及其關(guān)鍵算法研究［D］.北京:北京郵電大學(xué)，2006.

Design of a Large Flow Sampling Algorithm Based on Netflow Mechanism

LI Chuan，LI Min
（Mianyang Vocational and Technical College，Mianyang 621000，China）

It is a hot issue in the current study on network measurement that how to improve the measurement accuracy of the large flow under the certain condition of the limited fast memory capacity. First of all，the idea of a two-way flow sampling measurement has been put up while not affecting the application requirements.It is proved that the measurement of the two-way flow can improve the utilization of the stream table and the measurement accuracy of the large flow effectively based on the mathematical analysis of flow sampling algorithm.To realize the sampling algorithm based on the Netflow mechanism，the hash function and the structure of the stream table entry have been designed in detail and the problem that a two-way flow mapping to the same stream table entry has been focused on and solved.Finally，the algorithm has been simulated with the actual data from the network.The result indicates that the flow measurement accuracy of the algorithm is superior to that of the unidirectional flow measurement algorithm when the storage resource is limited.

large flow sampling，two-way flow，netflow，measurement accuracy

TP391

A

1002-0640（2015）08-0127-04

2014-06-25

2014-08-19

四川省教育廳自然科學(xué)重點(diǎn)基金資助項(xiàng)目（15ZA0369）

李川（1972-），男，漢族，四川綿陽人，碩士，副教授。研究方向：信號(hào)處理與傳輸?shù)取?/p>