动态令牌分配的TCSN多级令牌桶流量监管算法

赵晋南,, ,

(西南交通大学 信息科学与技术学院,成都 611756)

0 概述

列车控制与服务网络(Train Control and Service Network,TCSN)[1]是列车控制业务与服务业务一体化传输的新型列车通信网络。针对列车网络复杂而多样的业务特性,TCSN采用区分服务的模式。DiffServ[2-3]网络与用户之间定义了服务等级合约(Service Level Agreement,SLA),内容主要包括控制与服务业务流的流量特性和传输特性。如果用户的业务流违反了SLA,则其订购的服务质量需求将不能得到保证,甚至会遭到拒绝服务。在DiffServ网络中,流量监管是提供QoS保证的一项重要技术,其作用是通过监督进入网络的流量速率来对超出部分的流量进行“惩罚”,从而使进入的流量被限制在一个合理的范围内。

在TCSN网络中,关键业务控制列车的正常运行,其必须得到优先传输。除关键业务外的控制和服务业务在传输时需要一定程度的服务质量保证,同时不能对关键业务的传输产生影响。逐跳行为(Per Hop Behavior,PHB)[4-5]规定在网络传输中采用AF(Assured Forward)转发除关键业务外的控制业务和服务业务,AF业务主要包括除关键业务外的控制业务、音频流业务、视频流业务、交互类业务、高保证业务、一般Web业务和P2P业务。在TCSN实际工作中,AF业务流量的实际到达率与SLA规定的速率并不相符,其容易对关键业务的传输产生影响,因此,必须对AF业务流量进行监管。

传统的流量监管方式[6-7]通过令牌桶[8-10]来实现,但在列车网络交换机中,令牌桶自身的参数和结构通常是静态的,对流量的监管也是静态的,这容易导致服务等级高的流量越来越大,而服务等级低的流量越来越小,同时,高等级业务流对应令牌桶的令牌最终会因溢出而丢弃。

TCSN网络在实际工作中,网络状态是不断变化的,静态的监管方案并不合理。为此,本文提出一种TCSN多级令牌桶流量监管算法,通过两级令牌动态分配来实现AF业务流量的动态监管,并通过实验验证该方法的可行性。

1 多级令牌桶流量监管算法

1.1 应用背景

对于TCSN网络,有时某一业务流会在乘车高峰期大量突发,造成过多的数据流流入网络并长期占用网络带宽,致使其他业务得不到及时服务,特别是对一些时延、抖动及丢包敏感的实时数据,会造成较大的负面影响。有一些旅客服务业务流本身的流量变化较大,如VBR视频流和P2P业务流,其峰值速率比平均速率高出数倍,在传输过程中更易占用网络带宽。用户规模和业务种类的扩大,要求TCSN网络设备不仅能进一步细化业务流量,而且还能够对多个用户、多种业务、多种流量等传输对象进行统一管理[11]。为支持TCSN多业务的QoS要求,限制各业务流对网络资源的过度占用,需要对网络资源进行合理划分,即设计TCSN多级令牌桶流量监管算法。

1.2 多级令牌桶流量监管方案

多级令牌桶流量监管方案是TCSN多级令牌桶流量监管算法实现的基本框架,其主要包括令牌桶、一级令牌分配模块、二级令牌分配模块、分类着色模块和入队管理模块。当AF业务流进入队列时,首先由分类模块对业务流进行分类,将AF业务流归入不同的服务类,每个AF子队列对应一个令牌桶,一级令牌分配模块按SLA定义的令牌添加速率监管AF业务流的传输速率。二级令牌分配模块根据一级令牌分配模块的结果重新分配富余令牌。AF业务流经过令牌桶着色后被标记为绿、黄、红三色流量,入队管理模块根据标记结果将AF业务流归入下一个优先级队列。TCSN多级令牌桶流量监管方案总体结构如图1所示。

图1 TCSN流量监管方案总体结构

1.3 设计思路与系统实现

