高速网络中的主动队列管理算法研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
在2006年的IEEE INFOCOM会议中,会议组织专设了一个有关高速网络的讨论组,旨在讨论千G位网络所带来的挑战和解决的办法,其中高速网络中的拥塞控制机制正是当前研究领域上的一个热点内容。
     现有的针对高速网络的拥塞控制算法中,研究的主要热点分为两种:第一种为端到端的拥塞控制机制,这类机制的代表为HighSpeed-TCP、Fast-TCP;第二种为基于反馈的拥塞控制机制,即利用中间节点的参与,把链路的负载情况反馈给端节点,端节点再根据反馈信息调整发送速率,这类机制的代表为XCP、VCP、RCP等。但XCP、VCP和RCP这类协议过多的依赖路由器的参与,这将使得路由器的任务过于繁重,实现起来也有很大的困难。而且XCP需要修改数据包的结构,增加数据包的头部位数,这更加大了实施的难度。VCP的反馈信息较XCP的较为粗糙,而且在路由器中沿用了Drop-Tail算法,所以,VCP仍然存在全局同步、死锁等问题。所以这几年对源端节点的拥塞控制研究变得异常活跃,源端节点的拥塞控制研究的主要集中点在于如何正确及时地获得反馈信息以及在得到反馈信息的基础上如何正确及时地调整拥塞窗口。而发出反馈信息需要中间节点的参与,纯粹的端算法没有与中间节点的算法相结合。因此,本文主要研究的是在高速网络下,结合已有的端算法,在IP层解决网络拥塞问题的方案。主要的工作有以下三个方面:
     1、分析和比较几种典型的主动队列管理(Active Queue Management, AQM)算法在高速网络中的性能,经仿真实验发现这几种AQM算法在高速网络中的性能都不理想,主要表现为:链路的带宽利用率不高,全局同步现象严重,队列长度不能维持在一定值附近。这些现象说明了现有的AQM算法在高速网络下不能满足QoS(quantity of serve)的要求。
     2、PI控制器建立在Mirsa等人提出的TCP/AQM控制论模型上,使用控制理论研究主动队列管理算法。理论分析和实验都表明,PI控制器比RED算法具有更小的队列抖动,从而在保证高带宽利用率的前提下,为源端提供了更小的延时抖动。但是在PI控制器中,参数是固定设置的,在高速网络下性能很差,不能满足AQM的设计目标。因此,文中提出一种加强型的PI控制算法——EPI,使用平均队列长度对丢包概率进行在线调整,使得PI能满足高速网络下的性能要求。仿真结果表明,在高速网络下,EPI的综合性能较PI优秀。
     3、BLUE算法是RED算法的一种改进,其使用队列溢出和链路空闲事件来进行队列管理。BLUE算法维持了一个概率Pm用以标记丢包概率。如果由于缓存溢出而产生丢包事件,则增加Pm,从而增加向源端发送拥塞通知的速度,相反,如果由于链路空闲导致队列为空,则减小Pm。相对于RED算法来说,BLUE算法减小了丢包率及对路由器缓存空间的需求,并且具有“学习”的功能,不需要计算很多复杂的参数,但却能有效地对路由器中的队列进行管理。但是,BLUE算法仍然存在着对动态的网络环境缺乏自适应能力的缺点。在控制领域中,模糊控制理论不需要很精确的数学模型,仅依赖于经验的积累、感觉和逻辑判断就可以获得很好的控制效果,因此,文中提出一种基于模糊理论的主动队列管理算法——FBLUE,该算法在BLUE原有的基础上增加了门限机制,根据模糊理论使用平均队列长度来动态地调整丢包概率的变化步长。经过仿真实验证明,FBLUE在传统的网络环境下,有效地保持了BLUE算法丢包率低的优点,并且使队列长度更加稳定,出现溢出和空闲的现象减少,在链路的带宽利用率上明显高于BLUE算法。在高速网络中保证了高的带宽利用率,且有效地控制队列长度稳定在一定值附近,克服了BLUE算法的全局同步现象,与其他几种经典AQM算法相比,在链路的带宽利用率、队列长度的稳定程度上都有很大的提高,并且在网络负载变化的情况下,仍然能保持良好的性能。
