一種改進ＣＡＲＥ業務流估計算法

摘要：主要研究了基于CR(capture－recapture)模型業務流估計算法CARE的過程和模型，分析了區分水平值、估計次數和數據列表長度對CARE業務流估計結果的影響，提出一種改進CARE業務流估計算法。新算法修改了CARE算法的估計過程，通過遞歸逐漸得到穩定的估計結果。實驗分別采用計算機模擬數據和美國應用網絡研究國家實驗室NLANR的被動測量和分析工作組(PMA)的數據來對兩種算法進行比較分析。結果表明改進的CARE算法業務流估計更準確。改進的CARE算法可以應用于網絡中間設備實現業務流數目的估計，保證公平的帶寬分配，具有很廣泛的應用前景。

關鍵詞：捕獲—再捕獲模型； 業務流估計

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2007)12-0099-04

主動隊列管理（AQM）是近年來端到端擁塞控制研究中的一個熱點。它的主要技術目標是在減小排隊時延的同時保證較高的吞吐量，確保擁塞控制機制的穩定性，提高資源分配的公平性和對網絡動態變化的自適應性，最終實現QoS機制^[1]。

準確的業務流估計是AQM機制中實現QoS的基本保證。通用業務流估計算法的最基本思想是基于數據包的估計方法。該方法從隊列中隨機取出一個數據包與新的數據包進行比較，如果新數據包和隊列中的數據包是屬于同一個業務流，那么就認為該業務流是活動的；否則就認為隊列中數據包所屬的業務流是不活動的。準確估計的業務流數目為中間設備部署解決方案提供了一定的參考依據^[2，3]，對于中間設備實現QoS機制具有很大意義。

通用的業務流估計方法對于決定數據包的丟棄率是非常有效可行的，然而這種通用的方法對于數據包數量不確定的網絡就不能適用。針對這些不足，文獻[4]提出一種更加簡單有效的算法FNE。該算法維持一個zombie列表，這個列表保存著到達數據包的歷史。一旦到達的數據包與zombie列表中隨機取得的數據包相匹配，就稱為命中（hit）；否則稱為丟失（loss）。如果命中則zombie列表中該記錄不會改變；否則該記錄就會更新為當前新數據包的內容。FNE算法的實現是通過采集當前的命中比率Rhit和失效比率Rloss來計算當前業務流的數目。相比公平隊列機制的通用業務流估計算法來說，FNE算法在減少延遲的情況下保持資源的高利用率，并且容易實現。

文獻[5]提出基于CR模型的業務流估計算法CARE。其主要思想是：首先獲取數據包，并將其存儲在數據列表結構中；再根據數據包ID標志的次數構建一個頻率數據集合；最后利用jackknife estimator^[6]來估計業務流的總數目。相對通用算法來說，該算法的空間利用率高、算法復雜度低。但是，FNE算法和CARE算法均存在一些缺點。FNE算法在算法開銷方面比較大；而對參數的依賴性比較大，參數配置不合理會導致估計結果產生誤差。

1CARE算法

業務流估計算法CARE的基本原理是通過CR模型進行標記和構建頻率數據集合，應用Burnham 等人^[6]提出的generalized jackknife estimator原理來計算業務流數目。其中，CR模型^[7]最開始是用于估計野生動物或者瀕危物種的數量。其基本過程就是將首次捕獲（capture）的動物做上標記后釋放，在足夠時間間隔后再次捕獲（recapture）；基于jackknife estimator原理^[8]，根據再次捕獲的帶有標記的動物數目來估計當前動物的數目。CR模型的主要優點是不需要獲取所有的動物，僅僅根據捕獲部分標記動物數目就可以比較準確地估計整個動物的數目。

2．3數據列表長度的影響

