基于图形分类的令牌桶流控算法

王 勇,叶明川

基于图形分类的令牌桶流控算法

王 勇1,叶明川2

(1.桂林电子科技大学计算机科学与工程学院,广西桂林 541004; 2.桂林电子科技大学信息与通信学院,广西桂林 541004)

针对接入多维网关的异构网络因信道速率不同而引起的网络拥塞,在GPON技术的DBA算法和流控算法基础上,提出一种基于预测和分级轮询的动态带宽分配算法,并结合基于图形分类的令牌桶算法,通过对不同类型的服务进行动态带宽分配,实现流量控制。实验结果表明,该算法能有效地提高网关的服务质量。

DBA;预测轮询;图形分类;令牌桶

多维嵌入式Web服务网关是为异构网络提供数据转发服务的网关,同时,利用WebService技术可为用户在互联网上实现直接的控制和查询[1]。为了提升系统的性能,流量控制机制的作用日趋明显。如何防止网关可能遭到同一时间用户大量访问而造成网关崩溃,以及由于各种异构网络的通信速率差距太大而造成网络拥塞、数据丢失[2],成了亟需解决的问题。针对以上情况,提出了基于图形分类的令牌桶流控算法。该算法针对即将流入子网内的请求数据进行分类调度,创建了一个4种形状的四速令牌桶,把不同的请求分成4类,分别放到4个速率和桶深不同的子桶内,令牌桶的桶深、速率及漏桶的大小阈值定期更新,对不同类型的业务请求进行动态带宽的分配。

1 算法设计

DBA技术在GPON系统具有重要的作用[3-7],能动态分配上行的带宽,提高系统的宽带利用率、网络时延,保证良好的服务质量。参照GPON系统中的动态带宽分配机制,网关把带宽分为固定带宽、确保带宽、非确保带宽和尽力而为带宽4个级别,其级别优先级如图1所示。

图1 网关中带宽类型Fig.1 The bandwidth types in gateway

本算法4种类型的带宽分别对应4种T-CONT类型,4种带宽都可参与网关带宽的动态分配,在每个更新周期Tu内被重新分配,以此提供网关的QoS、提高带宽利用率。

在优先级别的设立机制上,网关把所有的单位服务划分为4种服务类型:1)紧急控制命令业务,该业务拥有最高级别的优先级,拥有固定带宽;2)即时数据请求业务,属于次优先级,拥有确保带宽和非确保带宽;3)非紧急数据业务,拥有确保带宽和非确保带宽;4)普通数据请求业务,优先级别最低,拥有尽力而为带宽。网关对这4种业务分别标记为A、B、C、D业务,优先级别依次降低。4种带宽的服务类型如表1所示

表1 4种带宽的服务类型Tab.1 Service for four bandwidth types

TSC-DBA算法对带宽的分配,通过令牌桶算法实现,TSC算法为每一类服务设置一种形状进行标记。这4种类型服务对应的形状为:1)A类型对应的令牌形状为正方形,该形状的请求优先级最高,对应固定带宽和确保带宽;2)B类型对应的令牌形状为三角形,该形状拥有确保带宽和非确保带宽;3)C类型对应的令牌形状为圆形,拥有的带宽同B类型的带宽,但是分配优先级低于B;4)D类型对应的令牌形状为菱形,优先级最低,只拥有尽力而为带宽,令牌不足时,最先被丢弃。TSC-DBA算法原理如图2所示。

对于网关收到来自sink节点的请求,算法根据其sink节点请求的服务类型优先等级进行区分,给当前的请求标记不同的形状。其标记含义如下:正方形代表优先级最高的请求,该请求直接使用A桶中的令牌,若A桶中令牌不足,可优先使用B桶中的令牌;三角形请求时,将使用B桶中的令牌,若B桶中令牌不足,优先使用C桶中的令牌;圆形请求时,使用C桶中的令牌,若C桶令牌不足,使用D桶中的令牌;菱形请求使用D桶中令牌,若D桶中令牌不足,则丢弃该请求。请求丢弃的顺序为菱形、圆形、三角形、正方形,通过该种方式既可保证高优先级的业务的服务质量,又能充分利用网络带宽,从而保证网关的性能。

图2 TSC-DBA算法原理Fig.2 Principle of TSC-DBA algorithm

由于在传统的DBA算法中,当前周期的网关数据决定下一个周期网关的带宽分配策略,这样会造成严重的滞后性。TSC-DBA算法引入了新的基于轮询的流量预测机制,动态分配令牌桶中的桶深和令牌速率。网关计算本周期的流量请求大小,再关联之前的所有周期实际转发的数据量,根据算法的预测机制对即将到达的流量进行预测。网关定义为:

1)设i和j分别为sink节点和周期,取值范围为1≤i≤N,N为sink节点或子网的个数。

2)设t为令牌的形状类型,t∈{1,2,3,4},分别为正方形、三角形、圆形和菱形类型的令牌。

3)设Pti,j为sink节点i在第j个周期内预测接收到的t类形状的令牌请求数,Ntj为实际接收到的t类形状的令牌请求数。

预测机制为:

其中:Ei,j-k为当前周期j之前的k个周期中请求数序列的算术平均值;ΔNti,j为Nti,j与Nti,j-1的差值; ω1,ω2,…,ωk为权重因子。经过多次实验,权重因子为4阶,依次为0.4、0.3、0.2、0.1。

为了更好地描述TSC-DBA算法,先定义以下几个概念:

1)Bti,j为sink节点在第j轮发送请求时,缓存区中还未转发的t类令牌的数据数量。

2)Wr1,Wr2,Wr3,Wr4分别为当t=1,2,3,4时当前的令牌数量。

3)Wtotal为可分配的令牌总数。

