一種新的數(shù)據(jù)包公平抽樣算法

摘 要：互聯(lián)網(wǎng)作為20世紀(jì)發(fā)展最為迅速的技術(shù)之一，已經(jīng)成為現(xiàn)代信息社會(huì)最重要的基礎(chǔ)設(shè)施，成為國家進(jìn)步和社會(huì)發(fā)展的重要支柱。本文針對(duì)現(xiàn)有數(shù)據(jù)包抽樣算法小流估計(jì)誤差大的缺陷，提出一種新的數(shù)據(jù)包抽樣算法。該算法根據(jù)到達(dá)數(shù)據(jù)包所屬流大小的估計(jì)值設(shè)置包抽樣率，使得大流所含數(shù)據(jù)包抽樣率低，小流所含數(shù)據(jù)包抽樣率高。理論分析和實(shí)驗(yàn)結(jié)果均表明，與已有算法相比，該算法具有更高的準(zhǔn)確性和良好的擴(kuò)展性，更適合于工程應(yīng)用。

關(guān)鍵詞：流量測量；流量抽樣；大流識(shí)別；數(shù)據(jù)包抽樣

中圖分類號(hào)：TP393.06

1 數(shù)據(jù)包公平抽樣概述

互聯(lián)網(wǎng)規(guī)模的不斷壯大，使得全面地理解、掌握網(wǎng)絡(luò)運(yùn)行行為、預(yù)測網(wǎng)絡(luò)未來的發(fā)展、監(jiān)控、管理互聯(lián)網(wǎng)越來越難?；ヂ?lián)網(wǎng)的復(fù)雜化致使人們對(duì)這樣一個(gè)日益信賴的信息基礎(chǔ)設(shè)施，依然知之甚少。在當(dāng)前高速網(wǎng)絡(luò)鏈路條件下，傳統(tǒng)的全數(shù)據(jù)測量方式已不再適用。為了實(shí)現(xiàn)線速測量，對(duì)于每個(gè)數(shù)據(jù)包，能允許的平均處理時(shí)間越來越小，如果使用專用的硬件實(shí)現(xiàn)流量測量，代價(jià)極大。為了降低代價(jià)，提高可擴(kuò)展性，流量縮減是有效的方法。抽樣是其中最有效的方法之一。然而，由于網(wǎng)絡(luò)數(shù)據(jù)流流量分布的不均勻性，常用的均勻隨機(jī)抽樣和固定周期抽樣卻無法完整地保留數(shù)據(jù)流級(jí)的流量信息，如并發(fā)流數(shù)目、流長分布等等。但是，網(wǎng)絡(luò)安全檢測、網(wǎng)路入侵檢測和業(yè)務(wù)流分類等需要完整數(shù)據(jù)流級(jí)信息的應(yīng)用而言，均勻隨機(jī)抽樣抽取了占網(wǎng)絡(luò)流總數(shù)很小那部分大流，而占網(wǎng)絡(luò)流總數(shù)很大的那部分小流卻有很多無法被抽取。這種情況下，公平抽樣被提出，是指通過犧牲大流的數(shù)據(jù)分組抽樣率以換取更高的小流數(shù)據(jù)分組抽樣率。

