FCA－ItswTCM:一种改进的滑动窗口的标记算法

陈蓉琳，龚 静*

(1.铜仁学院数学与计算机科学系，贵州铜仁 554300;2.铜仁学院计算机应用技术研究所，贵州铜仁 554300)

区分服务(differentiated services，DiffServ)［1］因其具有良好的可扩展性和简单性，成为最有可能在下一代网络主干中实施网络QOS的模型，自其提出以来，一直是网络研究的重要内容［2－3］.确保服务(assured service，AS)是DiffServ的主要服务类型，通过边界路由器执行的标记策略和核心路由器执行的主动式队列管理策略，从统计意义上保证汇聚流及微流带宽共享的公平性.AS中的滑动窗口标记算法较著名的有TSWTCM［4］、ItswTCM［5］、I2tswTCM［6］及 M－I2tswTCM［7］.文献［8］对 TSWTCM 算法改进，提出了一种基于拥塞感知的、保证TCP流和UDP流公平竞争带宽的标记算法FCA－ItswTCM［8］.本文对比分析了几种滑动窗口标记算法及FCA－ItswTCM算法，并设计仿真实验，从公平性、带宽利用率、稳定性方面进行了仿真性能比较.

1 滑动窗口标记算法分析

基于滑动窗口的标记算法，是一种比例分配的标记算法.在边界路由器对数据包标记为绿、黄、红，核心路由器按数据包标记情况实施不同的丢包策略，丢弃级别由高0 x到低依次为红、黄、绿.绿包用来保证获得数据流订购的带宽，黄包用来竞争剩余带宽.因此，某流注入黄包的数量越多，则可能竞争到更多的带宽.

以上两种滑动窗口标记算法，实现了对剩余带宽的比例分配，但难以确保TCP/UDP流带宽共享的公平性.拥塞发生时，由于TCP流是拥塞自适应的，TCP黄包不仅被丢弃，而且TCP源端还会因丢包事件而降低发送速率，导致TCP黄包标记量降低，以至于降低TCP流带宽竞争能力.对UDP流而言，由于丢包事件不会改变源端的发送速率，导致UDP黄包标记量增多，以至于提升UDP流带宽竞争能力.因此，纵使基于滑动窗口标记算法是保证TCP/UDP流剩余带宽的比例分配，但由于TCP流响应拥塞控制机制，则拥塞时，无法保证TCP流、UDP流能够获得公平的带宽分配.又因为Internet上数据突发本质，各流到达路由器的包是突发的，往往会导致短暂的突发拥塞，而于基于滑动窗口标记算法缺乏对网络拥塞状态的处理.所以，在网络拥塞时有可能注入黄包过多，使得丢弃过多的黄包，TCP流竞争带宽能力减弱;在网络空闲时有可能注入黄包较少，链路利用率降低.

2 FCA－ItswTCM［8］简绍

2.1 FCA－ItswTCM 主旨

FCA－ItswTCM的主旨是保证TCP流、UDP流公平竞争带宽，并且提高资源利用效率.其主要内容是:①近似区分标记.利用采样技术，识别TCP流、UDP流，并近似区分标记它们，规避拥塞控制机制对TCP汇聚流及微流带宽共享公平性的影响.其计算开销和存储开销较小，实现简单.②适应调节标记比例.细粒度描述核心域拥塞程度，预测拥塞状态，以此自适应调节黄包标记比例，兼顾网络拥塞状态对TCP流、UDP流公平竞争带宽的影响，并且提高资源利用效率.

2.2 FCA－ItswTCM 描述

FCA－ItswTCM是ItswTCM算法的改进，具体内容如表1.其中，X是链路带宽;CIR为汇聚流的目标速率;Fi是汇聚流i的比例公平因子;CI是拥塞指数，区分服务网络核心域拥塞状态的测度;λ是标记因子，调节黄包标记比例与核心域拥塞状态自适应.FCA－ItswTCM算法如下:

3 实验及分析

3.1 实验场景设计

本实验使用 ns－2仿真软件，对 TSWTCM、ItswTCM、I2tswTCM、FCA－ItswTCM进行了比较分析.网络拓扑结构见图1.本实验中设置了两汇聚流S0和S1、边界路由器R1、R3，核心路由器R2.核心域各链路带宽均为10 Mbps，其余链路带宽均为20 Mbps，延时均为5 ms.核心路由节点使用队列管理算法RIO－C，边界路由器节点使用标记算法 TSWTCM、ItswTCM、I2tswTCM、FCA－ItswTCM.

图1 网络拓扑Fig.1 Network topology

