作者：王鹏 金德鹏 伊鹏 曾烈光
论文关键词：on-off模型 突发业务 输入排队 调度
论文摘要：介绍了一种使用on-off模型完成网络突发业务建模的方法，并且利用该模型完成了突发业务在输入排队调度中的仿真，为下一步研究开发在突发业务条件下具有鲁棒性的输入排队调度算法打下了基础。
1 概述
伴随着各种宽带技术的出现,近几十年发展起来的新业务如数字广播、数字电视、ip电话和数字视频点播等迅速增长。这使得现代网络融合了数据、语音和图像等多种业务,从而需要针对不同业务、不同需求提供服务质量保证。这对传统的网络业务建模理论提出了新的挑战,同时也对于通信网络的性能分析、资源分配与流量控制等提出了新的要求。
网络业务源的分析建模问题在网络性能分析、控制中尤为重要。合理的假设近似不亲能够反映特定业务的特点，而且可以极大的简化分析计算，从而快速准确的得到完了性能。WwW.11665.CoM传统的排队论理论[1]，一般是假设时间的到达具有独立同分布和无记忆的特性，那么这个过程就构成了poisson过程。但是在某些场合下，以上两个假设无法同时成立，尤其是在日益复杂的通信网中，即使可以假设各个事件的到达或吃力满足相互独立性，但其间隔分布一般不具备无记忆性[2]。一个典型的例子就是在当前的计算机网络中，骨干网高速路由器为了提高硬件处理速度对到达的变长数据（64byte~64kbyte）包采用了切片（fragment）技术。数据包经过切片后成为多个固定长度的信元（cell），这样对于切片后的业务流就不能再简单的假设为poisson到达过程，并且对于每个cell的处理时间变为定长，所以也不能用负指数分布来近似。大量测试表明，这样的信元到达具有极大的突发性[3]。
本文正是针对核心路由器输入端口的这种突发型业务使用马尔代夫过程调制的on-off模型对其近似，并且针对输入排队调度系统应用该业务源进行仿真，从而得出典型调度算法在突发业务下的性能。通过研究表明，典型算法在突发业务条件下性能迅速恶化，需要研究新型抗突发调度算法来弥补这项空白。
2 输入排队调度背景
当前网络高速发展，宽带技术不断出现，作为网络核心设备的路由器和交换机通常采用输入排队的纵横开关（crossbar）这种交换体系结构[4]。如图1所示，但是在这种交换结构中，对头（hol）信元阻塞使系统性能大幅下降[5]，为了克服（hol）信元阻塞，一般在输入端采取虚拟输出排队（voq）的形式，这样就要求有一个调度器来控制数据包的交换转换。
考虑一个n*n输入排队交换结构：每个输入端口的缓存分为n个voq队列，每个voq队列存储从输入端口i到达，目的端口为j的数据包。在以下讨论中，假定所有的数据包定长，t时刻voq队列长度用qn(t)表示。q(t)=[qn(t)]为n*n维矩阵指示在t时刻voq的队列长度。
在输入端i(1<=i<=n),设到达过程ai(t)是离散时间过程，每个时刻在美国输入端有0或1个信元到达（对于单播业务），而每个数据包都有一个指向其目的输出端j(t<=j<=n)的标识符。定义at,j(t)为输入i到输出j的到达过程，其到达率为λt=i，到达过程集合a(t)={ai(t);t<=i<=n},若输入和输出都在负载范围内（
），则a（t）被认为是容许的，否则就是非容许的。显然输出端j得离开过程di(t)也是一个离开率为μi的离散时间过程，在每个时刻有0个或个数1 据包离开，定义输入到i 输出的j 离开过程di,j(t)，其i,jμ离开率为。x(t)ij使用表示t 时刻输入端口i 与输出端口j的连接关系。x(t)=1ij当且仅当时，输入端口i和 输出端口j相连通。不失一q(t)=0ij般性，考虑完全连接关系，即当时允许输入端口i与输出端口j连 通。因此可以将crossbar的结构约束描述如下：x(t)∈{0,1}ij，其中i,j=1,2,l,n;
1=i一个可行的连接关系可以看作是图论中的二分图的匹配，调度算法的核心就是在各个时刻根据voq的状态决定匹x(t)配，从而置相应的ij。在到达过程ai(t)的建模中，作者设计并实现了简单的贝努力分布的业务和基于马尔可夫过程调制的on-off过程的突发业务。需要指出的是，对于突发业务建模的方法很多，作者使用on-off过程建模实现简单并且能够真实地反映核心路由器线路卡输入数据包切片后的到达情况[5]。
当前在输入排队调度算法中最为流行的是nickmckeown 于1994年 提出的islip算法[5]，该算法以其高性能易于硬件实现成为了输入排队调度算法的里程碑，并且已经在cisco 的gsr12000 路由器和stanford 大学的tiny tera项目中得到了成功应用。算法已经被证明在均衡业务条件下可以达到100%吞吐率[4]。
3 on-off模型分析
本文使用马尔可夫过程调制的on-off过程对突发业务建模。把输入排队调度系统设定为离散时间系统，以固定间隔时隙(slot)为基本时间单位。
如图2 所示，on －off过程可以考虑成一个恒定速率发送cell的信源通过一个随机开关后得到的随机过程。使用“on” 区间表示开关闭合期，“off”区间表示开关开启期。所以在“on”区间内，信元的到达速率恒定(本文中使用归一化到达率，信元到达率为1，即每个时隙均有信元到达)；在“off” 区间内，信元的到达率为0，即没有信元到达。on-off 信源产生的突发业务如图3所示。
对于开关的on 和off状态使用两个状态的一阶马尔可夫过程来调制，由图4可 见，由on状态转移到自身的概率为1-p1 ，转移到off 的概率为p1， 由off状态转移到自身的概率为1-p2 ，由off 状态转移到on 状态的概率为p2。本时刻的转移与当前信源所处状态有关，与上个时隙信元所处的状态无关。
以sn表示本时隙的状态，sn+1表示下一个时隙的状态，
则上述转移过程可以描述为：
p(sn+1=on ∣sn=on)＝1 －p1(3)
p(sn+1=off∣ sn=on)＝p1(4)
p(sn+1=off∣ sn=off)=1－ p2(5)
p(sn+1=on ∣sn=off)=p2(6)
一步概率转移矩阵为：
以ti-j
表示从状态i出发首次进入状态j的时刻，则
p(ton-off=n ∣s1=on)＝(1－ p1)n-1×p1(8)
p(toff-on=n ∣s1=off)＝(1－ p2)n-1×p2(9)
由几何分布的定义可知，on和 off状态保持时间分别服从参数为1－ p1和 1－ p2的几何分布。
在使用on －off过程模拟突发业务时，一般设定如下几个参数：
(1)平均到达率λ，表示平均在一个时隙产生一个cell的概率；
(2)平均突发长度burst_length，表明突发数据包的平均大小(单位为cell)；
(3)on区 间长度几何分布参数average_on；
(4)off区 间长度几何分布参数average_off。
在实际仿真中这几个参数满足如下关系式：
idle_length=burst_length×(1-λ)/λ(10)
average_on=(burst_length)/(1 ＋burst_length)(11)
average_off=(idle_length)/(1 ＋idle_length)(12)
说明：根据马尔可夫链稳态方程[1]可知
所以λ×p1=(1－λ)×p2(13)又由于on和 off状态的保持时间均服从几何分布，因此其平均保持时间应该满足
burst_length=1/p1；(14)
idle_length=1/p2；(15)
将式(14)、(15)代入式(13)可得式(10)。故on状态几何分布参数为
average_on=1 －p1＝(burst_length－ 1)/burst_length;(16)
average_off=1－ p2＝(idle_length －1)/idle_length；(17)
考虑到实际意义和编程实现，burst_length 和idle_length应该取大于0的正整数，故对以上两式作相应修正得到式(11)、(12)。
4应用及仿真结果
作者针对islip算法对贝努力业务源和突发业务源分别作了仿真，结果如下。在这里设定input buffer最大能容纳10 000 个cell ，系统选用的是32 ×32 的crossbar结构，仿真时间为1 000 000个时隙。在本仿真中对于突发业务有如下约定，对于在同一个突发，各个cell的目的端口相同，而各个不同的突发，其目的端口在所有输出端口中均匀选择。
图5 显示出islip算法在贝努力业务的情况下，负载增加延时的变化情况。在这种非突发情况下，系统来出现丢包。
图6 显示出islip算法在一次迭代情况下，突发度分别为16 、32 、64 和128的条件下，系统平均延时随复载增加的变化情况。图7显示出在输入缓存有限(这里设定为5 000 个cell)的情况下，在平均突发长度分别为16 、32 、64和 128时系统平均丢包率随负载增加的变化情况。
可以看出，当负载增加时突发业务的延时明显大于非突发业务，并且当存储器深度有限时，会出现不同程度的尾丢弃。这些结论与文献[4,5]中的理论和仿真结果基本相同，说明仿真结果正确。
5结论
在突发业务建模中使用马尔可夫过程调制的on-off模型是一种简单实用的方法，通过这种模型可以有效地反映出一个调度算法在突发业务下的性能。本文介绍了使用on-off模型来模拟离散时间系统中的突发业务的方法，并且将该算法应用于输入排队调度仿真中。文章给出了该突发业务对于典型调度算法的仿真结果。这为将来进一步深入进行调度算法研究，尤其是在突发业务下各种算法的鲁棒性研究，以及开发出对突发业务具有鲁棒性的调度算法提供了参考。
参考文献
1 daigle j n.queuing theory for telecommunications.addison-wesley pub.co.,1992
2 leland w e,willinger w,taqqu m,et al.on the self-similarnature of ethernet traffic.san francisco:proc.of sigcomm,1993-09:183-193
3 sriram k,whitt w.characterizing superposition arrivalprocesses in packet multiplexer for voice and data traffic.ieeej.select.area commun.,1986,4(6)
4 mckeown n,anantharan v,walrand j.achieving 100％
throughput in an input-queued switch.san francisco:ieeeinfocom96,1996-03,1:296-302
5 mckeown n.the islip scheduling algorithm for input-queuedswitches.ieee transactions on networking,1999,7(2):22