4)Rti,j、Gti,j分别为sink节点i在第j个周期请求和分配的t类形的令牌数量。

关于TSC-DBA算法的桶深和分配速率,遵循准则为:

1)网关给优先级最高的A桶分配固定的桶深和令牌速率,在算法上实现了A类型服务所需的固定带宽。固定带宽由正方形令牌类型组成,对时延的敏感程度最高。算法先预测在下一个周期即将到达的正方形类型的请求数据大小,然后再向网关报告。因此,A类的传输为:

更新剩余桶深和令牌数量,得

2)为确保带宽分配对应的桶深和令牌数量,分成两部分:三角形类型令牌桶的确保带宽和圆形类型令牌桶的确保带宽。

a)在本算法中,三角形类型令牌中的确保带宽部分的分配有着和正方形类型令牌相同的预测方法。因此,B类型的传输为:

b)分配圆形令牌桶中的确保带宽,圆形令牌桶的确保带宽优先级小于三角形令牌桶,因此,圆形令牌桶的传输为:

其中,Mmin为每个周期内sink的圆形令牌传输的最小确保带宽。更新剩余桶深和令牌数量,得

3)为非确保带宽分配对应的桶深和令牌,由圆形令牌桶组成,只有在分配完了确保带宽需求的令牌数量,然后再检测剩余的令牌数,如果还有剩余,才为非确保带宽分配所需求的令牌数量。即-Mmin),t=3时,

更新剩余的桶深和令牌数量,得

4)为尽力而为带宽分配对应的桶深和令牌数量。菱形令牌桶优先级最低,对时延最不敏感,因此,菱形令牌桶的分配在所有其他高优先级的业务没有需求后才进行。如果最后还有剩余的令牌,就为菱形令牌桶分配令牌。

更新剩余的桶深和令牌数量,得

5)若Wr4＞0,则从步骤3)开始进行第2次桶深和令牌分配,如此循环,直至分配完毕,退出循环。

2 实验仿真

实验在流量控制的TSC-DBA算法中进行仿真,验证TSC-DBA算法的正确性和优势。本仿真程序使用C#语言编写程序,构造虚拟流量源和虚拟交换机,并在虚拟交换机上实现TSC-DBA算法,监测统计流量源产生的数据包转化情况。

通过不同的参数设置,进行多次实验,如图3所示。从图3可看出,随着数据包的发包数逐渐增加, TSC-DBA算法的请求响应成功率呈下降趋势,但TSC-DBA算法下降缓和,说明TSC-DBA算法对请求响应成功率有所提升,间接地提高了整个多维网关的QoS,达到了预期目的。

图3 整体请求成功率Fig.3 The overall request success ratio

在如图4所示的分类业务曲线中,随着请求数据包的增加,A、B、C、D四种类型的丢包率都有所增加,但是优先级别最高的A类数据包的丢包率增加比较缓慢,说明之前分析的结果吻合,TSC-DBA算法能保证重要请求业务的QOS,对于低优先级的请求只是尽力而为而已,只有满足了最高优先级的请求后才给其分配桶深和令牌。

图4 分类业务丢包率Fig.4 Loss rate of classification business

3 结束语

结合DBA算法和流量整形[8-9],提出了基于形状分类的令牌桶流控算法,仿真测试实现了动态带宽的分配。仿真结果表明,算法能判断业务请求的优先级别,并且分配所需要的带宽,提高网关的服务质量。

[1] 尼四凯,王勇,钟明旸.多维Web服务网关的高并发问题研究[J].微型机与应用,2014(7):34-36.

[2] 屈伟平.物联网掀起新的信息技术革命浪潮[J].物流技术与应用,2009(11):42-45.

[3] 张勇,朱祥华.基于周期轮询的GPON上行链路动态带宽分配算法[J].现代传输,2006,32(4):75-79.

[4] 刘杨.GPON系统中一种高性能的DBA分配算法研究[D].上海:复旦大学,2011:23-25.

[5] 孙捷,杜江,谭毅,等.GPON中一种二端动态带宽分配算法的设计与分析[J].光通信技术,2009,33(4):15-17.

[6] 裘紫清,陈雪.一种基于改进AR模型的预测型GPON动态带宽分配算法[C]//全国第十三次光纤通信暨第十四届集成光学学术会议,2007:908-913.

[7] 雷震洲.千兆比无源光网——GPON[J].电信网技术, 2003,29(8):12-15.

[8] 陈彪.IP接入网络面向QOS的分组调度和流量整形研究[D].浙江:浙江大学,2003:15-17.

[9] 涂文伟,张进,张兴明.分级统筹分配令牌参数的流量整形算法[J].计算机应用,2006,26(9):21-24.

编辑:梁王欢

A token bucket flow control algorithm based on pattern classification

Wang Yong1,Ye Mingchuan2
(1.School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,China; 2.School of Information and Communication Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

Aiming at network congestion of heterogeneous network accessing to multidimensional gateway caused by different channel rate,a dynamic bandwidth allocation algorithm based on prediction and grading polling is proposed according to DBA and flow control algorithm of GPON technology.Combining token bucket algorithm based on graphics categorization, flow control is realized by dynamic bandwidth allocation on different types of services.Experimental results show that the algorithm can improve effectively service quality of gateway.

DBA;prediction of polling;pattern classification;token bucket

TP393

A

1673-808X(2015)05-0391-04

2015-04-20

国家自然科学基金(61163058,61363006);广西可信软件重点实验室开放基金(KX201306)

王勇(1964-),男,四川阆中人,教授,博士,研究方向为计算机网络技术与应用、信息安全。E-mail:ywang@guet.edu.cn引文格式:王勇,叶明川.基于图形分类的令牌桶流控算法[J].桂林电子科技大学学报,2015,35(5):391-394.