基于流量負載的改進型幾何抽樣算法

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

(空軍工程大學 信息與導航學院，陜西 西安710077)

網絡流量測量和分析是研究網絡行為的基礎，其對于網絡問題的解決、協議的調試和網絡性能評估等方面均有極大的幫助。但是隨著近年來高速網絡技術的發展，想要全部采集鏈路上的數據流量十分困難，而且需要巨大的開銷，因而抽樣測量技術成為當今在高速鏈路上進行流量測量的一種解決方案。近年來，對網絡流量抽樣技術的研究已成為高速網絡流量測量研究的重點內容。

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

1 算法分析

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

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

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

2 改進方案

報文被丟棄的根本原因是在流量高峰時網絡節點的處理能力與報文的到達速率不匹配，造成抽樣報文在緩存中累積，當達到緩存容量的上限時被丟失。節點工作最理想的狀態是當節點處理完上一個抽中報文時恰好抽中下一個報文，這樣每一個抽中的報文將得到及時的處理而不會在緩沖中累積，丟失的報文數將大大減小。為了實現這一點，抽樣算法應該根據流量負載的動態變化自適應地調節抽樣概率以匹配節點的處理能力從而盡量避免報文的丟失。

2.1 抽樣概率的調節

報文的到達過程如圖1所示。

圖1 報文的到達過程

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

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

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

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

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

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

在流量高峰時，抽樣算法將根據節點的處理能力和負載狀況利用式(6)動態計算抽樣概率以減少丟棄的報文數量。

圖2 改進型算法的基本流程

2.2 算法流程

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

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

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

3 實驗驗證

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

3.1 有效性分析

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

圖3 單位時間丟棄的報文數比較

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

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

3.2 測量精度比較

利用上述算法得到的樣本分析單位時間內經過節點的網絡流量，定義測量誤差，其中，為估計流量，Q為實際流量，分析結果如圖5所示。

圖5 測量誤差比較

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

如果實驗所用的流量數據在時間上是均勻分布的，即每隔606.3μs到達一個報文，那么抽樣算法即使以概率p=p0=1抽樣，節點也能順利地處理完所有報文而不存在測量誤差。但是根據測量結果可知網絡流量的突發是不可預測的，在任意測量時間內都可能出現流量突發的情況，因此所做的改進是十分必要的。

4 小結

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

［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］.計算機工程，2010，36(15):7-11.

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

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

［7］張震，汪斌強，朱珂.流量測量的關鍵技術分析與研究［J］.計算機應用研究，2009，26(9):3442-3447.

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

［9］楊家海，吳建平，安常青.互聯網絡測量理論與應用［M］.北京:人民郵電出版社，2009.

［10］張進，劉勤讓，司亮，等.一種基于兩級存儲結構的網絡流量測量算法［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.