增加估計次數可以提高估計的準確度。但是如果不改變估計次數，而單純增加數據列表長度同樣會獲取到比較充分的數據。在固定估計次數增加數據列表長度的情況下，業務流估計值是逐漸增加的。但是數據列表長度超過一定數值以后，估計值開始逐漸偏離真實業務流數目。因此，雖然增加數據列表長度有利于提高估計的準確度，但是不能任意地無限增加。因為選擇合適的數據列表便能夠獲取到具有代表性的數據，就足以獲得比較準確的估計，冗余的數據信息只能造成數據的重復，不會明顯提高估計值的準確度。要尋找最合適的區間來保證在該區間范圍內估計的業務流數目與真實業務流數目接近。

3改進CARE算法

通過以上對CARE算法的研究，得出一些基本結論。但是針對CARE算法存在的缺點，尤其是區分水平值對估計結果的影響，修改CARE算法的估計過程，提出了一種改進的CARE業務流估計算法。

3．1改進CARE算法的基本原理

改進CARE算法同樣也是基于Mh CR模型通過jackknife estimator機制來進行估計的。但是CARE算法中人為設定區分水平值對估計結果造成了一定的影響。對此筆者修改了CARE算法的估計過程，通過不斷地遞歸來逐漸逼近真實業務流數目。算法估計過程首先假設估計次數為真實業務流的一半進行估計得到第一個估計值S1。但是這次估計僅僅是在假設情況下計算的結果，所以需要調整估計次數再次進行估計，通過遞歸得到穩定的結果，選取第n次的結果作為最終的業務流估計數目?？傊?，改進的CARE算法的基本原理就是在遞歸過程中不斷修正估計次數來滿足條件，最后得到穩定的估計結果。改進的CARE算法偽代碼如下：

從整體上看，改進的CARE算法相對于CARE算法估計出的結果更加接近實際業務流數目。另外隨著真實業務流的增加，CARE算法的估計值與實際業務流誤差越來越大。尤其是當業務流的數目超過50以后，在第七次實驗實際業務流為60的情況下，CARE算法估計出的流數目為33，誤差為45％，而改進的CARE算法估計出的流數目為61，誤差僅為1％；在第八次實驗實際業務流為80的情況下，CARE算法估計出的流數目為34，誤差為57.5％，而改進的CARE算法估計出的流數目為72，誤差為10％。八次實驗CARE算法的平均誤差為26．5%；改進CARE算法的平均誤差為1.6%。所以相比CARE算法來說，改進的CARE算法在估計業務流數目上誤差更小。

本文還選取美國應用網絡研究國家實驗室^[9]的被動測量和分析工作組^[10]的權威被動測量數據來比較兩種算法的性能。PMA旨在為高級網絡提供協作性的服務支持。它采用OC3com數據搜集系統，包括專門的群機系統、裝有FORE ATM cards 和optical splitters，在HPC網絡中設置多個測量點被動測量Internet數據，采集ATM的數據流。本文使用的數據來自測量點TXS^[11]。TXS站點位于Texas Universities GigaPOP at Rice University，每經過3 h采集一次數據，每天采集八次數據。其提供的數據格式為TSH，每個報文長度44 Byte。TSH數據格式包含整個IP報頭和TCP報頭的內容。該實驗采集測量數據時間為2006年5月21日0時~2006年5月27日24時，設定業務流的最長存在時間為20 ms。TXS測量點一周的數據包和實際業務流的結果如圖2所示。

從圖2中可以大致看出，TXS站點實際數據包一周的平均數目為15 000，而業務流數目基本上保持在8 000，并且基本在每天的18時以后數據包數量開始增加達到當天最大值。

在得到TXS測量點5月21日~5月27日一周實際業務流分析結果后，在每個采樣時段分別實施改進的CARE算法和CARE算法來估計業務流數目。通過分析實際業務流，其結果如圖3所示。

