APID：一种自适应调节参数的拥塞控制器

杨湘 ，王建新

(1.中南大学 信息科学与工程学院，湖南 长沙，410083；2.武汉科技大学 计算机科学与技术学院，湖北 武汉，430081)

随着Internet规模越来越大，Internet的拥塞控制作为保证网络性能的手段也显得越来越重要。Floyd等[1]提出RED(Random early detection)算法之后，在路由器上部署AQM[2](Active queue management)模块，并配合源端的TCP协议来调整流量以缓解拥塞的机制也逐渐被人们所认同并广泛采用。但是，RED以及一些变种算法[3-7]提出后，算法性能只能依靠仿真实验来进行评价，缺乏一些理论工具来分析性能，并指导算法设计。随后，人们利用控制理论、优化理论等工具来对AQM算法进行分析与设计，提出了一系列的AQM算法。Low等[8-9]基于流量控制对偶模型提出了REM(Random exponential marking)算法，试图在获得高带宽利用率的同时降低延迟。Misra等[10]对TCP/AQM模型进行分析，建立了非线性TCP流量控制模型，提出一对非线性微分方程描述了TCP流和AQM控制器的瞬态行为；而Hollot等[11-12]利用小信号理论对此模型进行线性化处理后，将其等效为带反馈延迟的二阶反馈控制系统，得到了TCP/AQM反馈控制系统简化的系统模型，并在此基础上提出了一种比例-积分控制器PI。随后，人们基于线性控制理论提出了一系列的AQM算法[13-19]。基于传统线性控制理论设计的拥塞控制器的稳定性在很大程度上依赖于受控对象的数学模型精度，因此，人们采用了智能控制、非线性控制理论等来设计了一些拥塞控制器[20-28]，以使得各控制器能适应网络状态的动态变化。但是，这些算法普遍存在过程复杂、计算量偏大、在大规模网络中无法实际部署的缺点。基于线性控制理论设计的拥塞控制器具有计算小，易于部署的特点，这类算法在动态网络中的性能表现并非很好，RED，REM，PI，LRED[16]和AOPC[13]等忽略了网络延迟对稳定性的影响，DC-AQM[14]和IMC-PID[15]等虽然考虑了延时补偿，但是，这些算法参数的计算依赖于固定的网络参数(即往返延时、网络中活动流的数目以及链路带宽)，当网络状态发生变化，算法参数与当前网络状态失配，算法性能会受到影响。在此，本文作者提出一种自适应调节参数的PID拥塞控制器APID。

1 往返延时RTT对网络性能的影响

TCP/AQM拥塞控制系统本质上是一个带有反馈延时的闭环控制系统。当网络状态变化时，其性能表现因参数与实际网络状态失配而受到较大影响。表1中给出了从中南大学访问几个国外站点的往返延时统计情况。从表1可以看出：在1 d中，延时的变化很明显，忽略网络延迟和固定参数设置的方法都无法很好地适应网络状态的动态变化。

为了研究AQM算法在往返延时(Round trip time,RTT)变化情况下的性能，选取了PI，REM，IMC-PID，LRED和AOPC几种具有代表性的AQM算法进行仿真实验。仿真实验采用经典的哑铃状单瓶颈链路拓扑结构(如图1所示)。瓶颈链路R1-R2的带宽为15×106bit/s，路由器缓冲区设为300个分组长度，目标队列长度设置为150个分组长度，平均每个分组为500字节。在各算法的参数设置方面，PI和IMC-PID算法按照活动流数目为60、瓶颈链路带宽15×106bit/s (3 750 packets/s)、往返延时400 ms来计算控制器参数；REM算法按照原仿真实验[9]参数进行设置；LRED算法参数配置中丢包率计算权重系数为0.1，丢包率测量时间间隔为1.0 s，丢包率计算历史值个数为4，β=0.001。在实验过程中，将S1，S2和S3改为D1，D2和D3的链路传输延迟分别为100，400和700 ms，观察各算法在带宽利用率、平均队列长度以及队列长度标准差等性能指标见表2。

表1 中南大学到一些著名机构网站的RTT统计Table1 RTT statistics between CSU and some famous organizations’ website ms