在TCSN网络中,各类AF业务流具有不同的流量特性和传输特性,对应SLA中定义的服务等级也不相同。传统的单独令牌桶只能应用于单一服务等级的流量,在TCSN多业务存在的情况下,需要使用多个令牌桶对AF业务流进行更精细的流量监管[12-16]。在TCSN网络实际工作中,不同AF业务的实际流量到达率可能与SLA允许到达的流量不相符,当AF业务流量违反SLA合约时,需要通过令牌桶限制业务流的传输速率。但随着网络负载的不断增大,应当适当降低SLA允许到达的流量,并调节令牌添加速率,以避免出现网络拥塞。AF业务流的实际流量到达率不同,按照令牌添加速率来添加令牌,会导致各令牌桶的令牌存在富余或欠缺,即某些AF业务流量速率一直维持在很大或很小的状态。为确保令牌分配比例的公平性,需要重新分配队列的富余令牌。

流量监管采用令牌桶技术来控制流量,每传输一个报文则令牌桶减少相应数量的令牌。SLA定义了各AF业务流的流量特性,由此可以计算出各AF子队列对应令牌桶的令牌添加速率。一级令牌分配模块按照令牌添加速率为每个令牌桶添加令牌,同时根据网络负载状态调整SLA允许到达的流量。二级令牌分配模块根据一级令牌分配后各AF子队列令牌的富余或欠缺情况,重新分配令牌桶的富余令牌。为进一步避免网络拥塞,针对区分服务网络,通过采用TWSTCM算法[17]比对平均流量到达率来标记监管后的AF业务流量。同时对RIO-C算法[18-19]进行改进,标记后的三色流量按转移概率将AF业务流归入下一级AF队列和BE队列,而不是直接丢弃业务报文。

2 两级令牌分配

传统的令牌桶机制为每个服务队列配置一个令牌桶,各业务流的输出速率由令牌桶控制,令牌桶自身的参数设置决定了流量的输出速率和带宽占有率。但网络设备中令牌桶自身的参数配置和结构通常是静态的,一旦配置完成后一般不会进行较大改动,而TCSN的实际应用情况是动态变化的,特别是AF业务流量,其在不同时间段网络流量的业务组成可能会有很大差距,有可能出现一些业务带宽剩余,而另一些业务得不到满足的情况。流量超负荷时会引起网络拥塞,导致系统带宽利用率下降[11]。

在令牌桶监管的基础上,本文增加一级令牌分配模块,其根据系统的信道利用率来估算网络负载状态,以此提高或降低当前按SLA允许到达的流量,进而动态调整令牌桶的令牌添加速率,并将AF业务流量的输出速率控制在合理的范围内。一级令牌分配模块按照令牌添加速率为令牌桶添加令牌,但流量到达速率与SLA允许到达的流量不匹配时,会使不同AF子队列的令牌桶令牌存在富余或欠缺。二级令牌分配模块对一级令牌分配后的令牌进行重新分配,累计每个AF子队列的令牌富余或欠缺情况,计算欠缺令牌子队列的令牌分配配额,然后等比例公平地将富余令牌分配给欠缺令牌队列,从而为不同业务流提供一定程度上的带宽动态分配[20],提高网络带宽利用率。

2.1 一级令牌分配

一级令牌分配模块按照令牌添加速率为AF业务流对应的令牌桶添加令牌。SLA定义了各类AF业务流的流量特性,对应令牌桶的令牌添加速率为各类AF业务流的平均报文间隔。在网络带宽一定的情况下,网络的平均信道利用率反映了网络的负载状态。根据网络的轻载或中载状态来逐渐降低当前按SLA允许到达的AF业务流量,重载时,为避免加重网络拥塞,只允许AF业务中优先级较高的业务流量进入队列。通过指数平均来计算每个AF子队列的平均流量到达率,并与当前按SLA允许到达的流量进行比对后,调节各个令牌桶的令牌添加速率。一级令牌分配模块的动态令牌分配实现了AF业务流量的初步监管,它能够将流量的传输速率控制在合约允许的范围内。设平均信道利用率为η,当前依据SLA允许到达的流量计算得到的监管后实际允许的流量为S1,SLA允许到达的流量为S2,AF子队列的空余队列长度为q*,平均流量到达率为RA,当前令牌添加速率为RT,令牌添加速率的动态调整算法描述如下。

