摘 要：針對(duì)CSFQ算法存在的對(duì)TCP流的抑制及緩存策略等問題，提出采用ARED作為緩存管理的CSFQ改進(jìn)算法A-CSFQ，并在多瓶頸鏈路下對(duì)其性能進(jìn)行仿真。仿真結(jié)果表明，改進(jìn)算法在保持CSFQ其他優(yōu)點(diǎn)的基礎(chǔ)上，顯著減弱了對(duì)TCP流的抑制作用，提高了其對(duì)TCP流的公平性。

關(guān)鍵詞：TCP;擁塞控制;主動(dòng)隊(duì)列管理;RED;公平帶寬分配;CSFQ

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004-373X(2008)22-155-03

Design and Simulation of Improved CSFQ Algorithm

ZHANG Pingping1，WANG Qiaoqiao2

(1.96 Unit，92941 Troop of the PLA，Huludao，125001，China;2.Automation College，South China University of Technology，Guangzhou，510640，China)

Abstract：This paper brings forward A-CSFQ algorithm based on CSFQ to solve the problem of CSFQ，such as its restraining effect on TCP flows and buffer management strategy.A-CSFQ uses ARED as its buffer management algorithm.It is simulated in multiple congested link network topologies.The simulation results show that the improved algorithm decreases its restraining effect and improves fairness on TCP flows based on keeping the virtue of original CSFQ algorithm.

Keywords：TCP;congestion control;active queue management;RED;fair bandwidth allocation;CSFQ

隨著Internet規(guī)模的增長(zhǎng)，互聯(lián)網(wǎng)上的用戶和應(yīng)用都在快速增長(zhǎng)，擁塞己經(jīng)成為了一個(gè)重要的問題，如果不在Internet中使用有效的擁塞控制算法，擁塞崩潰的發(fā)生會(huì)嚴(yán)重降低網(wǎng)絡(luò)性能。在Internet中使用擁塞控制算法對(duì)Ineternet的穩(wěn)定性和提高網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS )具有十分重要的意義。

CSFQ(Core Stateless Fair Queuing)是一種分布式的核心路由器，不需要維護(hù)每流狀態(tài)的近似公平分配算法。由于其在顯著地降低了核心路由器的復(fù)雜程度的同時(shí)達(dá)到了較好的帶寬分配的公平性，所以在國內(nèi)外路由器廠商及科研機(jī)構(gòu)中引起了廣泛的關(guān)注和研究。但其存在對(duì)TCP流的抑制、流速估計(jì)中的參數(shù)設(shè)置等問題，仍沒有解決。

1 CSFQ算法存在的問題

1.1 CSFO算法對(duì)于TCP流的抑制

在CSFQ算法中，各個(gè)流的到達(dá)速率在邊界路由器上進(jìn)行估算，并將估算值插入分組標(biāo)記中，由分組攜帶轉(zhuǎn)發(fā)到路徑中的下一個(gè)節(jié)點(diǎn)上。在算法中，邊界路由器用指數(shù)平均算法來估算一個(gè)流的到達(dá)速率。令tki和lki分別表示流i的第k個(gè)分組的到達(dá)時(shí)刻和分組的長(zhǎng)度，則每當(dāng)流i有新的分組到達(dá)時(shí)，CSFQ算法對(duì)流的到達(dá)速率的估算值進(jìn)行更新:

rnewi=(1-e-Tki/K)lkiTki+e-TkiKroldi(1)

其中Tki=tki-tk-1i，為當(dāng)前分組到達(dá)時(shí)間距同屬該流的前一個(gè)分組到達(dá)的時(shí)間間隔，K為常數(shù)。

另外，按照式(1)計(jì)算獲得丟棄概率對(duì)TCP流顯得過于激進(jìn)。通常，在穩(wěn)定狀態(tài)下，TCP擁塞窗口在W/2和W之間變化，發(fā)送速率在2a/3~4a/3之間變化，對(duì)應(yīng)的CSFQ分組丟棄概率在0～0.25之間變化。對(duì)于TCP來說，一個(gè)分組足夠使其發(fā)送速率減小，這樣的丟棄概率對(duì)于TCP流來說過大。因此，對(duì)于TCP流來說，CSFQ難以實(shí)現(xiàn)公平帶寬分配。

