基于分形布朗业务模型的差分队列服务建模*

郭棉 姜胜明 官权升 毛华超

(华南理工大学电子与信息学院，广东广州510640)

在下一代网络标准体系中，服务质量(QoS)保证是极为关键的内容，尤其是实时业务必须考虑服务质量保证问题.目前，互联网工程任务组(IETF)主要采用2种服务质量模型:综合服务(IntServ)和区分服务(DiffServ)质量模型.综合服务质量模型主要采用资源预留协议为每个数据流在其所经过的各个路由器进行资源预留，从而为其提供服务质量.由于网络需要存储大量的状态信息，综合服务质量模型具有可扩展性问题，因而不适用于大型网络.区分服务质量模型采用分类的机制对业务实现差分服务，每类业务中的数据流在所经过的区分服务域内的所有路由器中获得相同的服务.尽管这种机制具有可扩展性，但其服务粒度比较粗糙.在未来的通信网络中，接入网络包括有线网络和各种无线接入网络，而承载的业务主要以实时业务为主.实时业务要求网络提供多种多样的服务质量，因而要求端到端的服务质量方案既具有可扩展性又能提供细粒度的服务质量.文献［1-3］中提出的端到端的服务质量方案，大多是将传统的综合服务和区分服务的机制进行改进，使其适用于无线网络，因而实质上没有解决综合服务的可扩展性问题和区分服务的基于类的服务粒度的粗糙性问题.

差分队列服务(DQS)是一种不同于综合服务和区分服务的新的服务质量模型［4-6］.文献［4］中提出了基于差分队列服务的缓存准入机制(BAC)，基于数据包粒度明确了数据包进入队列的条件和在队列中的排队方式;文献［5-6］将其进一步完善，提出了提供端到端服务质量的差分队列服务模型，明确了差分队列服务模型的队列结构、超时数据包的处理规则等，使其适用于有线和无线网络.差分队列服务模型要求每个数据包携带其服务质量要求，如时延要求、丢包优先选择标志等.路由器根据数据包的服务质量要求来确定其在缓存队列中的位置，即确定数据包调度的顺序以及丢弃的优先级，从而保障数据包的服务质量.差分队列服务模型具有如下优点:(1)由于服务质量要求是由数据包携带的，因而具有可扩展性;(2)由于将新到的数据包按时延要求放入队列的合适位置，因而具有数据包粒度的服务质量保障;(3)队列由一个差分队列服务队列和一个或几个其它队列组成，因而调度非常简单.

文献［4］中基于数据包粒度分析了端到端时延和传输路径上各节点时延之间的关系，并根据数据包在各节点的时延要求明确了数据包进入队列的条件和在队列中的排队方式.文献［6］中基于指数限制突发业务模型(EBB)分析了单个数据流在差分队列服务系统中的时延超时概率与分配带宽之间的关系.但文献［4］的分析无法满足基于呼叫级别的接纳控制和资源分配.而基于呼叫级别的接纳控制是提高网络资源利用率和为实时业务提供服务质量的关键.文献［6］需要预先对数据流进行指数限制突发参数估计及包络处理，而且仅针对单个数据流进行了时延超时概率和所分配带宽的关系分析，没有给出丢包率和对多个不同时延要求的数据流共享带宽的资源分配方式进行分析.然而，根据文献［5-6］的思想，差分队列服务系统中不同时延要求的数据流是共享系统带宽的，丢包率是衡量服务质量的重要性能指标，因此，文中基于流模型分析的方法，将多个分形布朗运动(FBM)业务模型作为实时业务的到达业务模型，推导出系统带宽共享方式下差分队列服务系统的丢包率，以期为研究基于差分队列服务模型的接纳控制及资源分配策略提供理论基础.

1 业务模型

文献［7］中认为传统的泊松到达模型不适用于描述基于互联网协议(IP)的实时业务模型.实际上，20世纪90年代初，贝尔实验室公布的网络实测数据表明，IP网络的流量具有自相似性和长期依赖性，用FBM来描述的实时业务模型与实测的网络流量非常相似［8］.因此，文中采用FBM来描述输入的实时业务流量模型.

