FCA－ItswTCM:一種改進的滑動窗口的標記算法

陳蓉琳，龔 靜*

(1.銅仁學(xué)院數(shù)學(xué)與計算機科學(xué)系，貴州銅仁 554300;2.銅仁學(xué)院計算機應(yīng)用技術(shù)研究所，貴州銅仁 554300)

區(qū)分服務(wù)(differentiated services，DiffServ)［1］因其具有良好的可擴展性和簡單性，成為最有可能在下一代網(wǎng)絡(luò)主干中實施網(wǎng)絡(luò)QOS的模型，自其提出以來，一直是網(wǎng)絡(luò)研究的重要內(nèi)容［2－3］.確保服務(wù)(assured service，AS)是DiffServ的主要服務(wù)類型，通過邊界路由器執(zhí)行的標記策略和核心路由器執(zhí)行的主動式隊列管理策略，從統(tǒng)計意義上保證匯聚流及微流帶寬共享的公平性.AS中的滑動窗口標記算法較著名的有TSWTCM［4］、ItswTCM［5］、I2tswTCM［6］及 M－I2tswTCM［7］.文獻［8］對 TSWTCM 算法改進，提出了一種基于擁塞感知的、保證TCP流和UDP流公平競爭帶寬的標記算法FCA－ItswTCM［8］.本文對比分析了幾種滑動窗口標記算法及FCA－ItswTCM算法，并設(shè)計仿真實驗，從公平性、帶寬利用率、穩(wěn)定性方面進行了仿真性能比較.

1 滑動窗口標記算法分析

基于滑動窗口的標記算法，是一種比例分配的標記算法.在邊界路由器對數(shù)據(jù)包標記為綠、黃、紅，核心路由器按數(shù)據(jù)包標記情況實施不同的丟包策略，丟棄級別由高0 x到低依次為紅、黃、綠.綠包用來保證獲得數(shù)據(jù)流訂購的帶寬，黃包用來競爭剩余帶寬.因此，某流注入黃包的數(shù)量越多，則可能競爭到更多的帶寬.

以上兩種滑動窗口標記算法，實現(xiàn)了對剩余帶寬的比例分配，但難以確保TCP/UDP流帶寬共享的公平性.擁塞發(fā)生時，由于TCP流是擁塞自適應(yīng)的，TCP黃包不僅被丟棄，而且TCP源端還會因丟包事件而降低發(fā)送速率，導(dǎo)致TCP黃包標記量降低，以至于降低TCP流帶寬競爭能力.對UDP流而言，由于丟包事件不會改變源端的發(fā)送速率，導(dǎo)致UDP黃包標記量增多，以至于提升UDP流帶寬競爭能力.因此，縱使基于滑動窗口標記算法是保證TCP/UDP流剩余帶寬的比例分配，但由于TCP流響應(yīng)擁塞控制機制，則擁塞時，無法保證TCP流、UDP流能夠獲得公平的帶寬分配.又因為Internet上數(shù)據(jù)突發(fā)本質(zhì)，各流到達路由器的包是突發(fā)的，往往會導(dǎo)致短暫的突發(fā)擁塞，而于基于滑動窗口標記算法缺乏對網(wǎng)絡(luò)擁塞狀態(tài)的處理.所以，在網(wǎng)絡(luò)擁塞時有可能注入黃包過多，使得丟棄過多的黃包，TCP流競爭帶寬能力減弱;在網(wǎng)絡(luò)空閑時有可能注入黃包較少，鏈路利用率降低.

2 FCA－ItswTCM［8］簡紹

2.1 FCA－ItswTCM 主旨

FCA－ItswTCM的主旨是保證TCP流、UDP流公平競爭帶寬，并且提高資源利用效率.其主要內(nèi)容是:①近似區(qū)分標記.利用采樣技術(shù)，識別TCP流、UDP流，并近似區(qū)分標記它們，規(guī)避擁塞控制機制對TCP匯聚流及微流帶寬共享公平性的影響.其計算開銷和存儲開銷較小，實現(xiàn)簡單.②適應(yīng)調(diào)節(jié)標記比例.細粒度描述核心域擁塞程度，預(yù)測擁塞狀態(tài)，以此自適應(yīng)調(diào)節(jié)黃包標記比例，兼顧網(wǎng)絡(luò)擁塞狀態(tài)對TCP流、UDP流公平競爭帶寬的影響，并且提高資源利用效率.

