t服 （ 是服务窗服务一个顾客的平均时间）
09:09:02 17
5 排队系统的目标参量

绝对通过能力 A
单位时间内被服务完顾客的均值

相对通过能力 Q
单位时间内被服务完顾客数与请求服务顾客数之比值

损失概率P损
系统的损失概率
09:09:02
18
6 排队论已知条件与所求目标






概率特征：方差为0 主要应用：

09:09:02

周期性到达事件 定长服务系统（例如ATM网络）
27
3 几个连续型分布—负指数

负指数分布(记为M)
一个随机变量T,它的分布密度函数为
e t t 0 f (t ) t0 0
称T服从负指数分布
分布函数为
1 e t F (t ) 0
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
负指数分布的概率分布函数F(t)
09:09:02
30
3 几个连续型分布—负指数

负指数分布的均值与方差
ET DT 1

1

变异系数
DT ET 0 ET =1，是一个随机变量服从负指数分布的必要条件
2

09:09:02

满足对方要求给予服务的——服务窗 顾客与服务窗构成一个排队系统，或称之为随机服务系统 顾客的到达时刻是随机的 服务窗服务完一个顾客的时间也是随机的 在某时刻，要求服务的顾客数超过所有服务窗的总容量时， 顾客就要排队等待服务

排队现象的产生

09:09:02
6


(Kleinrock) "We study the phenomena of standing, waiting, and serving, and we call this study Queueing Theory." "Any system in which arrivals place demands upon a finite capacity resource may be termed a queueing system."
顾客到达间隔时间 A(x) 服务时间B(x) 排队模型


平均系统队长Ls 平均等待队列长度Lq 平均服务队列长度L服 平均系统时间Ws 平均队列时间Wq 平均服务时间t服 A，Q，P损
09:09:02
19
7 排队模型的分类与记号

通常用3~5个字母X/Y/Z/m/K来表示排队模型


单服务窗的排队服务进程图
Cn-1 Vn Cn Vn+1 Cn+1 Cn+1 Idle Vn+2 Cn+2 Cn+3 time Cn+2
服务
Cn 排队 n+1 Cn
09:09:02
n+2 Cn+1 Cn+2
n+3 Cn+3
26
2 几个连续型分布—定长

定长分布（记为D）
若顾客到达间隔时间（或服务时间）为一常量a，此 时称输入（服务）分布为定长分布，用T表示此时 间，则 P(T=a) = 1 用分布函数表示有 F(t) = P(Tt) = 0 t<a 1 ta
设Cn(n=1,2,…)表示到达排队系统的第n个顾客， 其到达时刻为tn，则n=tn-tn-1表示Cn与Cn-1的间 隔时间。我们假定t0=0,则1=t1。如果顾客到达 是相互独立的，则{n}是独立的随机变量序列， 假定它们有相同的分布函数，此分布函数记作 A(t)，称它为输入分布也称到达间隔时间分布， 设N1(t)表示(0,t]时间内到达的顾客数，它称为输 入流。
09:09:02
12
4 排队系统的三个基本要素

服务规则


先到先服务 后到先服务（堆栈） 随机选择服务 优先级服务（特快专递）
09:09:02
13
4 排队系统的三个基本要素

三、服务窗



窗口个数可一个或多个 多个服务窗是，顾客可以平行多队排列，串列 或者串并同时存在的混合排队 一个服务窗可以为单个顾客或成批顾客进行服 务 各窗口的服务时间可为确定型或随机型。服务 时间往往是平稳的
09:09:02
11
4 排队系统的三个基本要素

二、排队规则



损失制－ 顾客到达系统时，如果系统中所有服务 窗均被占用，则到达的顾客随即离去 等待制－ 顾客到达系统时，如果所有服务窗均被 占用，则系统能够提供足够的排队空间让顾客排队 等待 混合制－ 是损失制与等待制混合组成的排队系统， 此系统仅允许有限个顾客等候排队，其余顾客被拒 绝
09:09:02
21
7 排队模型的分类与记号

排队模型举例

