第三章 网内业务分析

第三章 网内业务分析

上一章涉及到网络的基本结构，但流量假设是平均的，或近似不变的，这在大多数场合是不恰当的。

本章将要应用排队论对通信网（包括电话网，数据网等）建模，进行分析，较多的考虑一些随机因素，主要针对稳态的情形（在B-ISDN中，瞬态的研究具有重大的意义，但需要较深入的数学工具）。

本章先介绍排队论的基础知识，然后分别对电话网，分组数据网建立模型，进行一些优化分析，得到线路容量，交换节点容量等许多结论。

第3.1节 排队论基础

3.1.1排队论

排队论又称随机服务系统，主要解决与随机到来、排队服务现象有关的应用问题。排队论的创始人Erlang正是为了解决电话交换机容量的设计问题而提出排队论。

排队论主要研究三个方面的内容：

（1）形态问题，即研究各种排队系统的规律性，这包括队长分布、等待时 间分布、忙闲期分布等，同时又分稳态和瞬态两种情形。

（2）最优化问题，又分静态最优和稳态最右；前者指最优设计，后者指现 在排队系统的最优运用。

（3）排队系统的统计推断，即判断一个给定的排队系统符合那种类型，以 便根据排队理论进行分析研究。 排队系统的组成包括三个部分：

1.输入过程 2.排队规则 3.服务机构

为了有一个简单模型描述排队系统, 使用点移动模型, 同时有如下基本假设:

(1)到达间隔独立同分布; (2)服务时间独立同分布; (3)服务时间同到达间隔独立; 各部分具体含义为：

1.输入过程是对顾客到来的特征进行描述,包括顾客总体数目，到来方式（单个或成批），到来间隔的规律等。

2.服务规则包括先到先服务（FIFO），后到先服务（LIFO），随机服务，有优先权服务等。

3.服务机构包括服务员数目，服务时间特征等。

排队系统的表示：

一般用X/Y/Z/A/B/C来表示一个排队系统。其中： X表示顾客到达间隔时间的分布，即到达规律 Y表示服务时间的分布，服务规律 Z表示服务员数目，也即窗口数

A表示系统容量限制，也即排队时的截止队长 B表示顾客源数目 C表示服务规则

若略去后三项，即指X/Y/Z///FIFO

第三章 网内业务分析

3.1.2常见分布

分析一个排队系统，首先要知道知道顾客到达间隔和服务时间的分布规律。我们将在本节介绍Poisson分布，负指数分布，Erlang分布等。 （1）Poisson过程

设N(t)表示在时间区间[0,t) 内到达的顾客数(t>0)

令pk(t1,t2) 表示在时间区间[t1,t2)(t2t1)内到达顾客数为k的概率,即:

pk(t1,t2)p{N(t2)N(t1)k} (t2t1,k0)

当满足下列三个条件是，称顾客的到达形成Poisson流，这三个条件是： 1、不相重叠的时间区间内到达顾客数相互独立，称之为无后效性

2、平稳性：在区间[t，t+T)内到达k个顾客的概率与t无关，只与T有关,即 pk(t,tT)pk(T)；

3、对充分小的Δt，在[t，t+Δt)内到达1个顾客的概率Δt成正比，即：

p1(t,tt)t0(t)，>0为常数，

它表示单位时间内有一个顾客到达的概率，也称为到达率

对充分小的Δt，在[t，t+Δt]内到达2个或2个以上顾客的概率为极小， 即：

pk2k(t,tt)0(t)

在以上假设条件下求解设T内到达顾客数为k的概率为pk(T)，将T分成n等分,每一份为Δ

Δ=T/N.................

Δ内有1顾客到达概率--Δ·λ Δ内无顾客到达概率--1-Δ·λ

有2个到达概率--()

2T(=NΔ)

据无后效性和独立性及二项分布, N个贝努利分布，T内有k个到达的概率:

Nknkpk(T)1k

k(T)Tn得pk(T)ek!固定T时,k为离散随机变量，其分布即为Poisson分布，此外：

E[N(t)]Var[N(t)]t

第三章 网内业务分析

顾客到达间隔t--连续变量,求解t的分布

解： 把t分N份，则这N个Δ内均没有到达，但是过了这N个Δ，就有到达 了，所以到达间隔为t的概率为：

(1)N

（N个Δ内无到达，第N+1个必然到达） 若t的密度a（t）存在，则有：

a(t)(1)N

a(t)lim(1)lim(1NNNtN)eNt

或者, 如果T为到达间隔, 由于

p{Tt}et, 所以的概率密度为: et （2）负指数分布

定义：随机变量T的概率密度若为：

t0et　　 fT(t)

t00则称T服从负指数分布，它的分布函数为：

t01et　　 FT(t)

t00 E[T]1Var[T]12[T]1

容易知道，负指数分布满足如下Markov性：

P{T>t+s|T>t}= P{ T>s}

当输入过程为Poisson过程时，由上述（1）可知，顾客相继到达的间隔时间服从负指数分布。

能够证明，反过来也成立，也就得到如下著名结论：

定理3.1一个随机过程是Poisson过程当且仅当其相继到达间隔时间是独立同分布且为负指数分布。

下面的定理3.2描述了负指数分布的性质:

定理3.2 T1, T2代表两个独立的负指数分布, 参数为λ1和λ2, 令T=min(T1, T2), 那么: 1. T是一个以λ1+λ2为参数的负指数分布;

2. T的分布与T1, T2谁是最小数无关; 3. Ti为较小数的概率与λi成正比. 对于多个负指数分布有类似的性质. （3）Erlang分布

设v1,v2,…vk是k个相互独立的随机变量，服从相同k参数的负指数分布，那么，T= v1+v2+…+vk的概率密度为：

第三章 网内业务分析

k(kt)k1ktak(t)e

(k1)!称T服从k阶Erlang分布。 该概率密度是用变换得到的。 此外：

11 E[T]Var[T]2k在实际中，Erlang分布簇提供了更为广泛的模型类： k1时，Erlang分布化为负指数分布 k增大时，Erlang分布逐渐变为对称的； k30时，Erlang分布近似与正态分布；

k时，Var[T]0，所以Erlang分布化为确定型分布；

ak(t)k=11k=3k=2k=1t

综合以上可见：一般Erlang分布可看成完全随机与完全确定的中间型

3.1.3 M/M/Z排队系统分析

本小节将讨论输入过程是Poisson过程，服务时间v服从负指数分布的随机服务系统。设服务时间v的分布函数和概率密度为：

Fv(t)1etfv(t)ett0 t0

1E[v]表示一

其中表示单位时间服务完的顾客数，又称平均服务率，而

个顾客的平均服务时间。