In the IEEE INFOCOM 2006, there was a High-Speed Networking Workshop, which was to study and discuss the Terabits challenge, and the congestion control for high-speed network also becomes the hot issue and difficulty issue of the Internet research.
     The exiting congestion control mechanism for high-speed networks can be classified into two categories: end-to-end mechanism and network feedback based mechanism. HighSpeed-TCP, Fast-TCP and H-TCP are the typical end-to-end mechanism. XCP, VCP and RCP are the network feedback based mechanism. In the feedback-based mechanism, the routers become a part of congestion control mechanism, so the end node can get more nicety feedback about the network’s congestion state. But this makes routers be busier and it is very difficult to come true. Specially, XCP require a non-trivial number of bits to encode the feedback, bits which are not available in the IP headers. The VCP leverages the existing two ECN bits for network congestion feedback, but it is more roughness than XCP, and also has the global synchronization and the lock-out problems. In resent years, the research of end-to-end algorithms for high-speed network become greatly activity, theses algorithms major in how to get the feedback about the network’s state and then how to adjust the congestion window. The feedbacks are send by the routers, but the pure end-to-end congestion control schemes don’t combine with the AQM, so this paper major in the research of the AQM algorithms for the high-speed networks, combining with the end-to-end schemes. The main work in this paper is:
     1. Analyzing and comparing several typical AQM algorithms’performance in the high-speed network, from the simulation’s result, we found that these AQM algorithms are perform badly in the high-speed networks, behave as: low bandwidth’s utilization, global synchronization, the queue length can’t maintain at a range of the target. These phenomenon shows that the exiting AQM algorithms can’t satisfy the need of quantity of serve in high-speed network.
     2. PI bases on a developed linearized model of TCP and AQM, and uses classical control system techniques to study the active queue management. Both the theory analysis and the simulations show that PI’s performance is better than RED. But the parameter a and b of PI are constant, they can’t adapt to the high-speed network. Thus, this paper puts forward an enhanced PI algorithm named EPI, EPI uses average queue length to adjust the dropping probability online. By the simulation, the general performance of EPI is better than the PI on the high-speed network.
     3. BLUE uses buffer overflow and link idle events to manage congestion. It maintains a Pm to mark the probability. If the buffer is overflow, it increase the Pm, the other way round, if the link is idle, it decrease the Pm. Compare to RED, the BLUE has lower packets-loss-ratio, and needs smaller buffer size. BLUE also has the“study”function, it doesn’t need many parameters, but can manage the queue effectively. However, BLUE also has the disadvantage, it isn’t adaptive in difference environments. In the control field, fuzzy doesn’t need the precision model, only needs the experience, logic judgement and gets the excellence effect. So, in this paper, a new active queue management algorithm named FBLUE is proposed. Combined with a threshold and based on the fuzzy theory, FBLUE uses average queue length to adjust the dropping probability’s increment and decrement factor dynamically. By the simulation, in the tradition network, FBLUE is shown to perform significantly better than BLUE in terms of queue size and link utilization. In the high-speed network, FBLUE is shown to perform better than other typical AQM algorithms.
