一种改进的CSFQ算法的设计与仿真

摘 要：针对CSFQ算法存在的对TCP流的抑制及缓存策略等问题，提出采用ARED作为缓存管理的CSFQ改进算法A-CSFQ，并在多瓶颈链路下对其性能进行仿真。仿真结果表明，改进算法在保持CSFQ其他优点的基础上，显著减弱了对TCP流的抑制作用，提高了其对TCP流的公平性。

关键词：TCP;拥塞控制;主动队列管理;RED;公平带宽分配;CSFQ

中图分类号：TP393文献标识码：B

文章编号：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规模的增长，互联网上的用户和应用都在快速增长，拥塞己经成为了一个重要的问题，如果不在Internet中使用有效的拥塞控制算法，拥塞崩溃的发生会严重降低网络性能。在Internet中使用拥塞控制算法对Ineternet的稳定性和提高网络服务质量(QoS )具有十分重要的意义。

CSFQ(Core Stateless Fair Queuing)是一种分布式的核心路由器，不需要维护每流状态的近似公平分配算法。由于其在显著地降低了核心路由器的复杂程度的同时达到了较好的带宽分配的公平性，所以在国内外路由器厂商及科研机构中引起了广泛的关注和研究。但其存在对TCP流的抑制、流速估计中的参数设置等问题，仍没有解决。

1 CSFQ算法存在的问题

1.1 CSFO算法对于TCP流的抑制

在CSFQ算法中，各个流的到达速率在边界路由器上进行估算，并将估算值插入分组标记中，由分组携带转发到路径中的下一个节点上。在算法中，边界路由器用指数平均算法来估算一个流的到达速率。令tki和lki分别表示流i的第k个分组的到达时刻和分组的长度，则每当流i有新的分组到达时，CSFQ算法对流的到达速率的估算值进行更新:

rnewi=(1-e-Tki/K)lkiTki+e-TkiKroldi(1)

其中Tki=tki-tk-1i，为当前分组到达时间距同属该流的前一个分组到达的时间间隔，K为常数。

另外，按照式(1)计算获得丢弃概率对TCP流显得过于激进。通常，在稳定状态下，TCP拥塞窗口在W/2和W之间变化，发送速率在2a/3~4a/3之间变化，对应的CSFQ分组丢弃概率在0～0.25之间变化。对于TCP来说，一个分组足够使其发送速率减小，这样的丢弃概率对于TCP流来说过大。因此，对于TCP流来说，CSFQ难以实现公平带宽分配。

1.2 CSFQ算法的缓存策略所存在的问题

CSFQ中的队列管理一般采用“去尾”的方法，在队列缓存己满时会发生大量的丢包，这种丢包方式适合于UDP流，因为UDP总是以固定速率发送数据。而TCP使用的是和式增加积式减小(Additive Increase Multiple Decrease，AIMD)的基于窗口的端到端拥塞控制机制，对于包的丢失非常敏感，只要检测到1个包丢失就认为网络发生了拥塞，从而会进入慢启动阶段减小发送速率，当包丢失较多时其发送速率将急剧下降。这样带宽会更多的被UDP流所占据，TCP流所得到的带宽越来越少，造成了TCP流与UDP流之间的不公平。

2 缓存策略和丢包率计算的改进

如果对队列缓存进行适当的管理，可以避免丢包后产生的TCP与UDP之间的不公平。调度算法与分组丢弃相结合，是提高公平性的一条途径。本文提出的采用ARED(Adaptive RED)的CSFQ(在本文中记为A-CSFQ)能够较好地解决这个问题。

ARED是一种较好的缓冲管理机制，但是在ARED中丢包概率只与缓存的平均占用率有关，与网络的拥塞状况无关。在CSFQ中，调度算法本身己经对数据包的到达速率和转发速率进行估算，可以区分出网络是否拥塞，利用ri和α，可以在链路拥塞时采用ARED实现缓存管理。

设Qsize为缓冲区的大小,Qavg为缓存的平均占用率，Qth为队列长度的门限值，maxp为最大丢包概率。根据ARED，丢包概率为p1=maxp・Qavg-QthQsize-Qth。又根据CSFQ的丢包概率公式知，速率的丢包概率pr=max(0,1-α/ri)，丢包的概率同时应该与缓存的占用率β相关，取β=γ・QavgQsize，式中γ为调节因子。这样，当每次网络出现拥塞时，与速率相关的丢包率为p2=β・pr=γ・QavgQsize・max(0,1-α/ri)。

因此，改进方案为：

当网络未发生拥塞时(A(t)≤C)，AR-CSFQ的丢包概率取:

P=p1=maxp・Qavg-QthQsize-Qth,当Qavg-Qth>0

0,当Qavg-Qth≤0(2)

当网络进入拥塞时(A(t)>C)，AR-CSFQ的丢包概率取:

P=p1=maxp・Qavg-QthQsize-Qth+γ・QavgQsize・

max(0,1-αri), 当Qavg-Qth>0

0,当Qavg-Qth≤0(3)

因此，丢包概率由网络拥塞状况和输出缓存占用率两方面决定。这样的丢包策略更能够符合网络的实际情况，从而对丢包概率进行更加精确的控制。当网络拥塞度低时，丢包概率很低;当网络出现拥塞时，随着拥塞度的提高，缓存占用率相应提高，丢包概率逐步提高。

3 改进的CSFQ算法的仿真与分析

