正在加载图片...
D0I:10.13374/1.issnl00103.2007.09.046 第29卷第9期 北京科技大学学报 Vol.29 No.9 2007年9月 Journal of University of Science and Technology Beijing Sep·2007 网络动态调度系统的服务质量性能分析 陶丽红)郝卫东)杨扬)梁哲) 1)北京科技大学网络中心，北京1000832)北京科技大学信息工程学院，北京100083 摘要提出了考虑具有不同输入速率和输出速率的任务队列的网络动态调度系统状态空间模型，描述了网络动态调度系 统的清空型调度策略，并在此基础上给出了系统服务质量性能指标包括队列长度、总任务数量、系统吞吐量、响应时间等的分 析算法，数值计算表明，适当的调度策略可以使网络动态调度系统的响应时间处于受控的范围内，系统吞吐量处于稳定的状 态 关键词服务质量：计算机网络：动态调度系统：性能分析：离散事件动态系统 分类号TP273 计算机网络不断向高速度、高性能的方向发展， 队列i中的作业请求的平均完成速率用“：(=1,2， 对骨干网中起核心作用的一体化路由交换机而言， 3,,n)表示 其动态调度策略的性能尤其重要[】.当考虑大量 一旦网络服务选择执行某个网络作业队列，就 用户作业请求网络服务时，尤其是考虑组成某个完 会将网络服务能力切换到适当的作业队列，因此， 整业务流程的不同类型的多个用户作业在不同的网 通常用离散的逻辑变量表达相应的调度策略，记为 络服务上分布运行时，这种调度由于其分布性和异 s,(=1,2,3,…,n),其中，当网络服务决定将服 构性而往往是一个离散事件系统的NP完全(non~ 务能力切换到作业队列i时，s:=1,否则s=0,考 deterministic polynomial complete)f问题y. 虑可以同时被处理的网络作业队列的个数为1个， 本文采用连续流逼近的离散事件动态系统 (DEDS)分析网络服务调度方案中离散事件交互影 即之=1，∈0,1. 1 响所导致的系统状态的演化过程和相应的调度策 在网络服务的缓冲区中等待被处理的网络作业 略，给出了分析网络服务调度系统的多种服务质量 个数用连续取值的状态变量表达，记为x,=1,2, 指标的算法，并进行了实例演算. 3,…,,分别表示各个网络作业队列中同种类型作 1网络动态调度的状态空间模型 业的数量.其中，x≥0，=1,2,3，，n.y:表示各 个作业队列中单位时间内离开网络服务的作业个 当用户报文或用户作业要被分配到下一跳地址 数，在某段时间内，离开网络服务的作业个数的总数 时，往往出现多个满足路由匹配条件的不同用户作 等于进入的作业个数的总和减去在队列中等候被处 业队列排队等候某个网络服务的情况，此时需要该 理的作业个数的总和. 网络服务执行某种本地调度策略以保证用户满意的 由此，对所描述的网络服务调度系统动态过程 服务质量(Q$),比如队列长度、队列中作业的总个 的状态方程为： 数、系统的吞吐量、作业请求的响应时间等一 dxi(t) 对所描述的网络服务调度系统涉及的变量命名 dt =入一s: (1) 作如下假设：系统中有n个异构的网络作业队列共 yi(t)dt=xitdt-xi(t)dt 享单一的网络服务资源，该网络服务系统具有有限 容量的输入缓冲区：同一个网络作业队列中的网络 上述状态方程模型中x:是用连续流逼近的离 作业是同种类型的，而且每个网络作业以平均速率 散变量，$是离散的逻辑变量，入和凸是连续变量， 入进入网络作业队列i(=1,2,3,…,),网络作业 因此整个系统构成一个混合类型变量系统· 收稿日期：2006-05-15修回日期：2007-07-05 2清空型调度策略 基金项目：国家自然科学基金资助项目(N。-60673160) 调度策略的本质可以理解为从多个对象中选择 作者简介：陶丽红(1973一)，女，工程师 一个符合某个条件的对象进行服务[].网络动态调度系统的服务质量性能分析 陶丽红1） 郝卫东2） 杨 扬2） 梁 哲1） 1） 北京科技大学网络中心北京100083 2） 北京科技大学信息工程学院北京100083 摘 要 提出了考虑具有不同输入速率和输出速率的任务队列的网络动态调度系统状态空间模型描述了网络动态调度系 统的清空型调度策略并在此基础上给出了系统服务质量性能指标包括队列长度、总任务数量、系统吞吐量、响应时间等的分 析算法．数值计算表明适当的调度策略可以使网络动态调度系统的响应时间处于受控的范围内系统吞吐量处于稳定的状 态． 关键词 服务质量；计算机网络；动态调度系统；性能分析；离散事件动态系统 分类号 TP273 收稿日期：2006-05-15 修回日期：2007-07-05 基金项目：国家自然科学基金资助项目（No．60673160） 作者简介：陶丽红（1973—）女工程师 计算机网络不断向高速度、高性能的方向发展 对骨干网中起核心作用的一体化路由交换机而言 其动态调度策略的性能尤其重要［1—3］．当考虑大量 用户作业请求网络服务时尤其是考虑组成某个完 整业务流程的不同类型的多个用户作业在不同的网 络服务上分布运行时这种调度由于其分布性和异 构性而往往是一个离散事件系统的 NP 完全（nondeterministic polynomial complete）问题［4］． 本文采用连续流逼近的离散事件动态系统 （DEDS）分析网络服务调度方案中离散事件交互影 响所导致的系统状态的演化过程和相应的调度策 略给出了分析网络服务调度系统的多种服务质量 指标的算法并进行了实例演算． 1 网络动态调度的状态空间模型 当用户报文或用户作业要被分配到下一跳地址 时往往出现多个满足路由匹配条件的不同用户作 业队列排队等候某个网络服务的情况此时需要该 网络服务执行某种本地调度策略以保证用户满意的 服务质量（QoS）比如队列长度、队列中作业的总个 数、系统的吞吐量、作业请求的响应时间等［5—7］． 对所描述的网络服务调度系统涉及的变量命名 作如下假设：系统中有 n 个异构的网络作业队列共 享单一的网络服务资源该网络服务系统具有有限 容量的输入缓冲区；同一个网络作业队列中的网络 作业是同种类型的而且每个网络作业以平均速率 λi 进入网络作业队列 i（ i＝123…n）网络作业 队列 i 中的作业请求的平均完成速率用μi（ i＝12 3…n）表示． 一旦网络服务选择执行某个网络作业队列就 会将网络服务能力切换到适当的作业队列．因此 通常用离散的逻辑变量表达相应的调度策略记为 si（ i＝123…n）．其中当网络服务决定将服 务能力切换到作业队列 i 时si＝1否则 si＝0考 虑可以同时被处理的网络作业队列的个数为1个 即 ∑ n i＝1 si＝1si∈｛01｝． 在网络服务的缓冲区中等待被处理的网络作业 个数用连续取值的状态变量表达记为 xii＝12 3…n分别表示各个网络作业队列中同种类型作 业的数量．其中xi≥0i＝123…n．yi 表示各 个作业队列中单位时间内离开网络服务的作业个 数在某段时间内离开网络服务的作业个数的总数 等于进入的作业个数的总和减去在队列中等候被处 理的作业个数的总和． 由此对所描述的网络服务调度系统动态过程 的状态方程为： d xi（ t） d t ＝ λi － siμi ∫yi（ t）d t ＝∫λitd t －∫xi（ t）d t （1） 上述状态方程模型中 xi 是用连续流逼近的离 散变量si 是离散的逻辑变量λi 和μi 是连续变量 因此整个系统构成一个混合类型变量系统． 2 清空型调度策略 调度策略的本质可以理解为从多个对象中选择 一个符合某个条件的对象进行服务［6—9］． 第29卷 第9期 2007年 9月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．29No．9 Sep．2007 DOI:10．13374／j．issn1001－053x．2007．09．046