1.2 CSFQ算法的緩存策略所存在的問題

CSFQ中的隊(duì)列管理一般采用“去尾”的方法，在隊(duì)列緩存己滿時(shí)會(huì)發(fā)生大量的丟包，這種丟包方式適合于UDP流，因?yàn)閁DP總是以固定速率發(fā)送數(shù)據(jù)。而TCP使用的是和式增加積式減小(Additive Increase Multiple Decrease，AIMD)的基于窗口的端到端擁塞控制機(jī)制，對(duì)于包的丟失非常敏感，只要檢測(cè)到1個(gè)包丟失就認(rèn)為網(wǎng)絡(luò)發(fā)生了擁塞，從而會(huì)進(jìn)入慢啟動(dòng)階段減小發(fā)送速率，當(dāng)包丟失較多時(shí)其發(fā)送速率將急劇下降。這樣帶寬會(huì)更多的被UDP流所占據(jù)，TCP流所得到的帶寬越來越少，造成了TCP流與UDP流之間的不公平。

2 緩存策略和丟包率計(jì)算的改進(jìn)

如果對(duì)隊(duì)列緩存進(jìn)行適當(dāng)?shù)墓芾恚梢员苊鈦G包后產(chǎn)生的TCP與UDP之間的不公平。調(diào)度算法與分組丟棄相結(jié)合，是提高公平性的一條途徑。本文提出的采用ARED(Adaptive RED)的CSFQ(在本文中記為A-CSFQ)能夠較好地解決這個(gè)問題。

ARED是一種較好的緩沖管理機(jī)制，但是在ARED中丟包概率只與緩存的平均占用率有關(guān)，與網(wǎng)絡(luò)的擁塞狀況無關(guān)。在CSFQ中，調(diào)度算法本身己經(jīng)對(duì)數(shù)據(jù)包的到達(dá)速率和轉(zhuǎn)發(fā)速率進(jìn)行估算，可以區(qū)分出網(wǎng)絡(luò)是否擁塞，利用ri和α，可以在鏈路擁塞時(shí)采用ARED實(shí)現(xiàn)緩存管理。

設(shè)Qsize為緩沖區(qū)的大小，Qavg為緩存的平均占用率，Qth為隊(duì)列長(zhǎng)度的門限值，maxp為最大丟包概率。根據(jù)ARED，丟包概率為p1=maxp·Qavg-QthQsize-Qth。又根據(jù)CSFQ的丟包概率公式知，速率的丟包概率pr=max(0，1-α/ri)，丟包的概率同時(shí)應(yīng)該與緩存的占用率β相關(guān)，取β=γ·QavgQsize，式中γ為調(diào)節(jié)因子。這樣，當(dāng)每次網(wǎng)絡(luò)出現(xiàn)擁塞時(shí)，與速率相關(guān)的丟包率為p2=β·pr=γ·QavgQsize·max(0，1-α/ri)。

因此，改進(jìn)方案為：

當(dāng)網(wǎng)絡(luò)未發(fā)生擁塞時(shí)(A(t)≤C)，AR-CSFQ的丟包概率取:

P=p1=maxp·Qavg-QthQsize-Qth，當(dāng)Qavg-Qth>0

0，當(dāng)Qavg-Qth≤0(2)

當(dāng)網(wǎng)絡(luò)進(jìn)入擁塞時(shí)(A(t)>C)，AR-CSFQ的丟包概率取:

P=p1=maxp·Qavg-QthQsize-Qth+γ·QavgQsize·

max(0，1-αri)， 當(dāng)Qavg-Qth>0

0，當(dāng)Qavg-Qth≤0(3)

因此，丟包概率由網(wǎng)絡(luò)擁塞狀況和輸出緩存占用率兩方面決定。這樣的丟包策略更能夠符合網(wǎng)絡(luò)的實(shí)際情況，從而對(duì)丟包概率進(jìn)行更加精確的控制。當(dāng)網(wǎng)絡(luò)擁塞度低時(shí)，丟包概率很低;當(dāng)網(wǎng)絡(luò)出現(xiàn)擁塞時(shí)，隨著擁塞度的提高，緩存占用率相應(yīng)提高，丟包概率逐步提高。

3 改進(jìn)的CSFQ算法的仿真與分析

3.1 仿真環(huán)境