3.1 仿真环境

下面在仿真环境下对本文提出的改进算法性能进行分析。为了提供参照，将改进算法A-CSFQ的性能与CSFQ，DRR，FIFO几种算法的性能进行比较。由于该改进算法是在CSFQ的基础上的改进，所以与原算法之间的比较为改进算法的性能评价提供了参照。

仿真所采用的网络拓扑结构如图1所示。数据流从S(1,2,…,n)分别流向D(1,2,…,n)，业务流的类型包括TCP长流、TCP短流、UDP流及On/Off流，所发送分组长度为1 000 b/s。各队列管理算法都在Router1中实现。参数K，Kc均为100 ms,Ka为200 ms。maxp=0.2，Qth=0.8Qsize，γ=1.6，β=2.0，f=1.20。缓冲空间大小为64个分组大小。其中CSFQ算法和A-CSFQ算法队列域值设置为32个分组大小。

图1 仿真网络拓扑结构图

3.2 单纯TCP流的仿真比较

该仿真中所有流均为TCP流，仿真开始时接入，一直持续到仿真结束，仿真时间为20 s。图2显示了各流在20 s内的平均吞吐量。该实验主要验证A-CSFQ算法解决CSFQ算法对TCP流抑制的有效性。从图2中可以看出，A-CSFQ算法中，各流的平均吞吐量高于CSFQ算法，与DRR算法节点接近，但算法在公平性方面略差于DRR算法。

3.3 TCP流与UDP流共存下的仿真比较

该仿真中，19个TCP长流和1个UDP流在仿真开始时接入，并一直持续到仿真结束，仿真时间为150 s。其中0～18号流为TCP流，19号流为UDP流，其发送速率为10 Mb/s。图3为各流的所获得的平均吞吐量。从图中可以看出，DRR，CSFQ和A-CSFQ都实现了较好的公平性。FIFO算法由于没有实现任何公平算法，UDP流所获得的平均带宽为9.47 Mb/s，因此，UDP流获得的带宽远远高于TCP流，为了图形清晰起见，在图中没有显示。从图3中可以看出，采用A-CSFQ算法中，各流的平均吞吐量高出CSFQ算法中各流的平均吞吐量，可见与CSFQ算法相比，A-CSFQ对于TCP流的抑制减弱。

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

在该仿真中，所有20个流均为UDP流。流i的到达速率为其公平带宽的(i+1)倍，即0号流的到达速率为0.5 Mb/s,1号流的到达速率为1.0 Mb/s，依此类推。图4为各流在150 s内的平均吞吐量。从图4中可以看出，DRR,CSFQ,A-CSFQ在不同达到速率的UDP流之间保持了非常好的公平性。而在FIFO算法中，各流的平均吞吐量基本与各流的到达速率成比例。

3.5 不同数目UDP流的仿真比较

在此仿真中，1个TCP流与N(1～19)个UDP流竞争同一瓶颈链路。UDP流的发送速率为其可获得的公平带宽的2倍。图5显示了该TCP流所获得的实际平均吞吐量与理想的公平带宽的比值随N值的变化过程。从图5中可以看出，在UDP流的个数为1时，A-CSFQ算法中TCP获得的带宽明显高于CSFQ算法。随着UDP流的数目的增加，单个UDP流的发送速率逐渐降低，CSFQ算法、DRR算法及A-CSFQ算法中，TCP流所获得的带宽均接近其理想带宽。

图2 20个TCP流在20 s内的平均吞吐量

图3 19个TCP流和一个UDP流(10 Mb/s)的平均吞吐量

图4 不同速率的UDP流之间的公平性

3.6 ON/OFF流的仿真比较

在该仿真中，19个TCP流和1个ON/OFF流在仿真开始时接入，一直持续到仿真结束，仿真时间为100 s。其中ON/OFF流ON时间间隔为100 ms，OFF时间间隔为900 ms。在处于ON状态时，其数据发送速率为10 Mb/s。图6显示了各流的平均带宽。此实验中只对CSFQ与A-CSFQ算法进行仿真。从图6中可以看出，A-CSFQ对于突发流的适应能力要强于CSFQ算法。在路由器采用A-CSFQ算法时，ON/OFF流所获得的吞吐量为采用CSFQ算法该流获得的吞吐量的2倍。各TCP流的平均吞吐量在A-CSFQ算法下高于CSFQ算法中各流的平均吞吐量。同时可以看出，两个算法在存在突发流的情况下，TCP流所获得的带宽都低于其公平带宽。

图5 不同数目的UDP流下TCP的平均吞吐量

图6 19个TCP流与1个ON/OFF流的平均吞吐量

4 结 语

作为无状态公平队列算法的代表，CSFQ算法在提出后获得了很大的重视，得到了较充分的研究，但算法仍存在一些问题。本文针对CSFQ算法仍存在的一些问题，提出了一种结合队列管理的CSFQ算法的改进算法，并对其进行了仿真评价。仿真结果表明，改进算法在保持CSFQ算法的性能的同时，提高其对TCP流的公平性，同时增强CSFQ算法对突发流的适应能力。

参考文献

［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,Floyd 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.

作者简介

张萍萍 女，1975年出生，工程师，硕士。主要从事网络拥塞控制方法的研究。

王巧巧 女，1968年出生，讲师，华南理工大学在读博士。主要从事网络控制、网络应用等方面的研究工作。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文