设FBM 业务模型［9］在时间间隔［0，t)内到达的业务量A(t)满足:A(t)=(t)，t∈(0，∞)，其中A(0)=0，m为业务的平均到达速率，a＞0为方差系数，BH(t)为标准的FBM且自相似系数(Hurst参数)满足 H∈(0.5，1.0)，则称A(t)为FBM业务.其中BH(t)具有如下特性:

(1)BH(t)具有稳定增量，即［s，s+t)内到达的业务量与［0，t)内到达的业务量具有相同的分布;

(2)BH(0)=0，而且对任意的t，BH(t)的数学期望E(BH(t))=0;

(3)对任意的t，BH(t)的方差 E((BH(t))2)=

(4)BH(t)基本上是处处连续的;

(5)BH(t)是高斯过程.

目前，基于FBM的研究主要是有关先进先出和具有严格优先级的服务模型的研究［9-14］，文中基于时延优先级的差分队列服务模型对FBM业务进行研究.

设差分队列服务系统收到N组不同时延要求的业务，对于第 i(i∈［1，N］)组业务，其时延为 di，当该组的某个数据包在s时刻到达系统时，根据该业务的服务质量要求，系统必须在s+di时刻前转发该数据包.设具有相同时延的到达业务可用一个FBM业务模型来表示，即对于第i(i∈［1，N］)组业务，其到达业务模型为

这里Ai(0)=0.

因此，在［0，t)内到达差分队列服务系统的总业务量为

其中Fa(0)=0.

差分队列服务系统总是先服务最迟离开时刻(数据包到达的时刻加上其时延要求)最小的数据包，因此，系统实际上是按照先进先出的规则服务同一时延组的数据包，必须在t时刻前服务的第i组业务的业务量为

即对于时延要求为di的业务组，系统必须在t时刻处理t－di时刻前到达的业务量，否则该时延组的部分业务的时延将超过di.

从系统角度来说，在［0，t)内系统必须处理的业务量为各时延组在［0，t－di)(i∈［1，N］)内到达的业务量之和.因此，系统必须在［0，t)内处理的总业务量为

2 差分队列服务建模

2.1 相关定义

在差分队列服务模型中，缓存丢包包括由于缓存溢出而丢弃的数据包和由于BAC而主动丢弃的数据包.BAC主动丢包的原因有:(1)系统不能在该数据包要求的时延前转发该数据包;(2)该数据包进入队列后将会影响队列中已有数据包的服务质量.为了便于分析，文中假设不存在由于缓存溢出而丢弃的数据包，即丢包主要是由BAC引起的.

设在［0，t)内已服务的业务量为S(t)，因BAC而丢弃的业务量为Dr(t)，在任意时间间隔［s，t)内必须服务的业务量为Wr［s，t］，等待服务的业务量为 W［s，t］，则根据差分队列服务规则，有

即在［s，t)内必须服务的业务量是在t时刻前必须处理的业务量Fr(t)减去s时刻前已服务的业务量和已丢弃的业务量.但由于系统是处于工作保存模式下，即只要系统中有数据包等待发送，系统就不会空闲，因此，可能存在Fr(t)＜S(s)+Dr(s)≤Fa(s)的情况(尤其当 t－s＜di时)，式(5)使用了 max(·)函数来避免出现 Wr［s，t］＜0 的情况.

而等待服务的业务量为

即在［s，t)内等待服务的业务量为t时刻前总到达的业务量减去s时刻前已服务的业务量和丢弃的业务量.

根据差分队列服务规则，系统总是按数据包的最迟离开时刻顺序来处理数据包，即如果有业务要求在t时刻前服务，则系统不会先处理要求在t+k(k＞0)时刻前处理的业务，且丢弃的主要是其服务质量不能得到保障的业务，即应服务而未能获得服务的业务，因此，［0，t)内丢弃的业务量为

即t时刻前丢弃的业务量为s(s≤t)时刻前丢弃的业务量加上［s，t)内应服务而未能获得服务的业务量.式中，C 为系统的总带宽，C(t－s)为在［s，t)内系统可服务的最大业务量，max(0，Wr［s，t］－ C(t－ s))为［s，t)间隔内应服务而未能获得服务的业务量，max(·)函数保证在任何时间间隔内应服务而未能获得服务的业务量不小于0.

