孫 昱，夏靖波，趙小歡，申 健

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

網(wǎng)絡(luò)流量測量和分析是研究網(wǎng)絡(luò)行為的基礎(chǔ)，其對于網(wǎng)絡(luò)問題的解決、協(xié)議的調(diào)試和網(wǎng)絡(luò)性能評估等方面均有極大的幫助。但是隨著近年來高速網(wǎng)絡(luò)技術(shù)的發(fā)展，想要全部采集鏈路上的數(shù)據(jù)流量十分困難，而且需要巨大的開銷，因而抽樣測量技術(shù)成為當(dāng)今在高速鏈路上進(jìn)行流量測量的一種解決方案。近年來，對網(wǎng)絡(luò)流量抽樣技術(shù)的研究已成為高速網(wǎng)絡(luò)流量測量研究的重點(diǎn)內(nèi)容。

1993年，Claffy在測量NSFNET主干網(wǎng)流量時，對采用不同觸發(fā)機(jī)制的傳統(tǒng)抽樣方法進(jìn)行了分析對比［1］，證明了基于計數(shù)觸發(fā)機(jī)制的抽樣算法要普遍優(yōu)于基于時間觸發(fā)機(jī)制抽樣算法。2005年，Duffield等人指出了均勻抽樣在流量測量領(lǐng)域存在的問題，并提出了“非均勻抽樣”的方法［2］。由于自適應(yīng)抽樣可以利用網(wǎng)絡(luò)流量的相關(guān)性預(yù)測流量狀態(tài)，并實時調(diào)整抽樣策略或參數(shù)以獲得更好的測量效果，因此逐漸受到重視。自適應(yīng)抽樣算法主要分為兩類，一類通過流量模型對未來的流量進(jìn)行預(yù)測，然后根據(jù)預(yù)測的結(jié)果動態(tài)地調(diào)節(jié)抽樣概率以提高測量的精度，目前應(yīng)用效果比較好的模型是FARIMA模型［3-4］和NMSM模型［5］。另一類自適應(yīng)算法主要從抽樣資源有限的角度出發(fā)，通過調(diào)節(jié)抽樣概率匹配報文的到達(dá)速率以避免資源耗盡對測量造成的不利影響。抽樣資源主要包括設(shè)備的處理能力和緩存等，目前，這方面的大多數(shù)研究工作都是根據(jù)緩存容量的大小來設(shè)計自適應(yīng)的抽樣方案［6-8］。但是由于網(wǎng)絡(luò)流量具有突發(fā)性，在流量高峰期短時間內(nèi)來的報文基數(shù)會很大，采用基于緩存的自適應(yīng)抽樣也同樣難以避免緩存溢出而導(dǎo)致的報文丟失，進(jìn)而影響了抽樣算法的效能，使得測量不能準(zhǔn)確地反映峰值的狀況。要較好地解決這一問題，還必須將抽樣設(shè)備的處理能力考慮在內(nèi)，由于幾何抽樣具有良好的抽樣性能，因此，本文將對其進(jìn)行改進(jìn)，使之能根據(jù)抽樣設(shè)備的處理能力和流量負(fù)載動態(tài)地調(diào)節(jié)抽樣概率，通過降低設(shè)備的丟包率來提高網(wǎng)絡(luò)流量的測量精度。

1 算法分析

幾何抽樣算法［9］是以固定的概率p對經(jīng)過的每個報文進(jìn)行抽樣，當(dāng)每到達(dá)一個報文時，網(wǎng)絡(luò)節(jié)點(diǎn)就產(chǎn)生一個在0～1之間服從均勻分布的偽隨機(jī)數(shù)，若該隨機(jī)數(shù)小于抽樣概率p，則該報文被抽中，否則該報文被丟棄。它的抽樣間隔X服從概率為p的幾何分布，即P(X=n)=(1-p)n-1p。幾何抽樣是一種運(yùn)用廣泛的抽樣技術(shù)，與RFC2330所推薦的泊松抽樣一樣，具有以下優(yōu)點(diǎn):1)樣本在總體中分布均勻，分析所得的各種參數(shù)都相對比較準(zhǔn)確;2)不易引起同步效應(yīng)，能夠用來準(zhǔn)確地收集周期行為的測量樣本;3)抽樣方法實現(xiàn)簡單，具備良好的可擴(kuò)展性。

