一种分段平滑的随机早期检测队列管理的创新策

　0引言
　　如今，在迅速发展的网络系统中，网络拥塞的情况已经越发严重，对于网络拥塞［1-2］问题的控制也愈显迫切。其中，TCP/IP［3-4］ 协议下的拥塞控制机制是大多数研究者的主要研究对象。虽然TCP/IP 协议下的拥塞控制机制研究已取得了一定的成果，但是在公平性、灵活性和端节点负担等方面仍存在一些问题。某些研究人员关于 TCP 端到端拥塞控制部分在进行了众多的尝试与努力后却发现，现存问题仍然并未获得很好的解决［5-6］，于是开始转变研究方向，由对发送端拥塞控制的研究转向对网络中间节点拥塞控制的研究，以此来对网络拥塞实现更好的避免与控制。并且中间节点是最早了解网络负载情况的，所以能够根据网络负载情况在第一时间进行链路资源调节，从而可以达到对拥塞做出实时反应的目的。研究中，路由缓存队列管理机制就是中间节点控制拥塞的重要组成部分，可将其大致分为被动队列管理(PQM)以及主动队列管理(AQM)［7-8］两种方式。
　　被动队列管理并没有对网络负载情况进行预测并采取措施，而是在缓冲溢出时才会丢弃或标记数据包。所以说，这是一种被动的队列管理方式。但是，随着缓冲区的溢出就会造成发送端全局同步、死锁以及缓冲区队列长度振荡较大等问题，继而就有学者提出了主动队列管理的思想。
　　1993 年，Floyd 等人［9］提出了一种主动队列管理机制——随机早期检测（RED）算法。这是一种对缓冲区队列长度先进行预测，同时根据预测值的大小采取相应措施的方法。只是，随机早期检测（RED）算法中需要设置的参数较多，并且参数设置的变化在很大程度上会影响算法性能，同时不同网络负载对算法性能影响也会较大。为了克服以上问题，本文提出一种新的改进思路——分段平滑的随机早期检测队列管理算法（RED-P）。
　　1RED算法
　　RED（Random Early Detection）的基本思想是对下一时刻的队列长度进行预测，再以此预测值为基础计算丢包概率，并根据计算得到的丢包概率值对数据包进行预先丢弃，以避免拥塞的发生。其中关键就是如何按照预测值计算丢包概率。在 RED算法中，引入了两个重要的参数，minth和maxth，分别表示队列门限的最大值与最小值，可用于拥塞检测。具体计算过程阐述如下：
　　当一个数据分组进入路由时，主要按如下两个步骤来执行算法。
　　第一步计算平均队列长度:
　　当前队列为空时：
　　m=f(t)（1）
　　avgn=(1-wq)mavgn-1（2）
　　当前队列不为空时：
　　avgn = (1-wq )avgn-1 + wq（3）
　　其中，t表示队列空闲时间，f表示关于空闲时间t的线性函数，avgn表示本次将要计算的平均队列长度，avgn-1则表示前一次计算队列的平均队列长度，而wq表示当前队列权重。
　　第二步 依据所得到的平均队列长度avgn的值计算丢包概率。
　　当avgn ≥maxth时，pb=1,即到达的所有数据包将会全部丢弃;当avgn ＜minth时，接收所有到达的数据包;当minth ≤avgn ＜maxth时，先计算概率，再以此概率来决策丢包行动。具体公式为：
　　Pb=maxp×avgn-minthmaxth-minth（4）
　　Pa=Pb1-count×Pb（5）
　　其中，maxth表示平均队列长度上阈值，minth表示平均队列长度下阈值，pb表示过渡概率值。平均队列长度avgn在区间（minth，maxth）不断增大时，pb呈线性增加，从0增加到maxp，如图1 所示。maxp表示预先设定好的最大概率值，pa表示最终丢弃概率，Count则表示上次丢弃分组后到当前所接受分组数。
　　在计算最终丢包概率时，加入一个count值，也就是上次丢包后收到的数据包个数。这样做是为了使得丢包的间隔时间能够均匀一些，不会因为连续丢包而导致对某一个突发数据流的丢包数量就将偏大现象的发生。第3期赵宇红，等：一种分段平滑的随机早期检测队列管理算法智能计算机与应用第4卷
　　图1丢包概率计算原理图
　　Fig.1The principle diagram of the packet loss
　　probability calculationRED算法的缺陷之一就是丢包概率在不同的网络负载程度中变化过快，也就是对网络负载程度的变化较为敏感。如果网络负载较轻或maxp较大时，avgn接近minth; 如果拥塞比较严重或maxp 较小，则avgn接近maxth，尤其avgn超过maxth时，丢包概率将直接突变为1，过于陡峭。同时也可以看到，RED算法对参数的设置也比较敏感，例如上面所说的maxp等。参数设置为不同数值时，算法性能就会产生重大变化。上述这两个问题也是造成avgn抖动剧烈的主要原因，由此也将导致算法性能的不稳定。avgn作为实际队列长度的预测量，对实际队列长度也具有很好的指示作用，为此可将avgn的变化程度作为算法性能目标来对算法性能展开判断。相应地，降低avgn的抖动幅度就具有十分重要的意义和价值。
　　2RED-P算法
　　2.1问题分析
　　为了改善RED 算法中的以上两个问题，这里提出针对性的改进思路。具体分析如下。
　　首先，解决对参数maxp设置敏感的问题。maxp是一个大于0、小于1的常数，根据过渡概率值pb的计算公式，即公式（4）可知，maxp可对pb起到一个适度调小的作用，但maxp的设置却引入了一定劣势，如取值。为此，可以通过加大原始比例分母的方法来达到同样调小概率的目的，即将分母的区间长度由maxth-minth增加为Qmax-minth。这样既可以减少算法性能对参数设置的敏感性，同时也避免了RED算法中，当avgn超过maxth时丢包概率突变为1的问题，其实现原理如图1所示，原RED算法中pb的计算公式也由pb=maxp*(a/b),改进为pb=a/c。
　　其次，解决RED算法性能不稳定的问题。在原RED算法中，pb是基于avgn的一个线性函数，若pb的变化较快则会导致avgn也随之发生很快变化，以及高抖动，由此即进入恶性循环，最终则造成算法性能不稳定。此处采用二次函数来完成概率计算，见公式（6）：
　　Pb=avgn-minthQmax-minth2,avgn∈(minth,Qmax)（6）
　　即pb=（a/c）2可以缓解这一问题。
　　二次函数较线性函数来说具有天然的非线性特性，在关键参数已知的情况下，可以使得二次函数的变化率始终大于线性函数的变化率，这就决定了利用二次函数计算得到的结果更小，丢包概率也将更为平滑，并减小了队列的抖动，因而采用二次函数既可以满足所需求的丢包概率，也可以减缓丢包概率变化速度，并减小平均 队列长度avgn的抖动，进一步增强了算法的稳定性。同时，也能够减小端到端的延时，这一点即可从下文的仿真结果中得到明确的验证。
　　公式（6）下的算法命名为RED-T，其中Qmax为队列物理缓冲的最大长度。该算法不需如RED一样分别设置maxp和maxth，而是只需设置Qmax，因此RED-T比RED的设置参数要更少，即适度减小了算法性能对参数设置的敏感性。仿真验证，算法取得了良好的效果。
　　但是，在仿真分析的过程中，发现该算法仍然存在一定缺陷，即当网络负载较高时，二次函数的计算会将丢包概率调小，从而无法在高负载时对拥塞实施有力控制。为应对这一状况，对算法实行了进一步的改进，通过控制不丢包概率来控制丢包概率。
　　2.2RED-P算法描述
　　采用不丢包的概率只需将分子区间由avgn-minth改为Qmax-avgn即可，如图1中不丢包概率为1-a/c=d/c，同理仍然对保留概率进行平方计算，而后用1减去保留概率的平方即可，如公式（7）：
　　Pb=1-Qmax-avgnQmax-minth2,avg∈(minth,Qmax)（7）
　　即pb=1-（d/c）2。
　　这样的话就将保留概率适当调小，并适度地放大了丢包概率，在满足概率变化平滑性的同时，也部分放大了概率值，当网络负载较为严重时，丢包概率也不会过小，由此可以对拥塞进行有效控制。公式（7）下的算法命名为RED-S（RED-Smooth）。
　　RED-S算法pb计算概率则如公式（7）所示。
　　但是，这个方案同样存在类似的问题，对丢包概率的适度放大并没有分段，当负载不严重时，概率也将适当放大，这样就有可能会使得低负载时的丢包数量增多，并降低吞吐量。所以这里在区间（minth，Qmax）范围内找到中点P，将区间（minth，Qmax）分隔为相等的两个区间（minth，P）以及（P，Qmax）。当avgn位于区间（minth，P）时，采用公式（6）对过渡概率进行计算。当avgn位于区间（P，Qmax）时，采用公式（7）对过渡概率进行计算。综合公式如公式（8）所示。
　　pbpb=avgn-minthQmax-minth2,avgn∈(minth,P)
　　pb=1-Qmax-avgnQmax-minth2,avg∈(P,Qmax)(8)
　　这样的话就既可以保证网络负载较高时算法对拥塞的控制力度，同时也可以在网络负载较低时保证相应的吞吐量，避免过度丢包。这就是本文提出的算法RED-P(RED-Paragraphing)。
　　RED-P通过扩大概率计算比例的分母区间省略了maxp的参数设置，也减小了算法的参数敏感性。同时，利用二次函数特性来增加丢包概率变化的平滑性，由此而减小avgn的抖动率。再通过反面控制来保证需求的丢包概率大小,并且在不同区间采用了不同公式计算丢包概率，这就在增加拥塞控制力度的同时，进一步保证了吞吐量。当平均队列长度在［minth，Qmax］变化时，pb概率将在［0，1］之间平滑过渡。
　　3RED-P算法的仿真和结果分析
　　在NS2下构建如图2 所示的仿真网络拓扑。由图2可见，源端S1～Sn均为TCP 发送端，分别向终端D1～Dn一一对应发送数据，即Si发送数据，而由Di接收。S1～Sn均为持续性FTP源，到R0的链路速率为10Mbps，延时2 ms。R0-R1为瓶颈链路，链路速率为1.5 Mbps ，延时20 ms。R1到D1~Dn链路速率为10 Mbps，延时2ms。n为120。R0-R1节点缓存队列长度均为300 packets，数据包大小为1 000 packets，接收窗口设置足够大，使得TCP的发送仅受拥塞窗口的控制。
　　图2 仿真网络拓扑结构
　　Fig.2The simulation network topology3.1仿真实验的描述
　　图2中t=1秒时，开始启动30个TCP发送端，30秒启动90个TCP发送端，60秒后停止90个TCP的发送端，100秒停止120个发送端，仿真结束。瓶颈链路队列管理分别采用RED，RED-T，RED-S以及RED-P。RED 的参数设置maxth =150packets，minth=15 packets，其余参数为NS2［10］默认。RED-T，RED-S以及RED-P的参数设置:minth = 15 packets，Qmax= 250packets。仿真结果分别对端到端的延时、队列的平均长度、还有吞吐量进行了比较，详细仿真结果分别如图3 ～5所示。
　　3.2仿真实验的分析
　　图3中，delay1、delay2 、delay3以及delay4为使用原RED算法、算法RED-T、算法RED-S以及RED-P下得到的延时。从仿真结果来看，RED-P算法在端到端的延时方面性能最优。
　　图3 端到端延时的对比
　　Fig.3The contrast of end-to-end delay 图4中，AVG1、 AVG2、 AVG3、 AVG4分别为原RED算法、RED-T、RED-S以及RED-P算法所得到的平均队列的长度。由图4可以看出RED算法得到的AVG波动曲线其波动范围大大超过了RED-T、 RED-S以及RED-P的波动范围，且由RED-P算法得到的平均队列长度的波动最小，且抖动率最低。
　　图4 平均队列长度的对比
　　Fig.4The contrast of avgn图5中，Th1、Th2 、Th3以及Th4分别为使用原RED算法、RED-T算法、RED-S算法以及RED-P算法得到的吞吐量。仿真显示，三种算法得到的吞吐量是比较接近的。
　　图5 吞吐量的对比
　　Fig.5The contrast of throughput仿真表明，本文提出的RED-P算法能有效改进RED的参数敏感性以及网络负载敏感性的问题，简化了参数设置，在瓶颈段端到端的延时更小，同时更减小了平均队列的波动范围与抖动幅度，并且能维持几乎接近的吞吐量。
　　4结束语
　　为了改进RED算法中平均队列长度对网络负载程度以及参数设置较为敏感的问题，提出了一种改进的算法RED-P。RED-P采用分段正反面控制并且将二次函数融入丢包概率的计算，适当地减少了参数的数量，并有效改进了算法的性能。最后通过NS2仿真实验进行了验证，得到了较为理想的仿真效果，使得平均队列长度的抖动幅度得到了有效控制，同时也减小了算法在瓶颈段端到端的延时，而且能保持接近或者相等的吞吐量，进而提高了服务质量。
　　参考文献：
　　［1］徐昌彪,鲜永菊.计算机网络中的拥塞控制与流量控制 ［M］.北京:人民邮电出版社,2007.
　　［2］冯峰.互联网络拥塞控制分析与研究［J］.计算机工程与科学,2008,30(6):37-39.
　　［3］刘俊,童学红.TCP 拥塞控制算法［J］.计算机工程与设计, 2011,32(7):2309-2313.
　　［4］魏佳杰,郭晓金.TCP 拥塞控制技术研究［J］.现代电子技术, 2009,32(15):2-4.
　　［5］FUKATUS T, KIURA T, HIRAFUJI M. A web-based sensor system with distributed data processing approach via web applicat ion［J］.Computer Standards &Interface,2011,33(6): 565-573.
　　［6］暴建民.物联网技术与应用导论［M］.北京:人民邮电出版社,2011.
　　［7］吴俊新,赵旭,张宇献,等.主动管理队列算法的研究［J］.控制工程,2008,15(2):178-181.
　　［8］SABATO M, MARIO B, FRANCO G. Design validation and experim- ental testing of a robust AQMcontrol ［J］. Control Engineering Practice， 2009, 19(3): 1-6．