设计两种实验场景:①聚集流S0由10个TCP流组成，它们的发送速率为1 Mbps，它们的订购速率在1 Mbps到10 Mbps之间变化，表示订购级别从30%变化到120%;聚集流S1是1个UDP流，它的订购速率为2Mbps，发送速率由0.5Mbps增加到10Mbps，用来表示竞争带宽.②聚集流S0由10个TCP流组成，它们的发送速率为1 Mbps，它们的订购速率在1 Mbps到10 Mbps之间变化，表示订购级别从30%变化到120%;聚集流S1由9个TCP流和2个UDP流组成，订购速率固定为2Mbps.其中，TCP流的发送速率为1Mbps，UDP流的发送速率从0.5Mbps递增到10Mbps.本文用R.Jain提出的公平指数(FI，fairness index)以及系统吞吐量的变化情况分析算法的性能.

3.2 订购速率与公平指数

在图2中，无论是场景一，还是场景二，随着订购级别的增加，在公平指数方面，改进算法 FCAItswTCM，比TSWTCM、ItswTCM、I2tswTCM算法高，另外，改进算法FCA－ItswTCM的波动范围也较小.可以说，与其它几种滑动窗口标记算法相比较，改进算法FCA－ItswTCM提高了数据流竞争带宽的公平性，稳定性也较好.

图2 公平指数与订购级别关系Fig.2 Relationship of fairness index and order level

3.3 TCP聚集流的吞吐量

接下来分析，场景一、二中，TCP汇聚流的吞吐量随其订购速率变化的情况.图3(a)(b)显示:订购不足时，TSWTCM、ItswTCM、I2tswTCM、FCA－ItswTCM算法中，汇聚流S0、S1均能获得其订购带宽;订购足量时，FCA－ItswTCM能够保证汇聚流S0、S1获得订购带宽，而TSWTCM、ItswTCM、I2tswTCM不能保证汇聚流S0获得订购带宽;订购过量时，四种算法中汇聚流S0、S1均获得一定的降级服务.但在按目标速率的比例公平享用剩余带宽方面，FCA－ItswTCM算法优于其它算法.另外，采用FCA－ItswTCM算法，S0的吞吐量变化较其它几种算法稳定.显然，FCA－ItswTCM算法既能确保TCP汇聚流的公平性，同时也能确保UDP汇聚流有公平性，及提高带宽利用率.这主要是FCA－ItswTCM算法调节各流注入的黄包数量与核心域拥塞状态自适应，可以保证对网络带宽的充分利用;适度区分标记TCP流和UDP流则保证了TCP汇聚流和UDP汇聚流带宽共享的公平性.

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

3.4 TCP微流的吞吐量

图4(a)中，当订购不足时，网络拥塞程度增加，S1中的TCP微流得到的带宽降低，但采用FCA－ItswTCM算法，TCP微流获得的带宽比其它几种算法高、降低速度较慢、减小的幅度较小.图4(b)显示，订购足量时，仅当网络进入轻度拥塞状态，即UDP发送速率为5 Mbps左右，TSWTCM、ItswTCM、I2tswTCM中TCP的吞吐量已接近于零.采用FCA－ItswTCM算法，当网络进入严重拥塞，即UDP发送速率为8 Mbps左右，TCP的吞吐量才接近于零.图4(c)显示，订购过量时，在网络负载较轻时，相比其它算法，采用FCA－ItswTCM，TCP微流能获得较好的吞吐量.而在网络轻度拥塞时，所有算法中TCP微流的吞吐量均接近于零.显然，FCAItswTCM算法，能够保证TCP微流的带宽竞争能力.这也是FCA－ItswTCM能够感知网络拥塞情况，自适应调节各流公平竞争网络带宽的能力.

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

4 小结

本文对几种滑动窗口标记算法进行了理论分析，指出影响TCP流和UDP流带宽共享公平性的主要因素是拥塞控制机制及拥塞状态，因此提高其公平性，在于标记黄包与网络拥塞状态自适应，以及规避拥塞控制机制的影响.并与本文作者以此提出的一种能保证TCP流、UDP流公平竞争带宽、并能提高资源利用率、且具有较好的稳定性的FCA－ItswTCM，同时与几种滑动窗口标记算法进行了比较研究.

仿真实验表明，与其他几种滑动窗口标记算法相比，FCA－ItswTCM对确保TCP流和UDP流带宽共享的公平性、提高资源利用率及系统稳定性有较好的效果.

［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:区分服务中一种公平的拥塞自适应标记算法［J］.电子学报，2011，39(7):1624－1627.