簡單、高效、準(zhǔn)確地測量是深入理解網(wǎng)絡(luò)基本特性、掌握網(wǎng)絡(luò)行為規(guī)律的基礎(chǔ)，而網(wǎng)絡(luò)流量測量作為網(wǎng)絡(luò)測量的重要組成部分，通常以數(shù)據(jù)包為處理單元進(jìn)行操作。在每個(gè)數(shù)據(jù)包到來時(shí)需要進(jìn)行一次處理，因此，數(shù)據(jù)采集的計(jì)算復(fù)雜度與網(wǎng)絡(luò)數(shù)據(jù)包到達(dá)的頻率PPS（packets per second，每秒分組數(shù)）成正比。隨著帶寬的增加，數(shù)據(jù)包到達(dá)頻率越來越高，使得單位數(shù)據(jù)包的處理時(shí)間越來越短，處理難度越來越大，這就要求網(wǎng)絡(luò)流量測量設(shè)備具有更高的能力去處理每個(gè)數(shù)據(jù)包。在這種情況下，通過抽樣選擇部分有代表性的數(shù)據(jù)進(jìn)行處理，是高速網(wǎng)絡(luò)流量測量的一個(gè)解決方案。1993年，Claffy提出將抽樣方法用于網(wǎng)絡(luò)流量測量中，以估計(jì)數(shù)據(jù)包大小和到達(dá)間隔。在此之后，抽樣成為高速網(wǎng)絡(luò)流量測量的基本方法之一。當(dāng)前應(yīng)用最廣泛的抽樣方法是均勻隨機(jī)抽樣和系統(tǒng)抽樣。均勻隨機(jī)抽樣以固定概率p對(duì)任意數(shù)據(jù)包進(jìn)行抽樣。系統(tǒng)抽樣以固定的間隔抽取對(duì)象，在選擇抽取第一個(gè)對(duì)象后，每隔N個(gè)對(duì)象選擇下一個(gè)對(duì)象。Cisco將抽樣機(jī)制應(yīng)用于Netflow中，成為當(dāng)前網(wǎng)絡(luò)設(shè)備中應(yīng)用最廣泛的流量采集技術(shù)之一。

由于網(wǎng)絡(luò)中的流具有“重尾分布”的特性，隨機(jī)抽樣等傳統(tǒng)的抽樣方法會(huì)丟失大量小流信息，正是在這一背景下，研究人員提出了“公平抽樣”，其基本思想是犧牲少量大流數(shù)據(jù)包的抽樣率，提升小流數(shù)據(jù)包的抽樣率。比較經(jīng)典的算法為SGS算法（sketch guided sampling），通過設(shè)置包抽樣比為該數(shù)據(jù)包所屬流的當(dāng)前流量的遞減函數(shù)，與傳統(tǒng)抽樣方法相比，SGS算法較好地保證了數(shù)據(jù)流之間公平性，但仍然存在小流估計(jì)誤差大的缺點(diǎn)。本章正是針對(duì)這一缺陷，提出一種新的用于流大小估計(jì)的算法，我們稱之為EstFlows算法。

2 EstFlows算法原理

設(shè)置一塊緩存用于存儲(chǔ)流記錄，當(dāng)有數(shù)據(jù)包到來時(shí)，查看緩存中是否存在對(duì)應(yīng)的流記錄，若存在，則以概率p（s）抽取該數(shù)據(jù)包并更新流記錄；否則，抽取該數(shù)據(jù)包，創(chuàng)建新的記錄?？紤]到緩存溢出時(shí)的特殊情況，在查找流記錄之前，加入了緩存是否已滿的判斷語句。

公平抽樣的出發(fā)點(diǎn)是以犧牲少量大流數(shù)據(jù)包的抽樣率換取小流數(shù)據(jù)包的抽樣率，從而提高小流的估計(jì)準(zhǔn)確度。因此，數(shù)據(jù)包的抽樣概率應(yīng)設(shè)定為一隨數(shù)據(jù)包數(shù)目增加而遞減的函數(shù)，本章定義為p（s）=1/（1+（εs）2），其中ε為平均評(píng)估誤差。

該抽樣函數(shù)與SGS方法所使用的抽樣函數(shù)相比，隨著數(shù)據(jù)包的增加，函數(shù)值，即抽樣率下降的更快，進(jìn)一步降低了大流數(shù)據(jù)包抽樣時(shí)消耗的資源，用于小流數(shù)據(jù)包的抽樣，提高了小流估計(jì)的準(zhǔn)確性。

3 理論分析

