周鑫-主动队列管理(AQM)资料.精讲

主动队列管理

(ActiveQueuemanagement)周鑫2009-11-181历史背景1986年10月，由于拥塞崩溃的发生，美国LawrenceBerkeleyLaboratory到UCBerkeley的数据吞吐量从32Kbps跌落到40bps。探讨者从今相识到了拥塞限制机制对保证互联网的稳定性具有特殊重要的作用。因此，在网络拥塞限制领域内开展了大量的探讨工作，使拥塞限制成为计算机网络探讨领域的热点问题。2009-11-182TCP/IP下的拥塞限制TCP/IP协议是目前互联网中运用最广泛的传输协议。依据MCI的统计，总字节数的95%和总分组数的90%运用TCP协议传输。围围着TCP/IP协议的拥塞限制始终都是互联网的探讨热点。TCP源端拥塞限制IP链路拥塞限制2009-11-183TCP/IP下的拥塞限制拥塞限制TCP源端拥塞限制IP链路拥塞限制①慢启动②拥塞避开③快速重传④快速复原TahoeRenoSackHSTCPFastVegasTFRCXCP①队列管理②分组调度被动主动RedDRedWRedBLUEAVQPIPIDPAQM2009-11-184被动队列管理的缺陷算法：①弃尾队列管理算法（DT）②随机丢弃管理算法（RD）③从前丢弃管理算法（DF）缺陷：1.死锁问题：同步定时，数据独占队列2.满队列问题：队列充溢，延时3.全局同步问题：TCP流自适应特性2009-11-185发展趋势随着网络规模的急剧膨胀新出现的网络应用对服务质量的要求越来越高在路由器中接受AQM机制显得尤其重要1998年IETF建议在路由器中接受AQM机制在国际上掀起了探讨AQM机制的高潮至2005年8月止以AQM为关键词，在IEEE的数据库中可以检索到文章124篇，WebofScience数据库(SCI,SSCI,AHCI)中可以检索到文章624篇，在EI数据库中可以检索到文章492篇主动队列管理成为网络探讨的热点之一2009-11-186主动队列管理AQM机制的主要思想：网络节点在缓冲区没有溢出之前，依据网络的拥塞状况，以确定的概率丢弃报文或者通知拥塞，端节点调整速率缓解拥塞AQM机制的主要性能指标，包括链路利用率、报文丢弃率以及平均队列长度等2009-11-187显示拥塞指示（ECN）拥塞反馈信号的形式，主要包括丢弃分组和标记分组RFC3168提出ECN(ExplicitCongestionNotification)规范，主要工作原理是：在连接建立阶段，TCP发送端、接收端和路由器声明支持ECN；当网络发生拥塞时，路由器设置TCP分组头部的拥塞标记位；接收端检测到拥塞标记位后，设置确认分组的相应位；发送端依据拥塞标记位推断网络拥塞，并增减拥塞窗口2009-11-188主动队列管理算法分类发觉拥塞之后处理方法的不同可以将主动队列算法分为两类：(1)通过对数据包打标记(比如说ECN，通过这种方法实现的主动队列算法主要有BlUE以及针对BlUE的改进算法SFB(2)通过丢弃数据包，通过这种方法实现的主动队列算法比较多，主要有RED，FRED，CHOKe，CSFQ，PFED等2009-11-189随机早期检测(RED)算法随机早期检测(RED)算法是最著名的AQM算法之一，它由AQM创始探讨人员Floyd教授提出，并且是IETF举荐的标准AQM算法。RED是一种早期丢弃技术，即在网络发生拥塞的早期就丢弃部分分组数据，改善队列的动态特性，提高网络的利用率。与弃尾算法相比，RED为队列管理增加了两种新机制：(1)分组丢弃不是等到队列缓存溢出时发生，而是依据队列长度利用概率判定机制预先丢弃部分分组来预防可能发生的拥塞；(2)判定分组丢失概率依据的队列长度是平均队列长度，而不是即时队列长度，这在确定程度上可以吸取部分短暂的突发流量。2009-11-1810随机早期检测(RED)算法平均队列长度：RED队列管理策略依据分组到达或固定的时间间隔，先接受指数加权滑动平均计算Avg=(1-Wq)×Avg+Wq×q其中，Avg表示平均队列长度，q表示瞬时队列长度，Wq是一个加权系数，同时也是一个时间常数2009-11-1811随机早期检测(RED)算法丢弃/标记概率：接受平均队列长度Avg作为拥塞测度，并设定两个限制阈值minth和maxth，maxp是预先设置的分组丢弃概率，Pb为当前分组丢弃概率的计算值2009-11-1812随机早期检测(RED)算法若Avg小于minth，则没有包须要丢弃；当minth<Avg<maxth时，计算出概率Pb，并以此概率丢包；当Avg>maxth时，全部的包都被丢弃。2009-11-1813随机早期检测(RED)算法RED算法接受简洁的限制机制，很简洁实现，因此也得到了业界的广泛认可和支持；但是RED算法还存在很多问题：①参数设计和网络状况对RED算法的性能有很大的影响，在特定网络负载状态下照旧会导致队列震荡、吞吐量降低和延迟抖动加剧；②RED算法还存在公允性和稳定性问题。针对RED算法的缺陷，已经提出很多相关的改进方案（WRED，FRED，Stabilized-RED和AdaptiveRED等）和新的主动队列管理算法（PI限制器，REM和AVQ等），它们的主要思路是依据网络中负载的状况对标记或丢失概率进行动态调整。2009-11-1814基于限制理论的AQM随着对TCP协议运行机制相识的深化和计算机网络建模技术的发展，将限制理论应用于主动队列管理机制的设计成为可能并且已经成为目前探讨的热点。①基于经典限制理论的AQM②基于鲁棒限制理论的AQM③基于智能限制理论的AQM2009-11-1815基于经典限制理论的AQM2000年VishalMisra等建立了TCP与队列变更的非线性微分方程模型2001年C.V.hollot接受小信号线性化方法将该模型线性化，并且导出了线性模型的传递函数，在此基础上分析了RED的参数设置并设计了比例积分(PI)限制器。2009-11-1816基于经典限制理论的AQMTCP流量限制模型及其线性化其中，W(t)是拥塞窗口尺寸，R(t)表示来回时间，p(t)表示分组丢弃/标记概率，q(t)表示队列长度，N(t)表示TCP会话数，C(t)表示链路容量。2009-11-1817基于经典限制理论的AQMAQM反馈限制模型：将TCP动态模型线性化并忽视小延时，得：可得AQM系统框图：2009-11-1818基于经典限制理论的AQM比例积分微分限制器设计（举例）剩余问题就是选择合适的Kl、Kp、Kd使系统有足够的稳定裕度和快速的反应。2009-11-1819基于经典限制理论的AQMAQM控制模型特点BLUEOn-off动态微调报文丢弃概率REDI加权平均队列长（min,max）DREDI常值队列长度作为控制目标AVQP维持一个虚拟队列并调整PIPI控制目标，更快，无稳差PAQMPID获控制量变化趋势早期修正2009-11-1820新型限制理论的AQM基于鲁棒限制理论的AQM基于智能限制理论的AQM作用：随着被控对象越来越困难，基于精确模型的限制方法在面对困难限制系统的不确定性和困难性的时候往往力不从心。主要是解决经典限制理论难以解决的困难系统的限制问题，针对的探讨对象是不确定的模型、高度的非线性、困难的任务要求。2009-11-1821基于限制理论的AQM优越性：(1)设计方法更加科学，参数配置变得简洁(2)算法的性能对网络条件的敏感性降低(3)大部分基于限制理论设计的AQM机制的困难程度与RED相当，实现简洁，适用于高速网络(4)具有明确的限制目标，消退了队列长度与负载的耦合，减小了队列振荡2009-11-1822基于限制理论的AQM基于限制理论的AQM算法是当前探讨的热点和主流，但照旧存在不足：(1)没有充分考虑被控对象模型的不精确性，如①近似模型只考虑了TCP流而没有考虑UDP等接受其它协议的流②只考虑了TCP协议的拥塞避开阶段忽视了慢启动和超时阶段③在模型线性化过程中假设活跃的TCP连接数目TCP连接的RTT等参数在较长时间内保持不变(2)对被控对象缺乏深化的分析导致AQM限制器不能很好地保证系统的稳态性能和暂态性能。当传输延迟比较大的无线网络接入到高速有线网络中构成了与当前网络不同的高带宽延迟积网络，仿真试验中现有的算法在这些困难的网络环境中不能取得令人满足的效果。(3)当前的限制模型忽视了网络中多个路由器接受异种AQM机制时报文标记效果的相互影响而这是AQM获得应用必须要解决的问题。2009-11-1823其他AQM机制最近，很多学者试图利用其它理论和方法来解决主动队列管理探讨中的一些问题，主要包括：①基于最优化理论和经济学的方法②基于仿生的方法③基于博奕论的方法等但上述算法仅仅作为一种新方法被提出来没有成为探讨的主流。2009-11-1824几种AQM与ECN对网络的影响把端到端的响应时间作为评价标准，则有如下的结论：没有利用ECN机制，运行在比特模式下的ARED是最好的设计方案，但是运行在分组包模式下时却是最差的设计，甚至比DT还要差。利用ECN机制的PI与REM是最好的设计，但是不利用ECN的话，REM的性能会比DT还要差。ECN对ARED没有什么帮助，即使改进ECN对ARED性能的提升也不高，ARED最好的性能发挥在比特模式下。AQM对网络性能的影响是否显著确定于RTT的抖动幅度，当RTT跳动的很大时，AQM于ECN对网络的响应时间性能的影响降低。对特定的网络，须要接受合适的AQM，才能在网络高负荷时照旧能获得很好的网络性能。2009-11-1825总结由于Internet传输的突发性和弃尾队列管理方法的不足，IETF建议在路由器中接受主动队列管理机制以克服DT的缺陷，并且在尽力服务网络中供应低延迟低丢失率的服务尽管多数路由器支持RED等算法例如Cisco的多数路由器部署了RED的变种算法Cisco’sWRED，但是AQM机制在路由器的默认配制中都是禁止的，因此目前为止AQM的应用状况照旧很难估计。自1998年以来探讨者提出了近百种的AQM算法，尽管该领域的探讨已经持续了几年，但照旧没有获得广泛认可和应用的方案，照旧存在很多尚未充分绽开和尚待解决的问题，包括流量模型稳定性、多AQM协同工作等理论难题，以及在无线网络区分服务组播等环境下的应用问题都须要探讨者的进一步关注2009-11-1826参考文献LongLe,JayAikat,KevinJeffay,andF.DonelsonSmith.TheEffectsofActiveQueueManagementandExplicitCongestionNotificationonWebPerformance.IEEE/ACMT