带有进出优先级的RED改进算法

朱国晖

(西安邮电学院通信工程系, 陕西 西安 710061)

0 前 言

缓冲管理是对网络传输节点中队列缓冲资源的管理.在分组传输过程中，其流经的网络传输节点通常采用队列缓存、延迟转发的服务方式提高输出链路的带宽利用率.缓冲管理机制在分组到达队列前端时依据一定的策略和信息决定是否允许该分组进入缓冲队列.从另一个角度看，也就是做出是否丢弃带分组的决策，因此也成为丢弃控制.缓冲管理在网络传输控制中发挥着相当大的作用，是网络服务质量(QoS)控制的核心技术之一，也是实现网络拥塞控制的重要手段.

1 缓冲管理

1.1 缓冲管理的意义

就单个网络传输节点而言，其控制目标在于解决输出链路的带宽资源分配问题，把有限的资源公平而有效的分配给不同的服务类别(或用户流等).而在众多网络传输节点构成传输网的基础上，网络传输控制需要整合、规划所有的网络带宽资源的使用，为用户提供端到端的有服务质量保障的网络传输服务，这也就是QoS控制的目标.

带宽资源的分配在网络传输节点上主要是通过基于多个队列的分组调度来实现.虽然缓冲管理机制直接涉及到的是节点中的队列缓冲资源，直接影响到的也只是分组丢失率性能，然而其对系统带宽分配的性能有着不可忽视的影响：合理的系统队列缓冲容量，对于平衡系统吞吐量和分组排队延迟起着至关重要的作用；在多队列情况下，缓冲资源在不同队列之间的分配只有在与输出带宽的分配相互一致时才能获得最佳的缓冲效果.

最早的拥塞控制机制出现在TCP协议中，并采用慢启动和拥塞避免算法来调整自己的数据发送速率，缓解传输网络的压力.随着显示拥塞通告(ENC)和主动队列管理(AQM)的思想的提出，拥塞控制不再只是网络用户的责任，在网络的传输节点中也引入了拥塞控制的机制.如何有效配合网络用户采用的协议，尽量避免拥塞的出现；如何区分出不遵守拥塞控制范围的用户，并限制其不至于影响其它用户和整个网络的有效运行等，都成为网络传输节点中的对列缓冲管理机制需要解决的关键问题.

1.2 缓冲管理的目标

网络传输控制中通常采用的队列结构模型是为了提高输出链路的带宽利用率而设置的.在没有排队的情况下，到达的分组或者被丢弃，或者立刻获得服务，分组排队延迟可以降到最低，然而这是以低系统吞吐量和高分组丢失率为代价的，当大量的分组到达时将因为服务器忙而被丢弃，而在链路空闲时服务器又将因为没有服务对象而闲置，造成系统资源的极大浪费.

队列缓冲的设置使链路的带宽利用率和系统的吞吐量得以改善，然而同时也增大了分组排队的延迟，在对列缓冲空间的容量增大时情况尤为严重.随着网络时事应用的发展，用户对数据的传输延迟的要求越发苛刻，要求网络传输业务能够提供尽可能低的、稳定的传输延迟.而分组在网络中传输遭遇的延迟的最主要部分，也是最容易控制的部分，就来源于网络传输节点的排队延迟.因此，如何设置合适地队列缓存空间容量，如何在网络运行期间合理的控制队列长度的动态变化，以平衡系统吞吐量和分组排队延迟之间的矛盾，是缓冲管理乃至整个网络QoS控制需要解决的重要问题[1].

2 缓冲管理的典型算法

2.1 RED及其衍生算法

(1)RED算法.把拥塞控制引入到网络传输节点的控制机制中，提高网络资源的利用率成为重点关注问题，Floyd和Jacobson正是由此而提出了影响相当广泛的随机早期检测(random early detection，RED)算法[3].RED算法基于平均队列长度预测可能到来的网络拥塞，同时由于RED算法随机标记到达的数据分组，使不同的TCP流的拥塞相应异步化，因而解决了TCP流的全局同步问题.

RED算法存在的问题有：(a)对控制参数过于敏感，难以优化参数设定.算法的性能对控制参数和网络流量负载的变化非常敏感.在用户流增大的情况下，RED算法的性能会急剧下降.(b)不支持服务区分，基于best-effort服务模型，没有考虑不同等级服务之间、不同用户之间的差别，无法提供有效的公平性保障.