对于处于工作保存模式下的差分队列服务系统，［0，t)内已服务的业务量为

即t时刻前已服务的业务量为s(s≤t)时刻前已服务的业务量加上［s，t)内实际服务的业务量.当［s，t)内到达的业务量小于或等于系统在此期间可服务的业务量时，［s，t)内服务的业务量等于此期间到达的业务量，否则等于此期间系统可服务的最大业务量，因此，［s，t)内实际服务的业务量为

2.2 溢出率分析

溢出率是指在某统计时段内发生数据包溢出的概率，也称为队列长度尾分布［15］.在差分队列服务模型中，发生溢出的主要原因包括由于缓存限制而溢出和由于系统无法满足时延要求而主动丢包造成溢出.文中假设缓存足够大，即溢出率主要是主动丢包的概率.如果在［0，t)内丢弃的业务量Dr(t)大于0，则系统发生了数据包溢出.因此，在差分队列服务模型中，溢出率P(Dr(t)＞0)即为差分队列服务系统中业务因系统不能满足其时延要求而被丢弃的概率.

设在［0，t)内的任意s(s≥0)时刻前系统没有丢包，即Dr(s)=0，而［0，s)内已服务的业务量满足

即(0，s)内已服务的业务量不大于这期间到达的业务量，则可推导出［0，t)内的溢出率为

令 u=t－s，且

ξ(u)是关于 u的单调函数，则对ξ(u)求导，并令ξ'(u)=0，可解得实根 u=u0，使 inf(ξ(u))= ξ(u0).将结果代入式(10)，可近似得出差分队列服务模型的溢出率为

式中，exp(－ ξ2(u0)/2)为(ξ(u0))的上限.

2.3 丢包率与溢出率的关系

丢包率是衡量系统服务能力的重要性能指标，而分析因BAC引起的丢包对评估差分队列服务系统的服务能力并对系统进行接纳控制和资源分配具有重要意义.

溢出率是基于时间的概率比值，而丢包率是基于业务量的比值，是丢失的业务量与总业务量的比值.文献［14］指出丢包率与溢出率具有相似的分布，因此，文中根据丢包率与溢出率的这个关系来计算差分队列服务模型中的丢包率:

式中，α为一个比值常数，是缓存为0的情况下丢包率与溢出率的比值，

3 仿真验证及性能分析

为验证基于FBM业务的差分队列服务模型及其丢包率公式的准确性，利用文献［16］的方法产生FBM序列，并将其作为数据源在NS2中进行仿真.与文献［12］的验证方法类似，文中共进行20次仿真，结果取平均值，然后与文中模型的分析结果进行比较，如图1所示.可以看出，丢包率的仿真结果与分析结果几乎一致，表明文中所建立的差分队列服务模型及其丢包率分析是准确和有效的.

图1 丢包率的仿真结果和分析结果比较Fig.1 Comparison of packet loss rate between simulation and analysis results

由式(10)可知，差分队列服务系统提供的服务与业务特性、服务质量要求(时延要求、丢包率等)以及系统的带宽紧密相关.在时延要求不变的情况下，差分队列服务系统的业务特性、丢包率以及系统带宽之间的关系如图2所示，其中N=4，d1=1，a=10，di=di－1+0.2，i＞1.

从图2(a)可见，在系统带宽一定的情况下，丢包率随着业务平均到达速率M的增大而上升，且受业务的突发性影响较大，如H=0.9时的丢包率远大于H=0.6时的丢包率.这是因为随着业务的突发性的增大，瞬时需处理的业务量远远超出系统当前的处理能力，从而导致BAC主动丢包率的快速上升.

从图2(b)可见，在给定的业务特性及时延要求下，系统带宽越大，丢包率越低.在相同的丢包率下，业务的突发性越大所需的带宽越大.如H=0.9时所需的带宽远大于H=0.6时所需的带宽.这是因为当业务突发性很大时，瞬时需处理的业务量远大于平均速率下需处理的业务量，因此需预留充足的带宽来处理这些突发业务.

图2 丢包率与业务特性、带宽的关系Fig.2 Relationship between packet loss rate and traffic characteristics as well as bandwidth