下面在仿真環(huán)境下對(duì)本文提出的改進(jìn)算法性能進(jìn)行分析。為了提供參照，將改進(jìn)算法A-CSFQ的性能與CSFQ，DRR，F(xiàn)IFO幾種算法的性能進(jìn)行比較。由于該改進(jìn)算法是在CSFQ的基礎(chǔ)上的改進(jìn)，所以與原算法之間的比較為改進(jìn)算法的性能評(píng)價(jià)提供了參照。

仿真所采用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示。數(shù)據(jù)流從S(1，2，…，n)分別流向D(1，2，…，n)，業(yè)務(wù)流的類型包括TCP長(zhǎng)流、TCP短流、UDP流及On/Off流，所發(fā)送分組長(zhǎng)度為1 000 b/s。各隊(duì)列管理算法都在Router1中實(shí)現(xiàn)。參數(shù)K，Kc均為100 ms，Ka為200 ms。maxp=0.2，Qth=0.8Qsize，γ=1.6，β=2.0，f=1.20。緩沖空間大小為64個(gè)分組大小。其中CSFQ算法和A-CSFQ算法隊(duì)列域值設(shè)置為32個(gè)分組大小。

圖1 仿真網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

3.2 單純TCP流的仿真比較

該仿真中所有流均為TCP流，仿真開始時(shí)接入，一直持續(xù)到仿真結(jié)束，仿真時(shí)間為20 s。圖2顯示了各流在20 s內(nèi)的平均吞吐量。該實(shí)驗(yàn)主要驗(yàn)證A-CSFQ算法解決CSFQ算法對(duì)TCP流抑制的有效性。從圖2中可以看出，A-CSFQ算法中，各流的平均吞吐量高于CSFQ算法，與DRR算法節(jié)點(diǎn)接近，但算法在公平性方面略差于DRR算法。

3.3 TCP流與UDP流共存下的仿真比較

該仿真中，19個(gè)TCP長(zhǎng)流和1個(gè)UDP流在仿真開始時(shí)接入，并一直持續(xù)到仿真結(jié)束，仿真時(shí)間為150 s。其中0～18號(hào)流為TCP流，19號(hào)流為UDP流，其發(fā)送速率為10 Mb/s。圖3為各流的所獲得的平均吞吐量。從圖中可以看出，DRR，CSFQ和A-CSFQ都實(shí)現(xiàn)了較好的公平性。FIFO算法由于沒有實(shí)現(xiàn)任何公平算法，UDP流所獲得的平均帶寬為9.47 Mb/s，因此，UDP流獲得的帶寬遠(yuǎn)遠(yuǎn)高于TCP流，為了圖形清晰起見，在圖中沒有顯示。從圖3中可以看出，采用A-CSFQ算法中，各流的平均吞吐量高出CSFQ算法中各流的平均吞吐量，可見與CSFQ算法相比，A-CSFQ對(duì)于TCP流的抑制減弱。

3.4 不同速率UDP流的仿真比較

在該仿真中，所有20個(gè)流均為UDP流。流i的到達(dá)速率為其公平帶寬的(i+1)倍，即0號(hào)流的到達(dá)速率為0.5 Mb/s，1號(hào)流的到達(dá)速率為1.0 Mb/s，依此類推。圖4為各流在150 s內(nèi)的平均吞吐量。從圖4中可以看出，DRR，CSFQ，A-CSFQ在不同達(dá)到速率的UDP流之間保持了非常好的公平性。而在FIFO算法中，各流的平均吞吐量基本與各流的到達(dá)速率成比例。

3.5 不同數(shù)目UDP流的仿真比較

在此仿真中，1個(gè)TCP流與N(1～19)個(gè)UDP流競(jìng)爭(zhēng)同一瓶頸鏈路。UDP流的發(fā)送速率為其可獲得的公平帶寬的2倍。圖5顯示了該TCP流所獲得的實(shí)際平均吞吐量與理想的公平帶寬的比值隨N值的變化過程。從圖5中可以看出，在UDP流的個(gè)數(shù)為1時(shí)，A-CSFQ算法中TCP獲得的帶寬明顯高于CSFQ算法。隨著UDP流的數(shù)目的增加，單個(gè)UDP流的發(fā)送速率逐漸降低，CSFQ算法、DRR算法及A-CSFQ算法中，TCP流所獲得的帶寬均接近其理想帶寬。