在讨论之前先介绍一下我们要研究的排队系统的参量。 队长k，指t瞬间系统内的顾客数（含在窗口的），也就是排队长度。k是离散随机变量。平均队长k，又称系统数

等待时间w：从顾客到达到顾客开始接受服务的时间，它是连续的随机变量 服务时间v：从顾客开始接受服务到服务完毕离去 系统时间s，或称系统停留时间，从顾客到达到顾客离去的时间。显然有：s=w+v swv

第三章 网内业务分析

对任何排队系统，有s(wv)k 。这就是著名的little公式。 忙期与闲期

yx

如图所示：即y为一个闲期，x为一个忙期。 系统效率：指平均窗口占用率

若共有m个窗口，某时刻有r个被占用，则r/m就是占用率，其统计平均值就是系统效率。即 r m（1）M/M/1问题 1、状态图与状态方程

我们将取队长作为状态变量来建立系统差微分方程。 设pk(t)为t时刻系统内有k个顾客的概率（k=0,1,2, „） 设Δt为足够小的时间段，

则：Δt内到达1个顾客的概率—Δt Δt内离去1个顾客的概率—Δt

那么，系统在t+Δt时刻处于k状态（概率pk(tt)），取决于下述转移： t时刻处于k-1态，Δt内到达1人，无人离去 概率: pk1(t)t(1t)pk1(t)t t为k+1态，Δt内离1人，无到达： pk1(t)t(1t)pk1(t)t t为k态，Δt内到达1人，离去1人: pk(t)t2

t为k态，Δt内无到达，无离去:

pk(t)(1t)(1t)pk(t)(1tt)

状态转移图可表示为：

1-Δt-ΔtΔtk-1kΔtk+1

ΔtΔt

第三章 网内业务分析

1-Δt-Δt1-Δt0Δt1Δt2......kΔtΔt综合以上得：

pk(tt)tpk1(t)tpk1(t)pk(t)(1tt) 即

pk(tt)pk(t)pk1(t)pk1(t)()pk(t)t令t0得导数dpk(t)

pk1(t)pk1(t)()pk(t)dt即柯尔莫哥洛夫方程。 在稳态下：

dpk(t)0 dt即 (dt内进入k态的概率)(dt内离开k态的概率) k=0时, 需重写上述式子:

原有1人,离去1人概率 Δtp1(t)

原有0人,无人到达概率 (1-Δt) p0(t) p0(t+Δt)= Δtp1(t)+ (1-Δt) p0(t) 得:

dp0(t)p1(t)p0(t) dt至此,得M/M/1完整状态方程:

dpk(t)dtpk1(t)pk1(t)()pk(t) 

dp0(t)p1(t)p0(t)dt上式,已由，表示转移，由此可得状态图：

012k............

2、稳态解：

物理意义：系统内顾客的到达与离去达到平衡，系统稳，则pk(t)与t无关 数学描述： t,dpk(t)0,dtpk(t)pk

第三章 网内业务分析

于是得到稳态方程：

pk1pk1()pk0

pp010令得p1p0pk11[()pkpk1](1)pkpk1令k1,代入得 p2(1)p1p0(1)p0p02p0

k2,代入得:p33p0kpkkp01p01

求p0: 用归一化条件, 形式上

1pk(12)p0k0p01有稳态解的条件为 1

p0——系统无人概率（空闲率） 1-p0 = —系统有人概率（忙概率） 忙 太大不稳

得通解：Pk=kp0=k(1-), k0.

下面求解系统各种指标 平均队长k:

kkpk(1)k(1)kkk000k1dk(1)d011(1)(1)2(1)k的方差:

第三章 网内业务分析

k的母函数G(z)p0p1zp2zpkzzkpk2kk0由归一　G(1)pk1又　G(1)kpkk　

　　　　G(1)(kzk1pk)k(k1)zk2pkｚ＝１　　　　＝（k2k)pkk2k　　　　G(1)k(k1)(k2)pkk33k22k　　　所以有:

k的二阶(原点)矩　　Ek2k2G(1)G(1)k的方差（二阶中心矩）

２k(kk)2pkEk2k2G(1)G'(1)[G'(1)]2对M/M/1有　　　　pkk(1)　　　　　　Ｇ(z)(1)kzkk011z(1-)２２(1-)

G(z)　　　 G(z)2(1z)(1z)2k＝2２2(1)2(1)(1)(1)２2如图所示:

k2k0.51

等待时间w

若系统中已有k顾客，再来一顾客所需等待的时间w即为k人的服务时间 即:

w12ki

i1k i的特征函数: (a(t)的付氏变换)

第三章 网内业务分析

Z(z)0eejzdjz

k个i之和的特征函数wk(jz)k

因为k为离散变量,故w的特征函数:

w(z)wkpkk0kk()pk,pk(1),令x()jzk0jz (1)xkk(1)x(1)(1)1x1xk0(1)(1)(1)jzw的密度:

1jzwf(w)w(z)edz2

(1)w(1)(w)(1)e

平均等待时间:

wwf(w)dw0(1)we(1)wdw11(1)22(1)1

w的方差:

2w(2)wf(w)dww22

(1)22

系统时间(平均停留)

sw1

(1)反验Little公式:

s(1)1k

第三章 网内业务分析

系统效率：

1p0

忙期与闲期

设I--闲期平均长度 T --忙期平均长度

因为一个闲期就是系统处于无顾客状态后到有一个顾客到达之间的时间，因而与顾客到达规律相同。 fI(I)ett0

p01IIT11TI1

1T得：T1 设T为足够长的一段时间，

则T内闲期总长为: Tp0=T(1-) 闲期个数(亦即忙期个数) ：

T(1) (1)T

1对于M/M/1系统时间S可以用如下的方法求解，即定理3.3

定理3.3 稳态时, M/M/1的系统时间是参数为μ-λ的负指数分布. 考虑如下计算即可

p{st}E[p{st|N(t)n}](x)[exdx](1)n0n!n0tn

(x)(1)exdx0n!n0tn

1e()t从而，M/M/1的系统时间是参数为μ-λ的负指数分布.

（2）M/M/1/N/问题

这种情况下系统的最大容量为N，也就是最多有N-1个顾客排队的等待。系统如下图所示：

第三章 网内业务分析

排队系统队列顾客NN-1服务员321

当N=时，即为M/M/1，

而N=1时，即为即时拒绝 系统状态图为：

012k......N状态方程：



p1p0k01kN1 pk1pk1()pkpNpN1kN再根据：　仍令pi0Ni1

解得： 1p01N11 1kpkkNN11=1的情形，请读者做为练习考虑。

下面求解系统指标： 平均队长：

(N1)N1knpn11N1n0N(1)

平均等待时间：

第三章 网内业务分析

wkk1N11pkN1k11p0kkk1kN11p0kk1k1N1dp0d11