综上可知，差分队列服务所提供的服务质量受实时业务的突发性影响较大.在分配的带宽一定的情况下，突发性越强的业务，其服务质量越难以得到保障;为了保证高突发性的实时业务的服务质量，系统往往需要分配远高于业务平均到达速率的带宽.

4 结语

文中基于差分队列服务的思想，推导了在FBM模型下差分队列服务模型的丢包率.仿真结果表明，基于FBM的差分队列服务模型的分析结果与基于数据包粒度的仿真结果是一致的.性能分析结果表明，实时业务的突发性对差分队列服务的质量保证影响较大.为了满足高突发性的实时业务的服务质量要求，网络往往需要分配较大的带宽资源.因此，为了有效地利用网络资源，差分队列服务系统必须采用有效的接纳控制和资源分配策略.

［1］Callejo R M，Enriquez G J，Burakowski W，et al.Euqos:end-to-end QoS over heterogeneous networks［C］∥Proceedings of the Innovations in NGN:Future Network and Services.Geneva:ITU-T，2008:177-184.

［2］Senkindu S，Chan H.Enabling end-to-end quality of service in a WLAN-wired network［C］∥Proceedings of the IEEE Military Communications.San Diego:IEEE，2008:1-7.

［3］Stuckmann P，Zimmermann R.European research on future internet design［J］.IEEE Wireless Communications，2009，16(5):14-22.

［4］Jiang Sheng-ming.Granular differentiated queueing services for QoS:structure and cost model［J］.ACM SIGCOMM Computer Communication Review，2005，35(2):13-22.

［5］Jiang Sheng-ming.Differentiated queueing service(DQS)for end-to-end QoS provisioning:an evaluation from perflow，per-class to per-packet［C］∥Recent Advances in providing QoS and reliability in the future Internet backbone.New York:Nova Science，2011:13-28.

［6］Jiang Sheng-ming.Future wireless and optical networks:networking modes and cross-layer design［M］.London:Springer-Verlag，2012:73-102.

［7］Grimm C，Schluchtermann G.IP traffic theory and performance［M］.Berlin/Heidelberg:Springer-Verlag，2008:22-28.

［8］Leland W，Taqqu M，Willinger W，et al.On the self-similar nature of Ethernet traffic(extend version)［J］.IEEE/ACM Transactions on Networking，1994，2(1):1-15.

［9］Norros I.A storage model with self-similar input［J］.Queueing Systems，1994，16:387-396.

［10］Mannersalo P，Norros I.A most probable path approach to queueing systems with general Gaussian input［J］.Computer Networks，2002，40(3):399-412.

［11］Matache M T，Matache V.Queuing systems for multiple FBM-based traffic models［J］.Australian and New Zealand Industrial and Applied Mathematics Journal，2005，46(1):361-377.

［12］Cheng Yu，Zhuang Wei-hua，Wang Lei.Calculation of loss probability in a finite size partitioned buffer for quantitative assured service［J］.IEEE Transactions on Communications，2007，55(9):1757-1771.

［13］Jin Xiao-long，Min Ge-yong.Modelling and analysis of priority queueing systems with multi-class self-similar network traffic:a novel and efficient queue decomposition approach ［J］.IEEE Transactions on Communications，2009，57(5):1444-1452.

［14］谢明，叶梧，冯穗力，等.自相似业务流下的排队性能分析［J］.华南理工大学学报:自然科学版，2006，34(1):27-31.Xie Ming，Ye Wu，Feng Sui-li，et al.Analysis of queuing performance of self-similar traffic input［J］.Journal of South China University of Technology:Natural Science Edition，2006，34(1):27-31.

［15］Kim H S，Shroff N.Loss probability calculations and asymptotic analysis for finite buffer multiplexers［J］.IEEE/ACM Transactions on Networking，2001，9(6):755-768.

［16］片兆斌，白光伟，王军元.基于FBM模型的多媒体通信流特性分析［J］.计算机工程，2010，36(2):91-93.Pian Zhao-bin，Bai Guang-wei，Wang Jun-yuan.Communication traffic characteristic analysis for multimedia based on FBM model［J］.Computer Engineering，2010，36(2):91-93.