2.2 FCA－ItswTCM 描述

FCA－ItswTCM是ItswTCM算法的改進，具體內(nèi)容如表1.其中，X是鏈路帶寬;CIR為匯聚流的目標速率;Fi是匯聚流i的比例公平因子;CI是擁塞指數(shù)，區(qū)分服務(wù)網(wǎng)絡(luò)核心域擁塞狀態(tài)的測度;λ是標記因子，調(diào)節(jié)黃包標記比例與核心域擁塞狀態(tài)自適應(yīng).FCA－ItswTCM算法如下:

3 實驗及分析

3.1 實驗場景設(shè)計

本實驗使用 ns－2仿真軟件，對 TSWTCM、ItswTCM、I2tswTCM、FCA－ItswTCM進行了比較分析.網(wǎng)絡(luò)拓撲結(jié)構(gòu)見圖1.本實驗中設(shè)置了兩匯聚流S0和S1、邊界路由器R1、R3，核心路由器R2.核心域各鏈路帶寬均為10 Mbps，其余鏈路帶寬均為20 Mbps，延時均為5 ms.核心路由節(jié)點使用隊列管理算法RIO－C，邊界路由器節(jié)點使用標記算法 TSWTCM、ItswTCM、I2tswTCM、FCA－ItswTCM.

圖1 網(wǎng)絡(luò)拓撲Fig.1 Network topology

設(shè)計兩種實驗場景:①聚集流S0由10個TCP流組成，它們的發(fā)送速率為1 Mbps，它們的訂購速率在1 Mbps到10 Mbps之間變化，表示訂購級別從30%變化到120%;聚集流S1是1個UDP流，它的訂購速率為2Mbps，發(fā)送速率由0.5Mbps增加到10Mbps，用來表示競爭帶寬.②聚集流S0由10個TCP流組成，它們的發(fā)送速率為1 Mbps，它們的訂購速率在1 Mbps到10 Mbps之間變化，表示訂購級別從30%變化到120%;聚集流S1由9個TCP流和2個UDP流組成，訂購速率固定為2Mbps.其中，TCP流的發(fā)送速率為1Mbps，UDP流的發(fā)送速率從0.5Mbps遞增到10Mbps.本文用R.Jain提出的公平指數(shù)(FI，fairness index)以及系統(tǒng)吞吐量的變化情況分析算法的性能.

3.2 訂購速率與公平指數(shù)

在圖2中，無論是場景一，還是場景二，隨著訂購級別的增加，在公平指數(shù)方面，改進算法 FCAItswTCM，比TSWTCM、ItswTCM、I2tswTCM算法高，另外，改進算法FCA－ItswTCM的波動范圍也較小.可以說，與其它幾種滑動窗口標記算法相比較，改進算法FCA－ItswTCM提高了數(shù)據(jù)流競爭帶寬的公平性，穩(wěn)定性也較好.

圖2 公平指數(shù)與訂購級別關(guān)系Fig.2 Relationship of fairness index and order level

3.3 TCP聚集流的吞吐量

接下來分析，場景一、二中，TCP匯聚流的吞吐量隨其訂購速率變化的情況.圖3(a)(b)顯示:訂購不足時，TSWTCM、ItswTCM、I2tswTCM、FCA－ItswTCM算法中，匯聚流S0、S1均能獲得其訂購帶寬;訂購足量時，F(xiàn)CA－ItswTCM能夠保證匯聚流S0、S1獲得訂購帶寬，而TSWTCM、ItswTCM、I2tswTCM不能保證匯聚流S0獲得訂購帶寬;訂購過量時，四種算法中匯聚流S0、S1均獲得一定的降級服務(wù).但在按目標速率的比例公平享用剩余帶寬方面，F(xiàn)CA－ItswTCM算法優(yōu)于其它算法.另外，采用FCA－ItswTCM算法，S0的吞吐量變化較其它幾種算法穩(wěn)定.顯然，F(xiàn)CA－ItswTCM算法既能確保TCP匯聚流的公平性，同時也能確保UDP匯聚流有公平性，及提高帶寬利用率.這主要是FCA－ItswTCM算法調(diào)節(jié)各流注入的黃包數(shù)量與核心域擁塞狀態(tài)自適應(yīng)，可以保證對網(wǎng)絡(luò)帶寬的充分利用;適度區(qū)分標記TCP流和UDP流則保證了TCP匯聚流和UDP匯聚流帶寬共享的公平性.

