网络流量设计基础 通信网 教学课件

《网络流量设计基础 通信网 教学课件》由会员分享，可在线阅读，更多相关《网络流量设计基础 通信网 教学课件（57页珍藏版）》请在金锄头文库上搜索。

1、网络流量设计基础 3.23.2.2 M/M/1 排队系统 3.2.1 排队论基本概念 排队论基本概念 3.2.11排队系统的概念 有形排队现象：有形排队现象：进餐馆就餐，到图书馆借书，车站等车进餐馆就餐，到图书馆借书，车站等车 ，去医院看病，售票处售票，到工具房领物品等现象。，去医院看病，售票处售票，到工具房领物品等现象。 无形排队现象：无形排队现象：如几个旅客同时打电话订车票；如果有如几个旅客同时打电话订车票；如果有 一人正在通话，其他人只得在各自的电话机前等待，他一人正在通话，其他人只得在各自的电话机前等待，他 们分散在不同的地方，形成一个无形的队列在等待通电们分散在不同的地方，形成一个无

2、形的队列在等待通电 话。话。排队的不一定是人，也可以是物。如生产线上的原材料排队的不一定是人，也可以是物。如生产线上的原材料 ，半成品等待加工；因故障而停止运行的机器设备在等，半成品等待加工；因故障而停止运行的机器设备在等 待修理；码头上的船只等待装货或卸货；要下降的飞机待修理；码头上的船只等待装货或卸货；要下降的飞机 因跑道不空而在空中盘旋等。因跑道不空而在空中盘旋等。（1）排队论与排队系统的概念要求服务的一方称为顾客，提供服务的一 方称为服务机构，服务机构内的具体设施称为服务 员(或服务窗口)。顾客需求的随机性和服务设施的有限性是 产生排队现象的根本原因。服务员或设备不能同时满足顾客或用户

3、的需 求， 必然发生排队。排队的队可以是有形的也可以是无形的。如：几个旅客 同时打电话订购车票。 顾客和服务员可以是人也可以是物。如：打字员桌子上 等待打字的稿件；要求着陆的飞机等都可视为排队系统中的 顾客。 服务员分别为打字员和飞机着陆的跑道。排队论就是利用概率论和随机过程理论，研究随机服务 系统内服务机构与顾客需求之间的关系，以便合理地设计和 控制排队系统。由于顾客到达的数目和要求提供服务的时间长短都 是不确定的，这种由要求随机服务的顾客和服务机构两方 面构成的系统称为随机服务系统或排队系统。顾客顾客要求服务的对象。要求服务的对象。 服务员服务员提供服务的服务者（也称服务机构提供服务的服务

4、者（也称服务机构 ）。）。 顾客、服务员的含义是广义的。顾客、服务员的含义是广义的。顾客到达 队列 服务员 顾客离开输入 排队规则 服务规则 输出服务机构排队系统类型：排队系统类型：服务台服务台顾客到达顾客到达服务完成后离开服务完成后离开单单服务台排队系统服务台排队系统排队系统排队系统类型类型 ：服务台服务台2 2顾客到达顾客到达服务完成后离开服务完成后离开S S个服务台，一个队列的排队系统个服务台，一个队列的排队系统服务台服务台s s服务台服务台1 1排队系统类型排队系统类型 ：服务台服务台2 2顾客到达顾客到达服务完成后离开服务完成后离开S S个服务台，个服务台， S S个队列的排队系统个

5、队列的排队系统服务台服务台s s服务台服务台1 1服务完成后离开服务完成后离开服务完成后离开服务完成后离开排队系统类型排队系统类型 ：服务台服务台1 1顾客到达顾客到达离开离开多服务台串联排队系统多服务台串联排队系统服务台服务台s s（2）排队系统的一般表示顾客到达，排队等待，服务机构给予适当 的服务以满足顾客的需求，顾客离开服务机构，这 四个环节便组成一个排队模型。排队论基本概念 3.2.12排队系统的基本参数(1) 顾客到达率 顾客到达率 是单位时间内平均到达排队系统的 顾客数量。任意相邻两顾客到达的时间间隔 是一个随机 变量。 的统计平均值 就是顾客到达的平均时间 间隔，其倒数即为顾客到

