基于流量負(fù)載的改進(jìn)型幾何抽樣算法

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

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

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

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

1 算法分析

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

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

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

2 改進(jìn)方案

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法流程

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

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

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

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

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

3.1 有效性分析

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

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

圖4 單位時(shí)間的丟包率比較

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

3.2 測(cè)量精度比較

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

圖5 測(cè)量誤差比較

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

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

4 小結(jié)

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

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

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

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

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

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

［10］張進(jìn)，劉勤讓，司亮，等.一種基于兩級(jí)存儲(chǔ)結(jié)構(gòu)的網(wǎng)絡(luò)流量測(cè)量算法［J］.計(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.