1NN1(N1)Np0(1)2

系统时间：

sww1

读者可以自己验证公式。

系统效率：

1n1p0

1n1（3）M/M/m(n)问题

现在，我们讨论多服务台（m个），系统容量为n的情形。多个服务台相互独立，服务时间为负指数分布, 且服务率同为; 但总共只有一个队列，到达为参数是的Poisson过程。 状态转移图为：

012m......n

稳态方程:

2mmmk0　　　p0p100km　pk1(k1)pk1(k)pk0mkn　pk1mpk1(m)pk0kn　　　pn1mpn0　归一：　　　　pi1

i0n

第三章 网内业务分析

令:

 m通解:(m)kk!p0　　０kmmmpkkp0　　mkn

m!0　　　　　kn式中:

(m)r(m)m1nm11p0[]

r!m!1r0m1mmnp0 拒绝概率（k=n的概率）：pnm!可见：拒，当k>n时, pk=0有稳定状态, 也就是以拒绝换稳定.

求解各种指标： 平均等待时间w

km　　则w0分三种情况:mkn　　w0

kn　　w只算mkn　情况即可

k=m 等1人

k=m+1 等2 ……

对k 等k-m+1人 所以:

w(km1)kmn1n11pkmkm1mmkp0(令rkm1)mm!km rmmrm1p0m!r1mnm第三章 网内业务分析

nmmm1mp0rr1m!mr1nmmm1mdp0(r)m!mdr1nm1mm1dp0m()m!md1nmmm1(nm)nm1m1(nm1)p0m!m(1)2

系统效率:

当窗口不满 占用率k/m 当窗口满(k>=m) 占用率=1

nk则pkpk k1mkm代入pk可整理出的表达式m1当n,不拒绝多窗口 单窗口(1p0) m1p0

当n=m,即时拒绝

a(1pm)　　(am) m１－n1p0 当m=1时, 系统成为M/M/1(n) 1n1不拒绝系统只能取1,

当1时w, pn1,0系统不稳定

拒绝型系统可以取1,仍能稳定工作,以拒绝概率(呼损)为代价 一定,增加截止队长(n)可提高效率,当等待时间亦长—延迟换效率 所以，若延迟指标允许，用非即时拒绝型是合理的

读者可以演算下面一些特例中的各种系统指标: a）当n=m时，为多窗口即时拒绝系统

b）当n，为非拒绝系统,数学的M/M/m问题

读者可以计算拒绝概率、平均等待数并讨论m=1的情况。 c）当m=1,为单窗口。M/M/1(n)

第三章 网内业务分析

d）当m=1, n为M/M/1

例3.1：请比较M/M/m系统和m个M/M/1系统，其中每个服务员的服务率为。 解：显然单队列比m个队列有优势，因为它能更充分的利用系统资源。 假设=0.9（人/分钟），每个服务员=0.4（人/分钟），m=3，经计算做成下表以示比较： M/M/3 M/M/1 指标 0.0748 服务台空闲 0.25(每个子系统) 1.70 平均队长 9.00(整个系统) 系统时间 4.39分钟 10分钟 在本届中，我们讨论了随机服务系统，但只讨论了稳态的情形；在电话网和数据网中，稳态分析有成功的应用；而在ATM的CAC和交换设计中，瞬态的讨论有极为重要的应用，鉴于瞬态研究的复杂性，我们不做讨论，有兴趣的读者请参看[1]和[2]。

附录：生灭过程

定义：假定有一个系统，该系统具有有限个状态0,1,2,…,k或可数个状态0,1,2,…令N(t)为系统在时刻t所处的状态，在任一时刻t，若系统处于状态i，则在(t, t+t)内系统由状态i转移到状态i+1（有限状态时0ik；可数状态时0i）的概率为: it0(t), i>0为一个常数；由状态i转移到状态i-1（有限状态时1ik；可数状态时1i）的概率为： it0(t)，i>0为一常数；并且在(t, t+t)内发生距离不小于2的转移概率为0(t)，这样一个系统状态随时间变化的过程称为生灭过程。

稳态分析：若pi(t)p{N(t)i}，状态的微分方程为：

pi(tt)pi(t)(1itit)pi1(t)i1tpi1(t)i1t0(t),0ik

取极限得：

pi'(t)pi(t)(ii)pi1(t)i1pi1(t)i1,0ik

'(t)0p0(t)1p1(t)， 特别：p0'pk(t)k1pk1(t)kpk(t)（可数状态时，该方程省去）

若有稳态，那么

limp(t)0,limp(t)p 从而在状态可数时

'iiitt0p01p10

第三章 网内业务分析

ipii1pi1i1pi1ipi,0i  i1pi1ipi,0i

01...j1 pjjp0,0j;其中j12...j01,p0(j)1当然这个是形式上的解。

j0极限定理

对有限状态的生灭过程或满足条件j,j1i11的可数生灭过程，ipi极限分布limpj(t)pj,j0存在，且与初始分布无关。

t许多M/M过程均为生灭过程，应用上面的极限定理可以方便求得稳态分布，同时很便于记忆。

第三章 网内业务分析

（4）M/G/1问题：

设到达间隔为负指数分布：a(t)e布.

用 ci表示第i顾客:

cn到cn+1到t, 服务时间为密度是b(t)的任意分

....qn个vncn+qn到vn+1cn去.cn+1去cn-1去

令qn--第n个顾客离去时，系统内的顾客数。

vn--第n个顾客接受服务期间，到达的顾客数。

共有两种情况：（１）cn离去时cn1未到 （２）cn离去时cn1已到 则相应的有：

1) qn>0 , 有qn1= qn+ vn1-1

cn1去时人数= cn去时人数+ cn1服务期到达数 - 1 (cn1离去)

2)

qn=0, 有qn1= vn1

()ke.b()d k!

一顾客被服务期内到达k人的概率为：

kP(vk)0可得系统的转移概率（条件概率）为：

P(qn1j|qn0)j

P(qn1j|qni)ji1

n令dk表示cn去时观察系统队长为k(不包括cn)的概率，则：

dknP[第n人服务完毕观察k人有]

则有：

第三章 网内业务分析

d0n1d0n0d1n0d1n1d0n1d1n1d2n0 n1nnnndkd0kd1kd2k1dk10稳态下，dk与n无关，得M/G/1的特殊时刻的系统方程

d0d00d10d1d01d11d20d2d02d12d21d30

dkd0kd1kd2k1d3k2dk10

dk的概率母函数为：

Q(z)zk0kdk

k2d0zkd1zkd2zzkd3zkkk0k0k0zkk0k

(d0d1d2zd3zdrz1232r1)zkk

k0rz(d0zd1zd2zd3zdrz)zkkk0z[d0(z1)Q(z)]zkk