(2)自适应RED算法.RED算法通过有效地控制系统的平均队列长度，可以同时获得较高的系统吞吐量性能和较低的分组排队延迟.然而在RED算法中，平均队列长度受网络拥塞程度和控制参数的设置的影响非常大，如果网络负载较轻，或者最大标记概率参数maxp设置的较大，则平均队列长度将会趋于最小阈值minth；而如果网路负载较重或者maxp值设置的较大，则会导致平均队列长度趋于甚至超过最大阈值maxth.这就破坏了平均队列长度的稳定性，进而使得系统派对造成的延迟无法预先估测，同时也降低了系统的有效吞吐量.

出于提高RED算法性能稳定性的考虑，文献[6,7]提出并改进了一种自适应调整控制参数的自适应RED(adaptive-RED)算法.自适应RED算法的思路非常简单.为了控制平均队列长度稳定地保持在最小、最大阈值之间，当网络拥塞程度较大时，相应的增大标记概率maxp，而当网络拥塞程度较小时，则减小标记概率的数值，以达到保持平均队列长度稳定的目的.文献[6]提出的改进算法如公式(1)所示：

每次分组到达到时，

(1)

在此基础上，文献[5]更严格地限定了平均队列长度的允许变化范围和标记概率参数的调整范围，同时把标记概率参数的调整算法由乘法增大乘法减小(MIMD)改为加法增大乘法减小(AIMD).

自适应RED算法把RED算法的控制参数动态化，提高了RED算法的鲁棒性，使之更能适应网络流量的变化，获得更加稳定的性能.然而另外一方面，自适应算法也增加了处理的复杂度，同时引入的调整参数的设置也是在实现中需要考虑的问题.

3 带有进出优先级的RED改进算法

3.1 新算法的描述

在RED算法的基础之上，当多队列需要进入路由器时，对到达的分组在进入队列与离开队列时的次序进行调度，采用优先级的方法对队列进行选择，让最新到达的分组总是进入优先级最高的分组，从而降低分组丢失率.将此算法称为进出优先级的RED改进算法.

3.2 具体实现步骤

算法的具体流程如下：

Set1：假设路由器在其缓冲池中有3个队列q1，q2，q3，在分组到来之前假设：

(1)队列的入优先级分别是p1in，p2in，p3in，并且假设其优先级的高低顺序为p1in

(2)队列的出优先级分别是p1out，p2out，p3out,并且假设其优先级的高低顺序为p1out

(3)3个队列的平均队列长度分别为avg1，avg2，avg3.

Set2：每当分组进入路由器时，平均队列越长则该队列在这一时刻包含分组数目越多，在入队列处的优先级按照公式(2)进行计算，其含义是分组入对列时的优先级与平均队列长度成反比，即平均队列越短其优先级越高，设一常数K

Piin=K/avgii=1, 2, 3，…，n

(2)

当每次有新的分组到达队列时，我们都重新对p1in，p2in，p3in进行排序，再按照排序出来的结果，我们总是把新到来的分组放在优先级最高的队列中，这样就可保证总是把分组放入平均队长最短的队列中.

Set3：对于出队列的优先级可按照公式(3)进行计算，其含义是分组在出队列时的优先级与平均队列长度成正比，即平均队列越长则优先级越高，设一常数F

Piout=Favgii=1, 2, 3，…，n

(3)

每当有分组要出队列时，重新对p1out，pout，p3out进行排序，按照从高优先级到低优先级顺序读出数据，这样我们就可以保证总是让平均队列长度最长的分组优先传送出去.

Set4： 我们假设公式(2)所示的缓冲池为一个先到先服务的队列管理系统，且缓冲池的容量有限，假设其总容量为B，服务的速度设为c，容量B和服务速度c都为固定的常数. 在时刻t，qi表示在时间 (t-1，t)结束时业务源i的队列长度，yi表示在时间(t，t+1)开始时的所到的新分组数，则缓冲池中第i类业务源的队列长度的关系式为：

(4)

那么在每一个队列中，所有的业务源所占据的队列长度应该表示为

(5)

即为分组的瞬时队列长度.