當(dāng)一個報文被抽中時，網(wǎng)絡(luò)節(jié)點(diǎn)將對其進(jìn)行分析以得到某些需要的信息，然后將這些信息存入存儲設(shè)備中，這段時間稱為報文的處理時間。在網(wǎng)絡(luò)流量的高峰時期，報文的到達(dá)速率將高于網(wǎng)絡(luò)節(jié)點(diǎn)對報文的處理速率。因此，當(dāng)節(jié)點(diǎn)正在處理某個抽中報文時，很可能有新的報文到達(dá)并被抽中，此時，新抽中的報文將被存放于網(wǎng)絡(luò)節(jié)點(diǎn)的緩存中等待處理。但是在流量高峰期短時間內(nèi)經(jīng)過節(jié)點(diǎn)的報文基數(shù)很大，節(jié)點(diǎn)抽中的報文數(shù)量相對較多，來不及處理的報文都被放入緩存中，將很快造成緩存溢出，導(dǎo)致丟包率過高。雖然可以從硬件的角度，例如通過增加緩存容量和改善緩存結(jié)構(gòu)［10］等方法來緩解這一問題，但是這些措施的擴(kuò)展能力不強(qiáng)而且所需的成本太高，因此應(yīng)用受到限制。

報文被丟棄會對測量的精度造成十分不利的影響，以網(wǎng)絡(luò)流量的測量為例進(jìn)行說明。當(dāng)測量單位時間內(nèi)網(wǎng)絡(luò)中經(jīng)過的流量時，通過采樣得到單位時間內(nèi)的一個樣本X1，X2，…，Xn，Xi表示第i個抽樣報文的字節(jié)數(shù)。那么該段時間內(nèi)經(jīng)過鏈路總流量的估計值為由于一些被抽中的報文還來不及處理就被丟棄了，這將導(dǎo)致:1)抽樣樣本的隨機(jī)性變差，這會直接影響測量結(jié)果的精度;2)估計量X*是無偏估計的前提條件是樣本由等概率抽樣獲得，而發(fā)生報文丟棄的事件將破壞這一前提條件，也會造成測量精度的下降。

2 改進(jìn)方案

報文被丟棄的根本原因是在流量高峰時網(wǎng)絡(luò)節(jié)點(diǎn)的處理能力與報文的到達(dá)速率不匹配，造成抽樣報文在緩存中累積，當(dāng)達(dá)到緩存容量的上限時被丟失。節(jié)點(diǎn)工作最理想的狀態(tài)是當(dāng)節(jié)點(diǎn)處理完上一個抽中報文時恰好抽中下一個報文，這樣每一個抽中的報文將得到及時的處理而不會在緩沖中累積，丟失的報文數(shù)將大大減小。為了實現(xiàn)這一點(diǎn)，抽樣算法應(yīng)該根據(jù)流量負(fù)載的動態(tài)變化自適應(yīng)地調(diào)節(jié)抽樣概率以匹配節(jié)點(diǎn)的處理能力從而盡量避免報文的丟失。

2.1 抽樣概率的調(diào)節(jié)

報文的到達(dá)過程如圖1所示。

圖1 報文的到達(dá)過程

