一种DiffServ模型的主动队列管理算法FPRIO

摘要：面向QoS的DiffServ模型，在改进RIO-C算法的基础上，提出了一种新的主动队列管理算法——FPRIO。通过理论分析和仿真实验验证，证明该算法是一种适合于DiffServ模型的主动队列管理算法。

关键词：QoS；主动队列管理算法；DiffServ

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)13-3081-03

An Active Queue Management Algorithm FPRIO of DiffServ Model

SUN Jun-li, LIU Jia-liang, JIANG Li-qun

(School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China)

Abstract: For the DiffServ model of QoS, a new active queue management algorithm - FPRIO based on improving the RIO-C algorithm is presented. Through theoretical analysis and experimental verification, the algorithm is an active queue management algorithm for the DiffServ model.

Key words: QoS; active queue management algorithm; diffServ

随着Internet规模的迅速扩大，以及多媒体技术的蓬勃发展，QoS[1]已经成为下一代互联网正常运行的关键问题。作为QoS的实现模型，DiffServ[2]凭借其简单性和可扩展性的特点，成为目前实现IP QoS的首选方案和研究热点。

本文提出了一种新的AQM（Active Queue Management）算法。该算法旨在解决同一PHB组中，具有不同丢弃优先级的各类数据分组之间由于共享缓冲队列而引发的带宽分配的公平性问题。理论分析和仿真实验验证了该算法的可行性和有效性。

1 主动队列管理算法FPRIO（RIO Based On Fair and Priority）

1.1 算法的设计

1.1.1 参数设置

如果分组有n类不同的丢弃优先级，FPRIO算法相应设置 n 组参数，其中包括最小门限值minthi、最大门限值maxthi和分组平均队长达到最大时的分组丢弃概率pmax i（下标i越大表示丢弃优先级越高）。

参数采用交错设置，即：

pmax1< pmax2 <…pmax i<…pmaxn 条件(1)

maxth1>minth1≥maxth2>minth2≥…maxthi>minthi≥…maxthn>minthn条件(2)

maxth1- minth1> maxth2- minth >…maxthi - minthi >…maxthn - minthn 条件(3)

其中：

条件(1)确保在平均队长达到最大时，低丢弃优先级分组的丢弃概率小于高丢弃优先级分组。

条件(2)确保低丢弃优先级的分组比高丢弃优先级分组较晚进入概率丢弃阶段。

条件(3)确保低丢弃优先级的分组处于概率丢弃的阶段长于高丢弃优先级分组。

1.1.2 平均队长的计算

平均队长直接影响到分组的丢弃概率。在FPRIO算法中，考虑到既要反映当前队列中各优先级分组的数目，又要考虑低丢弃优先级分组对高丢弃优先级分组的影响，本算法中第i类分组的平均队长采用如下公式计算：

（4）

对于有三个优先级的情况：

对于公式（4）的说明：avg为整个队列的平均队长，计算方法采用指数加权滑动平均算法。q为缓冲区总的队列长度，qi为第i类分组的队列长度。λj是一个权值参数。

1.1.3 分组的丢弃概率的计算

计算公式如下：

（5）

当minthi≤avgi≤maxthi时，丢弃概率不直接采用pbi,而是用pai来标记。其计算公式如下：

（6）

其中counti表示第i类分组从上一次丢弃开始到现在进入队列的分组个数。

1.1.4 算法描述

以下是对FPRIO算法进行描述(分组丢弃优先级的数目n=3)：

For each packet arrival

Calculate the new average queue size

Get the number of the packet

If (number=1)

avgi=q1/q*avg；

If (minth1<=avg1<=maxth1)

Calculate dropping probability P1 of the packet, and drop the packet with probability P1

else if (avg1>maxth1) Drop the arriving packet

if (number =2)

avg2=(q2+q1*λ)/q*avg;

if (minth2<=avg2<=maxth2)

Calculate dropping probability P2 of the packet, and drop the packet with probability P2

else if (avg2>maxth2) Drop the arriving packet

if (number =3)

avg3=(q3+q2*λ+q1*λ1)/q*avg;

if (minth3<=avg3<=maxth3)

Calculate dropping probability P3 of the packet, and drop the packet with probability P3

Else if (avg3>maxth3) Drop the arriving packet

2 FPRIO算法的仿真实验