图1 单瓶颈链路仿真拓扑图Fig.1 Network topology of single-bottleneck simulation

从表2可以看出：当往返延迟RTT为100 ms时，各种算法均有很好的性能，带宽利用率都达到了98%以上，队列的均值都与目标值150个分组相差不大，同时队列的抖动情况也较好；当RTT为400 ms时，除了IMC-PID之外，各算法性能与链路传输延迟为100 ms时比较均有明显下降，而IMC-PID由于此时处于控制器参数与网络状态匹配的状态，链路带宽以及队列稳定性均比链路传输延迟为100 ms时有所提升；而当RTT增加到700 ms时，各算法性能均出现明显下降，带宽利用率下降，同时，队列长度到目标队列长度的偏离值增大且队列抖动更加剧烈。

表2 RTT变化情况下各算法的性能表现Table2 Performances of algorithms with RTT varying

2 自适应调节参数的拥塞控制器

2.1 TCP/AQM拥塞控制系统

Misra等[10]基于流体流理论建立了TCP Reno的拥塞避免阶段流量控制的非线性模型，同时用一对微分方程来描述TCP Reno的拥塞控制机制的瞬态行为；随后Hollot等[11]得到了TCP/AQM联合控制系统的系统框图(见图2)以及近似描述整个系统控制机制的简化模型。

图2 TCP/AQM联合控制系统框图Fig.2 Block diagram illustrating TCP/AQM control

如图2所示，G1(s)为AQM控制器，G2(s)为TCP窗口调整和路由器缓冲队列模块，它是受控对象，G2(s)的传递函数R(s)如下：

2.2 TCP/AQM拥塞控制机制下队列长度和丢包概率之间的关系

若将G2(s)作为受控对象，则q(s)和p(s)则为此过程的输出和输入；而G1(s)则可以看成是回路反馈。在本文提出的方法中，通过研究G2(s)，得到队列长度q(s)和丢弃概率p(s)之间的关系表达式，然后，通过在路由器上采集到的队列长度和丢弃概率的数据，计算出在G1(s)影响下的路由器中队列长度q(s)和丢弃概率p(s)关系表达式中的各个参数，并进一步利用这些参数计算出符合当前网络环境的PID控制器的参数。

定理1 给定一个受控过程G(s)，其传递函数为：

其中：q(s)和p(s)为此过程的输出和输入。若采用采样周期T=R，可得到q和p之间的离散关系表达式如下：

其中：Q(z)和P(z)为受控对象G2(z)所代表的控制器的输出和输入信号。

证毕。

2.3 自适应调节参数的拥塞控制器的设计和实现

为了计算拥塞控制器各参数，首先计算得到θ0，θ1以及θ2等参数，然后，根据式(2)求得符合当前网络状态的Km，T1以及T2，用以计算拥塞控制器的参数。

在本文提出的方法中，取最近的3个采样周期中测量得到的队列长度q(k)，q(k-1)，q(k-2)以及丢包概率p(k-1)，代入式(2)，并联立得到包含3个方程的方程组，这个方程组只包含了3个未知数θ0，θ1以及θ2；同时可以看出：这个方程组为一个非齐次线性方程组，不存在奇异解。这样，通过解这个方程组，可以得到θ0，θ1以及 θ2。然后，可以通过式(1)和(2)计算得到Km，T1，T2和R。由于采用内膜控制的方法估计PID控制器的参数能够很好地消除时滞对系统性能的影响，因此，利用IMC-PID中的方法，计算得到PID控制器中3个控制参数。在IMC-PID中，采用理想PIDγ=2，ε=0.5R时，可以得到控制器参数Kc，Ti，Td与Km，T1以及T2等参数之间的关系式如下：

第k个时间间隔中分组丢弃概率的计算表达式如下：

当路由器收到一个数据包时，根据式(6)以及结合保存在路由器上的丢包概率和队列长度的历史数据，可计算出丢包概率，依据此丢包概率对收到的数据包进行丢弃。由于式(6)中Kc，Ti，Td等参数是符合当前网络状态的控制器参数，因此，依据此控制器调节丢包概率，就不会出现当网络状态发生变化时因控制器参数失配导致网络稳定性变差，最终使得队列抖动加大，链路带宽利用率降低的现象。APID通过周期性地计算符合当前网络状态的控制器参数，对控制器进行配置，能够保证路由器缓冲队列的稳定，提高链路的带宽利用率。