圖3 TCP匯聚流S0的吞吐量Fig.3 Throughout capacity of S0 in TCP aggregation flow

3.4 TCP微流的吞吐量

圖4(a)中，當訂購不足時，網(wǎng)絡(luò)擁塞程度增加，S1中的TCP微流得到的帶寬降低，但采用FCA－ItswTCM算法，TCP微流獲得的帶寬比其它幾種算法高、降低速度較慢、減小的幅度較小.圖4(b)顯示，訂購足量時，僅當網(wǎng)絡(luò)進入輕度擁塞狀態(tài)，即UDP發(fā)送速率為5 Mbps左右，TSWTCM、ItswTCM、I2tswTCM中TCP的吞吐量已接近于零.采用FCA－ItswTCM算法，當網(wǎng)絡(luò)進入嚴重擁塞，即UDP發(fā)送速率為8 Mbps左右，TCP的吞吐量才接近于零.圖4(c)顯示，訂購過量時，在網(wǎng)絡(luò)負載較輕時，相比其它算法，采用FCA－ItswTCM，TCP微流能獲得較好的吞吐量.而在網(wǎng)絡(luò)輕度擁塞時，所有算法中TCP微流的吞吐量均接近于零.顯然，F(xiàn)CAItswTCM算法，能夠保證TCP微流的帶寬競爭能力.這也是FCA－ItswTCM能夠感知網(wǎng)絡(luò)擁塞情況，自適應(yīng)調(diào)節(jié)各流公平競爭網(wǎng)絡(luò)帶寬的能力.

圖4 聚集流S1中TCP微流的吞吐量Fig.4 Throughout capacity of TCP microfluidic in aggregation flow S1

4 小結(jié)

本文對幾種滑動窗口標記算法進行了理論分析，指出影響TCP流和UDP流帶寬共享公平性的主要因素是擁塞控制機制及擁塞狀態(tài)，因此提高其公平性，在于標記黃包與網(wǎng)絡(luò)擁塞狀態(tài)自適應(yīng)，以及規(guī)避擁塞控制機制的影響.并與本文作者以此提出的一種能保證TCP流、UDP流公平競爭帶寬、并能提高資源利用率、且具有較好的穩(wěn)定性的FCA－ItswTCM，同時與幾種滑動窗口標記算法進行了比較研究.

仿真實驗表明，與其他幾種滑動窗口標記算法相比，F(xiàn)CA－ItswTCM對確保TCP流和UDP流帶寬共享的公平性、提高資源利用率及系統(tǒng)穩(wěn)定性有較好的效果.

［1］Nichols K，Jacobson V，Zhangl A.Two－bit Differentiated Services Architecture for the Internet IETF RFC 2638［S］.1999.

［2］Neda Moghim，Seyed Mostafa Safavi，Masoud Reza Hashemi.A New End－to－End Quality of Service Algorithm in DiffServ Networks［C］//Proc，IEEE ICCEE’2008，Phuket:IEEE ICCEE Press，2008:349－353.

［3］Nguyen Hong Son，M Eng，Le Huu Lap，PhD.A Method for Performing Connection Admission Control In Diffserv Networks［C］//Proc，IEEE ICACT’2009，Korea:IEEE Press，2009:227－232.

［4］W Fang，N Seddigh.Time Sliding Window Three Color Marker(tswTCM).RFC 2859［S］.2000.

［5］Su Hong Jun，Atiquzzaman M.ItswTCM:A new aggregate marker to improve fairness in Diffserv［C］//Proc，IEEE GLOBECOM’2001，San Antonio，TX:IEEE Press，2001(3):1841－1846.

［6］M A Elshaikh，M Othman，S Shamala，R Johari.Enhanced tswTCM to improve fairness in DiffiServ Networks［C］//Proc，IEEE International Conference on Networks，Arizona，USA:IEEE Press，2005(1):302－306.

［7］S Sudha，B Srinivasa Rao，N Ammasaigounden.A modified I2TSWTCM to improve bandwidth fairness in Diffserv［C］//Proc，The 2008 IEEE Region 10 Colloquium and the Third ICIIS，Kharagpur:IEEE Press，2008(12):8－10.

［8］龔靜，吳春明，孫維榮，等.FCA－ItswTCM:區(qū)分服務(wù)中一種公平的擁塞自適應(yīng)標記算法［J］.電子學(xué)報，2011，39(7):1624－1627.