周鑫——主动队列管理(AQM)分析.pptVIP

主动队列管理(Active Queue management) 周鑫 历史背景 1986 年10 月，由于拥塞崩溃的发生，美国Lawrence Berkeley Laboratory 到UC Berkeley 的数据吞吐量从32Kbps 跌落到40bps。 研究者从此认识到了拥塞控制机制对保证互联网的稳定性具有十分重要的作用。因此，在网络拥塞控制领域内开展了大量的研究工作，使拥塞控制成为计算机网络研究领域的热点问题。 TCP/IP下的拥塞控制 TCP /IP协议是目前互联网中使用最广泛的传输协议。根据MCI 的统计，总字节数的95%和总分组数的90%使用TCP 协议传输。围绕着TCP /IP协议的拥塞控制一直都是互联网的研究热点。 TCP源端拥塞控制 IP链路拥塞控制 TCP/IP下的拥塞控制 被动队列管理的缺陷 算法： ①弃尾队列管理算法（DT） ②随机丢弃管理算法（RD） ③从前丢弃管理算法（DF） 缺陷： 1.死锁问题：同步定时，数据独占队列 2.满队列问题：队列充满，延时 3.全局同步问题：TCP流自适应特性 发展趋势 随着网络规模的急剧膨胀新出现的网络应用对服务质量的要求越来越高在路由器中采用AQM 机制显得尤其重要 1998 年IETF 建议在路由器中采用AQM 机制在国际上掀起了研究AQM 机制的高潮 至2005 年8 月止以AQM 为关键词，在IEEE 的数据库中可以检索到文章124 篇，Web of Science 数据库(SCI,SSCI,AHCI)中可以检索到文章624 篇，在EI 数据库中可以检索到文章492 篇主动队列管理成为网络研究的热点之一 主动队列管理 AQM 机制的主要思想： 网络节点在缓冲区没有溢出之前，根据网络的拥塞状况，以一定的概率丢弃报文或者通知拥塞，端节点调整速率缓解拥塞 AQM 机制的主要性能指标，包括链路利用率、报文丢弃率以及平均队列长度等 显示拥塞指示（ECN） 拥塞反馈信号的形式，主要包括丢弃分组和标记分组 RFC3168 提出ECN (Explicit Congestion Notification)规范，主要工作原理是：在连接建立阶段，TCP发送端、接收端和路由器声明支持ECN；当网络发生拥塞时，路由器设置TCP 分组头部的拥塞标记位；接收端检测到拥塞标记位后，设置确认分组的相应位；发送端根据拥塞标记位判断网络拥塞，并增减拥塞窗口 主动队列管理算法分类 发现拥塞之后处理方法的不同可以将主动队列算法分为两类： (1)通过对数据包打标记(比如说ECN，通过这种方法实现的主动队列算法主要有BlUE以及针对BlUE的改进算法SFB (2)通过丢弃数据包，通过这种方法实现的主动队列算法比较多，主要有RED，FRED，CHOKe，CSFQ，PFED等 随机早期检测(RED)算法 随机早期检测(RED)算法是最著名的AQM算法之一，它由AQM创始研究人员Floyd教授提出，并且是IETF推荐的标准AQM算法。RED是一种早期丢弃技术，即在网络发生拥塞的早期就丢弃部分分组数据，改善队列的动态特性，提高网络的利用率。 与弃尾算法相比，RED为队列管理增添了两种新机制：(1)分组丢弃不是等到队列缓存溢出时发生，而是根据队列长度利用概率判定机制预先丢弃部分分组来预防可能发生的拥塞；(2)判定分组丢失概率依据的队列长度是平均队列长度，而不是即时队列长度，这在一定程度上可以吸收部分短暂的突发流量。 随机早期检测(RED)算法 平均队列长度： RED队列管理策略根据分组到达或固定的时间间隔，先采用指数加权滑动平均计算 Avg=(1-Wq) ×Avg+Wq×q 其中， Avg表示平均队列长度，q表示瞬时队列长度，Wq是一个加权系数，同时也是一个时间常数 随机早期检测(RED)算法 丢弃/标记概率： 采用平均队列长度Avg 作为拥塞测度，并设定两个控制阈值minth 和maxth，maxp 是预先设置的分组丢弃概率，Pb 为当前分组丢弃概率的计算值 随机早期检测(RED)算法 若Avg小于minth ，则没有包需要丢弃；当minth Avg maxth时，计算出概率Pb ，并以此概率丢包；当Avg maxth时，所有的包都被丢弃 。 随机早期检测(RED)算法 RED算法采用简单的控制机制，很容易实现，因此也得到了业界的广泛认可和支持； 但是RED算法还存在许多问题： ①参数设计和网络状况对RED算法的性能有很大的影响，在特定网络负载状态下依然会导致队列震荡、吞吐量降低和延迟抖动加剧； ②RED算法还存在公平性和稳定性问题。 针对RED 算法的缺陷，已经提出许多相关的改进方案（WR