3 仿真实验与性能分析

在仿真平台NS2[29]上对APID拥塞控制器在单瓶颈链路和多瓶颈链路上进行了仿真实验，并将其与PI，REM，IMC-PID，AOPC和LRED等算法的带宽利用率、队列长度平均值以及队列长度标准差等性能指标进行了比较。

3.1 单瓶颈链路拓扑结构

在本次实验中，网络拓扑结构、网络各节点、链路参数配置以及各算法参数配置均与本文实验所采用的参数配置一致，往返延迟为100，400和700 ms情况下，APID算法的带宽利用率、平均队列长度以及队列长度标准差的仿真实验结果如表3所示。

比较表2和表3可以看出：本文提出的算法在几种传输延迟环境下，都具有较好的带宽利用率，即使在RTT为700 ms，其他算法的带宽利用率急剧下降的情况下，APID仍然能够使得带宽利用率达到95%以上；同时，APID能够更好地控制队列长度(使其更接近于目标队列长度，同时队列抖动更小)，在RTT为700 ms的情况下，其他算法影响下的路由器队列长度已经严重偏离了预先设定的目标队列长度，而APID算法仍然能够保持平均队列长度为127.906 4，同时，队列标准差为46.336 8，此队列长度标准差与RTT为100 ms和400 ms时的相差不大(分别为48.800 4和46.863 0)。LRED和AOPC由于忽略了延时对算法性能的影响，所以在延迟很小的情况下具有很好的性能，但是在延迟加大之后算法性能恶化很明显，以LRED为例，RTT为100 ms的情况能够保持98%以上的带宽利用率，平均队列长度为157.659 2个分组长度，队列标准差为19.388 4；但是，当RTT增加到700 ms时，带宽利用率下降到77.276 3%，平均队列长度为48.466 2，严重偏离了目标队列长度，队列长度标准差也变为45.307 3，结合48.466 2的平均队列长度来看，此时的队列抖动已经非常剧烈。同样，PI和IMC-PID等算法在网络参数失配的情况下(传输延迟为100 ms和700 ms)，与在参数匹配的情况(传输延迟为400 ms)相比，对队列长度的控制也明显变弱，带宽利用率下降明显。以IMC-PID为例，队列长度均值从146.738 1(RTT为400 ms)变成49.204 5(RTT为700 ms)，严重地偏离了目标队列长度；队列标准差值也从44.316 8个分组(RTT为400 ms)增大到47.718 6个分组(RTT为700 ms)，注意到RTT为700 ms的情况下IMC-PID的平均队列长度只有49.204 5个分组长度，47.7186个分组长度的队列长度标准差意味着很剧烈的队列抖动。而APID由于能够根据网络状态动态的调整控制器的参数，使得队列长度更加接近于目标队列长度(RTT为700 ms时偏离值最大，队列长度平均值为127.906 4个分组长度，偏离值约为23个分组长度)；同时，队列抖动更小(3种情形下的队列长度标准差变化不大，分别为48.800 4，46.863 0和46.336 8)，链路的带宽利用率也更高(RTT为700 ms时带宽利用率最低为95.465 2%)。

表3 单瓶颈链路拓扑结构下APID算法的性能Table3 Performances of APID algorithm in network with single-bottleneck topology

3.2 多瓶颈链路拓扑结构

本次实验网络拓扑结构如图3所示，网络配置如下：R3-R4链路带宽为5×106bit/s，其他链路带宽均为15×106bit/s。120条TCP流从最左边发送方(S1,S2, …, Sn)向最右边的接收方(R1, R2, …, Rn)传送数据，其中，2对背景流的数目为90个TCP流，分别经由R2-R3和R4-R5 2条瓶颈链路从Cross Traffic Senders发往Cross Traffic Receivers。各算法参数配置与本文第1节仿真实验中一致，设置往返延时分别为100，400和700 ms。在本次实验中，R2-R3，R3-R4，R4-R5均为瓶颈链路，而仿真统计结果发现它们的队列长度变化有很大的相似性。表4所示为R3-R4链路上的带宽利用率、队列长度均值和标准差。