为了验证算法的有效性，在网络仿真软件NS2[6-7]上实现了FPRIO算法，并将算法与RIO-C算法进行了比较。

2.1 实验环境的设置

本文选用的实验环境是NS2，NS是一个离散事件模拟器。在NS2中已经提供了许多支持区分服务的模块，通过调用这些模块，可以实现区分服务的一系列控制策略，以此来提供QoS保证。用户可以组合组建出自己想要模拟的网络系统模型。本文便是将自己编写的FPRIO模块编译到NS2中。

2.2 使用NS进行网络模拟的一般过程

通过NS解释程序调用仿真器，NS解释程序是otclsh[8]命令shell的扩展。一个方针是用一个otcl脚本程序定义的。脚本程序使用Simulator类作为与NS的接口。通过此类定义的方法，可以定义网络的拓扑结构，还可以通过simulator类中的函数运行仿真程序，并收集所需数据。

NS仿真器常用的命令和语法较多，下面对与本文紧密相关的部分做简要介绍：

1) 产生事件调度器

set ns [new simulator]

调度事件

$ns at

开始调度

$ns run

2) 跟踪

跟踪所有连路上的分组

$ns trace-all[open test.ot w]

以nam-1格式跟踪所有连路上的分组

$ns trace-all[open test.name w]

跟踪特定链路上的分组

$ns trace-queue $n0 $n1

$ns nam-trace $n0 $n1

3) 插入错误检测模块

生成错误模块

$ns loss-module[new ErrorModule]

$loss-module set rate_0.01

$loss-module unit pkt

$loss-module ranvar[new RandownVariable/uniform]

$loss-module drop_target[new Agent/NULL]

插入错误模块

$ns lossmodule $loss-module $n0 $n1

2.3 仿真的网络示意图和参数设置

1) 网络示意图如图1所示。

其中S0，S1，S2为源端，S0，S1，S2发出的数据分组分别被标记为绿色(G)，黄色(Y)和红色(R)。D0,D1和D2为相应的接收端。E1和E2分别为边缘路由器，C为核心路由器。其中，10Mbps和5Mbps代表带宽，5ms代表延迟，这样在C和E2之间就形成一个瓶颈链路。在核心路由器C处监视分组丢弃情况，仿真时间为1分钟。

2) 参数设置。

如表1所示。

2.4 仿真实验的结果

从S0，S1，S2均发送分组长度为1000bytes,速率为2.5Mbps的UDP流。分别对RIO-C算法和FPRIO算法进行了仿真。结果如表2，表3所示。

从仿真结果可以看出，当采用RIO-C算法时，绿色分组没有丢失，黄色分组有极少的丢失，而红色分组几乎全部丢失。当采用FPRIO算法时，绿色分组虽然有丢失现象，但是分组丢失率极小，黄色分组的丢失率相对来说有所增加，但红色分组丢失率明显的减少。实现了DiffServ模型中体现各类分组相对优先级的要求。

3 结束语

本文提出了一种新的主动式队列管理算法——FPRIO算法。该算法使带宽能够按照优先级在各类分组之间公平分配，避免了因长期“饥饿”状态而导致分组的大量丢失。理论分析和实验验证均证明该算法在体现了各类分组之间优先级的同时又极大的提高了带宽分配的公平性和合理性，增强了系统对突发数据的处理能力，使系统更富于“弹性”，提高了DiffServ模型的总体性能。

参考文献：

[1] 林闯,单志广.计算网络的服务质量[M].北京:清华大学出版社,2004:50-133

[2] 曲延光,刘云超.Internet 主动队列管理算法研究[J].计算机应用,2003,28(10):36-38.

[3] Shenker S,Partridge C,Guerin R.Specification of Guaranteed Quality of Service[Z].RFC2212,1997.

[4] Floyd S.TCP and explicit congestion notification[J].ACM Computer Communication Review,1994,24(5):10-23.

[5] Clark D,Fang W.Explicit allocation of best－effort packet delivery service[J].IEEE/ACM Trans on Networking,1998,6(4):362-373.

[6] Floyd S.NS network simulator[EB/OL]..cn/qkpdf/dnjl/dnjl201113/dnjl20111341-1.pdf" style="color:red" target="_blank">原版全文 推荐访问： 队列 算法 模型 主动 管理