if η<20%,网络处于轻载状态

S1=S2

else if η<80%,网络处于中载状态

S1=(1-η)S2

else 网络处于重载状态

if RA

RT=RA

else

RT=S1

2.2 二级令牌分配

一级令牌分配后各令牌桶的令牌存在富余或欠缺的情况,二级令牌分配统计每个AF子队列令牌的富余和欠缺情况,将所有富余令牌等比例公平地分配给欠缺令牌的AF子队列。当AF子队列的平均流量到达率小于当前按SLA允许到达的流量时,该队列富余令牌,此时累计所有AF子队列的富余令牌;反之,该队列欠缺令牌,此时记录每个队列的欠缺令牌数量。二级令牌分配的依据是AF欠缺令牌子队列的富余令牌分配配额。

2.2.1 富余令牌重分配配额计算

在DiffServ服务网络中,富余令牌分配配额应由AF业务流的传输服务质量需求来决定,AF业务流的传输服务质量需求包括时延优先级和包丢弃优先级。但当网络处于轻载状态时,系统的时延和丢包率都较小,对AF欠缺令牌子队列的富余令牌分配配额影响也较小,此时队列的欠缺令牌数在较大程度上影响富余令牌的分配。综上,AF欠缺令牌子队列的富余令牌分配配额由队列的欠缺令牌数、时延和丢包率共同决定,3个影响因子对应的富余令牌分配配额之和即为每个AF子队列的富余令牌分配配额。基于3个影响因子的富余令牌分配配额计算方法如下。

1)基于欠缺令牌数的富余令牌重分配配额W1为:

其中,W1i为AF子队列i的基于欠缺令牌数的富余令牌重分配配额,Qi为AF子队列i的欠缺令牌数,K为欠缺令牌子队列个数,P为AF队列总的富余令牌数。

2)基于时延的富余令牌重分配配额W2

设时延优先级级数为X,最低优先级欠缺令牌的AF子队列的富余令牌重分配配额为M,按优先级高低等比例重分配富余令牌给各欠缺队列,则时延优先级为Xi的欠缺令牌子队列i分配到的富余令牌重分配配额为:

W2i=Xi·M

所有欠缺令牌AF子队列的富余令牌重分配配额之和等于富余令牌数量,即:

则有:

3)基于丢包率的富余令牌重分配配额W3

设包丢弃优先级级数为Y,最低优先级欠缺令牌的AF子队列的富余令牌重分配配额为N,按优先级高低等比例地分配富余令牌给各欠缺队列,则包丢弃优先级为Yi的欠缺令牌子队列i分配到的富余令牌重分配配额为:

W3i=Yi·N

所有欠缺令牌AF子队列的富余令牌重分配配额之和等于富余令牌数量,即:

则有:

2.2.2 权值因子动态调整

在网络处于轻载时,AF欠缺令牌子队列时延和丢包率较小,富余令牌重分配配额主要由队列的欠缺令牌数决定。随着AF业务流量的不断增大,网络逐渐处于中载状态,系统时延增大,AF子队列的时延优先级成为富余令牌重分配配额的关键影响因素。在网络处于重载时,系统不断丢包,AF欠缺令牌子队列的丢包优先级开始主导队列的富余令牌重分配配额。网络状态不同,3个影响因素对AF欠缺令牌子队列富余令牌重分配配额的影响程度各不相同。TCSN多级令牌桶流量监管算法提供2种基于网络状态的权值因子动态调整算法。算法描述如下。

算法1权值因子分段调整算法

if 网络处于轻载状态

then (α=0.80,β=0.15,γ=0.05)

else if 网络处于中载状态

then (α=0.01,β=0.98,γ=0.01)

else if 网络处于重载状态

then (α=0.1,β=0.1,γ=0.8)

其中,α、β、γ分别为欠缺令牌数、时延、丢包率的权值因子,且α+β+γ=1。

算法2权值因子连续调整算法

权值因子连续调整主要依据AF子队列的欠缺令牌数和队列的传输服务质量需求,假设其相应的权重分别为δ1和δ2。其中,α=δ1,队列的传输服务质量需求特性包括时延优先级和包丢弃优先级。在TCSN网络中,δ1随着信道利用率的增加而递减,δ2随着信道利用率的增加而递增,则:

α=δ1=1-η

δ2=η

将δ2分配到时延优先级和包丢弃优先级,得到:

β=(1-η)δ2=(1-η)η

γ=ηδ2=η2

综上,AF子队列的富余令牌重分配配额为:

W=αW1+βW2+γW3

当AF业务流量经过多级令牌桶流量监管模块时,二级令牌分配模块根据每个AF子队列的富余令牌重分配配额为其分配令牌,进而对AF流量进行监管。

3 仿真结果与分析

TCSN多级令牌桶流量监管算法的关键在于两级令牌分配的实现。一级令牌分配根据令牌添加速率控制AF业务流传输速率,其分配结果由AF子队列的平均流量到达率和令牌桶的令牌添加速率决定。本文主要对二级令牌分配进行仿真分析。二级令牌分配统计每个AF子队列令牌的富余和欠缺情况,将所有富余令牌等比例公平地分配给欠缺令牌的AF子队列。富余令牌分配为基于欠缺令牌数、时延优先级和包丢弃优先级的富余令牌重分配配额之和。考虑到网络状态不同,3个影响因子对富余令牌重分配配额的影响权重不同,在仿真时分别计算分段权值和连续权值下的富余令牌重分配配额。随着仿真时间的延长,网络的平均信道利用率不断增大,网络负载也随之增大。仿真中AF子队列参数设置如表1所示。3种富余令牌重分配配额的权值因子如表2所示。

表1 AF子队列仿真参数设置

表2 富余令牌重分配配额权值因子

富余令牌重分配配额变化趋势如图2所示,实线为3个欠缺令牌子队列的欠缺令牌增长曲线,虚线为欠缺令牌子队列的富余令牌重分配配额,加粗线为网络平均信道利用率的变化曲线。

图2 富余令牌重分配配额变化趋势

图2(a)为分段权重下AF欠缺令牌子队列的富余令牌重分配配额,从中可以看出,网络处于轻载时,网络的时延和丢包都较小,欠缺令牌越多,则分得的令牌越多,富余令牌重分配配额由队列欠缺令牌数决定;网络处于中载时,网络时延不断增大,队列时延优先级越高,富余令牌重分配配额越大,时延优先级成为富余令牌重分配配额的主要影响因素;网络处于重载时,网络不断丢包,子队列的包丢弃优先级越高,则分得的富余令牌越多,包丢弃优先级开始主导子队列的富余令牌重分配配额。但是,随着网络不断丢包,AF子队列的欠缺令牌越来越多,富余令牌越来越少,导致每个AF子队列的富余令牌配额越来越小。图2(b)为连续权重下的AF欠缺令牌子队列的富余令牌重分配配额。同样地,网络负载状态不同,决定富余令牌重分配配额的影响因子不同,连续权值是随着平均信道利用率而不断变化的。因此,其富余令牌重分配配额的变化趋势与图2(a)有所不同。

由上述实验结果可知,每个AF子队列所传输的AF业务具有不同的流量特性,所对应的令牌添加速率由流量特性决定。当网络处于轻载、中载或重载状态时,AF欠缺令牌子队列的欠缺令牌数、时延优先级和包丢弃优先级对富余令牌重分配配额的影响程度不同。两级令牌分配算法根据每个AF子队列的流量特性和传输特性,公平地为子队列分配令牌,从而实现AF业务流量的动态监管。

4 结束语

列车控制业务的复杂化和旅客服务业务的多样化,使得在列车控制与服务业务一体化传输的TCSN网络中的流量监管极其重要。传统的流量监管方式是静态的,不宜直接应用于TCSN网络。为此,本文提出一种动态令牌分配的多级令牌桶流量监管算法。在令牌桶流量监管的基础上,采用两级令牌分配模块实现对AF业务流对应令牌桶令牌添加速率的动态调节和富余令牌的重新分配。仿真结果表明,该方法具有可行性,可为动态监管列车控制与服务业务流量提供一种新思路,对TCSN网络设备的设计具有一定的参考借鉴意义。下一步将根据实际应用情况对算法参数进行优化。