从表4可以看出：在多瓶颈链路网络拓扑情况下，APID具有较好的带宽利用率、更接近于目标队列长度的平均队列长度以及更小的队列抖动；而LRED和AOPC忽略了往返延时的影响，使得这些算法在延迟很小只有100 ms的情况下，带宽利用率均能在99%以上，同时，平均队列长度分别约为161个分组长度和157个分组长度，都非常接近设定的目标队列长度，队列长度标准差比较合理，分别约为25和15；但是，在延时变大时，算法性能下降很明显，在RTT为700 ms时，带宽利用率降低到73.094 6%和77.332 0%，平均队列长度分别为50.505 1个分组长度和55.327 0个分组长度，严重地偏离了目标队列长度，同时，队列标准差分别为48.904 1个分组长度和48.376 8个分组长度，与此时的平均队列长度相比，队列的抖动非常剧烈。同样，其他算法如PI和IMC-PID等由于参数失配，也有带宽利用率下降、平均队列长度越来越偏离目标队列长度以及队列长度抖动加大等问题。而APID算法能够根据当前网络状态自适应地调整控制器参数，使得队列长度更好地稳定在预先设定的队列长度附近，具有更小的队列标准差即更小的队列抖动，并能提供更高的带宽利用率。

图3 交叉式多瓶颈链路拓扑图Fig.3 Performances of algorithms in network with multi-bottleneck topology

表4 多瓶颈链路拓扑结构下各算法的性能表现Table4 Performances of algorithms in topology with multi-bottleneck

4 结论

(1)通过分析TCP/AQM拥塞控制机制中受控过程的传递函数，得到受控过程队列长度和丢包概率之间的关系，并在此基础上，提出了一种根据当前网络状态自适应调节参数的PID控制器APID。

(2)在NS2上对APID进行了测试，并与PI，REM，AOPC，LRED和IMC-PID等进行比较。测试结果表明，当网络状态动态变化的情况下，APID能够使得路由器队列长度更接近于预先设定的目标队列长度，能够使得缓冲队列抖动更小，同时能够获得更高的链路带宽利用率。

[1]Floyd S, Jacobson V.Random early detection gateways for congestion avoidance[J].IEEE/ACM Transactions on Networking,1993, 1(4): 397-413.

[2]IETF RFC 2309, Recommendations on queue management and congestion avoidance in the Internet[S].

[3]Ott T, Lakshman T, Wong L.SRED: Stabilized RED[C]//Proceedings of IEEE INFOCOM.New York: IEEE Press, 1999:1346-1355.

[4]Floyd S, Gummadi R, Shenker S.Adaptive RED: An algorithm for increasing the robustness of RED’s active queue management[EB/OL].[2001-03-20].http://www.icir.org/floyd/papers/adaptiveRed.pdf.

[5]SUN Jin-sheng, Ko K, CHEN Guan-rong, et al.PD-RED: To improve the performance of RED[J].IEEE Communications Letters, 2003, 7(8): 406-408.

[6]WANG Chong-gang, LIU Jiang-chuan, LI Bo, et al.LRED: A robust and responsive AQM algorithm using packet loss ratio measurement[J].IEEE Transaction on Parallel and Distributed Systems, 2007, 18(1): 29-43.

[7]CHEN Wu, YANG Shuang-hua.The mechanism of adapting RED parameters to TCP traffic[J].Computer Communications,2009, 32(13/14): 1525-1530.

[8]Low S H.A duality model of TCP and queue management algorithms[J].IEEE/ACM Transaction on Networking, 2003,11(4): 525-536.

[9]Athuraliya S, Low S H, Li V H, et al.REM: Active queue management[J].IEEE Network Magazine, 2001, 15(3): 48-53.

[10]Misra V, GONG Wei-bo, Towsley D.Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED[C]//Proceedings of Special Interest Group on Data Communications(SIGCOMM).Stockholm: ACM Press,2000: 151-160.