引文
[1] 全球互联网统计信息跟踪报告[R]. CNNIC, 2006
    [2] http://industry.ccidnet.com/pub/article/c218_ a30229_pl.httnl
    [3] 任丰原, 林闯, 刘卫东. IP 网络中的拥塞控制[J]. 计算机学报, 2003, vol. 26, no. 9, 1025~1034
    [4] Floyd, S. Jacobson, V. Random early detection gateways for congestion avoidance [J]. IEEE/ACM. Transactions on Networking, 1993, 1(4): 397~413
    [5] S. Floyd. A report on some recent development in TCP congestion control [EB/OL]. http://www.aciri.org/floyd/papers/TCPreport1.ps
    [6] M. May, T. Bonald, T. Bolot. Analytic evaluation of RED performance [A]. In: IEEE INFOCOM 2000 [C]. Tel Aviv, Israel: 2000. 1415~1424
    [7] Floyd, S., Fall, K. Promoting the use of end-to-end congestion control in the Internet[J]. IEEE/ACM Transactions on Networking, 1999, 7(4): 458~472
    [8] Teunis J Ott, T V Lakshman, Larry H Wong, SRED: Stabilized RED [A]. In: IEEE INFOCOM 1999 [C]. New York, USA: 1999.1346~1355
    [9] W Feng, D Kandlur, D Sah, K Shin. A self-configuring RED gateway [A]. In: IEEE INFOCOM 1999[C]. New York, USA: 1999. 1320~1328
    [10] Sally Floyd, Ramakrishna Gummsdi, Scott Shenker. Adaptive RED: An algorithm for increasing the robustness of RED’s active queue management [EB/OL]. http://www.aciri.org/floyd/papers/adaptiveRed.ps
    [11] D Lin, R Morris. Dynamics of random early detection [A]. In: ACM SIGCOMM 1997 [C]. Cannes France: 1997. 127~137
    [12] F Anjum, L Tassiulas. Balanced-RED: An algorithm to achieve fairness in internet [EB/OL]. http://www.isr.umd.edu.CSHCN
    [13] W Feng, D Kandlur, D Sah, K Shin. Blue: A new class of active queue management algorithm [R]. University of Michigan Technical Reports CSE-TR-387-99, April 1999
    [14] C Hollot, V Misra, D Towsley, W B Gong. On designing improved controllers for AQM routers supporting TCP flows [A]. In: IEEE INFOCOM 2001[C]. Anchorage, Alaska, 2001.1726~1734
    [15] Sanjeewa Athuraliya, Steven H Low, Victor H Li, Qinghe Yin. REM: Active queue management [J]. IEEE Network, 2001, 15(3): 48~53
    [16] R J Gibbens, F P Kelly. Distributed connection acceptance control for a connectionless network [A]. In: the 16th International Teletraffic Congress [C]. Edinburgh, Scotland:1999
    [17] S Kunniyur, R Srikant. Analysis and design of an adaptive virtual queue algorithm for active queue management [A]. In: ACM SIGCOMM 2001 [C]. San Diego, USA, 2001
    [18] R J Gibbens, F P Kelly. Resource pricing and the evolution of congestion control [EB/OL]. http://www.statslab.cam.ac.uk/~frank/evol.html, 1998
    [19] W. Feng, Kang G. Shin, D.D. Kandlur, D. Saha, The Blue active queue management algorithms[J], IEEE/ACM Transactions on Networking 10 (4) (2002) 513–528
    [20] V. Misra, W. Gong, D. Towsley, A fluid-based analysis of a network of AQM router supporting TCP flows with an application to Red [A], In: ACM SIGCOMM 2000, Stockholm, Sweden, September 2000
    [21] C.V. Hollot, V. Misra, D. Towsley, et al, Analysis and design of controllers for AQM routers supporting TCP flows[J], IEEE Transactions on Automatic Control 47 (6) (2002) 945–959
    [22] S.H. Low, D.E. Lapsley, Optimization flow control, I: basic algorithm and convergence[J], IEEE/ACM Transactions on Networking 7 (6) (1999) 861–874
    [23] Sally Floyd. HighSpeed TCP for Large Congestion Windows. RFC 3649, December 2003
    [24] Cheng Jin David X. Wei Steven H. Low. FAST TCP: Motivation, Architecture, Algorithms, Performance[A]. In: IEEE INFOCOM 2004, Hong Kong, March 2004.
    [25] D.Katabi, M.Handley, C.Rohrs, Congestion control for high bandwidth delay product networks[DB/OL]. In: ACM SIGCOMM, August 2002.
    [26] Y Xia, L Subramanian, I Stoica, S Kalyanaraman, One More Bit Is Enough[A]. In: ACM SIGCOMM 2005[C]. Philadelphia, USA, 2005
    [27] Leith, R.Shorten. H-TCP: TCP for high-speed and long-distance networks[DB/OL]. http://www.hamilton.ie/net/main.htm?tcp, 2004
    [28] Lisong Xu, Khaled Harfoush, and Injong Rhee. Binary Increase Congestion Control (BIC) for Fast Long-Distance Networks[A]. In: IEEE INFOCOM 2004, Hong Kong, March 2004.
    [29] Nandita Dukkipati, Masayoshi Kobayashi, RuiZhang Shen, Nick McKeown. Minimizing the Duration of Flows[R]. Stanford HPNG Technical Report TR04-HPNG-061604, 2004
    [30] Low .S. H. A duality model of TCP and queue management algorithms [J]. IEEE/ACM Transactions. On Networking, 11(4):525-536, August 2003
    [31] S.Low, F. Paganini, J.C. Doyle. Internet Congestion Contro [J]. IEEE Control Systems Magazine,2002,22(1): 28-43
    [32] M. Vojnovic, J. Y. Le Boudec, C. Boutremans. Global fairness of additive-increase and multiplicative-decrease with heterogenous round-trip times [A]. In: IEEE INFOCOM 2000, March 2000
    [33] Paganini F, Doyle J, Low S. Scalable laws for stable network congestion control [DB/OL]. http://www. Ee. Ucla. Edu/~paganini, September 2001
    [34] S Mccannne, S Floyd. Ns-LBNL the network simulator [EB/OL]. http://www.isi.edu/nsnam/ns
    [35] LiQing, Qingxin Zhu, Mingwen Wang. Designing Adaptive PI Algorithm Based on Single Neuron[A]. In: ICCNMC 2005, LNCS 3619, 800-807
    [36] 刘明, 窦文华, 张鹤颖, 张锰. 主动队列管理机制中 PI 算法的一种参数配置方法[J]. 国防科技大学学报, 2006; 27(3), 115-119
    [37] 陆锦军, 王执铨. 基于速度控制的 API 网络拥塞控制策略[J] . 计算机应用, 2006; 26(5)1137-1143
    [38]Chengnian Long, Bin Zhao, Xinping Guan et al. The Yellow active queue management algorithm[J]. Computer Networks, 2005; 47: 525–550
    [39] Chonggang Wang, Bin Li, Thomas Hou, et al. LRED: A robust active queue management scheme based on packet loss ratio[C]. In: IEEE INFOCOM, 2004
    [40] 张顺亮,叶澄清,李方敏.一种加强的主动队列管理算法—EBLUE[J]. 通信学报, 2003; 24(11), 109-115
    [41] 吴春明,姜明.Sblue:一种增强 Blue 稳定性的主动队列管理算法[J]. 通信学报, 2005; 26(3), 68-74
    [42] M Yaghmace, H Toosi. A Fuzzy Based Active Queue Management Altorithm [DB/OL], http://www.scs.org/scsarchive/getDoc.cfm?id=2449
    [43] 韩峻峰, 李玉惠. 模糊控制技术[M]. 重庆大学出版社,2003. page31

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700