1k0z[(d0(z1)Q(z)]z1kk00()keb()d k!z[d0(z1)Q(z)](10k0(z)k)eb()d k!z[d0(z1)Q(z)]ezeb()d

10z1[d0(z1)Q(z)]B(z)

第三章 网内业务分析

得母函数解为：

Q(z)

(z1)d0B(z)

zB(z)下面用dk的归一性求解d0： Q(1) 而：

dk0k1

(z1)d0B(z)Q(1)

zB(z)z1对其应用罗必达法则，上下求导，

再代入1得：

d0B(0)1 Q(1)'1B(0)由拉氏变换得： B(0)

b()d1

B'(0)b()dm1

B''(0)2b()dm2



B(r)(0)(1)rmrd0d0B(0)1由Q(1) '1B(0)1得：d011（令）

已知d0即可写出Q(z)式：

(1)(z1)B(z)Q(z)

zB(z)定理3.4

M/G/1的顾客离去时队长概率的母函数解，它由服务时间密度b(τ)的拉氏变换B(s)所确定, 并且有:

第三章 网内业务分析

Q(z)(1)(z1)B(z)

zB(z)下面求解各种系统指标： 平均队长：

2m2 kkdkQ(z)|z1

2(1)k0'上述母函数解还可求出k的各阶矩：

Q(z)zdkQ(z)kzk1dkk'k0k0zQ'(z)kzkdk[zQ'(z)]'k2zk1dkk0k0

k2[zQ'(z)]'z1等等

M/G/1等待时间W的统计特性

cn到tnwncn+1到τcn-1去ncn去

其中：wi —第i顾客等待时间

i —第i顾客服务时间

tn —第n顾客与第n+1顾客到达间隔

可见：

tnWnnWnntnW n1

　　　0　　　　tWnnn稳态时，

wn分布与n无关，记为W，令其密度p(w)存在，则：

p(x)b()a(t)dtddx(w)p(x)a(t)b()dtdxdtxtp(w)wtwxt0p(wt)b()eddt(w)p(x)b()etdtdxd

0000x第三章 网内业务分析

令wuup(u)b()e(uw)ddu(w)p(x)b()e(x)dxdw000u[p(u)b()d]e(uw)du(w)G()B()

w0式中B(λ)与G(λ)分别为b(τ)与p(x)的拉氏变换，即：

 B()()b()ed 0 G()p(x)e0xdx

为解上述积分方程，（p(x)为所求密度），对左右量端求拉氏变换：

 左端:

0p(w)eswdwG(s)

sw[右端式]edw 0 右端:

ue(s)wdw[p(u)b())d]eudu0w0G()B()G(s)B(s)G()B() ss得

G(s)SG()B()

SB(s)其中G(s)为等待时间w的密度p(x)拉氏变换， B(s)为服务时间τ的拉氏变换 用归化条件进一步求解： G(0)=1

G(0)得

B()G()G()B()G()B()]s01 '1B(s)1[B(0)]1m11()sB()G()1m11d0

实际上, B(λ)G(λ)就是w=0的概率。 最后得w分布密度p(w)的拉氏变换解

第三章 网内业务分析

G(s)s(1)由B(s)确定。

sB(s)定理3.5

等待时间的Laplace变换为

s(1)G(s), 其中B(s)为服务时间的Laplace变换.

sB(s)这样可以计算一些结果如下

wG'(s)|s0其中m2为τ的二阶矩，m2=B''(0) 同时可求w的各阶矩及方差

m2

2(1)2ww2(w)2G''(0)[G'(0)]2

2m32m2  23(1)4(1)

例3.1以M/M/1为例，有： B(s),B'(0)1m1,B''(0)22

s2(m1) w2(1)(1)如果为M/D/1有，m2b2

b2bw2(1)2(1)2第三章 网内业务分析

（5）G/M/1问题

设到达间隔为密度是a(t)的任意分布, 服务时间为负指数分布：

b()e.

令tn——cn与cn1到达间隔

vn——tn内服务完毕（离去）的顾客数 qn——cn到达时观察到的队长（不含cn）

k——tn内离去k个的概率

则：

kp[vnk]()k(k)A()k!其中：

0(t)ktea(t)dtk!

A(S)L[a(t)]A(k)0a(t)estdt,

dkA(s)　　　　(A(S)对S的k阶导)kdSqn1非负qn1qnvn1

设rk—到达时队长为k的概率 则：

rkrk10rk1rk12rkii1

上式为线性差分方程，令通解：

　　　　rkr0kkk10k1k12ki1i除k1得：

第三章 网内业务分析

＝０12ir2irr0r(t)rtea(t)dtr!r00(t)rtea(t)dtr!r00

(t)ra(t)dtr!0r0

eteta(t)dt0e()ta(t)dtA()0

归一化:

r01rkr01k0k0k

得:

r01, 其中<1且由a(t)的拉氏变换决定，

通解为:

rk(1)k.

1

此解与M/M/1解的形式类似. 故平均队长:

r

 G/M/1等待时间W 到达时已有r人,等12r

w的概率密度为1,2,r的概率密度的卷积 则w概率密度的拉氏变换是r个的拉氏变换的乘积

第三章 网内业务分析

设fw(w)为w的密度W(s)为fw(w)的拉氏变换,B(s)为服务期(M分布)的拉氏变换,B(s)则

sw(s)rkBk(s)k0(1)(s)

其反变换即密度fw(w):fw(w)(1)(w)(1)e(1)w平均w＝（１）验证M/M/1系统: 在M/M/1系统中：

ssA()1()111(1)2A(s),B(s)

2(1)0二解:1;2101,取1此时即M/M/1解,如队长k时，

若D/M/1:

(1)k(1)ka(t)(ta)A(s)esa1)aea(1)e(1)/(

1时,在(0,1)区间有唯一解, 从而得到队长分布。 需要注意的是, 上面的G/M/1 和M/G/1分别考虑了两个特殊时刻来考虑问题, 从而使问题简化. 可以证明, 对于任意随机时刻, 有如下结论:

对于M/G/1, 任意随机时刻队长的分布和离去时刻观察队长的分布是一样的; 对于G/M/1, 任意随机时刻队长的分布和到达时刻观察队长的分布是不一样的, 并且可以由后者( =

A())得到前者的结果. 具体结果可以参考

第三章 网内业务分析

[1]; 同时一些其它复杂的排队系统如G/G/1等也可参考[1].

第三章 网内业务分析

第3.2节 排队论在电话网中的应用

一方面由于通信网中信息流是随机的，另一方面，出于成本效益的考虑，网络中的公共资源有限的，所以发生排队现象是不可避免的。本节讨论电话网中的一些情况。

在通信的话务工程中，业务量是指在指定的时间内线路被占用的总时间。若某线路有m条信道，第r条信道被占用Qr秒，则m条信道或该线路上的业务量为QQr。如果换一种角度观察，记R(t)为t时刻被占用的信道数，T是观察

r1m总时间，则QtTtR(t)dt，当然这是一个随机变量。业务量的单位为时间，例

如秒。假设一个信道代表一条电话话路，则业务量的单位为秒话路。业务量的强度称为呼叫量。它可定义为业务量与观察时间之比。即：

呼叫量业务量Q

观察时间T呼叫量是无量纲的，或叫Erlang。自然，一条信道的呼叫量最多是一个Erlang。了解一个地区的呼叫量时非常重要的，它对网络设计有很大的影响，而在电信网建成之后，测试呼叫量也是重要的日常工作，其统计数据可为管理网络和优化网络运行提供背景资料。

为了将排队论又用于电话网，用Poisson过程模拟电话呼叫的到达，这在用户数较多，并且较为正常时，效果良好；并且假设电话呼叫持续时间为负指数分布，那么此时的服务员数即为信道数或中继数。

设每秒到达的呼叫数为，而平均服务持续时间为-1，记a=/，在通信工程中，常将它称为呼叫量，单位为Erlang。下面的例子解释它的合理性。 例3.2 求M/M/的稳态分布和平均队长

解:因为有个服务员，所以不会有排队等待，一定有稳态分布。 状态转移图为：

012k......3k......(k+1)

状态方程为:

2p0p1pk1(k1)pk1(k)pkk1

pk0k1记: a/

第三章 网内业务分析

解得：

akapkek!k0,1,2,...

队长分布是一个Poisson分布. 系统中的平均顾客数为：

E[N]kpka

k0 而a也是平均占用服务台的数目，这也正好指明了a的单位应为Erlang或erl。同时，若想真实地测定一个地区的呼叫量，信道数应该比较大才能准确。同时这个例说明对于M/M/系统，到达顾客流为Poisson过程时，系统中的的队长为Poisson分布，这个结果在分析溢出话务流的特征时有应用。

在实际的电话网中,表明电话网质量的主要指标为呼损。在工程中定义为：

Pc被拒绝呼叫次数　

总呼叫次数当然，还有其他的一些指标，但在本节中将主要应用呼损这个指标，做为讨论准则。经过以上的讨论，我们用M/M/m(m)模型来拟合电话网中的交换机，其中m为中继线，记a/ 那么

队长分布为：prr!　中继线全满的概率为：pmkrak0k!amarm!　mak k0k!am定理3.6(Erlang)

中继线全满的概率为：pcpmm!　mak k0k!这是著名的Erlang公式，它表明了系统中的中继线全满的概率，也称

pm　为阻

塞率。因为在阻塞期间也未必有顾客的到来，所以有：pcpm　。但一般二者差别不大，常混用（应用背景不一样）。

由前面排队论的知识知道，呼叫量a被拒绝的概率为pm，从而系统的通过量为：

a(1pm)。它也是m条线路被占用的平均数，从而线路利用率

第三章 网内业务分析

a(1pm)， 可以自己验证。 m当一个电话呼叫要经过n经过几次转接时，若每段上的呼损为pci（i=1,2,…k）那么近似计算总呼损为pc1(1pci)。这个关系只有在各段之间业务量完

i1k全独立时才成立，在一般情况下是不满足的。在讨论干线网时，由于业务量的巨大汇集，业务量独立的假设近似得到满足，这个近似公式更加准确。

下面讨论一下全网平均呼损的计算。在上面讨论了端对端呼损的计算基础上，可以计算网络的平均呼损。

如果网络用图G=(V, E)表示，ai,j表示端i和端j之间的话务量，ci,j表示端i和端j之间的呼损，那么全网平均呼损如下计算：

pcacai,ji,ji,j

网络平均呼损的结果取决于许多因素，如网络拓扑结构、网络的容量配置、网络业务的路由规划等。网络平均呼损是电话网络优化的重要指标。 下面将要讨论一下集中的好处

例3.2：若呼损为2%, 请计算30个信道能满足多少业务量；而若将30个信道化为3组又如何？

解：通过计算或查表，对30各信道，业务量为a=21.9erl；

而对于10个信道，a'=5.08erl.

因为3a'与a有较大的差距，故集中能带来很大的好处。

换一种方式说明, 如果呼损为1%, 看看对不同的话务量需要多少中继线? 如果 a=1, m=3, =31%; 如果 a=10, m=13, =70.5%;

如果 a=100, m=96, =94%; 说明的问题是一样的. 例3.2说明业务越集中中继线效率越好，现在的电信网的发展也正顺应这个趋势。

有许多应用问题，不能简单应用Erlang 公式。若是M/M问题，可以列出状态转移图，建立状态方程并利用归一条件求解。下面的例子说明了这种方法。

例3.3：有限用户即时拒绝系统

交换站服务于N个用户，每用户的到达率为0，m条中继线，每条中继线服务时间（占用时间）为服从密度函数e的负指数分布，总到达率N0

N

交换m

第三章 网内业务分析

定义状态变量队长k。

模型：非纯 M/M/m(n) 问题。状态转移图如下：

N012(N-1)2k(N-k+1)k(k+1)m(N-k)(N-m+1)m

稳态方程：

(Nk1)0.Pk1(k1)Pk1[(Nk)0k]Pk(0km)(k0) N0P0P1(Nm1)PmP(km)0m1m及

Pr0mr1

求解： 令 0/

递推（或根据生灭过程）：P1NP0

2 P22P0

N . . .

NkP kkP0

归一求P0：

Nk1 P0[k]

k0m时间阻塞率——即拒绝概率Pm

NmNmm Pm P0mmNrrr0第三章 网内业务分析

呼损——Pcn(Nn)0Pn

(Nn)0Prr0Pc(Nm)0Pm(Nr)Pr0m0r(Nr)Pm (Nr)PrNm(Nm).mP0  mNr(Nr)rP00N1mm  mN1rrr0N kN!

(Nk)!k!NN1有(Nk)N.

kk以m2,N1为例 （N1即

N01N0—到达与服务统计平衡）

N(N1)212N ]25N1m2，相当于强度0.5

代入得P0[1N即aN0N1 mm2占（满）线率（拒概） P2PmN1 （与 N 有关） 5N1 N2,P2Pm10.11  有阻塞 91)(N2) 呼损：Pc(N25N5N2 N2,Pc0  无呼损

第三章 网内业务分析

k0时,0效率或占用率 k1时, 1/2

k2时,10P0P1P2P1P2

N而P1 P011212 12N1 P0P225N1a(1Pc)为泊桑，此处不可用。 m若用，当N时亦可得 0.20.12468102N1 5N1N

可见：PcP2

N时 PcPn

Nm时 PcPn （约N>10）

可取N>>5m即可近似

例3.4：主备线即时拒绝系统 设交换站有二种输出线路A是主用线B是备用线（A被占用时再有呼叫则用B）并非A故障时用 B

A:主用线B:备用线 用（x，y）表示系统状态变量，定义状态：（x，y）={00，01，10，11} 其中01状态是指AB均占用后，A中顾客先服务完毕，B尚有顾客。 状态转移图:

第三章 网内业务分析

000110

状态方程为：

  11

p00(p10p01)

p11()p01

2p11(p01p10)

()p10p00p11

加

p ij1 即

p00p10p01p111

令解得:

p00p0122222

(1)(222)

(2)p10

(1)(222)2p00222系统利用率:

1(1)(p01p10)p11

2222此时利用率系统呼损同M/M/2(2).

例3.5公用备线即时拒绝系统

第三章 网内业务分析

如图，系统有2个输入，3个输出，其中A,B公用一条备线C

12

AACB

B状态为三维矢量(x,y,z),分别表示三线的空闲状况 状态图:

2000010211201111+21110011101100211012

服务率均为状态方程:

(12)p000(p010p001p100)

(12)p001(p011p101)

(12)p0102p000(p011p110)(12)p1001p000(p110p101)(12)p0112(p010p001)p111

(122)p1101p0102p100p111(22)p1011(p001p100)p111

3p1111p011(12)p1102p101

归一化条件:

pijk1

第三章 网内业务分析

的条件下：

在12解得:

3752p000

p0012(43)

p010p100p011p101(35.532)

2(43)(0.5)

p110p1112(2243)

3(4263)其中

(1)(44123152103)

A路呼损率——A，C忙，B路呼损率——B，C忙， 在上述1

pc1p101p111

pc2p011p111

2，12条件下，二者相等，为：

2(83202163)2

pc1pc2全系统阻塞率为

p111

公用备线与两个主备系统的比较

第三章 网内业务分析

A主备主备AAB

BAC

右图省一条备用线，今讨论省此线对呼损的影响，取A路呼损。

左图

pc222pc'2

2(83202163)2

右图

当结果） 当

1时，pc0.2，pc'0.26，共用备线呼损大，（省一线的

<<1为低呼叫率情况

左图

2pc22221

2121  2212212'c右图 p221

（或

21163）

21103'pp 低时c与c差别较小，共用线有好处(省一条线)

可见，在业务量不大的情况下，公用备线对呼叫率影响甚小,可取（省线）。在业务繁忙的情况下，采用公用备线需考虑呼损是否允许。

例3.6优先制系统

第三章 网内业务分析

以上三例均为即时拒绝系统，现考虑优先制情况。 优先制方式：多个业务流共用一个信道 事先确定的优先级（低级别的占线条件:高级别的无排队） 可强拆(优先级高的呼叫可强行中断在占线的低优先级用户)。 以两队为例（A，B均可排队，线空A优先，不强拆）

1A2B

定义状态及变量:

状态: =0表示系统中无顾客，=1表示系统中有顾客； 变量r,s表示A队中有r人等待，B队中有s人等待；

prs——=1时，A队r人，B队s人等待的概率（不计服务中的） p0——表示系统中无顾客的概率； 状态图：

 (s=0) (s=2) 状态方程为: r=0，第一行=1：(12)p0sp1,sp0,s12p0,s1 s=0，第一列=1: (12)pr0pr1,01pr1,0

r>0，s>0：(12)prs1pr1,s2pr,s1pr1,s

(r=0) (r=1) (r=2) 第三章 网内业务分析

r=s==0：(12)p00p00

 归一化：p0prs1

r0s0解一种特例： A队—优先，不拒绝 B队—非优先,即时拒绝(即S=0) ，或B队来人,见线空才用

1+200,0 1 1,0 1 2,0

稳态方程为:

(12)p0p00(1)

...r0

(1)p00(12)p0p10(2)

(1)pr0pr1,01pr1,0(3)

为一维差分方程,通解形式

(1),(2)联立 P101P00

P00(12)P0

由(3):

Pr1,0(11)Pr01Pr1,0

2 取r=1代入得 P20(11)P101P00P00 3 r=2 P30(11)P201P10P00

…

通解r Pr01rP00 而P00(12)P0,须求P0 用归一求P0:

第三章 网内业务分析

1P0Pr0

r0 P0P001rP0P00r01 11 P0(12)P012P0 111 11 其中P0——线路空闲率

P011 12 1-P0——线路忙概率,即效率 (单窗口) ∴12

12 纯M/M/1

=1

此例中1(12/1)1(∵11)

12 效率有所增加 (∵非优先队存在) 但加大优先队等待时间(换取) ∴

1(11)(12)dW(r1)Pr0r012d1r11 (1r101) 11 1(11)(12)11(12)1 12(11)2121111(若20,W11=W0, 标准M/M/1解W0)

W---本特例解；

W0---标准M/M/1之解，(相当于20),无B队

二者之比:

可见:

W12/11 W012由于有B队的存在,使A队的W↑

第三章 网内业务分析

由于有B队,使系统↑

12(12/1)W 101212W0 0WW0 (等待换效率)

呼损: A队: 不拒,无呼损,Pc,a0 B队: 即时拒绝, Pc,b1P012

12 Pc,b

在例3.4中，输出线C承担的是A和B的溢出话务量之和，其概率特征较为复杂，[4]中计算了一下溢出话务量的期望值和方差。现将结果陈述如下： 呼叫量a由m条中继线承载，溢出话务量的均值为：a2apm(1apm方差为：

pm　

a　)

m1aapm由于均值和方差不等，溢出话务量肯定不是Poisson流，虽然溢出话务量的特征复杂，但对它的研究是很有必要的。这是因为：电话呼叫不是唯一路由的。

唯一路由管理简单，但网络利用率不高，可靠性也不好；故而两个城市之间的电话呼叫一般均有第一路由，第二路由等等。这样，在许多中继群上承载的第二路由业务就是第一路由业务量的溢出部分。一般看来，中继路由上的呼叫量是直达话务量和溢出话务量之和，虽然不再是Poisson流，为了简单起见，我们仍用Poisson流来近似分析。下面例3.5表明备用路由能很好地改善网络性能。 例3.7网络由3个节点组成，每对节点之间的中继线数目和呼叫量均已确定，如图所示：

3a13=25.0c13=301a23=15.0c23=202

a12=40.0c12=40路由表为：

第一路由 第一路由 a12 {(1,2)} {(1,3),(3,2)} a13 {(1,3)} {(1,2),(2,3)} a23 {(2,3)} {(2,1),(1,3)}

第三章 网内业务分析

假设Aij是链路（i,j）承载的业务量之和，则链路（i,j）的阻塞率为：

pij(i,j)被阻塞的话务量Aij

计算的方法遵照后面的说明，具体过程不再演算，经过迭代，最后得到：

p120.096ˆ120.116pp130.096ˆ130.053pp230.115 ˆ230.045 p而如果没有迂回路由的话；

ˆ)0.116max(pmax(p)0.115

注意，电话网提供的质量应该是一致的，从而应比较阻塞率的最大值和平均值这两个指标。前例采用备用路由最大阻塞率略有下降，但在大和复杂的网络中，效果会明显很多。当然这是用网络控制复杂为代价，综合利用网络资源得到的。在[4]中的一个例子，一个4端点的全连接网络，每边的容量为2，每对节点之间的呼叫量为1erl，有两个备用路由。全网平均呼损由0.2下降到0.134, 效果比较明显.

下面将上面的例一般化说明方法，为了简单起见, 网络结构是三角形，路由也有两种选择：直达和迂回。Bi,j表示边(i,j)阻塞率，pi,j表示端对端呼损，ai,j表示端对端话务量，Ai,j表示边(i,j)承载的话务量，mi,j表示边(i,j)的容量。下面来计算网络的平均呼损：

首先，考虑边承载的话务量的计算

Ai,j(1Bi,j)ai,j(1Bi,j)ai,kBi,k(1Bi,j)(1Bj,k)aj,kBj,k(1Bi,j)(1Bi,k)

所以有

Ai,jai,jai,kBi,k(1Bj,k)aj,kBj,k(1Bi,k)

根据Erlang公式有：

Ai,ji,jBi,jmmi,j!ri,jr1mi,jA

r!可以迭代求方程组中的边阻塞率Bi,j，然后根据下面的公式计算端对端呼损pi,j，

pi,jBi,j[1(1Bi,k)(1Bk,j)]

最后可以计算网络的平均呼损

pcapai,ji,ji,j

最后，当网络较大时，计算量较大，可以用计算机迭代求解；同时应该能够看出，不同的路由规划会有不同的网络平均呼损。

第三章 网内业务分析

第3.3节 排队论在数据网中的应用

早期的数据网络是采用信息交换的方式，而后采用分组交换的方式。为了便于讨论，我们先讨论信息交换，在讨论分组交换。为了能采用较简单的模型，我们采用了Kleinrock的假定或他的模型。

要描述数据业务，就比电话业务复杂的多。第一是业务特征突发性强，速率差别较大，并没有一个一致的简单业务模型；第二，数据业务的质量不再象电话业务主要由呼损描述，而是由延时组成，当然这是在一定误码率的基础上讨论。为了保证低误码率，就要有对抗差错的措施。视情况可能采用反馈重发或前向纠错等手段，而前者会大大影响整个网络延时的讨论。另一个影响延时的讨论是路由安排，尤其在分组交换中，路由是核心控制。不同的路由策略甚至使网络面貌有本质变化。所有这些，并不是短短一节能讨论得了的。但通过下面将要采用的Kleinrock模型的讨论，能获得许多有用的定性概念。 信息交换

网络由许多节点组成。假设信息的长度服从负指数分布，平均为1（bit），

处理时间与长度成正比；每个节点有无限大存储器；到每个节点的信息包数服从

1Poisson过程，这样假设之后，每个节点均可采用M/M/1模型，处理时间为：，

CC为信道速率，单位bit/秒。若，那么由M/M/1的知识得： CC(1)

信息在某个节点的等待时间为：W=

系统时间SW111。这只对一个节点的一个输出端CC(1)C口来讨论。若假定只采用固定路由（为简单起见），再根据下面这个关于M/M问题的输入输出问题定理就可以讨论整个网络了。

定理3.7：M/M/m不拒绝排队系统的输出过程与输入过程相互独立，并具有同样的分布规律，即都是以为均值的Poisson流。

证明需要较深的数学知识，这里忽略；不过可以通过讨论2次排队问题了解一些。对单个节点来说，系统时间为： S1。 C(1)例3.9 两次排队的问题

信息转接： 包到达为Poisson流，且到达率为入包/秒， 包长不定，服从负指数分布，平均包长为a bit， 且 A(a)ea

第三章 网内业务分析

容量C1bit/s存储A存储BrC2bit/ss

其中C1，C2为信道速率，单位为 bit/s。 服务率 1c1c （包/秒），22 （包/秒） aaA ,B有存储器足够大，两个排队系统为不拒绝系统。

设: r-第1个排队系统中的包数，

s-第2个排队系统中的包数。 状态转移图为：

r=000201202.....20s20s+111121121210r=11,s-11,s...2011...r-1,sr-1,s+1r-1,0212r-1,1r,s-12112r,s+1r,sr0r1r+1,ss=0...s=1...r+1,s-1

(1)(2)(3)(4)状态方程为： rs0p002p01s0(1)pr0pr1,02pr1 r0(2)p0s1p1,s12p0,s1r0,s0(12)pr,spr1,s2pr,s11pr1,s1归1 令通解:

ps0r0rs1

代入(1)得yprsp00xrys2rsprsp0012 代入(2)得x1求p00：

第三章 网内业务分析

s1p001r2p00p00(11)(12)

(11)(12)通解：

sprs(11)(12)1r2

r12,s 1112全程系统时间为：

111111 cc1(11)2(121)1212aa

上面的结果表明可以将两个排队系统分离考虑。

例3.10：若将业务量集中n倍，系统时间为原来的1/n（保持利用率不变）。

ˆ解：业务量集中n倍后，=n，cnc，不变，从而S11S

c(1)n从而，对数据业务也适宜集中，能降低时延。当然本例和电话网中的例子主要是指在中继网上。由于前面的输入-输出定理，这样网络的每个节点的输出端口都可由M/M/1来拟合,全程的时延可将各个端点的时延汇集起来就可以了。下面采用Klenirock[3]定义的网络总时延来讨论。 定义jk为从节点j至节点k的信息到达率；那么进入网络的总信息率为

jkj,k

jk穿过链路i的系统时间为：Ti1 Cii其中1是平均信息长度，而是Ci链路i的速率。 Klenirock网络总时延TTii

i如果根据每对节点分别计算时延,再根据流量比例加权得到的全网平均时延和上面的Klenirock网络总时延是一致的.

Klenirock关于网络优化的讨论是根据上述假设和T的定义得来。网络优化问题包括如何选择ci或路由而使T最小等。 下面举一个例来描述T的计算：

例3.11：有5个节点的网络如图，节点对之间容量是一样的；节点对之间如下表，也是对称的。

jk第三章 网内业务分析

C14C13DC8C7C9C10C12C11C6C5CC3C4C1C2EBC9.340.820称D0.6100.628E2.942.400.753A

AABCDEB对0.9350.1310.608

路由是这样固定安排且唯一：能直达就直达；A，E是ABE；A，D是ACD；C，E是CDE；另一个方向也经过相同的节点。 而链路容量（单位比特/秒）为：

C1= C2=3130，C9= C10=2990，C3= C4=5390，C5= C6=1340，C7= C8=517，C11= C12=3020，C13= C14=2790

1100bit

这样，j,kjkjk38.33，1112ADCDCE3.638等等。

这样，计算得到T=0.045秒。显然这个结果是与路由有关的，不同的路由会有不同的结果。

分组交换

由于信息交换方式引入较大时延，且对节点处理要求较高，不能适宜数据网的要求。X.25等分组交换方式与信息交换方式有了很大不同，X.25将信息分割成较小的分组，并加上复杂的通信协议，能够大大改善节点的吞吐量和大大减低时延。这主要包括两个方面：分组交换方式下，节点不需要收齐全部分组后再传输，而是可以收一个，发一个，这使等待时延大大缩小。另外由于可以引入灵活的路由策略，而能充分利用全网资源，使节点的吞吐能力大大提高。

但要应用排队论知识对全网讨论比较困难。从信息交换中可以看到用M/M/1拟合实际过程是做了许多假设，要再用M/M/1拟合分组交换近似性就更差。考虑到纠错措施和路由的安排，问题就变得更加复杂。Kleinrock在[3]中对信息交换，分组交换、数据网做了许多讨论，得到了许多结果。数据网的发展日新月异，鉴于理论分析的复杂性，研究很多采用计算机模拟和实际建网后运行获得许多经验数据来进行。

第三章 网内业务分析

但是如果仅对一个节点来分析，那么工作可以做得很详尽。采用较复杂的M/G/1模型，此时工作重点大都是存储器设计，寻求在误码率和延时方面的调和。另外，考虑路由安排和拥塞控制对每个节点的影响。

当今发展的方向是B-ISDN，而ATM是B-ISDN的可能解决方式。ATM方式因为要处理综合业务，其构想虽然很先进，但在网络管理，带宽分配，连接接纳控制（CAC），拥塞控制（Congestion Control），交换机的存储设计上皆遇到很多挑战。主要矛盾是：所有事情需要在很短时间内完成。为了达到这一目的，又要适应多种业务，方法又不能太复杂，这种综合目标较难达到。目前，ATM的商用并不是很成功，上述问题的解决大大影响ATM网络的效率。下面举一个[5]中ATM交换机的模型分析来了解一下排队论在ATM中的一些应用。

ATM是将信息等分成53个字节的信元。5个字节的头，在信道中采用统计复用技术，导致在ATM交换机必须缓冲存储，由于采用信元，故而采用M/D/1模型拟合。

例3.12：ATM交换单元性能分析

假定ATM交换单元是NN的，在任意给定的时隙内，信元到达某一特定入线的概率为p(0p1)。每一信元被寻址到任何一个给定的输出的概率都为1/N，那么，对任一给定的出线来说，信元到达任一条入线的概率为p。由于缓冲存N储可以安排在输入，输出和中央，故模型分析分三种类型。这里只分析输入和输出排队两种类型。 （1） 输出排队：

在一个信元时间内i个信元到达某一个输出队列的概率xi,

PiPxiCN()i(1)Nii0,1,...N

NN{xi}的母函数为：

X(z)xizznCN(nii0i0NNPiP)(1)NiNN(1PPz)NNN

类似于M/D/1的方法，可以得到队列数概率分布的母函数如下：

Q(z)(1P)(1z)

X(z)z通过Q(z)可计算得到平均队列长度：

N1P2Q

N2(1P)而具有Poisson过程的M/D/1的模型的平均队列长度：

QM/D/1P2 2(1P)第三章 网内业务分析

显然，当N时，QQM/D/1

pip而limxie为参数p的Poisson分布； Ni!从而：limX(z)ep(1z)

N(1p)(1z)

Nep(1z)z上式右面正好是稳态下M/D/1的队列生成函数。 平均等待时间

N1WWM/D/1，当负荷超过0.8时, 等待时间显著增加; 同时N对平均等待

N时间的影响很小. （2） 输入排队：

对于输入排队模型，采用相同的输入假设。到达信元存储在一输入队列中，并按FIFO原则工作。如果N个输入队列上的N个排头信元中只有一个要到某一出线去，它显然会被选中；如果j个信元要到同一条出线，信元将被随机选择，每一信元被选择的概率为1/j。其他的信元必须等待下一个信元时间后的选择过程。为分析输入队列行为，假定所有队列都是饱和的，即每一输入队列中总有信元在等待。

此时：limQ(z)

假定有Bin个信元要去往出线i，但在信元时间n被阻塞在队头，因为他

们没有被随机选择过程选中。而在信元时间n期间，许多信元将被服务并被

i传送到相应的出线；假定在信元时间n内又有An个以i为目的地的新信元出

现在队头，那么应有如下关系：

ii Bnmax(Bn11An,0)i在每一输入队列中，新信元将逐渐移到队头；在信元时间n所有队列的队头中被服务的信元总数为LAi。因为有Bin个信元被阻塞，故Ln又可计

nni1Ni算为：LnNBn。

i1N在稳态下，Ln平均记为L，它又等于Np，这里p代表每条输出链路的吞吐量，即

L= N p。

当N时，稳态情况下移到队头欲去往i的信元数是Poisson分布，其参数为p。当N时，Bn的平均稳态值类似于在输出排队方法中所解的

i第三章 网内业务分析

M/D/1，那么，BNip2 2(1p)i对LnNBn，求极限：

i1LNBi

i1`N再结合

LNi1`Np

iBN(1P)

i当N时B(1p)

P2根据1P

2(1P)P220.586

从而基于输入排队原理的交换单元性能有限，其极限吞吐能力为58.6%。这主要是由队头效应（HOL）造成。至于中央排队和输出排队性能一样，只是大大节约了存储器，代价是复杂的控制。

以上这个例简单地示意ATM交换单元的性能分析，这方面的工作做了很多，方法也不尽一致。另外在ATM的许多其他方面排队论也有许多应用，但很多模型较复杂。理论分析不易得到简单的解析结果，取而代之是计算机仿真。

参考文献：

[1]随机服务系统， 徐光辉， 科学出版社 1987 [2]Queueing System I Kleinrock [3]Queueing System II Kleinrock [4]通信网理论基础 周炯磐 [5]ATM, Martin de Pryker 1993 [6] CCITT Recommendation E.521 “Calculation of the Number of Circuits in Group Carrying Overflow Traffic,” Siocth Plenary Assembly, Orange Booh, 1977