令牌桶算法比较研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇令牌桶算法比较研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要:令牌桶算法是流量整型的重要方法,该文在对令牌桶算法作了分析的基础上,对IETF的两种令牌桶算法:单速率三色标记算法和双速率三色标记算法进行了研究。对算法的性能进行了比较分析,并用仿真实验对不同算法的输出流与参数值之间的关系作了研究,揭示了不同算法中参数设置的内在关系。

关键词:令牌桶算法;srTCM;trTCM;仿真

中图分类号:TP312文献标识码:A文章编号:1009-3044(2010)04-0861-02

A Comparative Study of Token Bucket Algorithms

JIANG Wei-cheng

(The Engineering & technical College of Chengdu University of Technology, leshan 614000, China)

Abstract: Token bucket algorithm is a import method in traffic shaping. Based on the analysis of token bucket algorithm, Single Rate Three Color Marker and Two Rate Three Color Marker provided by IETF are introduced. This article present a comparative analysis of performance of these algorithms. the simulation is implemented to study the relation on different algorithms between output stream and parameter values. The simulation results are analyzed.

Key words: token bucket algorithm; srTCM; trTCM; simulation

1 令牌桶算法

令牌桶算法[1]是流量整形和速率限制中常用的算法。在令牌桶算法中,有一个用来装令牌的令牌桶,每隔单位时间,产生一个令牌放入桶中,令牌桶装满后,新产生的令牌将被丢弃。分组能否被发送出去是根据令牌桶中令牌数量的多少来决定的,当桶中的令牌数大于分组的长度时就可以发送分组,假设分组的长度为L,每发送一个分组,则令牌桶中的令牌数目将减少L。当令牌桶中的令牌数减少到0时,停止发送数据,此时新到达的分组将在缓冲区中等待或被溢出。

通常,在令牌桶算法中,令牌产生的速率是固定的,令牌桶的容量也是固定的,其参数根据具体的应用环境和需要来设置相应的值。由于令牌产生速率和令牌桶桶深不能改变,缺乏灵活性,因此,出现了对令牌桶算法进行修改的相应算法,有的算法中令牌产生速率根据具体环境的变化而变化,有的算法中令牌桶桶深也可进行改变。

2 单速率三色标记算法

单速率三色标记算法(Single Rate Three Color Marker, srTCM)[2]由两个令牌桶构成。其中一个是C桶,桶深为CBS(即承诺突发尺寸);另一个是E桶,桶深为EBS(即超额突发尺寸),当然EBS>CBS。假设承诺访问速率用CIR来表示,那么在单速率三色标记算法中令牌的添加方式如下:每隔1/CIR个单位时间产生一个令牌,先往C桶中添加令牌, C桶满后再往E桶中添加令牌,若E桶满则新产生的令牌被丢弃。在该算法中对分组的处理也不是简单的允许通过或丢弃,而是采用标记的方式,将分组标记为不同的颜色,标记的方式如下:如果到达的分组长度未超过CBS则把它标记为绿色,如果超过CBS而未超过EBS则把它标记为黄色,若超过EBS则标记为红色。在算法中,先允许标记好的分组流入网络,当网络发生拥塞时,再对分组进行丢弃,先丢弃标记为红色的分组,然后丢弃标记为黄色的分组,最后才是标记为绿色的分组。

3 双速率三色标记算法

双速率三色标记算法(Two Rate Three Color Marker,trTCM)[3]也设置两个令牌桶,其中一个是C桶,桶深为CBS(即承诺突发尺寸),令牌产生的速率为CIR(即承诺访问速率);另一个是P桶,桶深为PBS(即峰值突发尺寸),令牌产生的速率为PIR(即峰值信息速率)。令牌的添加方式如下:以不同的速率往两个桶中添加令牌,往C桶添加令牌的速率为CIR,若C桶满则新产生的令牌被丢弃;往P桶添加令牌的速率为PIR,若P桶满则新产生的令牌被丢弃。