6、达率（3-22）排队论基本概念 3.2.1(2) 服务员数目 服务员数目 就是排队系统内可以同时提供服务 的设备或窗口数，它表征服务机构的资源。(3) 服务员服务速率服务员服务速率 指的是单位时间内由一个服务 员进行服务所离开排队系统的平均顾客数。系统的服务速率为 。设一个顾客被服务的时间为 ，它也是一个随机 变量。 的统计平均值 就是一个顾客被服务的平均 时间（即为单个服务员对顾客的平均服务时间）（3-23）3排队系统的三个特征排队系统在运行中包括三个过程：顾客输入过程排队过程顾客接受服务(然后离去)的过程 排队系统的特征，就是排队系统三个过程的特 征。输入过程这是指要求服务的顾客是按怎样的

7、 规律到达排队系统的过程，有时也把它称为顾客流 一般可以从3个方面来描述个输入过程。顾客总体数，又称顾客源、输入源。这是指 顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无 限的，而某个工厂因故障待修的机床则是有限的。顾客到达方式。这是描述顾客是怎样 来到系统的，他们是单个到达，还是成批到达。病 人到医院看病是顾客单个到达的例子。在库存问题 中如将生产器材进货或产品入库看作是顾客，那么 这种顾客则是成批到达的。顾客流的概率分布，或称相继顾客到 达的时间间隔的分布。这是求解排队系统有关运行 指标问题时，首先需要确定的指标。这也可以理解 为在一定的时间间隔内

8、到达K个顾客(K=1、2、) 的概率是多大。顾客流的概率分布一般有定长分布、二项分 布、泊松流(最简单流)、爱尔兰分布等若干种。随机变量 离散型随机变量 概率分布和概率分布图 数学期望和方差 常见离散型随机变量的概 率分布 二点分布 二项式分布 Poisson分布排队论基本概念 3.2.1(1)顾客到达的概率分布如果顾客的输入过程满足平稳性、稀 疏性和无后效性，称该输入为最简单流。满足下面3个条件的输入称为最简单流。(1) 平稳性 又称输入过程是平稳的， 指在长度为t的时段内恰好到达k个顾客的概率 仅与时段长度有关，而与时段起点无关。在 内有一个顾 客到达的概率为(2)稀疏性（简单性又称普通性

9、） 指在充分小的时段内最多到达一个顾客。在 内多于一个顾客到达的概率为 。（1）只与区间长度与起点无关。 （2）单位时间内顾客到达的概率为 。(3)无后效性。指在任意几个不相交的时间 区间内，各自到达的顾客数是相互独立的。过去现在将来当输入过程为最简单流时，在给定时间间隔内系统 有K个顾客到达的概率为 （3-24）式（3-24）称为泊松分布(poisson) 。EK=T, DK= T设 K为时间 内到达系统的顾客数则 K 为参数为 的Poisson过程的充要条件是 相继到达的时间间隔T服从相互独立的参数为 的负指数分布。 2/1,/1ll= KDTE对于Poisson流：单位时间平均到达的顾客