圖3橫坐標以d為單位起始于5月21日0時，終止于5月27日24時；縱坐標為業務流數目。5月21日~5月24日期間由于實際業務流相對較少，基本保持在8 000，所以兩種算法估計的業務流數目與真實業務流接近，但是改進的CARE算法還是比CARE算法更加接近實際業務流數目。雖然在估計小數值業務流方面改進的CARE算法超過CARE算法，但是在估計大數值業務流方面改進的CARE算法更加具有優勢，誤差相對更小。例如在5月26日9時實際業務流為12 995，改進的CARE算法估計的業務流為12 456，誤差僅為4.14%，CARE算法估計的業務流為9 849，誤差為24．42%；在5月26日18時實際業務流為12 236，改進的CARE估計的業務流為10 584，誤差為13．5%，CARE算法估計的業務流為9 885，誤差為19．2%；在5月27日3時實際業務流數目為14 316，而改進的CARE算法估計業務流數目為14 013，誤差僅僅為2．11%，CARE算法估計的業務流為10 784，誤差為24．67%。相比較而言，改進的CARE算法無論在估計數值方面還是在誤差方面的分析結果均優于CARE算法。通過分析以上結果，說明在大型中間路由設備上部署改進的CARE算法來進行業務流分析不僅是可行的而且更加具有實際意義。對圖3中的數據進行分析得到兩種算法的誤差分析表如表1所示。

4結束語

CARE業務流估計算法是基于CR模型利用jackknife estimator原理來估計業務流的算法。分別對CARE算法造成影響的區分水平值、估計次數、數據列表長度三個參數進行比較分析。首先，區分水平值是估計業務流的關鍵，對估計結果的選取有很大的影響。選擇不同的區分水平值，可能導致估計的結果產生很大的差異。通過實驗研究CARE算法得知：如果估計次數T超過真實業務流的N/2，那么區分水平E與真實業務流N比值的取值區間為[0.1，0.3]。其次，在數據列表長度與估計次數比率恒定的情況下，CARE算法的估計數目隨著估計次數的增加而逐漸接近真實業務流數目。最后，在估計次數不變、增加數據列表長度的情況下，估計值是不斷增加的。在研究CARE算法的估計過程中，提出一種改進的CARE算法。該算法運用遞歸的方法通過不斷修正估計次數進行估計并且得到了穩定的估計結果。實驗證明相對于CARE算法來說，改進的CARE算法可以避免人為因素的影響達到準確估計業務流數的目的。因此改進CARE業務流算法可以應用于網絡中間設備實現業務流數目的估計，保證公平的資源分配，具有很廣泛的應用前景。

通過以上實驗證明，區分水平值、估計次數和數據列表長度均影響算法估計業務流數目。如何分析三個參數之間的關系，建立一個統一的模型用來動態地、準確地估計業務流數目將是未來的工作。

參考文獻：

［1］林闖，任豐原，劉衛東.IP網絡中的擁塞控制[J].計算機學報，2003，26（9）:1025－1034.

［2］OTT T J， LAKSHMAN T V， WONG L H. SRED:stabilized RED [C]//DOSHI B. Proc of IEEE INFOCOM. New York: IEEE Computer Society，1999:1346－1355.

［3］MORIS R.Scalable TCP congestion control[C]//Proc of IEEE INFOCOM. Tel－Aviv:[s.n.]， 2000:1176－1183.

［4］LI J S， LEU M S. Fair bandwidth share using flow number estimation[C]//Proc of IEEE International Conference(ICC2002). 2002:1274－1278.

［5］ CHAN M K， HAMDI M. An active queue management scheme based on a capture－recapture model[J]. IEEE Journal on Selected Areas in Communications，2003，21(4):572-583.

［6］BURNHAMK P， OVERTON W S. Estimation of the size of a closed population when capture probabilities vary among animals[J].Biometrika，1978，65(3):625-633.

［7］WHITE G C，ANDERSON D R，BURNHAM K P，et al.Capture－recapture and removal methods for sampling closed populations， La 8787－NERP[R]. Los Alamos:Los Alamos National Laboratory，1982.

［8］OTIS D L， BURNHAM K P， WHITE G C， et al. Statistical inference from capture data on closed animal populations[J]. Wildlife Monographs， 1978，62:1－135

［9］NLANR[EB/OL].http://pma.nlanr.net/Traces.

［10］PMA[EB/OL].http://pma.nlanr.net.

［11］TXS of PMA dataset[DB/OL].(2006-05-21). http://pma.nlanr.net/Traces/Traces/daily/20060521~20060527.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”