双方向中继线：
aA? B ? 50erl
E62 (50) ? 0.01388 ? 0.01
E63 (50) ? 0.00844 ? 0.01
S ? 64 2001-3-14 A? B
? ? ? @? 华? ?
26
马尔可夫型排队系统的应用（2）
? 例题：有限等待空间排队系统与无限等待空间排队系统 的性能比较
? ? ? @? 华? ?
12
M/M/1排队系统的性能分析
? 等待/滞留时间的概率分布
2001-3-14
? ? ? @? 华? ?
13
M/M/1排队系统的扩展（1）
? 顾客到达率和服务率可变的M/M/1排队系统
? 分组交换网中 window-based flow control ? ATM网中用于ABR业务的 rate-based flow control ? 电路/分组交换网中的 dynamic bandwidth assignment
9
2001-3-14
? ? ? @? 华? ?
10
M/M/1排队系统的性能分析
? 全局平衡方程式(Global Balance Equation)
其中：
? 平稳状态概率的求解
?局域平衡方程式(local balance equation)：
pi
?平稳状态概率：
i
2001-3-14
? ? ? @? 华? ?
s?
s?
s?
? ? ? @? 华? ?
15
M/M/s/K排队系统的性能分析
? 被截断的M/M/s排队系统
?
?
?
?
?
?
?
0
1
． ． ． ．
s-1
s
s+1
． ． ． ．
s+k
?
2?
(s ? 1)?
s?
s?
s?
s?
? 排队系统性能
2001-3-14
? ? ? @? 华? ?
16
其他变型的马尔可夫排队系统
28
马尔可夫型排队系统的应用（3）
? 例题4-4：三种排队模型的性能比较
模型III: 综合网络/集中排队
模型II: 分散网络/集中排队
模型I: 分散网络/独立排队
2001-3-14
? ? ? @? 华? ?
29
三种排队模型的性能比较
2001-3-14
? ? ? @? 华? ?
30
三种排队模型的性能比较
2001-3-14
? ? ? @? 华? ?
36
课外练习（2）
? M(N)/M/s(0) Queueing Systems (Engset Formula)
2001-3-14
? ? ? @? 华? ?
37
马尔可夫型排队系统的总结
2001-3-14
? ? ? @? 华? ?
38
马尔可夫型排队系统的总结
2001-3-14
? ? ? @? 华? ?
3
连续时间马尔可夫过程的状态转移
2001-3-14
? ? ? @? 华? ?
4
离散时间马尔可夫链
2001-3-14
? ? ? @? 华? ?
5
离散时间马尔可夫链
2001-3-14
? ? ? @? 华? ?
6
连续时间马尔可夫过程
2001-3-14
? ? ? @? 华? ?
11
M/M/1排队系统的性能分析
? 排队系统的性能参数
? 队列长度的均值、方差
? 等待/滞留时间的均值
? 队列长度的概率分布与?和µ本身无关，只与两者的比? 有关；但是，平均等待/滞留时间不仅与?有关，而且 与平均服务时间成正比
? 同等负载（ρ）情况下的快速服务系统与慢速服务系统的例 子
2001-3-14
? ｛Ｎｔ｝：一维马尔可夫型排队系统 ? ｛Ｎ１ｔ，Ｎ２ｔ，… ，Ｎｋｔ｝：ｋ 维马尔可夫型排队系统
? 由于排对系统的随机特性主要来源于顾客的到达和所 需的服务时间，不难想象，如果顾客的到达和服务时 间均没有记忆性，则该排队系统的状态变量也必然没
有记忆性，或称马尔可夫性
? 对于马尔可夫型排对系统的性能分析，只要针对该排
2001-3-14
? ? ? @? 华? ?
33
马尔可夫排队系统的过渡过程（续）
2001-3-14
? ? ? @? 华? ? Nhomakorabea34
M(N)/M/N模型的过渡解
2001-3-14
? ? ? @? 华? ?
35
课外练习（1）
? M/M/s Random Service Queueing System
2001-3-14
? ? ? @? 华? ?
39
多维马尔可夫排队系统的解析
? 例题：M1+M2/M1,M2/s(0,infty)
1
令 N_1=j 表示平稳状态下业务1
1
2
在排队系统中的顾客数；
2
N_2=i 表示平稳状态下业务2
s
在排队系统中的顾客数；
2001-3-14
? ? ? @? 华? ?
40
《通信网理论基础》
第4章 马尔可夫型排队系统的性能分析
2001-3-14
? ? ? @? 华? ?
1
马尔可夫型排队系统
? 定义：
? 可用当前状态变量或变量组（例如，任意时刻的队列长度）完 全描述的排队系统，即给定当前时刻的状态概率就完全可以
求解出将来时刻的状态概率
? 排队系统的状态变量本身是一个马尔可夫过程
(impatient customers)
2001-3-14
? ? ? @? 华? ?
17
到达率随队列长度变化的M/M/1排队系统
2001-3-14
? ? ? @? 华? ?
18
M/M/1/K Loss Performance
2001-3-14
? ? ? @? 华? ?
19
M/M/s(0)排队系统与Erlang-B公式
2001-3-14
? ? ? @? 华? ?
21
Erlang Loss Performance
2001-3-14
? ? ? @? 华? ?
22
Erlang-B Formula’s Application
2001-3-14
? ? ? @? 华? ?
23
Erlang-C Formula
2001-3-14
2001-3-14
? ? ? @? 华? ?
31
三种排队模型的性能比较
注：平均等待时间的比较会得出不同的结论
2001-3-14
? ? ? @? 华? ?
32
马尔可夫排队系统的过渡过程
? 过渡过程的分析是非常重要的（了解达到平稳 状态的过程和时间）
? 过渡过程的分析是非常困难的，即使是最简单 的M/M/1排队系统，其过渡过程解也非常复杂
? ? ? @? 华? ?
24
马尔可夫型排队系统的应用（1）
2001-3-14
? ? ? @? 华? ?
25
电路交换网的设计
单方向中继线：
aA? B ? 0.05x1000x(1000/1999) ? 25erl aB? A ? 0.05x1000x(1000/1999) ? 25erl E35 (25) ? 0.01165? 0.01 E36 (25) ? 0.00802? 0.01 S A? B ? 36 SB? A ? 36
对系统的当前状态建立起马尔可夫状态转移方程式就
可以求解出该排队系统的状态概率
2001-3-14
? ? ? @? 华? ?
2
排队系统的马尔可夫过程描述
队列长度Nt
K
t
? 马尔可夫型排队系统在任意时刻的队列长度实际 上是一个最简单的马尔可夫过程，即生灭过程。
? 生灭过程的状态转移只在相邻状态之间发生
? 多维状态变量可以构成一个多维生灭过程
? 一般来讲，求解无限等待空间排队系统比较容易 ? 但是，能否用无限等待空间排队系统的队列长度的尾分布来
近似有限等待空间排队系统的阻塞率性能？ ? 一般来讲是不行的，但对于马尔可夫排队系统有如下结果：
2001-3-14
? ? ? @? 华? ?
27
马尔可夫型排队系统的应用（2）
2001-3-14
? ? ? @? 华? ?
?M/M/s(k)中若k=0, 则
或
（Erlang-B公式）
? Erlang-B公式的鲁棒性
?只与a有关，与?，µ本身无关
?与服务时间的概率分布无关（M/G/s(0)也适用)
? Erlang-B公式的迭代计算
2001-3-14
? ? ? @? 华? ?
20
Erlang Loss Performance
? 平稳状态概率
? 例：M/M/s排队系统的平稳状态概率
2001-3-14
? ? ? @? 华? ?
14
M/M/s排队系统的性能分析
? 等待概率：
? 平均队列长度：
Erlang-C Formula
? 平均等待时间：
? 等待时间的概率分布：
?
0
?
2001-3-14
?
1
2?
?
?
?
?
s-1
s
s+1
(s ? 1)?
多维马尔可夫排队系统的解析
2001-3-14
? ? ? @? 华? ?
41
本章小节