網(wǎng)絡(luò)流量測量中通常使用時(shí)間復(fù)雜度、空間復(fù)雜度、內(nèi)存訪問次數(shù)和準(zhǔn)確性四個(gè)指標(biāo)衡量算法的優(yōu)劣。時(shí)間復(fù)雜度和內(nèi)存訪問次數(shù)直接關(guān)系到算法的處理速度，決定了算法是否滿足實(shí)際應(yīng)用的需求，尤其在當(dāng)前的高速網(wǎng)絡(luò)鏈路中，顯得尤為重要?，F(xiàn)在的半導(dǎo)體技術(shù)是否能達(dá)到算法的要求，空間復(fù)雜度是很重要的一個(gè)指標(biāo)，是工程應(yīng)用的基礎(chǔ)。

3.1 時(shí)間復(fù)雜度

當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)，首先查看流緩存中是否存在相應(yīng)的流記錄，本章采用hash方案，計(jì)算復(fù)雜度為O（1）。在此之后的操作包括流記錄的更新和新建等，都是有限常數(shù)次指針操作，其計(jì)算復(fù)雜度為O（1），因此該方法處理一個(gè)數(shù)據(jù)包所需時(shí)間為O（1）。

3.2 空間復(fù)雜度

由于EstFlow算法中每個(gè)流的第一個(gè)數(shù)據(jù)包都會(huì)被抽取，因此，該算法所需存儲(chǔ)空間的大小就是測量時(shí)間段內(nèi)流的數(shù)目，因而也是確定不變的，即為流記錄緩存的大小。假設(shè)R為鏈路速率（單位為字節(jié)每秒），b為數(shù)據(jù)包平均大??；n為每流平均數(shù)據(jù)包數(shù)，則在時(shí)間t內(nèi)到達(dá)的流個(gè)數(shù)，也即所需流記錄緩存大小為M=[t/（bn）]R。

3.3 內(nèi)存訪問次數(shù)

訪問存儲(chǔ)器次數(shù)，是影響一個(gè)算法能否處理高速網(wǎng)絡(luò)數(shù)據(jù)的重要因素之一。本章算法中，每個(gè)數(shù)據(jù)包到達(dá)時(shí)，查找是否存在相應(yīng)的流記錄，采用hash表存儲(chǔ)，需訪問存儲(chǔ)器1次。如果沒有相應(yīng)的流記錄，則新建，此時(shí)，需要訪問存儲(chǔ)器2次，包括寫操作和指針。否則，則丟棄該數(shù)據(jù)包。因此，每個(gè)數(shù)據(jù)包需要訪問內(nèi)存的次數(shù)最多為3次，最少為1次。

3.4 實(shí)現(xiàn)的考慮

EstFlow算法中，流記錄緩存最多需要訪問內(nèi)存3次。當(dāng)前的半導(dǎo)體技術(shù)中，SRAM的訪問速度可以達(dá)到2-4ns。假定采用訪問速度為3ns的SRAM，最壞情況下EstFlow算法需要9ns處理一個(gè)數(shù)據(jù)包。在OC-192鏈路上，設(shè)滿速率傳輸包長為40字節(jié)的數(shù)據(jù)包，則包到達(dá)間隔為32ns。因此，MFEPS算法完全可以滿足OC-192鏈路的要求。

4 實(shí)驗(yàn)驗(yàn)證

準(zhǔn)確性是測量的基本要求，本章使用測量誤差的標(biāo)準(zhǔn)差來衡量算法流量估計(jì)的準(zhǔn)確性。定義如下：假設(shè)在測量周期內(nèi)，鏈路上共有N條并發(fā)流Fi（1≤i≤N），F(xiàn)i的流量大小為fi（1≤fi≤M），fi的估計(jì)值為 。

令 ，Ej={ei|f=j}（j∈[1，M]），定義流量大小為i的數(shù)據(jù)流的測量誤差的標(biāo)準(zhǔn)差為 。

實(shí)驗(yàn)所用數(shù)據(jù)相關(guān)信息如表1所示。

圖1是我們對(duì)實(shí)驗(yàn)數(shù)據(jù)分析所得，橫軸表示流從小到大的順序，縱軸表示流的大小。為了有更直觀的顯示效果，我們只選取了放大后的部分曲線。可以發(fā)現(xiàn)，大流數(shù)量少，但包含流量多，而小流數(shù)量多，包含流量小，即滿足“重尾分布”特性，這是符合前人的研究成果的。