10、数顾客相继到达的平均间隔时间Poisson过程与负指数分布当输入过程为最简单流时， 的概率分布函数顾客到达间隔时间的概率密度函数为排队论基本概念 3.2.1典型分布 泊松分布 (平稳状态）如果顾客到达的人数是符合泊松分布， 0 为 单位时间平均到达的顾客数:P I = k = k e - / k! (k=0,1,2,) 在时间T内到达有k个顾客到达的概率为：P I = k = （T）k e-T/ k! ，在时间T内顾客到达的平均顾客数= T， 平均到达速度（顾客数/秒）= 例1：若某事件流是泊松流 ，求两个事件和 两个事件以上同时发生的概率。 解：根据泊松分布 ：P I = k = k e-/

11、 k! 两个事件和两个事件I 2，P（ I 2）= P（ 2）+ P（ 3）+ P（ 4） += 1- P（ 0）- P（ 1）=1- e- e-例2：设忙时每用户平均呼叫数= 4次/小时， 求在任意选定的30分钟内，出现5次或5次以上的呼 叫数的概率。 解：根据泊松分布 ：P I = k = (T)k e-T/ k! 已知： = 4次/小时，T=30m=0.5h, T=2 P（ I 5）= P（ 5）+ P（6）+ P（ 7）+= 1- P（ 0）- P（ 1）- P（ 3）- P（4）=1- e-T- (T)2e-T/2!-(T)3e-T/3!- (T)4e-T/4! =1-e-2- 22

12、e-2/2!-23e-2/3!- 24e-2/4! =0.3233 答：出现5次或5次以上的呼叫数的概率是0.3233(2) 服务时间分布:设某服务台的服务时间为V，其密度函数 为f（t），常见的分布有： （1）定长分布（D）：每个顾客接受服务的时间是一个确定的常数。 （2）负指数分布（M）：每个顾客接受服务时间相互独立，具有相互的负指数分布：其中 ，为一常数。- 单位时间平均服务完成的顾客数 1/ - 每个顾客的平均服务时间0.5m)=1-(1-e-t )= e-10x0.5=e- 5=0.0067例5：若电话呼叫的结束强度=1/10次/分钟， 通话时长的概率分布服从指数分布。如果有人刚好

13、在你前面占用了唯一的电话机，请问你将等待：1. 超过10分钟；2. 10分钟到20分钟之间的概率。 解：根据：指数分布P（T t ) = 1- e - t =0.1次/m, t1=10m,t2=20m 1.P(T10m)=1-(1- e- t ) = e- t = e -0.1x10=e-1=0.3682. P(20mT10m)=P(20mT)-P(T00为一常数。为一常数。 K K阶阶爱尔朗分布（爱尔朗分布（EnEn）：）：b(t)=k k ( (k k t) t)k-1k-1(K-1)(K-1)! !e e- k- k t t当当k=1k=1时即为负指数分布；时即为负指数分布；k k 30

14、, 30,近似近似 于正态分布。当于正态分布。当 k k 时，方差时，方差 0 0 即为完全非随机的。即为完全非随机的。排队论基本概念 3.2.14排队系统的几个主要指标及李特尔(Little)定律(1)排队系统的几个主要指标排队长度k (简称队长):即某时刻系统中顾客的数量，包括正在 被服务的顾客。 k 是一个离散随机变量，统计平均值 (即期望值) 为平均队长，用 N 表示。等待时间w : 指从顾客到达系统至开始接受服务的时间。w 是 连续随机变量，其统计平均值 为平均等待时间，用W 表示。服务时间 : 这是一个顾客被服务的时间，即顾客从开始被服 务起到离开系统的时间间隔。 的统计平均值 称

15、为平均服务时间 。排队论基本概念 3.2.1系统时间S : 这是顾客从到达系统至离开这段时间,也就是每 一个顾客在系统内所停留的时间。它显然包括顾客的等待时间和 服务时间，即S的统计平均值称为平均系统时间，用 S 或 表示，所以有（3-30）系统效率 ：这可定义为平均窗口占用率。（3-31）排队论基本概念 3.2.1稳定性： 也叫排队强度，用 表示，一般令若 1,即 m, 系统稳定。若 1,即 m, 系统不稳定。关于 的几点说明：顾客平均到达率顾客平均服务率一个顾客服务时间一个顾客到达时间服务强度即顾客的顾客平均到达率 小于顾客平均服务率时， 系统才能达到统计平稳。系统中至少有 一个顾客的概 率； 服务台处于忙 的状态的概率 ； 反映系统繁忙 程度排队论基本概念 3.2.1(2)李特尔(Little)定律对于一个平均到达率为的排队系统，在平均的意义上有（3-33）平均到达率为常数，平均服务时间常数1/，排队论基本概念 3.2.15排队系统的分类排队系统通常使用符号X/Y/m/n 表示。 其中 X 是顾客到达间隔时间的分布，Y 是服务时间的分布，m是服务员个数， n为排队系统中允许的顾客数，也称为截止队长。 如系统包括接受服务和等待共有 k 个位子，则 0k。当 k=s时，说