[11]Hollot C, Misra V, Towsley D, et al.A control theoretic analysis of RED[C]//Proceedings of IEEE INFOCOM.Anchorage: IEEE Press, 2001: 1510-1519.

[12]Hollot C, Misra V, Towsley D, et al.On designing improved controllers for AQM routers supporting TCP flows[C]//Proceedings of IEEE INFOCOM.Anchorage: IEEE Press, 2001:1726-1734.

[13]WANG Jian-xin, RONG Liang.AOPC: An adaptive optimized proportional controller for AQM[C]//Proceedings of International Conference on Parallel Processing (ICPP).Columbus, Ohio,2006: 164-171.

[14]任丰原, 林闯, 任勇, 等.大时滞网络中的拥塞控制算法[J].软件学报, 2003, 14(3): 503-511.REN Feng-yuan, LIN Chuang, REN Yong, et al.Congestion control algorithm in large-delay networks[J].Journal of Software,2003, 14(3): 503-511.

[15]WANG Jian-xin, RONG Liang, LIU Yun-hao.Design of a stabilizing AQM controller for large-delay networks based on internal model control[J].Computer Communications, 2008,30(10): 1911-1918.

[16]WANG Chong-gang, LI Bin, Hou T Y, et al.LRED: A robust active queue management scheme based on packet loss ratio[C]//Proceedings of IEEE INFOCOM.Hong Kong: IEEE Press, 2004: 1-12.

[17]XIAO Yang, WANG Lei, NIU Jun, et al.Congestion control algorithms for a new TCP/UDP router based on 2-D stability conditions[C]//Proceedings of 5th International Conference on Wireless Communications, Networking and Mobile Computing.Beijing: IEEE Press, 2009: 1-5.

[18]Ivan D B, Gonzalo R A, Bohacek S.Statistical approach for congestion control in gateway routers[J].Computer Networks,2011, 55(3): 572-582.

[19]Luca D C, Mascoloa S, Niculescu S I.Robust stability analysis of Smith predictor-based congestion control algorithms for computer networks[J].Automatica, 2011, 47(8): 1685-1692.

[20]ZHANG Yan-bin, HANG Da-ming, MA Zheng-xin, et al.A robust active queue management algorithm based on reinforcement learning[J].Journal of Software, 2004, 15(7):1090-1098.

[21]FAN Yan-fei, REN Feng-yuan, LIN Chuang.Design an active queue management algorithm based on fuzzy logic decision[C]//Proceedings of IEEE ICCT.New York: IEEE Press, 2003:286-289.

[22]FAN Yan-fei, LIN Chuang, REN Feng-yuan, et al.An intelligent packet dropping algorithm with ECN capability[J].Journal of Software, 2005, 16(9): 1636-1646.

[23]WANG Li, DU Shu-xin, LIN Jin-guo.An active queue management scheme using neural network based predictive control[C]//Proceedings of The 30th Annual Conference of the IEEE Industrial Electronics Society.Busan: IEEE Press, 2004:2556-2559.

[24]Rahnami K, Arabshahi P, Gray A.Neural network based model reference controller for active queue management of TCP flows[C]//Proceedings of IEEE Aerospace Conference.Big Sky:IEEE Press, 2005: 1696-1704.

[25]WANG Hao, TIAN Zuo-hua, ZHANG Qin-long.Self-tuning price-based congestion control supporting TCP networks[C]//Proceedings of IEEE ICCCN.Zurich: IEEE Press, 2010: 1-6.

[26]WANG Hao, TIAN Zuo-hua.Intelligent price-based congestion control for communication networks[C]//Proceedings of IEEE IWQoS.Beijing: IEEE Press, 2010: 1-5.

[27]Zheng F, Nelson J.Anapproach to the controller design of AQM routers supporting TCP flows[J].Automatica, 2009, 45(3):757-763.

[28]Papachristodoulou A, Jadbabaie A.Delay robustness of nonlinear internet congestion control schemes[J].IEEE Transactions on Automatic Control, 2010, 55(6): 1421-1427.

[29]UCN/LBL/VINT.Network Simulator-NS2[EB/OL].[2010-05-14].http://www-mash.cs.berkeley.edu/ns.