ON-OFF过程模拟突发业务在调度仿真中的应用研究.doc

《ON-OFF过程模拟突发业务在调度仿真中的应用研究.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ON-OFF过程模拟突发业务在调度仿真中的应用研究作者：王鹏金德鹏　伊鹏　曾烈光　　论文关键词：ON-OFF模型　突发业务　输入排队　调度　　论文摘要：介绍了一种使用ON-OFF模型完成网络突发业务建模的方法，并且利用该模型完成了突发业务在输入排队调度中的仿真，为下一步研究开发在突发业务条件下具有鲁棒性的输入排队调度算法打下了基础。　　1概述　　伴随着各种宽带技术的出现,近几十年发展起来的新业务如数字广播、数字电视、IP电话和数字视频点播等迅速增长。这使得现代网络融合了数据、语音和图像等多种业务,从而需要针对不同业

2、务、不同需求提供服务质量保证。这对传统的网络业务建模理论提出了新的挑战,同时也对于通信网络的性能分析、资源分配与流量控制等提出了新的要求。　　网络业务源的分析建模问题在网络性能分析、控制中尤为重要。合理的假设近似不亲能够反映特定业务的特点，而且可以极大的简化分析计算，从而快速准确的得到完了性能。传统的排队论理论[1]，一般是假设时间的到达具有独立同分布和无记忆的特性，那么这个过程就构成了Poisson过程。但是在某些场合下，以上两个假设无法同时成立，尤其是在日益复杂的通信网中，即使可以假设各个事件的到达或吃力满足相

3、互独立性，但其间隔分布一般不具备无记忆性[2]。一个典型的例子就是在当前的计算机网络中，骨干网高速路由器为了提高硬件处理速度对到达的变长数据（64byte~64kbyte）包采用了切片（fragment）技术。数据包经过切片后成为多个固定长度的信元（cell），这样对于切片后的业务流就不能再简单的假设为Poisson到达过程，并且对于每个cell的处理时间变为定长，所以也不能用负指数分布来近似。大量测试表明，这样的信元到达具有极大的突发性[3]。　　本文正是针对核心路由器输入端口的这种突发型业务使用马尔代夫过程调制

4、的ON-OFF模型对其近似，并且针对输入排队调度系统应用该业务源进行仿真，从而得出典型调度算法在突发业务下的性能。通过研究表明，典型算法在突发业务条件下性能迅速恶化，需要研究新型抗突发调度算法来弥补这项空白。　　2输入排队调度背景5　　当前网络高速发展，宽带技术不断出现，作为网络核心设备的路由器和交换机通常采用输入排队的纵横开关（Crossbar）这种交换体系结构[4]。如图1所示，但是在这种交换结构中，对头（HOL）信元阻塞使系统性能大幅下降[5]，为了克服（HOL）信元阻塞，一般在输入端采取虚拟输出排队（VOQ

5、）的形式，这样就要求有一个调度器来控制数据包的交换转换。　　考虑一个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<=

6、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相连通。不

7、失一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过程建模实现简单

8、并且能够真实地反映核心路由器线路卡输入数据包切片后的到达情况[5]。　　当前在输入排队调度算法中最为流行的是NickMckeown于1994年提出的iSLIP算法[5]，该算法以其高性能易于硬件实现成为了输入排队调度算法的里程碑，并且已经在Cisco的GSR12000路由器和Stanford大学的TinyTera项目中得到了成功应用。算法已经被证明在均衡业务