文档介绍：该【基于分组可调度性的实时QoS保证性能评价 】是由【十二贾氏】上传分享，文档一共【10】页，该文档可以免费在线阅读，需要了解更多关于【基于分组可调度性的实时QoS保证性能评价 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第!!卷!第"期计!!算!!机!!学!!报6789!!)79"
#$%$年"月&'()*+*,-./)01-2&-*/++:;<9#$%$
!
基于分组可调度性的实时!"#保证性能评价
%%#%%%
王高才!李!伟!赖明星
%%#广西大学计算机与电子信息学院!南宁!?!$$$>%
#%#德州南方大学计算机科学系!休斯顿美国德州BB$$>%
摘!要!文中运用随机网络演算中统计流量包络和统计服务曲线表征网络中实时分组到达和服务的随机变化$提
出概率可调度性的新概念$刻画某些弹性实时应用对O7+延时要求$通过研究某一时间间隔到达网络系统的累积
分组的最坏情况延时$测试其是否满足相应的概率可调度性条件来实现实时O7+保证性能评价9概率可调度性是
与实时分组到达时间相关的$因此$提出的方法能实现实时O7+保证下的瞬时特性研究以及研究某一时间间隔累
积到达分组的概率可调度性9文中研究了2(2-网络系统中指数分布和一般分布服务时间下的分组概率可调度性
特征$基于理论结论的数值结果和基于模型的模拟结果是一致的9同时$数值和模拟结果表明概率可调度性在实时
分组的O7+保证性能评价中具有较好的适应性9
关键词!实时O7+保证"随机网络演算"概率可调度性"性能评价
中图法分类号54!$#!!!$%&号!%$9!B#>)+49,9%$%A9#$%$9$%A?!
'()*")+,-.(/0,12,34"-"*5(,1674+(!"#82,),-3((9,:(;"-
#.<(;21,=4143>"*',.?(3:
P0)DDG7=&GH%%!1(P:H#%!10(3HJK=EHJK%%
%%#!"#$$%$&'$()*+,-./01%,"+-2".%3/&$-(.+2$/$4*./5627/28,-92+:$;.//2/5!?!$$$>%
#%#<,).-+(,/+$&'$()*+,-!"2,/",$=,!$*+#,-/7/28,-92+:$>$*9+$/$=?!B$$##%
@=:3),.3!(J<NHQ;G;:R$<N:GS<N7RQT:QLRHU:Q<7LNGQ<HLG88MLNGJK:7VGRRHWG8GJTQ:RWHJK7VR:G8=
<HF:;GLX:<QUMGQ<G<HQ<HLG8<RGVVHL:JW:87;:GJTQ<G<HQ<HLG8Q:RWHL:LSRW:957LNGRGL<:RHY:<N:R:=
ZSHR:F:J<7VQ7F::8GQ<HLG88MR:G8=<HF:G;;8HLG<H7JQV7RT:8GM$GJ7W:8L7JL:;<JGF:T;R7UGUH8HQ<HL
QLN:TS8GUH8H<MHQ;R7;7Q:T95N:;R7UGUH8HQ<HLQLN:TS8GUH8H<MHQR:8G<:T<7<HF:+G<;GLX:<QGRRHWG8$
Q7HJQ<GJ<GJ:7SQLNGRGL<:RHQ<HLLGJU:GJG8MY:TGJTLSFS8G<HW:;GLX:<QI7S8TU:QLN:TS8:TG<GJM
KHW:JR:G8=<HF:HJ<:RWG8UM<N:F:<N7T95N:;G;:RHJW:Q<HKG<:Q<N:;R7UGUH8HQ<HLQLN:TS8GUH8H<M7V
R:G8=<HF:;GLX:<QSJT:R:[;7J:J<HG8THQ<RHUS<H7JGJTK:J:RG8THQ<RHUS<H7JQ:RWHL:<HF:HJG2(2-
J:<I7RX95N:JSF:RHLG8GJG8MQHQUGQ:T7J<N:<N:7R:<HLR:QS8<QHQL7JQHQ<:J<IH<N<N:QHFS8G<H7J
GJG8MQHQ95N:R:QS8<QQN7I<NG<<N:F:<N7TNGQF7R:V8:[HUH8H<M<7LNGRGL<:RHY:<N:QLN:TS8GUH8H<M
7VR:G8=<HF:;GLX:<Q9
A(>B");:!R:G8=<HF:O7+KSGRGJ<::"Q<7LNGQ<HLJ:<I7RXLG8LS8SQ";R7UGUH8HQ<HLQLN:TS8GUH8H<M"
;:RV7RFGJL::WG8SG<H7J
收稿日期!#$%$=$>=#?"最终修改稿收到日期!#$%$=$@=$***@9本课题得到国家自然科学基金#A$BA!$%!$A$"A!$##$A%$A!$>?%&国家'九七三(
重点基础研究发展规划项目基金##$$"&C!#$?$>$#$%$&C!#@%$?%和广西自然科学基金##$%$DE)+2&$%!$%!%资助9王高才$男$%"BA年
生$博士$教授$主要研究领域为计算机网络技术及系统性能评价&随机方法等9*=FGH8!IGJKKG7LGH!MGN779L7F9LJ9李!伟$男$%"A%年
生$博士$教授$主要研究领域为网络模型&安全和可靠性等9赖明星$女$%"@?年生$硕士研究生$主要研究方向为随机网络演算和服务性
能分析9
书
%A?>计!!算!!机!!学!!报#$%$年
又能使延时在可控的范围内$即不会导致到达的实
C!引!言时业务分组的延时超过截止期限而缺乏实际的使用
价值9因此$网络系统通过设置分组可调度性测试机
在过去几十年中$网络O7+这一关键和核心的制$测试接收的分组能否在给定的截止期限内接纳
主题一直是互联网研究的热点9随着互联网的广泛调度$并做出相应的动作响应#如舍弃分组或杀死该
应用和深入研究$对网络系统提供的O7+保证进行进程等%9本文提出分组概率可调度性新概念$通过
性能#如延时和队列长度等%分析就显得非常重要研究某一时间间隔到达网络系统的累积分组的最坏
了$网络O7+保证性能分析对于O7+保证设计&接情况延时$测试其是否满足概率可调度性条件$实现
纳控制和网络规划等有着重要的指导意义*%+9特别实时O7+保证性能评价9这一概念是非常有实际意
地$新一代互联网对O7+实时控制和保证提出了更义的$例如能接受概率O7+保证服务的实时弹性业
高的要求和标准*#=!+$因此$根据网络业务的分布特务通常能容忍一定的延时$而某些数据流对丢失率
点和构成要素的演化特点$为新一代网络中的弹性要求较高$因此运用概率可调度性分析就不需要满
$
实时业务提供适合的O7+保证性能评价方法是不足所有业务中最严格的丢失率和延时要求能为
可回避的研究课题9O7+保证提供更为灵活的性能评价方法9另一方
$
目前$对于O7+保证有两种基本的性能评价方面我们提出的概率可调度性评价方法也为网络系
统O7+保证的性能评价提供了一种新的途径与新
法!确定型和随机型#或统计型%9基于确定的分析网
的研究角度9
络O7+保证就是要计算并给出服务性能确定的上
本文结构如下!在第#节我们给出O7+保证随
界$以此为基础提供保证的O7+传输$称为确定型
*>+机分析的相关研究工作"第!节中提出基于随机网
服务9如果计算评估网络所能提供服务容量的剩
络演算的分组概率可调度性模型和新概念"在第>
余分布$从概率意义上分析O7+$并以此为基础提
节中我们基于概率可调度性的新概念$研究2(2-
供相应的O7+保证$称为随机型服务*?+9由于网络
调度策略下$指数分布和一般分布服务时间的分组
系统中的业务到达通常为突发性较强的随机过程$
概率可调度性的特征"在第?节中给出数值和模拟
因此$网络所提供的服务容量也是变化的"而确定型
结果"最后在第A节中给出我们的结论和未来的研
服务以概率%保证服务性能的上界$即提供最坏情
究方向9
况下的O7+保证$这样会极大地浪费网络资源9随
机型服务则允许业务中极小部分的传输违背设定的
D!!"#保证随机分析的相关工作
服务性能上界$如延时超出某一设定的概率$从而能
*?+9O7+
显著提高网络资源的利用率尽管实时需要由于排队论&有效带宽#:VV:L<HW:UGJTIHT<N%理
网络保证传输过程中确定的分组延时界限来满足用论*A+等在分析网络服务性能方面的局限性#如不能
户要求的最坏情况延时$即保证分组在给定的截止用于运行常见类型调度算法$难以用于多节点的网
$$
期限内被接纳调度但实际上大多数弹性实时业务络系统以及缺乏通用性等%$推动了实时O7+保证
分组都能容忍延时超出最坏情况而接受随机型的服务性能分析的进一步研究9在网络中有效地提供
O7+保证服务$如(4电话分组的延时小于%?$FQ随机型服务必须以服务性能随机分析为基础$从概
及'\56分组延时在#?$FQ以内时$用户不会感率意义上计算&分析实时业务在网络系统中的服务
觉到明显的断续9因此$网络能以一定的概率满足这性能9特别是新一代互联网中多媒体业务和其它的
些弹性业务对O7+延时要求$即实时O7+可在容实时应用日益增长$这些应用对延时和丢失虽然都
忍范围内得到控制和保证9是敏感的$但它们一般能够容忍少量的延时和丢失$
通常$当分组到达网络系统后$&O+#&8GQQHVHLG=因此$提供随机型O7+保证更能适合这类应用9
<H7J$OS:SHJK$+LN:TS8HJK%结构根据分组优先级或随机网络演算#+<7LNGQ<HL):<I7RX&G8LS8SQ$
业务类别等参数确定其所应进入的队列$满足业务+)&%克服了传统理论和方法在对网络性能进行定
O7+级别要求9网络系统为不同级别的O7+分组设量和定性分析时表现出的不足$已广泛应用于网络
定一个概率延时界是非常有实际意义的!一方面$能O7+性能的建模和理论分析中*?$B=%%+9+)&是网络
充分利用网络资源$提高系统的利用率"另一方面$演算#):<I7RX&G8LS8SQ$)&%随机意义的扩展9)&
"期王高才等!基于分组可调度性的实时O7+保证性能评价%A??
基本模型为到达曲线#0RRHWG8&SRW:$0&%和服务曲下的统计下界9弱随机服务曲线I++&*%>+是确定
线#+:RWHL:&SRW:$+&%*>+$到达曲线表征业务在任性服务曲线在概率意义上的扩展$与*CC对应的
意时间间隔累积到达的确定意义的上界$其物理意*C2*%?+的界函数是负指数形式$*C2和有效服务曲
义源于网络O7+的流量整形"服务曲线则对应网络线*+&*%#+都是I++&的一个特例9I++&与+CC和
系统提供给业务的服务容量的确定意义的下界$其K+CC相互组合起来可得到单节点上和整个网络中
物理意义来自实际网络节点中实现区分服务的调度的随机积压和延时界$但I++&没有输出特征&级联
器$例如运行D4+&*\2&2(2-等调度算法的网络属性和单流服务的性质*%A+9随机服务曲线++&*%B+则
节点对业务的服务容量都能用服务曲线模型抽象9能很好地解析以上性质9在随机网络演算的研究过程
在)&中$通过3HJ=48SQ代数能得到延时和队列长中$一种基于3D2#37F:J<D:J:RG<HJK2SJL<H7J%
度的上界以及多节点网络的服务曲线9但是$)&只的+)&占有非常重要的地位$它不属于上述各类随
适用于网络服务性能确定分析$即分析计算网络对机到达和服务曲线$与同样基于3D2的有效带宽
业务服务性能#如时延和队列长度%的确定意义的上具有一定的联系92HT8:R提出了一种基于3D2的
界9在+)&中$对于)&的扩展主要体现在将到达曲随机网络演算*%@+$解决了该类随机网络演算难以满
线和服务曲线两个基本模型扩展到概率意义$分别称足级联属性的问题9总之$分组调度和队列技术使得
为统计流量包络#+<G<HQ<HLG85RGVVHL*JW:87;:$各业务获得与其要求相适应的服务性能$从而最大
+5*%*?+和统计服务曲线#+<G<HQ<HLG8+:RWHL:&SRW:$限度地满足用户的O7+保证$而+)&在研究网络
++&%*B$%#+9基于这两种扩展的模型$+)&将3HJ=O7+保证的概率意义上的延时和队列长度时具有
48SQ代数分析方法扩展到概率意义$能给出较为简很好的优势$更能体现网络服务的实际性能9
洁的时延和队列长度的剩余分布9
在基于+)&服务性能分析中$研究者主要关注E!基于#FG的分组概率可调度性模型
的是服务性能的界&流量模型和服务模型的表示方
法及相应的性能特征9如最早提出的流量模型是我们用到达过程C#+%表示时间间隔*$$+%内到
*%!+
*CC模型$其基函数!#"%]#"^$为线性函数$违达网络系统的累积分组总量大小#用毫秒度量%$即
*+
背概率函数&#$%]@:%$为负指数形式A+CC"则不实时业务分组对网络系统的资源请求A为刻画网络
再限定违背概率函数&为负指数函数$只要求函数&系统中业务分组到达的随机变化过程$我们使用任
的任意重积分收敛A1***!+则把基函数由线性函数意时间区间的累积分组大小#同样用毫秒度量%来表
扩展为通用函数$当&]&#$%$统计流量包络!#"%]示$定义类似文献*?+的统计流量包络A
_%
#"^&#&%时$1**就转化为+CC9+CC可应用于定义CA!统计流量包络!#9%A给定业务分组到
高斯B自相似输入过程$如分布布朗运动A然而实际达过程C#+%$在时间间隔*+$+^9+内到达网络系统
网络中的流量过程很多情况下并非高斯过程$如的实时业务累积分组大小C#+$+^9%对于任意
!BQ<GU8:自相似过程$其突发量的分布为幂函数$并9$+"$均满足概率不等式
*%%+
不满足+CC和1**的积分收敛条件9K+CC则包D-,C#+^9%_C#+%#!#9%-"%_&5#%%
含了非高斯=自相似输入过程$是+CC的扩展$只需则称!#9%为该业务分组的统计流量包络$其中&5表
要违背概率函数&为非负递减函数即可$对&的示相应的最大违背概率A
要求较*CC&+CC和1**宽松很多$D***?+则是类似地$为表征网络系统对到达业务分组服务
K+CC的一个特例$但其在实际应用中需要预先得的随机变化过程及网络系统对业务的服务容量的概
到忙期的界$对于含有延时的网络难以满足9基于最率意义的下界$我们用E#+%表示时间*$$+%内离开
大虚拟积压的F9U9L随机到达曲线*@+不仅具有和网络系统的累积分组大小#用毫秒来度量%$定义类
K+CC一样的优点$还能用于推导解析性能较好的似文献*B$%#+的统计服务曲线A
随机服务模型$但在文献*@+中并没有给出相应的数定义DA!统计服务曲线"#+%A给定业务分组的
值结果A到达和离开过程C#+%和E#+%$若存在非负非减函数
服务模型包括输出特性&级联属性&随机积压和"#+%对于任意+"$均满足
延时保证以及聚合的单流服务等9与服务曲线不同$D-,E#+%"C#+%$"#+%-"%_&9##%
统计服务曲线对应于网络系统服务容量概率意义则称"#+%为该业务分组的统计服务曲线$其中&9表
%A?A计!!算!!机!!学!!报#$%$年
示相应的最大违背概率A如下A
上述定义中$$为3HJ=48SQ代数中的卷积$其定义EA!概率可调度性A给定实时业务分组的
中两个实值函数&和5的卷积定义为对于任意+"$截止期限<$在时间间隔*$$+%内$如果到达网络系
均满足&$5#+%]HJV,&#9%^5#+_9%-A特别地$当统的业务累积分组的虚拟延时界0'#<$则该累积
$#9#+
最大违背概率&%$时$上述统计流量包络和统计服分组具有最大违背概率为&5^&9的概率可调度性A
务曲线转化具有概率%的确定型服务的到达曲线和值得指出的是概率可调度性这一概念对于网络
服务曲线A为了研究网络系统为分组服务的性能$必实时O7+保证的性能评价具有非常重要的意义A分
$
须得到分组的虚拟延时界$我们有以下引理A组如果是在一种确定性的条件下即分组有确定的
*%A+$
引理CA!对于任意的随机变量?和F$如到达时间和确定的服务时间能通过可调度性测试
$
果D-,?&6-#&#6%且D-,F&6-#5#6%$则有机制的分组将被接纳调度网络系统提供了确定型
$#&
D-,?^F&6-#&$5#6%A服务A然而对于某些应用如67\(4电话和高清
%$$
上述引理的证明可参见文献*%A+$我们用0'表电视等分组的延时和丢失都是敏感的但是它们
$
示分组在网络系统的虚拟延时G#+%的上界$又能够容忍少量的延时和丢失A因此为了提高网络
$
0']QS;,HJV,"(!#+%#"#+^"%--#!%系统的资源利用率对于分组的最坏情况延时可以
+"$""$适当放松A在随机环境下$如分组具有随机的到达过
因此$我们有如下定理A
程和服务时间$实时分组的虚拟延时界0'在概率意
定理CA!给定网络系统中实时业务分组到达
义上满足给定的截止期限$仍然是可以接受的A例
过程C#+%的统计流量包络!#+%和统计服务曲线
如$定义!保证了实时分组能以%_#&5^&9%的成功
"#+%$则有
概率完成接纳调度$上述的定义和以下的相关结论
'
D-,G#+%#0-"%_#&5^&9%#>%
很容易推广到多节点网络系统$通过使用3HJ=48SQ
!!证明A!对于G#+%]HJV,0"$!C#+%#E#+^代数能得到多节点网络中概率意义上的延时上界以
'
0%-$如果式#>%成立$则有D-,G#+%&0-##&5^
及相应的统计服务曲线A
&9%$同时
下面我们通过具体的例子说明定义!的应用A
C#+%_E#+^0%
相当多的研究者使用*CC业务模型描述统计流量
]C#+%_C$"#+^0%^C$"#+^0%_E#+^0%
包络$其基函数!#+%]#+^$为线性函数$相应的违
]C#+%_HJV,9"$!C#9%^"#+^0_9%-^
背概率&表示为函数&#$%]@:_%$为负指数形式A如
C$"#+^0%_E#+^0%
文献*B+研究了单节点网络系统中的随机服务特征$
#C#+%^QS;,9"$!_C#9%_"#+^0_9%-^
节点中的直行业务流#5NR7SKN287I%的统计流量
C$"#+^0%_E#+^0%包络和统计服务曲线以及相应的违背概率由下式
#C#+%_C#9%_!#+_9%^!#+_9%_
表示A
"#+_9^0%^C$"#+^0%_E#+^0%_%$
!#+%]#+$&5#$%]@:#?%
##C#9$+%_!#+_9%%^^#C$"#+%_E#+%%^^
@_%$
"#+%]#'_"_'%+$&9#$%]:#A%
QS;,!#+%_"#+^0%-$#%_:_%'
因此有在式#?%和式#A%中$#&$&'分别为直行业务流的平
#%'#%#%,!#%"#%-
G+_0#C+_E+^0_QS;+_+^0均到达速率&突发量&节点服务容量$#"为交叉业务
##$%!#%%^#"#%#%%^
#C9+_+_9^C$+_E+A流#&R7QQ287I%到达速率$'##'_##^#"%)#$则我
'
由定义%&#及引理%$得到D-,G#+%&0-#&5$们通过式#!%得
&9]&5^&9A证毕A!#+%#"#+^"%)#+##'_#"_'%#+^"%#B%
在传统的分组可调度性研究中$研究者通常使我们用"FHJ表示满足式#B%中最小的"值$如果
用最坏情况执行时间或最坏情况延时执行可调度性在时间间隔*$$+%内$存在"FHJ#<$则到达的累积
分析A为提高系统的利用率及更为真实地描述弹性业务流量具有概率可调度性$其成功的概率为%_
业务对网络系统的资源要求$同时放松分组所要求#&5^&9%A
的最坏情况延时$我们引入概率可调度性的概念统计服务曲线"#+%能表征网络系统随机变化的
研究实时O7+保证的性能评价与分析$我们定义服务容量特征$但其分析相对复杂A而确定型的服务
"期王高才等!基于分组可调度性的实时O7+保证性能评价%A?B
曲线尽管为确定意义$不能抽象网络系统的统计资为分组在+时刻的相对截至期限$我们假设其为随
源共享$但所表征的是网络系统服务容量绝对下界$机分布的随机变量A这一截止期限对于实时O7+保
通常与其它业务流量过程无关$只与分组到达和网证的性能评价是非常有意义的$如某些实时分组因
络系统本身提供的服务能力有关$使得相应的服务为无法按时交付而影响交互式应用的使用$因此$我
性能分析更为简洁清晰A因此$我们引入服务曲线们引入绝对截止期限测试分组的概率可调度性$实
(#+%来定义延时的概率上界以及概率可调度性$令现实时O7+保证性能评价A
'
0_]QS;,HJV,"(!#+%##+^"%--#@%此外$分组的延时是指从分组到达网络系统至
+"$""$(
'被服务完成的时间"队列的缓冲区是无限的"系统的
则相应的概率可调度性条件为0_#<$累积分组概
工作是持续型的$即只要队列系统中有作业$系统就
率可调度性的最大违背概率为&5A更为一般的情况
是$为研究在时间间隔*$$+%内累积到达的分组对不会空闲A对于具有泊松到达过程的分组来说$我们
O7+延时要求的均匀概率分布情况$同时考虑概率使用统计流量包络1*!#+%+])+)*$该函数与*CC
'业务模型具有相同的包络功能$给定的违背概率为
可调度性的瞬时特征$我们用0_#+%表示分组中最
_A
坏情况延时#或者最坏响应%期望值$则我们有&5]%$A
'#%,!*#%+*#%+-#%HJC!K!K!C模型下分组概率可调度性
0_+]HJV""$1!+#1(+^""
))
式#"%的物理意义在于!如果通过时间+^"$随我们首先研究33%模型中网络系统的服务
机到达的分组期望被服务的时间不小于1*!#9%+$则性能$如前所述$确定型的服务曲线(#+%表征的是网
在时间+到达网络系统的分组应该期望通过不多于络系统服务容量绝对下界$通常与其它业务流量过
$
时间"的延时能服务完成A例如$对于给定的时间+%$程无关只与分组到达和网络系统本身提供的服务
A#+%
$#+%#+$我们能找到最小值"%并使得1*!#+%%+#能力有关为了获得服务容量绝对下界(的期望
*#%+$'#%值$我们做如下分析!当分组到达网络系统时$定义
1(+%^"%则"%是最坏延时期望值0_+A如果
我们考虑分组的截止期限<为具有随机分布的随一个忙期开始$如果网络系统中没有分组#包括队列
机变量$表示为<#+%$相应的概率可调度性条件为中的和正在处理的分组%$则一个忙期结束A因此$传
'统的忙期是网络系统一直不空闲且没有干扰的一个
0_#+%#1*<#+%+$至少成功调度的概率为%_
*+持续时间A然而$我们所提到在时间间隔*$$+%内的
1&5A网络系统服务容量下界是不同于传统的系统忙期
H!I&I%调度策略下分组概率可调度性的$网络系统的服务容量绝对下界为该段时间内到
达的业务分组提供的服务时间$可能包括多个忙期
文献*%"+研究了2(2-网络系统中有限数量业或者少于一个忙期A下面我们给出3)3)%模型下
务流的网络分解$通过考虑统计*CC包络构造实时分组概率可调度性的重要结论$我们有如下
2(2-网络节点上的输出包络$研究结果表明在相定理A
$)
对较小流数目情况下输出包络和输入包络也是基定理DA!令)]$H]*$"#+%表示满足
)^)^
本吻合的$因此在有限的状态下网络分解是可行的**
下列表达式的最小的"值
分析方法$大大简化了端到端的网络性能分析$并考
I`,/KK
%#%#%#^%#+^%
虑了3)3)%和3)D)%模型的服务特征9下面基于_)^*+^")*"
+#+*%_:*.+a
)^*/*J%KJ$K
2(2-网络$我们研究3)3)%和3)D)%模型业务-
/L%
$#M#M^%%
分组概率可调度性的特征9在2(2-网络模型中我##M%.)H/
!!/.#%$%
A*!*.+
们做如下假设MJ#M^%0
#%*$%
%实时分组在时间间隔$+内进入网络系统如果在时间间隔*$$+%内$存在"#+%#1*<#+%+$则
$
的队列到达服从参数)的随机过程A网络系统服务到达的累积分组具有概率可调度性A
分组的速度为A在后续的讨论中$我们假设网络系
*证明A!令D$$$#6%表示在时间6网络系统处
$
统的服务时间服从指数分布和一般分布该结论也于空闲的概率$N#6%为其忙期分布$则我们有
很容易推广到其它分布A)
D$$$#6%]%_N#6%#%%%
##%分组到达网络系统就会被服务$并且必须*
在它们的绝对截止期限+^<#+%内完成A这里<#+%因为在时间6网络系统处于空闲的概率为
%A?@计!!算!!机!!学!!报#$%$年
D$$$#6%$则在时间间隔*$$+%内$网络系统处于空闲证明A!与定理#类似$令D$$$#6%为网络系统
+在时间6处于空闲的概率$则在时间间隔*$$++内网
时间的期望值为D$$$#6%T6A因此$网络系统所提
1$+
#%$
#+%络系统处于空闲的均值为D$$$6T6A因此网络
供服务容量绝对下界(的期望值可表示为1$
++
)系统对分组提供的服务容量绝对下界1*#+%+的期
!1*(#+%+]+_D$$$#6%T6]N#6%T6#%#%(
1$*1$望值为
很明显$我们有
+
+I"1*(#+%+]+_D$$$#6%T6#%B%
1*!#+%+#1*(#+^"%+)+#N#6%T6#%!%1$
$
1'
为进一步计算需要$我们令D$$$#9%表示D$$$#6%
为计算方便$我们做进一步简化A从文献*#$+$
$'#%*#%+
我们容易得到传统忙期的分布如下!的拉普拉斯变换即D$$$9]OD$$$6A我们可
'#%!
N#6%]从相关文献得到D$$$9如下
/L%'%
#
I`//M#M^%%D$$$#9%]'#%@%
_#)^%"#)^%6##M%.)H9^)_)P#9%
:**a/
**/.+**^%+
/J%,MJ#-T
这里$P'#9%为忙期密度函数P#6%]N#6%的拉普
#%>%T6
把式#%>%代入式#%!%$化简即得到式#%$%A如满拉斯变换A
足该表达式的最小"值用"#+%表示$我们有因此$我们有
"#+%]HJV,"!1*!#+%+#1*#+^"%+-!#%?%+`+#%/
$(_)6)6
""D$$$#6%T6]:N/#+_6%T6#%"%
$*$.
'1/J1$/
根据式#"%$我们有0_#+%]"#+%A通过相关定
$
义$我们得到3)3)%模型下累积到达的分组在时这里N/为N自身的/重卷积A
+
间间隔*$$+%内具有概率可调度性的条件A证毕A*#%+#%
1+]+_D$$$6T6
($
定理#表明了这样一个简单的事实!即对于任1
`+/
_)6#)6%
意时间间隔累积到达的业务分组$我们都能应用该]+_:N/#+_6%T6##$%
*$.
/J1$/
定理研究其分组的概率可调度性A特别地$随着时间
综合式#"%和##$%$我们用"#+%表示满足下式的最
的流逝$某些实时分组所要求的O7+延时变得越来
小值A
'
越紧急$我们通过设置0_#+%#1*<#+%+进行概率
"#+%]HJV,"!1*!#+%+#1*(#+^"%+-##%%
可调度性分析$保证O7+延时在概率意义上满足业""$
务的O7+延时要求A式##%%左边等价于
HJD!K!8!C)+
模型下分组概率可调度性1*!#+%+#1*(#+^"%+)##+^"%_
在>b%节中$我们基于3)3)%模型研究了分*
`+I"/
_)6#)6%
组的概率可调度性$通常$网络中的分组达到为泊松:N/#+^"_6%T6$
*$.
/J1$/
过程$而服务为一般分布的服务时间更具有实际和
经过化简$得到
应用意义A因此$下面我们给出3)D)%模型下分组`
+I"*#%+/
)+_)#+^"_6%)+^"_6*#%+
概率可调度性结论$即服务时间具有概率密度函数#:%_N/6T6
*$.
*/J1$/
#%)$
4+及均值%*我们有如下定理!A###%
定理EA!令"#+%表示满足下列表达式的最小'
根据式#"%$我们有0_#+%]"#+%A因此$我们得
的"值到3)D)%模型下累积到达的分组在时间间隔*$$+%
`+I"/
)+_)#+^"_6%*)#+^"_6%+
#:*%_N/#6%+T6