在双速率三色标记算法中,先对分组进行标记,如果到达的分组速率未超过CIR则把它标记为绿色,如果超过CIR而未超过PIR则把它标记为黄色,若超过PIR则标记为红色。算法中先允许标记好的分组流入网络,只是在拥塞发生时,按红、黄、绿的优先顺序对分组进行丢弃,从而达到减少网络流量、限制速率的作用。

4 算法性能分析

在令牌桶算法中,令牌产生的速率越大,则分组获得令牌的机会就越多,那么流向网络的流量也就越大,因此,设置令牌产生速率的大小是控制分组流入网络中流量多少的关键。当令牌产生速率增加时,分组流入网络中的流量将增大,反之,则减小。另外,令牌桶桶深也是一个重要参数,随着令牌桶桶深的增加,令牌桶中积累令牌的数目也将越多,发送分组的持续时间也将增加。在单速率三色标记算法中,存在桶深更深的E桶,在双速率三色标记算法中,存在令牌产生速率更大的PIR,那么流向网络的不同颜色标记的数据流量又将如何呢?下面用OPNET[4]进行仿真,比较令牌桶算法和srTCM算法,令牌桶算法和trTCM算法等输出流与参数之间的关系。

实验1中参数设置如下:令牌桶算法和srTCM算法的令牌产生速率都为70个令牌/时间单位,令牌桶桶深和C桶桶深都为70个令牌,E桶桶深为90个令牌。进行仿真实验,仿真结果如图1和图2所示。

在仿真实验中,令牌桶算法和单速率三色标记算法的令牌产生速率是一样的,并且令牌桶的深度也与单速率三色标记算法中C桶的深度相等。从图1可以看出,令牌桶的输出流与单速率三色标记算法中标记为绿色的数据流相同。分析图2可以得知,单速率三色标记算法中标记为黄色和红色这两部分的总和恰好与令牌桶算法中被丢弃的那部分数据流大小相等。这表明,对于在令牌桶算法中将被丢弃的那部分数据流,单速率三色标记算法根据E桶中令牌数的多少来进一步进行标记,将其标记为红色或黄色。由于单速率三色标记算法中E桶要比C桶大,从图1和图2两图的仿真结果还可进一步得知,单速率三色标记算法中标记为绿色和黄色的数据流的总和大于令牌桶的输出流,这也进一步说明了桶的深度是对输出流有影响的,当桶深增加时,分组获得令牌的机会将增多,输出流也将越大。

实验2中参数设置如下:令牌桶算法中令牌产生速率为70个令牌/时间单位,桶深为115个令牌。在trTCM算法中承诺访问速率为70个令牌/时间单位,峰值信息速率90个令牌/时间单位,tc桶和tp桶桶深都为115个令牌。进行仿真实验,仿真结果如图3和图4所示。

在仿真实验中,令牌桶算法中的令牌产生速率与双速率三色标记算法中承诺访问速率相同,令牌桶桶深也与双速率三色标记算法中的tc桶桶深相等。从图3可以看出,令牌桶的输出流与双速率三色标记算法中标记为绿色的数据流是一样的。分析图4可以得知,双速率三色标记算法中标记为黄色和红色的数据流的总和恰好与令牌桶算法中被丢弃的那部分相等。这说明,对于在令牌桶算法中将被丢弃的那部分数据流,在双速率三色标记算法中,根据是否超过峰值信息速率来进一步进行标记,将其标记为黄色和红色。由于双速率三色标记算法中峰值信息速率要比承诺访问速率大,从图3和图4的仿真结果还可以进一步得知,双速率三色标记算法中标记为绿色和黄色的数据流的总和大于令牌桶的输出流,这也进一步说明令牌产生速率越大,将会导致更大的输出流。

参考文献:

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

[2] Heinanen J,Finland T.A Single Rate Three Color Marker[S].IETF rfc2697,1999.

[3] Heinanen J,Finland T.A Two Rate Three Color Marker[S].IETF rfc2698,1999.

[4] 陈敏.OPNET网络仿真[M].北京:清华大学出版社,2002.

注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文