基于模糊控制理论主动队列管理算法的研究

I摘要Abstract吉林大学硕士学位论文2第2章背景知识3第2章背景知识2.1主动队列管理的介绍自1988年以来，研究人员做了大量的关于网络性能的研究，而且得到了如下的结论：尽管TCP拥塞控制机制是必须的，但不是在所有的网络环境下都能够提供良好的服务质量。因此，在路由器中添加某些机制是必要的，这样才能较好地避免拥塞或者从严重的拥塞中恢复出来。主动队列管理(AQM)是由IETF提出的，其目的就是为了弥补端到端拥塞控制机制存在的缺陷。AQM算法解决的问题主要包括以下几个方面[34]：(1)在延迟和吞吐量之间保持简单的权衡，保持队列处于未满的状态是十分必要的。(2)可以吸收突发流，对于持续流和间隙流进行公平的处理。(3)在队列满之前对新到达的数据包进行随机丢弃，或者在队列满的时候对缓存区的数据包随机丢弃，从而避免拥塞的发生。(4)避免多个TCP连接由于队列溢出而造成的“慢启动”状态。总之，主动队列管理算法机制对于响应流可以提供如下的优点[35]：(1)减少路由器中丢弃数据包的数量。突发数据流是一个分组网络中不可避免的方面。当路由器中所有的队列空间处于“稳态”或者路由器的空间不足时，路由器将没有缓存突发流的能力。通过保持小的平均队列长度，主动队列管理不需要丢弃数据包就具有很强的吸收突发流的能力。如果没有主动队列管理，在队列溢出时很多数据包将会被丢弃。这一点是我们所不希望的，原因有几点：首先，伴随着共有队列和弃尾规则，不必要的全局同步现象可能导致低的平均链路利用率，从而降低网络吞吐量。其次，与单纯的丢弃数据包相比，TCP从丢弃突发数据包的状态恢复过来是很困难的。最后，不必要的丢包代表着带宽的浪费。(2)提供低延迟的交互式服务。通过保持队列长度在一个较小值附近，队列管理将会减少数据流的延迟，这对于交互式应用(例如，短距离Web传输，Telnet流，交互式音频会议等)是极其重要的。(3)避免死锁行为。通过保证将要到达的数据包总是有一个可利用的缓存区，主动队列管理可以防止死锁的发生。同样，它还可以阻止路由器对于低带宽高突发数据流的偏袒。明显地，死锁是不希望出现的状况，因为这种情况对于多组数据流是不公平的。吉林大学硕士学位论文42.2中间节点路由器中的AQM算法2.2.1RED算法随机早期检测(RandomEarlyDetection，RED)[12]是路由器中的一种AQM算法，它提供了网络性能的很多优点。与传统的当路由缓存区满之后才丢包的队列算法相比，RED算法以一定的概率对将要到达的数据包进行丢弃。丢弃概率随着估算的平均队列大小的增长而增加。RED响应于平均队列长度，而不是瞬时队列长度。因此，如果队列几乎处于空闲状态，RED算法将不会丢包。另一方面，如果队列已经处于相当满的状态，并指示了拥塞，那么将要到来的数据包将以更大的概率被丢弃。RED算法自身包括两个主要的部分：估计平均队列长度的大小和决策将要到达的数据包是否被丢弃。(1)估计平均队列的大小。RED在转发路径中使用了一种简单的指数加权滑动平均的方法来计算平均队列长度aveQeqqeQWqWQavav1……………………(2.1)其中，qW为目前队列长度的权值，01qW，q是当前队列长度。由于网络流量是突发的或者短时拥塞，实际队列大小可能会瞬时增加，如果qW太小，那么aveQ对于实际队列长度大小变化的响应会太慢；如果qW太大，将不会滤除网关的暂态拥塞。(2)计算丢弃概率。这是算法的第二部分，RED决定是否要丢弃将要到达的数据包，从而有效地控制平均队列队列长度。RED有两个参数thmin(最小阈值)和thmax(最大阈值)。当平均队列大小低于thmin时，没有数据包丢失；当平均队列长度高于thmax时，丢弃所有的数据包；当平均队列大小介于两者之间时，数据包将以概率P进行丢弃，如下式所示。()/()maxavethththPPQminmaxmin………………(2.2a)/(1)maxmaxPPcountP…………………(2.2b)其中，maxP为最大丢弃概率，count为从上次丢包开始进入队列的数据包个数。RED算法有效地控制了队列长度，同时吸收突发数据包而不是对数据包进行丢弃，而且RED算法的随机性打破了导致死锁的全局同步现象。2.2.2ARED算法ARED算法[13]是针对RED参数敏感的问题而设计的，一般ARED的设计可以总结为基于链路速率自动地设置qW的值并根据测量的队列长度自适应的调节maxP，从而将平均队列长度维持在thmin和thmax之间。如果平均队列长度低于thmin，则证明拥塞控制比较激进，需要计算一个保守的maxP；如果平均队列长度高于thmax,则说明拥塞控制的比较保守，需要计算一个较激进的maxP。第2章背景知识5ARED是对RED稍做改动的一种算法，它的鲁棒性源于它慢且频繁地对maxP进行调节，为了确保ARED的性能在过渡期不会急剧下降，严格的将maxP限制在[0.01，0.5]之间。这确保了过渡期RED的整体性能被接受，即使平均队列长度可能不在一个目标范围内，平均延时和吞吐量也只会有轻微的波动。2.2.3SRED算法与RED不同的是，SRED算法[14]没有计算平均队列长度的机制。SRED可以分为SimpleSRED和FullSRED。SimpleSRED丢弃概率仅仅依赖于瞬时缓存占有和活跃流的估计数量，FullSRED丢包率计算依赖于数据包是否引起一个“hit”。其中hit是用来估计活跃流数量的。在SimpleSRED中，通过估计活跃流数量然后用于设置丢弃概率。基于非恶意流可以激发更多的hits的思想，也可以直接用“hit”来设置丢弃概率。因为与其它流相比，非恶意流有较多的数据包到达，而且，它们更可能出现在僵尸列表中。在FullSRED中，可以增加恶意流的丢弃概率，从而减小了TCP对短RTT流的偏袒。RED的队列长度波动较大，而SRED克服了RED的这个缺点，减小了延迟时间。SRED能够提够估计活跃数据流的数量，从而辨别非恶意流。通过统计活跃流的数量来调节丢弃概率从而使缓存占有情况得到很好的控制。2.2.4BLUE算法RED、ARED等算法都是以队列长度作为严重拥塞的指标，而BULE算法[19]是用丢包率和链路空闲事件来管理拥塞的。BLUE保持稳定的丢弃概率，当数据包入队时此概率被用来标记数据包。如果由于队列溢出而持续地丢包，BLUE将增大标记概率，这样将增大发回拥塞通知的速度。相反地，如果队列处于空闲状态，BLUE将减小标记概率。这有效地允许BLUE去“学习”它需要发回拥塞通知的正确率。当队列长度超过某一特定值时，BLUE将更新丢弃概率。这将在队列中为暂态突发流保留空间，并且，当队列被使用的值较大时允许队列控制排队时延。除了标记概率之外，BLUE使用三个其他的参数来控制标记概率的改变速度。一个参数是freeze_time，该参数决定了标记概率连续更新的最小时间间隔。freeze_time允许标记概率在再次更新前有效地发挥作用。其他两个参数1d和2d被用于决定队列溢出时标记概率的增加量和队列空闲时标记概率的减少量。通常1d要比2d大的多，因为当拥塞管理太激进或太保守时链路利用率会很低。通过权衡丢弃概率，BLUE可以快速地对网路负载的大量增加做出反应。BLUE最大的贡献在于用较小的缓存区完成了拥塞控制，从而减小了排队时延，提高了吞吐量。此外，较小的缓存区使得路由的其余空间用来执行其它的功能，如存强大的路由表，从而使路由器的整体性能得到提高。而RED则需要较大的缓存区才能吉林大学硕士学位论文6达到同样的效果。2.2.5PI算法文献[36]中，V.Misra等人基于流体流建立了AQM作用下的动态模型，得到的非线性化微分方程如下式所示pTCtqtRtCtWtRtNtqtRtptRtRtWtWtRtW21……………(2.3)上式中各个参数的含义分别是W：TCP窗口的大小(单位：包)；W：W的一阶微分；Tp：链路的传输迟延(单位：秒)；C：链路容量(单位：包/秒)；0q：队列长度的期望值；N：TCP连接个数；q：瞬时队列长度；R：往返时间(RTT)，)/q(2pTCR，Tp是固定的广播时延；p：丢弃概率。通过线性化处理和拉普拉斯变换得到传输函数，图2.1所示为该模型基础上得到的AQM系统模型。TCP/AQM动态模型+++PIq0qq0ppp图2.1TCP/AQM控制系统(PI)基于该AQM/TCP非线性动态模型，C.Hollot经过线性化处理，提出了PI第2章背景知识7(ProportionalIntegral)算法，这是一个非常有价值的工作，因为它的主要贡献是将AQM系统的算法转化成在控制理论中控制器的设计。从控制理论的角度来讲，AQM可以看作为一种经典的调节算法，该算法的目标是使队列长度始终保持在期望值q附近，参考的队列长度0q是用户可设定的。与RED算法相比，PI控制器能够使队列长度更稳定，具有更小的队列抖动。然而，PI控制器有一个致命的缺点，即调节时间过长，而且过度的依赖于缓存队列大小。另外，调节控制器参数的方法也是不确定的，这对于控制器的设计是非常重要的。所以研究人员对PI控制器引入了微分环节提出了PID控制器，并且用理论方法对控制器的参数进行调节。2.2.6PID算法从经典的控制理论中可以知道：在设计控制器的时候，能快速地将动态系统调节到期望的稳态是非常有帮助的。最简单的方法就是观察状态变量的变化，然后把它综合到控制器中，这也是PI和PID控制器最重要区别。微分环节可以大大地缩短暂态过程，因此，PID控制器可以克服PI控制器调节时间长的缺点[37]。图2.2描述的是PID控制系统的原理框图。图2.2PID控制器系统原理框图其中，pK、iK、dK分别是PID控制器的比例、积分、微分系数。实际应用中，采样队列系统需要控制器的离散形式，用一系列的采样时间kT代替连续时间t，用和与差分别代替积分与微分。则PID控制器的离散表达式可以表示如下001(1)kpidjkdpjiekekpkKekKejKTTTKekejekekTT…………(2.4)其中，piiKTK，ddpKTK，T为采样时间。写成增量的形式为吉林大学硕士学位论文8()()(1)2(1)()[1](1)(2)dddpipkpkpkTTTTKekekekTTTT…………(2.5)PID控制器即使在路由缓存较小的情况下也能加快AQM的响应速度。与PI算法相比，它能在多变的网络环境下很好的控制数据包的延迟时间，这对于保证服务质量具有很大的益处。2.3模糊控制理论处理模糊世界时，通常需要一种工具叫做模糊控制，其主要思想是在控制中引入模糊控制理论，从而作用于难以建立数学模型和缺乏精确模型的复杂系统。模糊控制不依赖于精确的数学模型，而是通过总结知识和积累经验对复杂的系统进行控制，因而对具有不确定性对象的系统具有很强的适应能力。简言之，模糊控制理论就是模仿人的思维方式和经验来实现自动控制的一种控制方法。2.3.1模糊控制理论的产生及应用模糊集的概念是美国加州大学Zadeh教授通过隶属度函数于1965年在他的《FuzzySets》[38]等著名论著中首先提出来的。1973年，他在文章中又引入了“语言变量”的概念，相当于一个变量定义成为模糊集。1985年，Takagi和Sugeno提出了Takagi―Sugeno模糊模型[39]，此模型的主要特点是通过线性系统模型来表达每一个模糊规则的特性。1974年，Mamdani首次将模糊控制应用于锅炉―蒸汽机的控制[40]，实验得到的效果比传统的控制算法要好得多。1985年Yasunobu和Miyamoto提出了模糊系统，并做了仿真，证明了模糊控制系统在仙台铁路中的重要性。他们的