Set5：在RED算法中，现在用分组的瞬时队列长度来表示平均队列长度avg，

当q=0 时avg=(1-wq)×avg

当q≠0时avg=(1-wq)×avg+wq×q

(6)

分组的丢弃概率pb按照下面的式子进行计算：

(7)

Set6：此时再按照自适应RED算法自动调整maxp：

(8)

根据以上的算法，每当平均队列长度avg超过maxth时，则增加maxp;而当平均队列长度avg低于minth时则要减少maxp的大小，这样可以保持平均对列长度在一个合理地范围内不至于有溢出或者空闲，更加合理地利用缓冲空间.

3.3 算法小结

与传统RED算法以及自适应ARED算法的比较： 传统RED算法的丢包概率P不仅和平均对列avg有关，而且还和从上一次丢包开始到现在连续进入队列的包的数量count有关.随着count的增加，下一个包被丢弃的可能性也在缓慢增加.这主要是为了在到来的包之间均匀间隔地丢包，避免连续丢包，以消除对突发流的偏见和产生全局同步现象.

自适应ARED算法提出了一种自动配置机制，根据流量的变化来配置参数maxp.ARED的基本思想就是通过检查平均队长的变化来决定RED是应更激进还是更保守，从而尽量保持平均队长在minth和maxth之间.具体地说，如果平均队长是在minth附近振荡，说明拥塞控制太激进了，那么就减小maxp，maxp=maxp/α；如果在maxth附近振荡，说明拥塞控制太保守了，那么就增大maxp，maxp=maxp*β,其中β>α>1.ARED是对RED改动很小的一种算法，它保留了RED的基本结构，只需调节参数maxp，从而保持平均队长在minth和maxth之间，消除了RED的队列延时问题和参数敏感性问题.

4 结束语

本文提出的带有进出优先级的RED改进算法也是对传统RED算法的一种改进算法，其首先考虑了进出对列的分组对于平均队列长度的影响并且设定了优先级，降低了分组丢失率，能够适应网络的各种负载的变化，并适时调整各参数的变化，减少了在拥塞发生时不必要的丢失数据，优化了网络的进程，提高了系统的利用率，从而提高了整个系统的吞吐量.此算法不仅考虑分组到达时对平均队列长度的影响，还考虑分组的离去对平均队列长度的影响，maxp可以随网络负载的变化而动态的变化，因此该算法能更准确反映网络的拥塞程度.

参考文献

[1] Altintas O. Uregncy-based round robin:a new scheduling discipline for packet switching networks[J]. IEEE Globecom，1997,2(1):1 119-1 183.

[2] Goyal P , Vin H M，Cheng H .Start-time fair queueing:a scheduling algorithm for integrated services packet switched networks[J]. IEEE Trans on Networking,1997,5:690-740.

[3] Parekh A K，Gallager R G. A generalized processor sharing approach to flow in integrated services: the sing-node case[J]. IEEE/ACM Trans Network,1993,1(3):344-357.

[4] Jacobson V. Cngestion avoidance and coutrol[J]. ACM Computer Communications Review,1998,18(4):314-329.

[5] Armitage G, 隆克平等译.IP网路服务质量[M].北京：机械工业出版社，2001.

[6] Zhang H, Ferrari D. Rate-controlled service disciplines[J].Journal of High Speed Networks,1995,3(4): 389-412.

[7] Feng W, Kandlur D, Saha D,etal. A self configuring RED gateway[J]. IEEE INFOCOM,1999,(3):1 320-1 328.

[8] Floyd S, Gummadi R, Shenker S .Adaptive RED: an algorithm for increasing the robustness of RED′s active queue management[Z], 2001.

[9] 王重钢，隆克平.分组交换网络中队列调度算法的研究及展望[J].电子学报，2001,29(4):553-559.

[10] 王宏宇，顾冠群.集成服务网络中的分组调度算法的研究综述[J].计算机学报，1999,22(10):37-42.

[11] Shreedhar M ,Varghese G. Efficient fair queueing using deficit round-robin[J]. EEE Transactions on Networking, 1996,4(3): 375-385.

[12] Ott T J, Lakshman T V, Wong L H. SRED: stabilized RED[J].: IEEE INFOCOM, 1999,(3):1 346-1 355.