圖2 20個(gè)TCP流在20 s內(nèi)的平均吞吐量

圖3 19個(gè)TCP流和一個(gè)UDP流(10 Mb/s)的平均吞吐量

圖4 不同速率的UDP流之間的公平性

3.6 ON/OFF流的仿真比較

在該仿真中，19個(gè)TCP流和1個(gè)ON/OFF流在仿真開始時(shí)接入，一直持續(xù)到仿真結(jié)束，仿真時(shí)間為100 s。其中ON/OFF流ON時(shí)間間隔為100 ms，OFF時(shí)間間隔為900 ms。在處于ON狀態(tài)時(shí)，其數(shù)據(jù)發(fā)送速率為10 Mb/s。圖6顯示了各流的平均帶寬。此實(shí)驗(yàn)中只對(duì)CSFQ與A-CSFQ算法進(jìn)行仿真。從圖6中可以看出，A-CSFQ對(duì)于突發(fā)流的適應(yīng)能力要強(qiáng)于CSFQ算法。在路由器采用A-CSFQ算法時(shí)，ON/OFF流所獲得的吞吐量為采用CSFQ算法該流獲得的吞吐量的2倍。各TCP流的平均吞吐量在A-CSFQ算法下高于CSFQ算法中各流的平均吞吐量。同時(shí)可以看出，兩個(gè)算法在存在突發(fā)流的情況下，TCP流所獲得的帶寬都低于其公平帶寬。

圖5 不同數(shù)目的UDP流下TCP的平均吞吐量

圖6 19個(gè)TCP流與1個(gè)ON/OFF流的平均吞吐量

4 結(jié) 語

作為無狀態(tài)公平隊(duì)列算法的代表，CSFQ算法在提出后獲得了很大的重視，得到了較充分的研究，但算法仍存在一些問題。本文針對(duì)CSFQ算法仍存在的一些問題，提出了一種結(jié)合隊(duì)列管理的CSFQ算法的改進(jìn)算法，并對(duì)其進(jìn)行了仿真評(píng)價(jià)。仿真結(jié)果表明，改進(jìn)算法在保持CSFQ算法的性能的同時(shí)，提高其對(duì)TCP流的公平性，同時(shí)增強(qiáng)CSFQ算法對(duì)突發(fā)流的適應(yīng)能力。

參考文獻(xiàn)

［1］Floyd S.Congestion Control Principles.RFC 2914，2000.

［2］Border J，Kojo M，Griner J，et al.Performance Enhancing Proxies Intended to Mitigate Link-Related Degradations.RFC 3315，2001.

［3］Handley M，F(xiàn)loyd S，Padhye J，et al.TCP Friendly Rate Control (TFRC):Protocol Specification.RFC 3448，2003.

［4］Bitorika A，Robin M，Huggard M.A Survey of Active Queue Management Schemes.Trinity College Dublin，Depart of Computer Science，Tech.Rep.，2003.

［5］Ke J，Willianmson C.Towards Rate-Based TCP Protocol for the WEB.In Proceedings of IEEE MASCOTS，2000.

［6］Ludwig R，Kata R H.The Eifel Algorithm: Making TCP Robust Against Spurious Retransmissions.ACM Computer Communication Review，2000，30(1):30-36.

［7］Windmer J，Denda R，Mauve M.A Survey of TCP-Friendly Congestion Control.IEEE Network，2001.

［8］Bansal Deepak，Balakrishnam Hari.Binominal Congestion Control Algorithm.In: IEEE INFOCOM 2001.Anchorage，AK，2001.

［9］Kunniyur S，Srikant R.Analysis and Design of an Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management.Technical Report，UIUC，2001.

［10］Chris Hollot，Vishal Misra，Don Towsley，et al.On Designing Improved Controllers for AQM Routers Supporting TCP Flows.In Proceedings of IEEE Infocom，2001.

作者簡(jiǎn)介

張萍萍 女，1975年出生，工程師，碩士。主要從事網(wǎng)絡(luò)擁塞控制方法的研究。

王巧巧 女，1968年出生，講師，華南理工大學(xué)在讀博士。主要從事網(wǎng)絡(luò)控制、網(wǎng)絡(luò)應(yīng)用等方面的研究工作。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文