M/M/n M/M/n/m M/M/n/m/m GI/M/1 Er/G/1/K Mx/Mr/1/
E2/G/1/K M3/M2/1/
09:09:02
22
第二节 几个重要的概率分布
23
1 基本概念

输入分布 输入流

09:09:02
3
第一节 排队问题的基本概念
4
1 排队现象

有形的队伍



超市出口处排队付款 餐厅排队买饭 公共电话亭打电话 …… 114查号台等待服务 网络中数据包传输 …… 交换机处理呼叫 …

无形的队伍



某些系统也可能根本不允许排队

09:09:02

5
1 排队现象

排队现象的抽象 要求服务的——顾客
排队 系统

服务窗
Ls＝Lq＋L服
系统排队长度的分布、均值Ls
系统内顾客数

排队等候顾客队列长度的分布、均值Lq
系统内排队等候的顾客数

09:09:02
服务队列长度的分布、均值L服
正被服务的顾客数
16
5 排队系统的目标参量
排队 系统 服务窗
Ws＝Wq＋t服

顾客在系统内逗留时间的均值Ws 顾客排队等候时间的均值Wq 服务时间的均值t服


每单位时间执行一次贝努力试验，“失败”则 继续，成功则完成 首次“成功”之前需要持续的时间就可以看成 是相应的到达间隔或服务持续时间
31
3 几个连续型分布—负指数

无记忆性
P(T>t+x| T>t) = P(T>x)

定理1.1
负指数分布具有无记忆性.即设T是随机变量,服从 负指数分布,参数为 >0,设t,x>0,则 P(T>t +x| T>t) = P(T>x) = e-x

定理1.2
设随机变量T是非负的连续型变量，它的分布具 有无记忆性，则T服从负指数分布 连续型随机变量分布中，只有负指数分布具有无记 忆特性
09:09:02
9
4 排队系统的三个基本要素
输入过程 排队规则 服务窗

09:09:02
10
4 排队系统的三个基本要素

一、输入过程




顾客到达时间间隔可分确定型（如定期航班） 和随机型（看病的病人） 顾客源可以有限或无限 顾客到达系统的方式可以逐个或成批 顾客到达系统可以是独立的或者相关的，输入 过程可以是平稳、马氏、齐次的等
f(t)= θiμ i e-μi t
i=1
k
其中
θ
i=1
k
i
1, i 0 (i μ 1, 2,..., k ) 0
i
则称T
服从k 阶超指数分布
09:09:02 36
5 几个连续型分布—超指数
k阶超指数分布(记为Hk) 其分布函数为 k F(t)=1- θ i e -μi t

计算机网络理论
排队论
1
第一节 排队问题的基本概念 第二节 几个重要的概率分布 第三节 到达与发送过程 第四节 M/M/C排队系统参数分析 第五节 M/M/1排队系统应用举例
09:09:02
2
教材与参考书

《排队论》 陆传赉
北邮出版社

《排队论基础及应用》 孟玉珂 同济大学出版社 《Queueing Systems》 Leonard Kleinrock 《Introduction to Queueing Theory》 Robert B. Cooper 《排队论》PPT 刘咏彬 liuyb@ 北京邮电大学
09:09:02
14
排队系统的三大要素 就是排队系统的已知条件

输入过程

顾客到达间隔时间的密度函数a(x)或分布函数A(x) 队列允许的最大长度 (以便确定系统最大容量n） 服务窗个数 m 顾客占用服务窗时间的密度函数b(x)或分别函数B(x)
15

排队规则


服务窗

09:09:02
5 排队系统的目标参量
i=1(t ຫໍສະໝຸດ 0)均值方差 变异系数
09:09:02
θi ET= i=1 μ i
k k θi θi 2 DT 2 2 ( ) i=1 μ i i=1 μ i k
＞1
37
6 几个离散型分布


离散时间的排队理论在计算机通讯中有着广泛 的应用。因为机械动作是间断的，用离散理论 可以得到更精确的结果。 排队论中常用的最重要的离散分布是几何分布 和负二项分布，实际上可以把它们看作是负指 数分布、爱尔兰分布离散化而得到的分布，因 此它们也应具有负指数分布、爱尔兰分布的类 似性质。