《周鑫——主动队列管理(AQM)资料.精讲.ppt》由会员分享，可在线阅读，更多相关《周鑫——主动队列管理(AQM)资料.精讲.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、主动队列管理主动队列管理(Active Queue management)周鑫2009-11-181历史背景1986 年10 月，由于拥塞崩溃的发生，美国Lawrence Berkeley Laboratory 到UC Berkeley 的数据吞吐量从32Kbps 跌落到40bps。研究者从此认识到了拥塞控制机制对保证互联网的稳定性具有十分重要的作用。因此，在网络拥塞控制领域内开展了大量的研究工作，使拥塞控制成为计算机网络研究领域的热点问题。2009-11-182TCP/IP下的拥塞控制TCP/IP协议是目前互联网中使用最广泛的传输协议。根据MCI 的统计，总字节数的95%和总分组数的90%使
2、用TCP 协议传输。围绕着TCP/IP协议的拥塞控制一直都是互联网的研究热点。TCP源端拥塞控制IP链路拥塞控制2009-11-183TCP/IP下的拥塞控制拥塞控制拥塞控制TCP源端拥塞控制IP链路拥塞控制 慢启动 拥塞避免快速重传快速恢复TahoeRenoSackHSTCPFastVegasTFRCXCP 队列管理 分组调度被动主动RedDRedWRedBLUEAVQPIPIDPAQM2009-11-184被动队列管理的缺陷算法：弃尾队列管理算法（DT）随机丢弃管理算法（RD）从前丢弃管理算法（DF）缺陷：1.死锁问题：同步定时，数据独占队列2.满队列问题：队列充满，延时3.全局同步问题：
3、TCP流自适应特性2009-11-185发展趋势随着网络规模的急剧膨胀新出现的网络应用对服务质量的要求越来越高在路由器中采用AQM 机制显得尤其重要1998 年IETF 建议在路由器中采用AQM 机制在国际上掀起了研究AQM 机制的高潮至2005 年8 月止以AQM 为关键词，在IEEE 的数据库中可以检索到文章124 篇，Web of Science 数据库(SCI,SSCI,AHCI)中可以检索到文章624 篇，在EI 数据库中可以检索到文章492 篇主动队列管理成为网络研究的热点之一2009-11-186主动队列管理AQM 机制的主要思想：网络节点在缓冲区没有溢出之前，根据网络的拥塞状况
4、，以一定的概率丢弃报文或者通知拥塞，端节点调整速率缓解拥塞AQM 机制的主要性能指标，包括链路利用率、报文丢弃率以及平均队列长度等2009-11-187显示拥塞指示（ECN）拥塞反馈信号的形式，主要包括丢弃分组和标记分组RFC3168 提出ECN(Explicit Congestion Notification)规范，主要工作原理是：在连接建立阶段，TCP发送端、接收端和路由器声明支持ECN；当网络发生拥塞时，路由器设置TCP 分组头部的拥塞标记位；接收端检测到拥塞标记位后，设置确认分组的相应位；发送端根据拥塞标记位判断网络拥塞，并增减拥塞窗口2009-11-188主动队列管理算法分类发现拥塞
5、之后处理方法的不同可以将主动队列算法分为两类：(1)通过对数据包打标记(比如说ECN，通过这种方法实现的主动队列算法主要有BlUE以及针对BlUE的改进算法SFB(2)通过丢弃数据包，通过这种方法实现的主动队列算法比较多，主要有RED，FRED，CHOKe，CSFQ，PFED等2009-11-189随机早期检测(RED)算法随机早期检测(RED)算法是最著名的AQM算法之一，它由AQM创始研究人员Floyd教授提出，并且是IETF推荐的标准AQM算法。RED是一种早期丢弃技术，即在网络发生拥塞的早期就丢弃部分分组数据，改善队列的动态特性，提高网络的利用率。与弃尾算法相比，RED为队列管理增添了
6、两种新机制：(1)分组丢弃不是等到队列缓存溢出时发生，而是根据队列长度利用概率判定机制预先丢弃部分分组来预防可能发生的拥塞；(2)判定分组丢失概率依据的队列长度是平均队列长度，而不是即时队列长度，这在一定程度上可以吸收部分短暂的突发流量。2009-11-1810随机早期检测(RED)算法平均队列长度：RED队列管理策略根据分组到达或固定的时间间隔，先采用指数加权滑动平均计算 Avg=(1-Wq)Avg+Wqq 其中，Avg表示平均队列长度，q表示瞬时队列长度，Wq是一个加权系数，同时也是一个时间常数2009-11-1811随机早期检测(RED)算法丢弃/标记概率：采用平均队列长度Avg 作为拥
7、塞测度，并设定两个控制阈值minth 和maxth，maxp 是预先设置的分组丢弃概率，Pb 为当前分组丢弃概率的计算值2009-11-1812随机早期检测(RED)算法若Avg小于minth，则没有包需要丢弃；当minth Avg maxth时，所有的包都被丢弃。2009-11-1813随机早期检测(RED)算法RED算法采用简单的控制机制，很容易实现，因此也得到了业界的广泛认可和支持；但是RED算法还存在许多问题：参数设计和网络状况对RED算法的性能有很大的影响，在特定网络负载状态下依然会导致队列震荡、吞吐量降低和延迟抖动加剧；RED算法还存在公平性和稳定性问题。针对RED 算法的缺陷，已
8、经提出许多相关的改进方案（WRED，FRED，Stabilized-RED和 Adaptive RED 等）和新的主动队列管理算法（PI 控制器，REM 和AVQ 等），它们的主要思路是根据网络中负载的情况对标记或丢失概率进行动态调整。2009-11-1814基于控制理论的AQM随着对 TCP 协议运行机制认识的深入和计算机网络建模技术的发展，将控制理论应用于主动队列管理机制的设计成为可能并且已经成为目前研究的热点。基于经典控制理论的AQM基于鲁棒控制理论的AQM基于智能控制理论的AQM2009-11-1815基于经典控制理论的AQM2000 年Vishal Misra等建立了TCP 与队列变
9、化的非线性微分方程模型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比例积
10、分微分控制器设计（举例）剩余问题就是选择合适的Kl、Kp、Kd使系统有足够的稳定裕度和快速的反应。2009-11-1819基于经典控制理论的AQMAQM控制模型特点BLUEOn-off动态微调报文丢弃概率REDI加权平均队列长（min,max）DREDI常值队列长度作为控制目标AVQP维持一个虚拟队列并调整PIPI控制目标，更快，无稳差PAQMPID获控制量变化趋势早期修正2009-11-1820新型控制理论的AQM基于鲁棒控制理论的AQM基于智能控制理论的AQM作用：随着被控对象越来越复杂，基于精确模型的控制方法在面对复杂控制系统的不确定性和复杂性的时候往往力不从心。主要是解决经典控制理论难
11、以解决的复杂系统的控制问题，针对的研究对象是不确定的模型、高度的非线性、复杂的任务要求。2009-11-1821基于控制理论的AQM 优越性优越性：(1)设计方法更加科学，参数配置变得容易(2)算法的性能对网络条件的敏感性降低(3)大部分基于控制理论设计的AQM 机制 的复杂程度与RED 相当，实现简单，适用于高速网络(4)具有明确的控制目标，消除了队列长度与负载的耦合，减小了队列振荡2009-11-1822基于控制理论的AQM基于控制理论的AQM 算法是当前研究的热点和主流，但仍然存在不足：(1)没有充分考虑被控对象模型的不精确性，如近似模型只考虑了TCP 流而没有考虑UDP 等采用其它协议
12、的流只考虑了TCP 协议的拥塞避免阶段忽略了慢启动和超时阶段在模型线性化过程中假设活跃的TCP 连接数目TCP连接的RTT 等参数在较长时间内保持不变(2)对被控对象缺乏深入的分析导致AQM 控制器不能很好地保证系统的稳态性能和暂态性能。当传输延迟比较大的无线网络接入到高速有线网络中构成了与当前网络不同的高带宽延迟积网络，仿真实验中现有的算法在这些复杂的网络环境中不能取得令人满意的效果。(3)当前的控制模型忽略了网络中多个路由器采用异种AQM 机制时报文标记效果的相互影响而这是AQM 获得应用必须要解决的问题。2009-11-1823其他AQM机制最近，许多学者试图利用其它理论和方法来解决主动
13、队列管理研究中的一些问题，主要包括：基于最优化理论和经济学的方法 基于仿生的方法 基于博奕论的方法等 但上述算法仅仅作为一种新方法被提出来没有成为研究的主流。2009-11-1824几种AQM与ECN对网络的影响 把端到端的响应时间作为评价标准，则有如下的结论：没有利用ECN机制，运行在比特模式下的ARED是最好的设计方案，但是运行在分组包模式下时却是最差的设计，甚至比DT还要差。利用ECN机制的PI与REM是最好的设计，但是不利用ECN的话，REM的性能会比DT还要差。ECN对ARED没有什么帮助，即使改进ECN对ARED性能的提升也不高，ARED最好的性能发挥在比特模式下。AQM对网络性能
14、的影响是否显著决定于RTT的抖动幅度，当RTT跳跃的很大时，AQM于ECN对网络的响应时间性能的影响降低。对特定的网络，需要采用合适的AQM，才能在网络高负荷时仍然能获得很好的网络性能。2009-11-1825总结由于 Internet传输的突发性和弃尾队列管理方法的不足，IETF建议在路由器中采用主动队列管理机制以克服DT的缺陷，并且在尽力服务网络中提供低延迟低丢失率的服务尽管多数路由器支持RED等算法例如Cisco的多数路由器部署了RED的变种算法Ciscos WRED，但是AQM机制在路由器的默认配制中都是禁止的，因此目前为止AQM的应用情况仍然很难估计。自 1998 年以来研究者提出了
15、近百种的AQM 算法，尽管该领域的研究已经持续了几年，但仍然没有获得广泛认可和应用的方案，仍然存在许多尚未充分展开和尚待解决的问题，包括流量模型稳定性、多AQM 协同工作等理论难题，以及在无线网络区分服务组播等环境下的应用问题都需要研究者的进一步关注2009-11-1826参考文献Long Le,Jay Aikat,Kevin Jeffay,and F.Donelson Smith.The Effects of Active Queue Management and Explicit Congestion Notification on Web Performance.IEEE/ACM TRANSACTIONS ON NETWORKING,VOL.15,NO.6,DECEMBER 2007.刘明,窦文华,张鹤颖.主动队列管理研究综述.计算机工程,2006 年12 月,第32 卷第24 期.邵立松.互联网端到端拥塞控制算法研究.万方数据库博士学位论文,2006年.袁萍.基于主动队列管理的网络拥塞控制若干问题研究.万方数据库硕士学位论文,2008年.张璐.网络拥塞控制中主动队列管理算法的研究.万方数据库硕士学位论文,2008年.2009-11-1827