圖1 中垂直的箭頭代表報文的到達(dá)，實線的箭頭代表該報文被抽中，虛線代表該報文未被抽中。假設(shè)節(jié)點(diǎn)處理一個報文需要的平均時間為T，若該節(jié)點(diǎn)在時刻t0時以概率p0抽中了一個報文A，然后再有報文到達(dá)時，節(jié)點(diǎn)將以新的抽樣概率p1進(jìn)行幾何抽樣，直到在時刻t1抽中下一個報文B。在時段(t0，t0+T］內(nèi)，經(jīng)過節(jié)點(diǎn)的報文數(shù)為N，在時段(t0，t1］內(nèi)，經(jīng)過節(jié)點(diǎn)的報文數(shù)為Y。當(dāng)t1≤t0+T時，由于節(jié)點(diǎn)正在處理報文A，若不考慮節(jié)點(diǎn)的緩存，報文B因來不及處理而被丟棄;當(dāng)t1＞t0+T時，報文A已被處理完，節(jié)點(diǎn)能接著處理報文B。由于Y是服從幾何分布的隨機(jī)變量，有P(Y=n)=(1-p1)n-1p1，因此報文B不被丟棄的概率為

若報文B不被丟棄的概率大于α，根據(jù)式(1)，即(1-p1)N≥α，由此得出下一步的采樣概率p1滿足

但是節(jié)點(diǎn)在抽中A后計算下一步的抽樣概率p1時，并不知道N的取值，此時節(jié)點(diǎn)只能依據(jù)歷史信息對N進(jìn)行估計。在時段(t0，t0+T］內(nèi)，報文到達(dá)的平均間隔Δt近似為T/N，在前一個相似的抽樣時段(t0'，t0］內(nèi)，報文到達(dá)的平均間隔Δt'≈(t0-t0')/Y'。流量高峰時，時段(t0'，t0+T］極短，可以認(rèn)為該段時間內(nèi)報文的到達(dá)是均勻的，即Δt=Δt'。由此得到

由于在前一個時段(t0'，t0］中，進(jìn)行幾何抽樣的概率是p0，所以，E(Y')=1/p0，故

式中:β為修正值。聯(lián)立(3)和(4)可得

將式(5)帶入式(2)中，得到下一步的抽樣概率為

在流量高峰時，抽樣算法將根據(jù)節(jié)點(diǎn)的處理能力和負(fù)載狀況利用式(6)動態(tài)計算抽樣概率以減少丟棄的報文數(shù)量。

圖2 改進(jìn)型算法的基本流程

2.2 算法流程

改進(jìn)型幾何抽樣算法的基本流程如圖2所示。

當(dāng)有報文到達(dá)時，節(jié)點(diǎn)將以抽樣概率p對該報文進(jìn)行抽樣，初始的抽樣概率為給定值p'。如果該報文被抽中，則判斷網(wǎng)絡(luò)節(jié)點(diǎn)此時是否空閑，如果節(jié)點(diǎn)正忙導(dǎo)致該報文被丟棄，則很有可能發(fā)生了流量負(fù)載過重的情況，此時將標(biāo)識符置1。當(dāng)下一次抽中報文且節(jié)點(diǎn)空閑時，由于標(biāo)識符為1，那么算法在記錄式(6)需要用到的相關(guān)參數(shù)后將進(jìn)入自適應(yīng)的抽樣階段2。在階段2中，每次抽中報文且節(jié)點(diǎn)的空閑時間沒有超過閾值時，都會利用式(6)動態(tài)地調(diào)整下一次的抽樣概率p。如果節(jié)點(diǎn)的空閑時間超過了閾值，即可認(rèn)為流量負(fù)載減輕了，此時，恢復(fù)初始的抽樣概率p'并進(jìn)入階段1中進(jìn)行抽樣。

由于改進(jìn)型幾何抽樣算法的采樣概率p是可變的，得到的樣本是一個非均勻采樣的樣本，因此在對結(jié)果進(jìn)行估計時無法使用基于等概率采樣的估計量。而Horvitz-Thompson估計量一個適用于非均勻采樣的無偏估計量［11］，因此可以使用它來估計總體的特征參數(shù)。例如在測量網(wǎng)絡(luò)流量時，得到抽樣樣本X1，X2，…，Xn后，先使用Horvitz-Thompson估計量估算無偏的總體均值，然后估計單位時間內(nèi)經(jīng)過節(jié)點(diǎn)的總流量為X*=NˉX=N×

3 實驗驗證

本文實驗所用數(shù)據(jù)來自MAWI工作組［12］在互聯(lián)網(wǎng)骨干鏈路上全流量采集中隨機(jī)抽取的100 s流量數(shù)據(jù)。該流量數(shù)據(jù)中報文到達(dá)的平均時間間隔為606.3μs，假定網(wǎng)絡(luò)節(jié)點(diǎn)處理一個報文需要的時間T為200μs。幾何抽樣的抽樣概率為p=0.8，改進(jìn)型幾何抽樣的初始抽樣概率為p'=0.8，流量高峰時報文不丟棄的概率α=90%。

3.1 有效性分析

為了衡量抽樣算法的有效性，首先定義兩個評價指標(biāo)。第一個為單位時間內(nèi)丟棄的抽中報文的數(shù)量，該指標(biāo)能直觀地反映算法對流量負(fù)載的適應(yīng)能力。由于改進(jìn)型幾何抽樣算法會在流量高峰時降低抽樣率，因此若其丟包數(shù)量更低并不足以說明該算法有效，故定義第二個評價指標(biāo)丟包率為單位時間內(nèi)丟棄的報文個數(shù)與抽中的報文總數(shù)之比。利用MATLAB進(jìn)行仿真，結(jié)果如圖3和圖4所示。

圖3 單位時間丟棄的報文數(shù)比較

圖4 單位時間的丟包率比較

從圖3中可以看出，改進(jìn)型幾何抽樣算法丟包數(shù)量明顯低于原抽樣算法，其單位時間內(nèi)平均丟包數(shù)為101.07個，標(biāo)準(zhǔn)差為27.35，而原算法單位時間內(nèi)平均丟包數(shù)為297.48個，標(biāo)準(zhǔn)差為79.70，這說明，改進(jìn)后的算法能有效降低節(jié)點(diǎn)丟棄的報文數(shù)量。流量高峰時，改進(jìn)算法的理論丟包率為10%，但是由于在非流量高峰時也有可能發(fā)生丟包的情況，因此實際丟包率將略高于10%。圖4中，改進(jìn)型算法的平均丟包率為15.67%，標(biāo)準(zhǔn)差為1.99%，原算法平均丟包率為22.50%，標(biāo)準(zhǔn)差為1.83%。從圖4中還能看出，改進(jìn)型算法在任一時段的丟包率均低于原算法，如果實際網(wǎng)絡(luò)流量突發(fā)次數(shù)多且持續(xù)時間較長，那么二者的差距將十分明顯。由于改進(jìn)算法丟棄的報文個數(shù)和丟包率均更低，證明了該算法對流量負(fù)載的變化具有更好的適應(yīng)性。

3.2 測量精度比較

利用上述算法得到的樣本分析單位時間內(nèi)經(jīng)過節(jié)點(diǎn)的網(wǎng)絡(luò)流量，定義測量誤差，其中，為估計流量，Q為實際流量，分析結(jié)果如圖5所示。

圖5 測量誤差比較

改進(jìn)型幾何抽樣的平均測量誤差為7.20%，標(biāo)準(zhǔn)差為5.33%，而改進(jìn)前的平均測量誤差為49.14%，標(biāo)準(zhǔn)差為4.66%。這說明改進(jìn)后的算法得到的樣本容量雖然可能減少，但是其樣本的隨機(jī)性卻明顯更優(yōu)，從而使測量的參數(shù)更精確，同時也證明了減少網(wǎng)絡(luò)節(jié)點(diǎn)丟棄的報文數(shù)確實能在很大程度上提高網(wǎng)絡(luò)測量的精度。由于在仿真時并沒有考慮節(jié)點(diǎn)的緩存，而實際的抽樣設(shè)備均有一定容量的緩存，所以該算法在實際應(yīng)用時，所得的相對誤差還將進(jìn)一步降低。

如果實驗所用的流量數(shù)據(jù)在時間上是均勻分布的，即每隔606.3μs到達(dá)一個報文，那么抽樣算法即使以概率p=p0=1抽樣，節(jié)點(diǎn)也能順利地處理完所有報文而不存在測量誤差。但是根據(jù)測量結(jié)果可知網(wǎng)絡(luò)流量的突發(fā)是不可預(yù)測的，在任意測量時間內(nèi)都可能出現(xiàn)流量突發(fā)的情況，因此所做的改進(jìn)是十分必要的。

4 小結(jié)

隨著高速網(wǎng)絡(luò)的不斷發(fā)展，網(wǎng)絡(luò)測量的應(yīng)用變得越來越普遍。本文提出的改進(jìn)型幾何抽樣算法能根據(jù)流量負(fù)載的變化自適應(yīng)調(diào)節(jié)抽樣概率以匹配網(wǎng)絡(luò)節(jié)點(diǎn)的處理能力，從而較好地解決流量突發(fā)時丟包率過高造成測量結(jié)果不精確的問題。該算法實現(xiàn)簡單，可擴(kuò)展性強(qiáng)，能為其他抽樣技術(shù)的應(yīng)用起到一定的借鑒作用，本文的下一步工作是考慮抽樣設(shè)備的實際緩存來將該算法進(jìn)行具體的應(yīng)用。

［1］CLAFFY K C，POLYZOS G C，BRAUN H W.Application of sampling methodologies to network traffic characterization［J］.SIGCOMM Computer Communication Review，1993，23(4):194-203.

［2］DUFFIELD NG，LUND C，THORUP M，et al.Sample less:control of volume and variance in network measurement［J］.IEEE Trans.Information Theory，2005，51(5):1756-1775.

［3］HARMANTZIS F C，HATZINAKOS D.Heavy network traffic modeling and simulation using stable FARIMA processes［EB/OL］.［2012-10-10］.http://www.stevens-tech.edu/perfectnet/publications/Papers/H H_ITC19.pdf.

［4］潘喬，羅辛，王高麗，等.基于FARIMA模型的流量抽樣測量方法［J］.計算機(jī)工程，2010，36(15):7-11.

［5］陳松，王珊，周明天.基于實時分析的網(wǎng)絡(luò)測量抽樣統(tǒng)計模型［J］.電子學(xué)報，2010，38(5):1177-1180.

［6］王洪波，韋安明，林宇，等.流測量中基于測量緩沖區(qū)的時間分層分組抽樣［J］.電子學(xué)報，2006，17(8):1775-1784.

［7］張震，汪斌強(qiáng)，朱珂.流量測量的關(guān)鍵技術(shù)分析與研究［J］.計算機(jī)應(yīng)用研究，2009，26(9):3442-3447.

［8］陳庶樵，張果，朱柯.一種基于包速率自適應(yīng)的報文抽樣算法［J］.計算機(jī)應(yīng)用研究，2010，27(7):2727-2729.

［9］楊家海，吳建平，安常青.互聯(lián)網(wǎng)絡(luò)測量理論與應(yīng)用［M］.北京:人民郵電出版社，2009.

［10］張進(jìn)，劉勤讓，司亮，等.一種基于兩級存儲結(jié)構(gòu)的網(wǎng)絡(luò)流量測量算法［J］.計算機(jī)工程，2007，33(10):10-12.

［11］HORVITZ D G，THOMPSON D J.A generalization of sampling without replacement from a finite universe［J］.Journal of the American Statistical Association，1952，47(26):663-685.

［12］MAWI working group traffic archive［EB/OL］.［2012-02-02］.http://mawi.wide.ad.jp/mawi.