表1 實(shí)驗(yàn)數(shù)據(jù)

DataLink typerateMeasurement interval

TraceOC19210Gbit/s4800s

圖1 實(shí)驗(yàn)數(shù)據(jù)分析圖

圖2為分別取ε=0.5和ε=0.2時(shí)EstFlow算法和SGS算法用于流量估計(jì)時(shí)的測量誤差標(biāo)準(zhǔn)差。可以發(fā)現(xiàn)，在ε=0.5時(shí)，EstFlow算法的標(biāo)準(zhǔn)差低于SGS方法，且在流大小為15000左右時(shí)，近乎相等。在ε=0.2時(shí)，兩種算法的標(biāo)準(zhǔn)差基本相同，在流大小為15000時(shí)，基本相同。綜合來看，對(duì)于小流來說，EstFlow算法的標(biāo)準(zhǔn)誤差低于SGS算法更為明顯，這恰恰驗(yàn)證了前文抽樣率的變化，即和SGS算法相比，EstFlow算法降低了大流的數(shù)據(jù)包抽樣率，提升了小流估計(jì)的準(zhǔn)確性。

（a）ε=0.5

（b）ε=0.2

圖2 流量估計(jì)誤差標(biāo)準(zhǔn)差

5 結(jié)束語

本章針對(duì)SGS算法的缺點(diǎn)，提出了一種用于網(wǎng)絡(luò)中流大小估計(jì)的算法—EstFlow算法。該算法設(shè)定數(shù)據(jù)包的抽樣概率為一隨數(shù)據(jù)包個(gè)數(shù)增加而遞減的函數(shù)，以達(dá)到數(shù)據(jù)流之間的公平抽樣。和已有的SGS算法相比，EstFlow算法進(jìn)一步降低了大流數(shù)據(jù)包的抽樣概率，提高小流估計(jì)的準(zhǔn)確性。通過理論分析和實(shí)驗(yàn)驗(yàn)證，EstFlow算法能夠滿足10Gbit/s鏈路的測量需要，同時(shí)具有較高的準(zhǔn)確性，且易于實(shí)現(xiàn)，更適合工程應(yīng)用。下一步的主要工作是根據(jù)不同的業(yè)務(wù)需求，有針對(duì)性地采用不同方法進(jìn)行流量測量。

參考文獻(xiàn)：

[1]Claffy K C，Polyzos G C，Braun H W.Application of sampling methodologies to network traffic characterization[J].ACM SIGCOMM Computer Communication Review，1993（04）：194-203.

[2]Hu C，Liu B，Wang S，et al.ANLS：Adaptive Non-Linear Sampling Method for Accurate Flow Size Measurement[J].Communications，IEEE Transactions on，2012（03）：789-798.

[3]Bhatia S，Kumar A，F(xiàn)iuczynski M E，et al.Lightweight，high-resolution monitoring for troubleshooting production systems[C]//Proceedings of the 8th USENIX conference on Operating systems design and implementation.USENIX Association，2008：103-116.

[4]董永吉，陳庶樵，劉強(qiáng).網(wǎng)絡(luò)自適應(yīng)公平分組抽樣算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010（02）：270-274.

[5]Kumar A，Xu J.Sketch guided sampling–using on-line estimates of flow size for adaptive data collection[C]//Proc.IEEE Infocom.2006.

[6]Grieco L A，Barakat C.An analysis of packet sampling in the frequency domain[C]//Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference.ACM，2009：170-176.

[7]張進(jìn)，鄔江興，鈕曉娜.空間高效的數(shù)據(jù)包公平抽樣算法[J].

作者簡介：夏靖波（1963-），男，河北秦皇島人，教授，博士后，主要從事軍事通信網(wǎng)絡(luò)規(guī)劃、軍事通信網(wǎng)絡(luò)管理技術(shù)研究。

作者單位：西安工業(yè)大學(xué)，西安 710021