系研一下学期通信网概论讲义

第三章网络的时延模型李辉中国科学技术大学电子工程与信息科学系通信与信号处李辉EEIS,USTC

1/1234Little定理M/M/1排队系统12345567M/M/1排队模型的推广6788李辉EEIS,USTC

2/(顾客源 呼 到达间

李辉EEIS,USTC

4/定义)(机构)所组成（如上图基本组 顾客源顾客的到达率、到达间隔到达方式。等待队列可容纳的顾客数目、顾客的离去规服务台服务的顺序、优先级等李辉EEIS,USTC

5/排队系统的311)2233先到先服务(FCFS)后到先服务(LCFS)李辉EEIS,USTC

6/2050DGKendallA/B/C[A/B/CA顾客到达过程的概率分布类型(MErHRD和G等李辉EEIS,USTC

7/t0tN(t)时刻tNq(t)时刻tWi第iSi第iTi第i个顾客在系统中花费的时间(TiWiα(t)在时间段[0tβ(t)[0t李辉EEIS,USTC

8/排队系统的主要参数1∫tNt t0NtN=limt→∞λ=lim

=

t→∞ t→∞ λ李辉EEIS,USTC

9/排队系统的主要参数t ∑α(tTiT=limTt=t→∞ t→∞则

Nq李辉EEIS,USTC

10/排队系统的时间图—先到先服务

李辉EEIS,USTC

11/N=Little定理的直观理若离开用户平均在系统中的延迟为T，用户到达率为λ，那么当用户数=λT。李辉EEIS,USTC

13/Little α(t)=在[0,t]内到达系统的顾客数β(t)=在[0,t]内离开系统的顾客数N(t)=α(t)−[0t内平均到达率为λt

α(t)（顾客数秒/t/李辉EEIS,USTC

14/Little∫

α(t)N(t)dt 第i 李辉EEIS,USTC

15/Little∫ α(t)γ(t) N(x)dx

Tt=Nt=γ(t)=γ(t)·α(t)=

李辉EEIS,USTC

16/Little若系统满足平稳稳态平均到达率：λ=limt→∞稳态平均顾客时延：T=limt→∞N=limNt=limTtλt=t→∞ t→∞

定理1(Little定理=N= 李辉EEIS,USTC

17/LittleNq= Ns= T=W+ 李辉EEIS,USTC

18/Little注1(Little定理与排队规则的无关性设a(i和l(i分别是第iα(t) α(t)Ti l(i)− α(t)

α(t)α(t) l(i)(j)

α(t) 用户，设第i个到达用户的离开时间为l(i)(j)j李辉EEIS,USTC

19/Little 只要排队系统达到统计平衡状态，就能应用Little 李辉EEIS,USTC

20/定义µµ

ρ=λS=

李辉EEIS,USTC

21/Little例KN(N≥K)；并假客)，问顾客在大厅内平均停留时间T=?:SLittleNλT,则TLittleKλS则λ可知T李辉EEIS,USTC

22/Little例失型排队系统此时顾客的阻塞率PB KB=(1−式中，KB（KB≤K)PB=1−KB≥1− 李辉EEIS,USTC

23/务过程：服务时间间隔服从i.i.d.负指数分布李辉EEIS,USTC

25/定义排队系统的状态变量或变量组具有Markov性( 性)的排Markov 李辉EEIS,USTC

26/设一个随机过程)τλτ(λτ)n−Pn(τ)=P[N(t+τ)−N(t)=n]

n=0,1,2,··τntn+1−tn概率密度函数p(τnλe−λτn分布函数F(τ)=P(τn≤τ)=1−e t≥李辉EEIS,USTC

27/nSnSnµ分布函数P(Sn≤s)=1− s≥概率密度函数p(Sn1{Sn,n0,1,2,···}2具有 P{Sn>r+t|Sn>t}=P{Sn> r,t≥李辉EEIS,USTC

28/Pi,i+1(∆t)=P[Nt+∆t=i+1|Nt=i]=λ∆t+Pi,i−1(∆t)=P[Nt+∆t=i−1|Nt=i]=µ∆t+Pi,i(∆t)=P[Nt+∆t=i|Nt=i]=1−λ∆t−µ∆t+Pi,i±k(∆t)=P[Nt+∆t=i±k|Nt=i]= k≥李辉EEIS,USTC

29/系统的“状态”是系统中的顾客数)NkN(tk∆t)tk∆t时刻的顾客数。此时系统的一Pij=P{Nk+1=j|Nk=i,Nk−1=ik−1,···,N0==P{Nk+1=j|Nk=i}i,j≥ Pn+m)

n,m≥0;i,j≥ 李辉EEIS,USTC

30/在稳态的情况下，状态n的平均到达率（输入率）必然等于 n- n- 李辉EEIS,USTC

31/全局平衡方程及稳态概率µ1p1λ0p0+µ2p2=(λ1+λ1p1+µ3p3=(λ2+ =λn−1pn−1+µn+1pn+1=(λn+ =其中定义pi=limP[Ntt→∞李辉EEIS,USTC

32/全局平衡方程及稳态概率pk

∏∏

λi

(λ)

=

pk1p=

1−∞ 1∞

k=1系统的稳态概率pnρn(1−ρ（几何分布李辉EEIS,USTC

33/M/M/11

λ N npn nρn(1−ρ)

1− µ−2顾客在系统中的平均时延（利用 T=

1− µ−3W=T−1=λ µ− µ(1−李辉EEIS,USTC

34/M/M/1系统的性能分析442NQ=λW 2

µ(µ− (1−5k5P(N(t)>k)=1

pi=1−(1−ρk+1)李辉EEIS,USTC

35/例某公园的售票处设有一个窗口，若购票者以Poisson流到达，顾每位顾客平均服务时间1.5分钟，求：11223344556系统中顾客数超过4人的概率P(Nt>677李辉EEIS,USTC

36/M/M/1例有2种方案购置计算机，A方案是购一台大型机；B方案是购m台小型机，它的处理能力是大型机的1/m。设要求上机的题目是参数为λ的Poisson流，两种计算机计算题目的时间服从负指数分布，大型机的参数是µ。以T和W比较应选择哪种方案？设ρλ/µ，按A WA=µ(1− TA=µ−李辉EEIS,USTC

37/M/M/1B方案：每台小型机的题目到达率为λ/m ρ=λ/m= WB=(µ/m)(1−ρ)=µ(1−ρ)=TB= = =mTAµ/m− (µ−所以，只从T和W李辉EEIS,USTC

38/采用呼损制( 型)系统，(M/M/m/k截止队长为k)

m李辉EEIS,USTC

40/M/M/m在M/M/m系统中服务员为m系统中的顾客源数n→∞

λk= µk

0<k≤m-m-mm-m-m012012

(m 李辉EEIS,USTC

41/k≤

012λp0=012(λ+

=

+k>

kk

(λ+mµ)pm=λpm−1+

λpn−1=λpn−1=

(λ+mµ)pk=λpk−1+n≤n>李辉EEIS,USTC

42/M/M/m全局平衡方程λ式中ρ

pn<

mmp0

≤n<n≥

李辉EEIS,USTC

43/ M/M/m pn=1， −1pn

p0

mm

p0=]=p01

−

+

·[p0 1

−

+

(mρ)n

]−

]

−1=

+

)−

1−李辉EEIS,USTC

44/M/M/m1顾客到达系统必须等待的概率(所有服务员都在忙

mm

(−ρ)PQ=P(n≥m) pn (−ρ)

上式称为ErlangC，它说明在具有m条线路的交20

李辉EEIS,USTC

45/M/M/mNQ npm+n利用 ρn= 式

p0(mρ)m!mm得

n

(1−

NQ=

−

=

·(1−

33W=NQ λ(1−

44T=1+W=1+ 46/ m46/

李辉EEIS,USTCM/M/m55N=λT=λ+NQ=mρ+ 1−

李辉EEIS,USTC

47/=µ=0.4次)。(1)呼叫到达后排成一队，依次送到空闲线路进行处理(图a)；(2)分别排成三个队列进行处理(图b)。窗口窗口0窗口0窗口00窗口 窗口 窗口0 0 00 0 0图 图李辉EEIS,USTC

48/M/M/m和M/M/1性能比较图(a)是一个M/M/3根据题意：m= λ=2.25,ρ=λ=2.25= 11[

) )]−p0

[

]−+ (2.25)0+(2.25)1+(2.25)+

+(2.25)3·

=

2(等待队长2(4)

×(1−

=33N=NQ+NS=1.70+2.25=李辉EEIS,USTC

49/4455

W=NQ1.70/0.91.89(分钟λTWS1.891/0.44.39(分钟66 P(n≥3)=0.0748×(1−0.75)×3!=将图(a)M/M/3(bM/M/1系统性能计算结果置于下表，可见(a)的性能优于(b)。李辉EEIS,USTC

50/P(n≥3)=李辉EEIS,USTC

51/1M/M/∞系统(服务员→∞) 李辉EEIS,USTC

52/ m- m- (m (m{λp0= n=(λ+nµ)pn=λpn−1+(n+ n≥

λpn−1= n=1,2,··李辉EEIS,USTC

53/M/M/∞

p=

(λ)n

n=1,2,·· 2 (λ 2µ pn=1=p0+ +µ

(pn

p0= λ)nn=1,2,·· µ

N npn

(n−1)!p0= 李辉EE李辉EEIS,USTC利用 T=N=1= M/M/∞系统仅有服务时延，没有等待时延，W=0NQ=李辉EEIS,USTC

55/服务员为m个，系统的容量也为m。

m-

m- (m λpn−1= n=1,2,···,(pn=

λ)n

n=1,2,···,

李辉EEIS,USTC

56/ M/M/m/m系统 pn=1，可[p0

(λ)

]−1

则 pn=∑

0≤n≤ ρ 李辉EEIS,USTC

57/1呼损率：系统的呼损率就是所有m(pn=pm)也就是新到系统的顾客 的概率(阻塞概率即B=pm

上式称为Erlang Erlang 2λL=λB=λe=λ(1−B)=λ(1−李辉EEIS,USTC

58/4Q4Q=1−B= A=λQ=λ(1−55 NS npn

(n−1)!p0=

−

=

1

=(mρ)(1−pm)=因为NQ0，所以N66·µη=(1−·µm

λ=(1−李辉EEIS,USTC

59/77T=N=NS=1= 李辉EEIS,USTC

60/李辉EEIS,USTC

61/例3.8由题意：1/µ=3(分钟),η=(1B)ρ，ρ=λ/mµ。由表3-1，对B≤5%可查出m1= ρ1= η1=m2= ρ2= η2=10×λ1

3λ=200.7625.08(呼叫分钟 可见，要求B降低，则系统可承担的负荷越小，各服务员的效率越低，在相同的B时，m增加，η和ρ都增加，这是统计复用带李辉EEIS,USTC

62/系统容量有限的M/M/m/kM/M/mk(km ，其余条件与M/M/m相同p{ppn[

0pp0

0≤n≤m<n≤]−p0

ρ̸=

k−m

1k

W= m!(1−NQ= m!(1−

(k

λ(1−N=NQ+mρ(1 T=W+李辉EEIS,USTC

63/对不系统(M/M/m/∞)，当到达率与服务率之比值大于窗口m时，顾客的队列会越来越长，等待时间趋于无限大，系统将不能稳定工作。令排队系统的利用系数(排队强度)ρ1=当ρ1<m时，系统是稳定的，ρ1≥m则不稳定。但对于截止型系统M/M/m/k,因为队长(k) 为地限制，即使ρ1>m，系李辉EEIS,USTC

64/例：主备线即 系统(二维主用线备用线设在交换站有两种输出线，A是主用线，B为备用线。当A线被占用时，再有呼叫才用B来传输，如上图所示。到达时间间隔和服务时间分别为参数是λ和µ的指数分布。为系统状态，xA的状态，yB的状态。xy∈{01}。”0表示空闲，”1{00011011}。系统李辉EEIS,USTC

65/例：主备线即 系统(二维 λp00=µ(p01 状态(λµ)p01= 状态(λµ)p10λp00 状态2µp11λp01p 状态 李辉(EEIS,USTC

66/例：主备线即 系统(二维又p00+p01+p10+p11=1，设ρ=λ/µp00

==

(1+ρ)(2+2ρ+ρ2p10=

21+ρ)(2+2ρ+ρ = p01B的呼损率，p10A的呼损率，而p11是系统的呼损率。若A和B不分主备，则成为标准的M/M/2/2系统。李辉EEIS,USTC

67/率（相当于队长等于m的概率pm）m新到达的顾客被的概率，相当于被的呼叫（顾客）阻塞状态的概率p—）mm一般来讲，p—≤m

李辉EEIS,USTC

68/277 1等待修理的平均机器数2需要修理的平均机器数345李辉EEIS,USTC

69/2个工人⇒2服务员⇒m=5台机器⇒顾客容量有限⇒K=5(系统中顾客最多为⇒每台机器进入修理状态的速率即到达率λ=修复率⇒服务速率⇒µ=李辉EEIS,USTC

70/ {P0,P1,P2,P3,P4,李辉EEIS,USTC

71/机修模型—问题的分析11NQ=1×P3+2×P4+3×22N

33

李辉EEIS,USTC

72/机修模型—问题的分析44W= (Little定理55T= (Little定理李辉EEIS,USTC

73/ 第i个顾客的服务时间为Xi,令X{X1X2···,平均服务时间XE{X}服务时间的二阶矩X2服务时间的方差D{X}σ2X2−李辉EEIS,USTC

75/ 1(P- 平均等待时间W

2(1−系统的平均时延TXWX

2(1−平均排队队列长度NQ

=2(1−=系统中的平均用户数NλTλX式中，ρλ/µ

2(1−李辉EEIS,USTC

76/M/G/11若GM(负指数分布)，则有X1/µ,X22/µ2，由P-ρW=µ(1− 2若服务时间是常量，即X1/µ,X21/µ2ρW=2µ(1−等待时间是M/M/1系统的一半。李辉EEIS,USTC

77/第l个用户正在接受t第i个用户到 第i个用户的剩服务时间Ri，此时等待队列中有Ni李辉EEIS,USTC

78/P- 的证明

Ni个用户待服

服务S第l个用户接受剩余服务时间加上排在i用户前的其他Ni：i−1Wi=Ri+Ni个用户的服务时间=Ri 李辉EEIS,USTC

79/P- 的证明第iWi=Ri

i−1Wi=E{Ri}+

∑

=E{Ri}+X·E{式中，Xk和Ni均为 量，令i→∞，W=limi→∞李辉EEIS,USTC

80/定义

定义R=limE{Ri}为平均剩余服务时间(Meani→∞ServiceTime)W=R+XNQ=R+1µ=R式中，NQ=E{Ni},ρ=

1λW=R+µRW=1−ρ

李辉EEIS,USTC

81/t为r(t0的时刻，则[0tRt=

∫r(τ)dτ

(t)22剩余服务时间剩余服务时间

X2XiRt=2

·0 X

XM(t

时间李辉EEIS,USTC

82/P- X(t)X

iRt=2

·达率，第三项为Xi的二阶矩。令t→∞，得R=2可得P-K

W 1−W=2(1−

李辉EEIS,USTC

83/P- 由P-K W∝X2。即使ρ1，但如果X2→∞，则W→∞，一旦 李辉EEIS,USTC

84/n-ARQ返回n-ARQ系统：分组(顾客)到达率为λ，Poisson分组长度相同(1个单位等待重传的最长间隔为(n−1)个单位，在当前分组应答来到前可以最多还可发送n−1个分组，如发送出错则错误分组以及该分组之后的n−1个分组也全部重发。李辉EEIS,USTC

85/n-ARQλPoisson−11(1−p)122次发送成功，1次重传的概率为(1−p)p21+3k1次发送成功，k(1−p)pk3间为1XkP(Xk=1+kn)=(1−李辉EEIS,USTC

86/n-ARQ X (1+kn)(1−p)pk=1

1−2np n2(p+ (1+kn)2(1−p)pk=1 1− (1−利用P- == 2(1−分组在系统中的平均时延：TX李辉EEIS,USTC

87/n-ARQ例假定p=10−3,n=8,则有X=1.008，X2=李辉EEIS,USTC

88/服务员有 分组到休假 时李辉EEIS,USTC

89/服务员有 V1,V2···Vi(i.i.d.)1有一个用户正在接受服务(剩余服务时间R与标准的2服务员正在休假（R为服务员 李辉EEIS,USTC

90/277M/G/1令M(t)和L(t)分别为[0,t]内到达的用户数和服务员 01∫0

(t)

L(t)Rt

r(τ)dτ=

i=1

X2 2=i=(t)

(t)

1L(t) 剩余服务时剩余服务时间

·M(t)+2·t·VX XV 550

X

X李辉EEIS,USTC

91/休假M/G/1−(1−ρ)/Vt→∞R=1λX2+1·(1−ρ)· R VW=1−ρ=2(1−ρ)+2·V

李辉EEIS,USTC

92/时隙FDM和TDM基本的频分复用(FDM)FDM系统：m个信道，到达率为λ/mm(1/µm)每个信道是标准的M/D/1系统ρ=(λ/m)=λ/m= WFDM=2µ(1−ρ)=2(1− 李辉EEIS,USTC

93/SFDM系统(时隙FDM系统时隙宽度τ为m服务员休假一次)，它被称为SFDM将SFDM系统做为一个有 V=m,V2= WSFDM=WFDM+2· m m2(1− 2(1−

李辉EEIS,USTC

94/FDMTDM李辉EEIS,USTC

95/时分复用(TDM)一帧(长度为τ=mTs),由m个时隙片(Ts)每个分组的传输时间为一个Ts(一个单位时间TDM中信道速率提高了m倍，分组的传输时间降为FDM中的1/m(TDM有m个时隙片，FDM分组在m个单位时,

=WSFDM

2(1−李辉EEIS,USTC

96/FDM、SFDMTDMTFDM=m+2(1−TSFDM=TFDM+2 =1

=

(m

2(1− 1李辉EEIS,USTC

97/M/G/1 周 2133221332

时预约时李辉EEIS,USTC

98/用户1的传输时1231321231321 型系统中用户1的到达区型系统仅传送预约分组传输前到达的新分组耗尽型系统将内存中所有到达的分组都 型系统仅传送预约分组传输结束前到达的李辉EEIS,USTC

99/单用户的预约M/G/1X=1/µX2,ρ=第l个预约分组的长度为Vl(是i.i.d的 V，二阶矩为 型系统(m=李辉EEIS,USTC

100/单用 性系统的性第i个分组到达时 第i个分组开始传输时在队列中的等待时间剩余等待时间

预约区间Vl(i)第i个分传输结E{Wi}=E{Ri}+1E{Ni}+E{Vlµ李辉EEIS,USTC

101/单用 性系统的性当i

E{Wi}=E{Ri}+1E{Ni}+E{VlµW=R+λW+V=R+ρW+ µW 1− 1− M/G/1系统相同李辉EEIS,USTC

102/277单用 型系统的性 W

V 2(1− 2 1−如果预约分组的长度为常量A，(V=AV2=A2)W

+A·3−2(1− 1−李辉EEIS,USTC

103/共有 剩余等待时间

分组i传输前的预约区间

第i个分组传输结李辉EEIS,USTC

104/VlVli个分组在第l个用户的预约传输期到达，但属于(ljmodm个用Yi=V(l+1)modm+···+V(l+j)mod

j≥E{Wi}=E{Ri}+1E{Ni}+E{Yi}µ当i→∞，有WRρWYW=R+−李辉EEIS,USTC

105/R=1λX2+1·(1−ρ)· 11 =1λX2+

ρ

11 m李辉EEIS,USTC

106/Yi的时间不同Yi取不同的值。(lj模待j个预约时隙)。

Yi|l,j}

V(l+1)modm+···+V(l+j)mod

j=j>李辉EEIS,USTC

107/Yi数据包属于任意一个用户的概率为E{Yi|lj}中的jE{Yi|l}

1−1m

−

m−j V(l+j)mod 户l的预约时隙中达到系统的概率为V(1−V

m 因此对E{Yi|l}在i→∞时，对l )−Y

ρ+(1−

−1m−jV(l+j)modV V

m

李辉EEIS,USTC

通信网理论基

108/

(m−Y2

1− —

1= =mV2(耗尽型预约系统的平均等待时间VW=

+(m−

+

=(Vl−Vl=

1 V其中V

m

(时隙)李辉EEIS,USTC

109/部 型系统性 也即要多增加mV时延（概率为Y(ρ/m)·mV=3(部 型预约系统的平均等待时间W=

+(m+

+V1− 2(1− +V李辉EEIS,USTC

110/ 型系统还要多增加mV时延（概率−ρ)/m−4( 型预约系统的平均等待时间XλXW=2(1

(m+2− ++V2(1− ++V

李辉EEIS,USTC

111/V设预留时隙为常数A(单用户)，A/m（多用户）,σ2VW +A3−

2(1−

21− W + 1−

2(1−

1− W + 1+

2(1−

1− W + 1+(2−

2(1− 1−李辉EEIS,USTC

112/277λW/m，因此多出的等待时间为λWV ˜W=R+ρW+˜+李辉EEIS,USTC

113/

R+˜ 1−

R+W 1−ρ− 1−ρ−λV1−

1−ρ−λ

(m+ σ2(1−VW=2(1−ρ−λ¯)+2(1−ρ−λ¯)+2V(1−ρ−λ¯)Vµ效平均服务时间为1V所以必须有ρλV1µ李辉EEIS,USTC

114/277 发生的概率是(1−ρ−λV)/m，相应的延迟为因此等效于Y上增加(1−ρ−λV)V (m+2−ρ− σ2(1−W=2(1−ρ−λ¯) 2(1−ρ−λ¯) +2V( ρ−λ)1李辉EEIS,USTC

115/M/G/1n1第n类最低，到达率分别为λ1λ2···λn注解1非强插型优先级排队系统ρ1+ρ2+···+ρn<设剩余平均服务时间为R，仿效P- 李辉EEIS,USTC

116/最高(第1类)W1=R+1NQ1=R+1·λ1W1=R+ρ1W1= 1−2W2=R+NQ1+NQ2+ 2项是最高优先级分组的传输时间32李辉EEIS,USTC

117/利用 W2=R+ρ1W1+ρ2W2+

W2=R+ρ1W1= 1−ρ1− (1−ρ1)(1−ρ1−Wk= (1−ρ1−ρ2−···−ρk−1)(1−ρ1−ρ2−···−

其中R为平均剩余服务时间，对n种业务流取 1iR i2李辉EEIS,USTC

118/kWk

iλi 2(1−ρ1−ρ2−···−ρK1)(1−ρ1−···−kTk=1+T=λ1T1+λ2T2+···+λnTnλ1+λ2+···+λn李辉EEIS,USTC

119/注解例如，有两类业务A和B，到达率分别为λA和λB为µA和µBT=λATA+λBTBλA+如果µAµB，则应给A分配高的优先级，这时用上式可计算出T1T2（T1是A优先级高时的平均时延，T2是B优先级高时李辉EEIS,USTC

120/例2一个分组交换网发送两种类型的分组(λ1(数据分组(到达率λ2)用于运载业务数据(长度l2,l2≫l1)设传输链路的容量为9600bit/s；到达该链路总的分组流是λ=λ1+λ2=6.0(分组秒)的Poisson过程，且λ1=0.2λ,λ2=0.8λ;l1=48bit,l2的平均长度为960bit，平均服务时间为0.1s,方差为0.02。李辉EEIS,USTC

121/277控制分组：1= =0.005s,方差为0，二阶矩1 1X2=25×10−数据分组：1

0.1s,方差为0.02 2X2=2 ρ1=0.006，ρ2=0.48，ρ=ρ1+ρ2= 二阶矩：X20.2X20.8X2≈ 平均剩余服务时间：R=1λ1X2+1λ2X2

W ≈72.4ms,W2 1−

1−

≈李辉EEIS,USTC

122/→

李辉EEIS,USTC

123/注解3强插型优先级排队系统例3(ATM传输系统当多种优先级业务流的分组复接在一个ATM系统时，一个分组通常被分为若干个ATM信元(cell)。当正在传输一个低优先级分组的cell流时，有一个高优先级分组到达，这时将暂停低优先级后，再恢复低优先级分组的cell流传输。李辉EEIS,USTC

124/277在这类系统中，直接考虑每一优先级的平均时延Tk(1/µ和Wk两部分)。到达的第k优先级分组的平均等待时间Wk包括两1k1∼k12k1∼(k−12级分组所需要的服务时间(Wnew,k)T=1+W=1+ +

李辉EEIS,USTC

125/277Wold,k可以按照无优先级M/G/11∼k优先级的分组，忽略第(k1∼n

(式中，R

1

λ

(1−

–

–···−

i22包括了第1∼(k−1Wnew,k

k−

·λiTk=1µi1µ

k−

k>k1，有T1= >， = (1−ρ1−ρ2−···−ρk−1)(1−ρ1−···−ρk李辉EEIS,USTC

126/277 按λ=2(人/小时)的Poisson到达= 中60%属一 ，30%属重病急病，10%是 该门诊部的服务规则是先治疗抢救，然后重病或急病病人，最后是一般(强插)同一级别的按到达先后次序李辉EEIS,USTC

127/G/G/1系统假 队列中的平均等待时间λ(σ2+W≤ 2(1−李辉EEIS,USTC

128/G/G/1队列中的平均等待时间λ(σ2+W≤ 2(1−abσ2到达时间间隔的方差σ2服务时间的方差abλρλ/µ,1/µ李辉EEIS,USTC

129/WktWWk tWk第kXk第kτk第k和第k+1李辉EEIS,USTC

130/G/G/1定义 Y+=max{0,Y}Y=E{Y}Y=Y+−

Y−=−min{0,Yσ2=E{Y2−YY+·Y−=有Y=Y+− σ2=σ2++σ2—+2Y+·

李辉EEIS,USTC

131/277G/G/1系统等待时间的证明Wk+1=(Wk+Xk−τk)+=(Wk+Vk=Xk−Ik=(Wk+Vk)−Ikkk1σ2σ

= ++ −+2(Wk+Vk)+·(Wk+Vk)− = + = = + = +σ+ 李辉EEIS,USTC

132/G/G/1系统等待时间的证明σ2+σ2+σ2= +σ2+2Wk+1· Wk+ 假设存在稳态值，取极限k→∞，则：Wk→W, →σ2,Ik→I,σ2→ 其中I1

σ2+W=

—WIσ2≥0I李辉EEIS,USTC

(2 λ bλ 2(1 2(1

133/G/G/1系统等待时间的证明G/G/1队列系统等待时间的λ(σ2+W≤ 2(1M/G/1

λ(σ2+ W= b 2(1− 李辉EEIS,USTC

134/中心思 1122的组合33李辉EEIS,USTC

136/11pi=limP[Nt=t→∞2nτn−2度来描述pi−=limP[Nτn−=t→∞3nn个顾客被服务完毕离开排队系统后的瞬间时刻τ+3npi+=limP[Nτn+=t→∞李辉EEIS,USTC

137/277,,当求解顾客的阻塞率时，应使用pi李辉EEIS,USTC

138/定理2(pi−(t)=pi(tti概率；pi(t为在任意时刻t排队系统内有i李辉EEIS,USTC

139/Nt为任意时刻t排队系统的队列长度，N(uτ)为区(uτ](τ>u内顾客到达的个数。显然，区间(τ−∆tτ]内有顾客到达的发生等价于N(τ−∆tτ)≥1。又根据泊松过程的无性可知，N(τ−∆tτ≥1发生的概率与时刻(τ−∆t)之前的历史无关，即Nτti与N(τ−∆tτ)≥1相互P[Nτ−∆t=i|N(τ−∆t,τ)≥1]=P[Nτ−∆t=令∆t→0，上式左侧 近于在时刻τ到达的顾客所观察到的队李辉EEIS,USTC

140/ (GASTA,General注更深入的内容请参见：Wolff,R.W.,StochasticModellingandTheoryofQueues,PrenticeHall,李辉EEIS,USTC

141/ 李辉EEIS,USTC

142/ 与时刻n−1{Xn}MarkovP(Xn+1j|Xni)只与现在的条件Xni对于G/M/1系统，任意时刻n在窗口前的顾客数{Xn}不能形成Markov链，因为每一时刻顾客的到达不是泊松分布，n时刻nG/M/1的问题难李辉EEIS,USTC

143/嵌入式马尔可夫链如果设某一顾客（Ck个顾客）nk，在窗口排队的顾客数为{Xnk}，那么Xnk的值完全取决于服务分布，即在时刻nk−排队顾客的转移概率仅由服务分布来决定。Markov链，它通常被称为嵌入式Markov李辉EEIS,USTC

144/嵌入式马尔可夫链+ 务结束的时点(嵌入点)在窗口排队的顾客数为{Qnk}，那么Qnk的值完全取决于到达分布，即在时刻nk+排队顾客的转移概率仅由到达分布（M分布）决定，所以Qnk也能形成M链，同样，它也是嵌入式Markov链。李辉EEIS,USTC

145/qn+n(Cn)令qqnCqxnqqCxnqnCCCC李辉ECC

146/M/G/1{qn+1+

qn+−1+ qn+>

qn+=vn+1qn+qn+1+ 李辉EEIS,USTC

147/M/G/1M/G/1系统中，Cn离开时系统中的顾客数qn+pij=P[Qn+1+=j|Qn+=令αjP(Vn+1j>0，由式(36)p0j=P[Qn+1+=j|Qn+]=P(Vn+1=j)={

i=0,j≥

=

=j+1−Qn+|Qn+==

0

1≤i≤j+李辉EEIS,USTC

148/M/G/1P=[pij]

·····0··00··000··

··αi-αi-αj-012ij

李辉EEIS,USTC

149/嵌入马尔可夫链的状态转移概率服务时间{xn,n≥1}是独立同分布的 为B(xP(Xnx)∫αj=P(Vn+1=j) P(Vn+1=j|Xn+1= 0

P(Vn+1=j|Xn+1=x)

e−λx∫αj0

∫e−λxdB(x)0

e−λx 李辉EEIS,USTC

150/M/G/1因为α0p000，而且M链各个状态是互通的，所以该M链分布{pjj≥0}，而且pj下面用概率母函数求解

pi=

j≥P(z)

李辉EEIS,USTC

151/ z0p0=(p0α0+z1p1=(p0α1+p1α1+··znpn=(p0αn+p1αn+p2αn−1+···+P(z)=p0A(z)+p1A(z)+p2zA(z)+p3z2A(z)+·· [p0z+p1z+p2z2+p3z3+···z

0=A(z)[p(z−1)+0z李辉EEIS,USTC

152/解关于P(z)P(z)=(1−A(z)−将A(z) αjzj以及αj代入式(41)，可P(z)

∫1[p0(z−1)+ 1 0

e−λ) ∫

[p0(z−1)+ e−λx

z0∫ −

λz [p0(z−1)+ z0

x·ezx李辉EEIS,USTC

153/令B∗(s)是b(x)的 ce-Stieltjes变换(LST)，∫B∗(s) b(x)e−sx s=(λ−0则P(z)=1[p0(z−1)+P(z)]B∗(λ−zP(z)

p0(z−1)·B∗(λ−z−B∗(λ−李辉EEIS,USTC

154/再利用pk的归一性，求则P(1)

P(1) pj=0[p(z−1)·B∗(λ−λz)0z−B∗(λ−{

p0[B∗(λ−λz)−(z−1)λB∗(1)(λ−1+λB∗(1)(λ−

=1=1λB∗(1)(0)1+p0

李辉EEIS,USTC

155/M/G/1LSB∗(0)=∫B∗(1)(0)=

−xp0=1−λE[xn]=1−李辉EEIS,USTC

156/M/G/1ρ1(1−ρ)(z−1)·B∗(λ−P(z)

z−B∗(λ− b(xB(sP(z展开成z的幂级数，这级数中zj的系数就是xn李辉EEIS,USTC

157/277M/G/1根据LS∫B(r)(s) (−x)rb(x)dx=(−1)rM0式中，MrE[xr]xrN jpj= =

–=ρ =ρ–

λ2σ2+2(1−式中，M2E[x2x2，方差σ2E[x2−李辉EEIS,USTC

158/

M/G/1 λ2σ2+T=λ=µ+2(1−ρ)=µ+2λ(1− =N−=W

λ2σ2+) =2(1−ρ)

2λ(1

N λ2σ2+NQ=λW=2(1−ρ)=2(1− 注式(46)即为P− 。可见W,T,NQ,N都仅仅依赖于ρ和李辉EEIS,USTC

159/277M/G/1系统的特例例4(M/M/1系统b(x)=

=1 M2=代入式(44∼47)N=

1− 1− )T=µ+µ(1−ρ=µ(1)1 W=µ·(1−NQ=(1−李辉EEIS,USTC

160/例5M/D/1系统b(x)=δ(x− M1= M2= λa=代入式(44∼47)

ρ 2(1− 1−N=ρ N=ρ

1− 2−T=µ+2(1−ρ)=µ+2µ(1−ρ)=2µ(1− W=µ·2(1−

NQ

2(1−M/G/1ρ不变时，NTσ2数分布（D分布）σ20，N与T李辉EEIS,USTC

161/τn服从负指数分布，其pdfa(τ)= (τ≥服务时间xn服从k阶Erlang分布，其pdfb(x)

(k−

(x≥E[X]=1,D[X]=1,k= kErlang李辉EEIS,USTC

163/口(参数为 务的时间是负指数分布(服务时为走过了 李辉EEIS,USTC

164/M/Er/1012kj 012kj

p= (λ+kµ)pj=

j=1≤j<(λ+kµ)pj=λpj−k+kµpj+1j≥李辉EEIS,USTC

165/M/Er/1(λ+kµ)pjzj= 1≤j<(λ+kµ)pjzj=λpj−kzj+ j≥将稳态方程两侧同乘以zj，再相加，求母函数P(z) ∞∞

(λ+kµ)pjzj

λpj−k pjzj

zj+1+zk

(λ+kµ)[P(z)−p0]=kµ[P(z)−p1z−p0]+z李辉EEIS,USTC

166/M/Er/1由方程以及λp0kµp1kµp0(1−1P(z)= =zλ+kµ−λzk−z

kµp0(1−kµ+λzk+1−(λ+

由P(1) pj=1，

kµp

1罗必达法则p01−λ1− 式中ρ=

P=1−p0 李辉EEIS,USTC

167/277M/Er/1将p0=1ρ代入式(48)P(z)= kµ(1−ρ)(1− = kµ(1—ρ)(1−z)λkµ+λzk+1−(λ+λ

λkµ−(z+z2+···+zk)(1当k=1时 M/[λ当k>1时，上式分母为λ(1 λ

––

k个不同z1z2···zk|zl|1l12··· λ zl=

(1 李辉EEIS,USTC

168/M/Er/1z0 =(−1)k+1z1z2···

P(z)

1−

(1

zP(z)=(1

)(1−)李辉EEIS,USTC

169/M/Er/1Al

11 zl1

Al=1利用∑∞xj=1 P(z)=(1−

(z)

=(1

–

jzjj

l=1 所以，p=(1−ρ)∑ − j=0,1,2·

l=1·李辉EEIS,USTC

170/设一顾客到达时，系统中已有j个相位，且一个相位平均需要服务时间1/kµ。于是，jj/kµ。故新到达的顾客平均等待服务的 dP( W pjkµ= {

}1 −[kµ+λzk+1−(λ+kµ)z]−(1−z)[λ(k+1)zk−(λ+kµ)]1[kµ+λzk+1−(λ

–

(z−1)λk(k+1)zk−1(1−W=2[kµ+λzk+1−(λ+kµ)z][λ(k+1)zk−(λ

[λk(k+1)zk−1+(z−1)λk(k+1)(k−1)zk−2](1−= 2[λ(k+1)zk−(λ+kµ)]2+2[kµ+λzk+1−(λ+kµ)z]λk(k+1)zk−1(k+=2kµ(1−李辉EEIS,USTC

171/M/Er/1W=(k+1)ρ=k+1 2kµ(1− µ(1T=W+µ

−µ(1−

(k−2kµ(1− (k− (k+N=λT=1−ρ−2k(1−ρ)=ρ+2k(1−k+ NQ=λW

(1k增加时，WNNQ会减少ρ)收敛。(k→∞k+1→李辉EEIS,USTC

172/M/Er/1当k→∞时，Er→D 2−W T2 2ρ−NQ→2(1− N→2(1−

r(1)r于M/Er/1李辉EEIS,USTC

173/的平均时间为0.75分钟，且服从k=25的爱尔兰分布，求：1122 0.72分钟、k=2李辉EEIS,USTC

174/批量到达排队系统λ(k)对每个顾客的服务时间服从参数µ的指数分布gi=P[X=i]，X是顾客群中所含的顾客数λgi=λ·gi，λgi为包含i个顾客的按批到达的速率Mk/M/1系统的状态转移图如下：g ggggggggg ggggk k k k

李辉EEIS,USTC

175/

(λ+µ)pk=µpk+1λp0=

k−1pi

(k≥(λ+ pkzk

µz

pk+1zk+1+k=1

kzz∞−

=

3k=1i i=0k−1

k=1

k−i

zk=

=

李辉EEIS,USTC

176/ 令P(z) pizi，G(z) (λ+µ)[P(z)−p0]=µ[P(z)−p0−p1z]

P(z)= µp0(1− µ(1−z)−λz[1− P(11，可计算p1−ρ，其中ρ=λG′(1 P(z)= µ(1−ρ)(1− µ(1−z)−λz[1−P(zpjpn(比较繁杂)李辉EEIS,USTC

177/必须等待这n个 S

iP[该顾客在k个当中排在第i位µ k=

µ×k 李辉EEIS,USTC

178/T E[|顾客到达系统时队长为n·pn=0 k+ k+ k+=

·pn=µ+

k+ T=2(µ−

µ>N=λk(k+2(µ−

µ>李辉EEIS,USTC

179/如果k是一个 T=n与k已知，整批顾客平均逗留时间的总和E[Tk|nkE[Tk|n,k]=kn+k(k+ 再将k为已知的条件去掉，即将k看作一个 nE[k]+E[k2]+E[Tk|n]=E(E[Tk|n,k])

李辉EEIS,USTC

180/再将n改为 E[Tk]=E(E[Tk|n])

N·E[k]+E[k2]+ 将上式代入T=E[Tk]N=T·T=

=2N·E[k]+E[k2]+2µ·=T·λE[k]+E[k2]+E[k] E[k2]+ 2µ· 2(µ−λE[k])·李辉EEIS,USTC

181/277李辉EEIS,USTC

183/李辉EEIS,USTC

184/277”李辉EEIS,USTC

185/李辉EEIS,USTC

186/ M/M/1组成的级连排队模型，Q1的离去过程Q2的到达过程，到达Q2的分组间隔将与分组长度有关，◦ 李辉EEIS,USTC

187/

/(1++

p/(1

/(1

假设µ≫λ，且被服务完毕的顾客以p≈1的概率反馈到输入端， 李辉EEIS,USTC

188/Kleinrock是 (UCLA)教授，在早期1960年代的研究中在排换和互联网的数学基础。1969年在其UCLA的 nets 李辉EEIS,USTC

189/2i2iijxs 1j3路(ij∑λij 所有经过(ixs是s李辉EEIS,USTC

190/277李辉EEIS,USTC

191/277Nij= µij−式中，1/µij(ij上的平均分组传输时间。

N

–

1 1T=

–

=

李辉EEIS,USTC

192/277∑γ s 时延之和dij，1T (Nij+λijdij γ ( ·Tp·

p上所链路(i,

(µij−

+dij

123项是处理与李辉EEIS,USTC

193/277例如图所示网络，由节点A通过链路L1和L2向节点B发送数据。链路服务速率为µ，节点A的到达是速率为λ的Poisson过程。如何在L1和L2两条链 李辉EEIS,USTC

194/27711L1L2上的分组流都是泊松到达，且与分组长度无关。每条链路都是到达率为λ/2的M/M/1队列，利用M/M/1的结果，可得数据分组的平均时延为TR= = µ− 2µ−李辉EEIS,USTC

195/22TM=1+ = 2µ− (2µ−λ)(1+但是它破坏了各队列的Poisson特性，这时若采用M/M/1影响Kleinrock的独立性近似的准确度。李辉EEIS,USTC

196/277定义Markov链{Xnn012···，其状态转移概率为Pij，稳态分布为pj>0j≥0，假定该Markov链处于稳态，即对所有的n有P{Xnj}=pj，若对于所有的状态i和jP∗Pij，则称此Markov链为时间可逆Markov其中P∗P{Xm

=i}，Pij=P{X

j|Xmi} 续时间随机过程(Xt1,Xt2,···,Xtn)，如果其反向过程(XT−t1,XT−t2,···,XT−tn)的概率分布与正向过程一致，则称该随李辉EEIS,USTC

197/277{X1X2···Xn−1,XnXn+1···,它的反向链{···Xn+1XnXn−1,···X2X1}，也是一个MP∗=P{Xm=P

=i,

=i2,···,

==P{Xm=j,Xm+1=i,Xm+2=i2,···,Xm+k=P{Xm+1=i,Xm+2=i2,···,Xm+k==P{Xm=j,Xm+1=P{Xm+1==P{Xm=j|Xm+1=李辉EEIS,USTC

198/P∗= =

=i}=P{Xm=j,

=

m

==P{Xm=j}P{Xm+1=i|Xm=P{Xm+1==pj

i,j≥即piP=p

比例(piP)。如果正向链路和反向链路的转移概率相同∗=Pij)Markov李辉EEIS,USTC

199/11 2若能找到一组正数pi,i≥ pi=1，并且由下式形成一2=i==i=

PP

0,1,···P∗=pjP

i,j≥则{pi|i≥0}

pj

=

∗=P P式中，pi=limP[Xn=i]为该Mn→∞李辉EEIS,USTC

200/277反向链的特征(续3一个3piPij=因此，根据时间可逆性的定义(P∗=Pij

=令δ→0。李辉EEIS,USTC

201/{pj|j≥0}，对所有的j有pj>011q∗=

i,j≥ ∑2若能找到一组正数pi,i≥2i

pi,并且对所有i≥0p q∗ j

i,j≥0满 q

李辉EEIS,USTC

202/3则{pi|i≥03∗ qij

44piqij= i,j≥李辉EEIS,USTC

203/1231231234qq23qqq01qq567李辉EEIS,USTC

204/对于一个时间可逆的Markov链，局域平衡方程成立，即piPij=pjPjiMarkov过对于李辉EEIS,USTC

205/277李辉EEIS,USTC

206/定理3Burke定理在M/M/m排队系统中，顾客的到达率为λ，每个服务员的服务µλmµ(初始分布为平112程无关(相互独立)。2李辉EEIS,USTC

207/11证明：当队长为n时，设有顾客离去的概率为an∆t n=an 0≤n≤mµm<

λ′ 李辉EEIS,USTC

208/[λ′

p0

λ) (mp(m

)−1

=λ

=1− 李辉EEIS,USTC

209/277Burke(续22tt之前的离开过李辉EEIS,USTC

210/277 tQ1Q2N1(t与N2(t李辉EEIS,USTC

211/例7两级串联排队问题(信息转接输入数据流仍为Piosson过程，到达率λ，A节点输出链路的服务率为µ1，B节点输出链路L2的服务率为µ2 令r和s分别表示L1和L2之前的排队长度(据包)，将r和s李辉EEIS,USTC

212/M/M/122122李辉EEIS,UST122

213/两级M/M/1串联排队系统分析r=s=s=r=

λp0,0=(λ+µ1)pr,0=λpr−1,0+(λ+µ2)p0,s=µ1p1,s−1+

r>0,s>

(λ+µ1+µ2)pr,s=λpr−1,s+µ1pr+1,s−1+∞

pr,s=1解上述方程组时可试用pr,s=p0,0xryss=0

y=λ/µ2=x=λ/µ1=李辉EEIS,USTC

214/两级M/M/1串联排队系统分析1∞1因

pr,s=

s=0

ρ=ρ=1=

r=0

r1 0,0

–

– p0,0=(1−ρ1)(1 r,) 李辉EEIS,USTC

215/rs（N1(tN2(t)）量Ts=Ts1+Ts2= + µ1(1− µ2(1−信道利用率分别为ρ1和ρ21η=2(ρ1+ρ1和ρ21李辉EEIS,USTC

216/个独立M/M/m排队节点稳态概率分布的乘积(productform)，这就是著名的Jackson定理。李辉EEIS,USTC

217/1957年，J.R.Jackson李辉EEIS,USTC

218/277定下一节点的路由概率为pij)或者以概率pjd=1 李辉EEIS,USTC

219/JacksonJackson网络由k个FIFO单服务员队列组成,李辉EEIS,USTC

220/ 过程，且在网络中至少有一个jrj>0

=1

队列j的总到达率λj是rj与来自其它队列的顾客到达率之和 λj=rj

j=1,···, λj=qsjλ

λ

qid

∃i,qid>0(保证式(59)有唯一解 李辉EEIS,USTC

221/李辉EEIS,USTC

222/李辉EEIS,USTC

223/定理4(Jackson定理j1···K，则对所有的n1n2···nK≥0P(n)

nj≥ P(n)=ρnj(1−ρ ρj < µ µj式中，P(nP(n1n2···nK表示j李辉EEIS,USTC

224/2771122则系统顾客数的稳态分布由K个独立的M/M/1队列决定，队列λj=rj

j=1,···qid

qij=

李辉EEIS,USTC

225/n=(n1,n2,···,11n(j+)=(n1,n2,···,nj−1,nj+1,nj+1,···,22n(j−)=(n1,n2,···,nj−1,nj−1,nj+1,···,3单个用户从Qj转到3n(i+,j−)=(n1,n2,···,ni−1,ni+1,ni+1,···,nj−1,nj−1,nj+1,···,李辉EEIS,USTC

226/qn(j+)=∑qn(j)=µ(j1 iqn(i+,j−)= λ µjP(n)= qsjP(n−Ij) qjdµjP(n+

+

j=1李辉EEIS,USTC

227/277Jackson(P(n−Ij)表示系统已处于(n−IjP(n1,n2,···,nj−1,nj−1,nj+1···,P(nIj代表P(n1n2···nj−1,nj1···nk)P(nIi−Ij代表P(n1n2···ni1···nj−1···nk)从李辉EEIS,USTC

228/Jackson(处于(nj−1状态的j从外部到达一个分组；处于(nj−1状态的j从i到达一个分组（i原处于(ni1李辉EEIS,USTC

229/Jackson(

λi

λ λjP(n−Ij)=λiP(n−Ij)=µiP(n+Ii−

李辉EEIS,USTC

230/Jackson(证明:将式(65)代入式(64)λP(n)

λjP(n−Ij)=

qsjP(n−Ij)

+

P(n+Ii−j=1λP(n)=

qsjP(n−Ij)

qjdµjP(n+Ij+

qijµiP(n+Ii−Ij)

λjP(n−j=1 李辉EEIS,USTC

231/Jackson(利用式(59)和(66)λP(n)=

qsjP(n−Ij)

qjdµjP(n+I+

qijλiP(n−Ij)

(λqsj

j=1λP(n)

qjdµjP(n+式(65可知λjP(nµjP(nIj)Kλ K

足式(64)的平衡方程，表明P(n李辉EEIS,USTC

232/Jackson(将式(65也即:λjP(n−Ij)=µjP(n)P(n)=λjP(n1,n2,···,nj−1,···,重复nj(P(n)

)λjλ

P(n1,n2,···,0,···,P(n)

K

)λjλ

李辉EEIS,USTC

233/Jackson(求P(n的和，并令所得的和为1∑P(n)=P(0)S=n λ λS ∞KS

ρnj (1−ρjj=1nj=0

李辉EEIS,USTC

234/Jackson(

P(n) (1−

λj=rj

j=1,···,显然，以上是用“一个源-目的对”证明的，但式(68)可推广到具有Poisson到达率和指数服务率的任何开放网络（需要µj相互李辉EEIS,USTC

235/ Jackson排队网络分成K个独立的M/M/m排队模型来分析； 李辉EEIS,USTC

236/277开放型排队网络时延计算例一个r2=2( 12( 1(3222(743 65(744 r5=李辉EEIS,USTC

237/277开放型排队网络时延计算图中ri表示节点i的Poisson到达率 求得此负荷)。µ=3（分组秒李辉EEIS,USTC

238/开放型排队网络时延计算L13(1→2→3E[T13]= + = µ− µ−L14(1→5→4

3−

– –E[T14]= + = 7µ− µ−λ547L14(1→5→2→4

3−

3−E[T14]= + + = µ− µ− µ−

3−

–3− –李辉EEIS,USTC

239/277虚电路网络的平均网络时延223145D源S源点

第1 第2 第M目 李辉EEIS,USTC

240/虚电路网络的平均网络时延 rE[T]=E[n]

E[nii上排队(包括正在服务)李辉EEIS,USTC

241/虚电路网络的平均网络时延E[ni]=式中，Ti= µi−E[T]

1r

λiTi

1r

λµi−李辉EEIS,USTC

242/277反馈网络的例子例例求下图所示计算机系统的总任务数N和总平均时延p21++ ++I/O(CPU)任务到达过程是速率为λ的PoissonCPU处理完的任务以概率p1离开系统。李辉EEIS,USTC

243/277反馈网络的例子λ1=λ+ λ2=(1−p1)λ1=则λ1λ/p1,λ2令ρ1=λ1/µ1,ρ2λ2/µ2,利用JacksonP(n)=P(n1,n2)=ρn1(1−ρ1)ρn2(1− 在形式上等效为两个M/M/1队列李辉EEIS,USTC

244/277反馈网络的例子因而CPU和I/ON= N2= 1− 1−

ρ2 N=N+N 1− 1−李辉EEIS,USTC

245/277反馈网络的例子T=N= + λ(1− λ(1−= + λ(1

+

λ(11

p2µ2S1− S2−式中：S1=p1µ1S2=p1µ2李辉EEIS,USTC

246/为了说明该问题，设上例中p1=p2=1/2,µ1≫µ2,即CPUI/O时间主要由等效的I/O李辉EEIS,USTC

247/Jackson过程，但是每一个节点队列的总到达过程不一定需要是Poisson

/(1++

p/(1

/(1

李辉EEIS,USTC

248/Jackson假设µ≫λ，且被服务完毕的顾客以p≈1内再次反馈到排队系统的输入端，并同时出该顾客的再依次类推可知，一个顾客的到达会出一串到达，使排队李辉EEIS,USTC

249/277Research,vol.5,no.4,pp.518-ManagementScience,vol.10,no.1,pp.131-(2002)J.Jackson,”Hownetworkofqueuescameabout,”OperationsResearch,vol.50,no.1,pp.112-113.李辉EEIS,USTC

250