第2章 网络排队模型和自相似通信量
1．泊松过程的报文到达间隔是连续随机变量，它的概率分布为：
一λt
F（t）＝1一e 则到达时间间隔的概率密度函数为：
一λt
α（t）＝ d F（t）/ dt ＝λe
这是负指数的概率密度函数。到达间隔是负指数分布的连续随机变量。
证明，平均到达时间间隔:
a1＝
??t α（t）dt ＝ 1/λ
0答案：
用分部积分证明
a1＝E
( t ) ＝
???0t α（t）dt ＝
?0tλe
一λ
t
dt ＝ —
??λ
t
0t d e
一 ＝ —[ t e
一λ
t
?0 —
??t
0e
一λ
dt
] ＝ 0 +
??λt 0e一dt
＝ —1/λ
??一λ
—1/λ
??t
0 e
t
d（—λt）＝ 0 d e
一λ
＝ —1/λ e
一λ
t
＝ —1/λ（ 0 — 1 ）＝ 1/λ
2．条件同1题，证明，到达时间间隔的方差为：
σ2a ＝??0 t 2 α（t）dt － a21 ＝ 1/λ2
答案：
证明
σ
2?a
＝ E( t
2
) — E 2
( t ) ＝
?0 t 2 α（t）dt －1/λ2
?上式第一项（采用分部积分）＝
??2
0 t α（t）dt ＝
?0 t 2 λ
e一λtdt
＝－
??0 t 2 de
一λ
t
＝ —[ t 2 e
一λ
t
?0 —
??λt 20e一d t ]
??＝0 +
?0e
一λ
t
d t 2
＝2
?0 t e
一λ
t
d t＝ —2/λ
??t
0 t d e
一λ
?＝ —2/λ[t e
一λ
t
?0— ?λt 0e一d t ]
?0
＝ —2/λ（ 0 —
???0e一λt d t ）
（1/λ）＝2/λ
2
＝ 2/λ所以
?0e一λt d t ＝2/λ
2
σ
2a
＝ E( t
) — E 2 ( t )
t 2 α（t）dt －1/λ
2
＝
??0＝ 2/λ－1/λ
22
＝ 1/λ
2
3．分组交换网中所有信道（链路、线路）容量加倍，也使用户数加倍（假定每个用户所在位置添一个用户，从同一个结点入网，其数据的目的地也与该位置原来那个用户的目的地相同），每个用户的数据量不变。采用固定路径（新添用户的报文路径与该位置原来那个用户的报文路径相同），从任何结点进入的报文流均为泊松流，具有相同的负指数长度分布，平均长1/μ。计算前后两种情况下全网平均时延间的关系。
答案：
这是一个M/M/1模型。计算结果如表2-1：
表2-1：
i链服务率 i链报文到达率 全网报文到达率 全网平均时延 先前 当前 C i /(1/μ)= μC i λi γ i链平均时延 E(T i )=1/(μC i -λi) i链队长 E(N i ) =λi E(T i ) =λi /(μC i -λi) E(N) =2C i /(1/μ)= 2μC i 2λi 2γ i链平均时延 E(T i )’ =1/(2μC i -2λi) =0.5 E(T i ) i链队长 E(N i )’ =2λi(0.5)E(T i ) = E(N i ) E(N)’ ==E(T)=E(N) / γ ?i E(N i ) ?i E(N i )’ ?i E(N i ) = E(N) E(T)=E(N) / γ E(T)’=E(N) ‘/ 2γ= 0.5E(T)
即全网平均时延减半。
4．分组交换网中所有信道（链路、线路）容量增加到原来的N倍，用户数也增加到原来的N倍（假定每个用户所在位置添N一1个用户，从同一个结点入网，其数据的目的地也与该位置原来那个用户的目的地相同），每个用户的数据量不变。采用固定路径（新添用户的报文路径
与该位置原来那个用户的报文路径相同），从任何结点进入的报文流均为泊松流，具有相同的负指数长度分布，平均长1/μ。计算前后两种情况下全网平均时延间的关系。
答案：
这是一个M/M/1模型。计算结果如表2-2：
表2-2：
i链服务率 i链报文到达率 全网报文到达率 全网平均时延 先前 当前 C i /(1/μ)= μC i λi γ i链平均时延 E(T i )=1/(μC i -λi) i链队长 E(N i ) =λi E(T i ) =λi /(μE(N) =NC i /(1/μ)= NμC i Nλi Nγ i链平均时延 E(T i )’ =1/(NμC i - Nλi) = E(T i ) /N i链队长 E(T)=E(N) / γ C i -λi) E(N i ) E(N i )’ = Nλi E(T i ) /N = E(N i ) E(N)’ ==?i?i E(N i )’ ?i E(N i ) = E(N) E(T)=E(N) / γ E(T)’=E(N) ‘/ Nγ = E(N) / Nγ= E(T) /N 即全网平均时延减小到原来的1/N。
5．假定报文输入是泊松过程，报文的平均到达率为λ，平均长度为1／μ，但报文长度 分布规律则是任意的（服务机构的能力是稳定的，因此，服务时间的分布与报文长度分布特性相同）。输出信道只有一个（一个服务机构），其容量为C。
2
A是在一个报文的发送 ( 服务 ) 时间Y内，报文的到达数目。A是一个随机变量，A是随机变量A的函数。 证明：
m ＝ E [ A/ Y ] ＝ 答案： 证明如下
2
?AA?1?2(?Y)eA??YA!＝λY ＋λ
2
Y 2
m ＝ E [ A2 / Y ] ＝
其中
?AA?1?2(?Y)eA!A??Y＝λY e
―λ
Y
＋?AA?2?2(?Y)eA!A??Y
?AA?2?2(?Y)eA!A?1A??Y＝λY e
―λ
Y
?AA?2?2(?Y)A?1A!
又其中
?AA?2??2(?Y)A!＝?A?2A?1?(?Y)A?1(A?1)!λ
[(A?1)?1]＝λY
Y
Y
?A?2?(?Y)A?2(A?2)!
＋[?A?2(?Y)(A?1)!]?1?1＝λY e＋e
λ
―1
[ 注：e x ＝1+x+x2/2!+x3/3!+……+xn/n!+…… (―∞< x < +∞)]
所以
m ＝ E [ A2 / Y ] ＝λY e＝λY e
―λ
―λ
Y
＋λY e
―λ
Y
[λY eλY＋eλY―1]
―λ
Y
＋ （λY） ＋λY ―λY e
2Y
＝λY ＋λY 2
2
6．输入是泊松过程，报文的平均到达率为λ，平均长度为1／μ，但报文长度的分布规 律则是任意的（服务机构的能力是稳定的，因此，服务时间的分布与报文长度分布特性相同）。输出信道只有一个（一个服务机构），其容量为C。
2
A是在一个报文的发送 ( 服务 ) 时间Y内，报文的到达数目。A是一个随机变量，A是随机变量A的函数。
Y是一个随机变量，Y的概率密度是b（Y）,Y分布范围：0―∞，按全概率公式：
A ＝E [ A] ＝? m b（Y）dY
22
?0其中，m ＝ E [ A2 / Y ] ＝ 证明：
??AA?1?2(?Y)eA??Y＝λY ＋λ
2
Y 2
A!?2
A ＝E [ A] ＝
2?0 m b（Y）dY＝
?0( λY ＋λ
2
Y 2 ) b（Y）dY
?＝λ
?0 Y b（Y）dY ＋ λ
2
2
2
??02
Y 2 b（Y）dY
＝λ/μC ＋λ ( σY＋ 1/μC ) 答案：
证明如下，一个报文的发送 ( 服务 ) 时间Y的平均值为：
?2
1/μC＝E[Y] ＝
?0 Y b（Y）dY
?σ
2Y
＝E[Y 2 ] ―E 2 [Y] ＝
??0
Y 2 b（Y）dY ― 1/μ2 C 2
2Y
则 所以
?0
Y 2 b（Y）dY ＝σ
＋ 1/μ
2
C 2
??A＝λ?02 Y b（Y）dY ＋ λ
2 Y
2
?0
Y 2 b（Y）dY
＝λ/μC ＋λ2 ( σ
＋ 1/μ
2
C 2 )
7．经一条通信线路到交换中心的报文流的到达过程是泊松过程，平均每分钟240个报文。线路传送速率800字符/s。报文长的分布（包括控制字符）近似为指数型，其平均长为176字符，计算系统性能的主要参数。假定缓冲器的容量足够多。
答案：
平均服务时间为 （1/μ）/ C = 176字符/（800字符/s） = 0．22 s λ＝ 240个报文 / 60 s ＝ 4报文/ s ρ＝λ/μ C = 0．88 利用M／M／1公式，计算
队长 N＝ρ/（1一ρ）＝ 7．33 报文 ;
等待队长 NW＝ρ2/（1一ρ）＝ 6．45报文； 报文排队时延T＝1/（μ C一λ）＝ 1．83 s ; 等待时间 T W＝ρ/μ C（1一ρ）＝ 1．61 s
8．一个车间有5台机器，机器故障间隔为指数分布，平均间隔长为50h，一个工人平均在0.5h内修好机器，假定修理时间也是指数分布。在开工期间，若希望98%的时间机器可以使用，问需几个维修工人？
答案：
这是一个M/M/m问题，求其最优m值，其排队模型如图2-1所示：
图2-1 一个M/M/m排队模型