通信网理论基础(修订版)

《通信网理论基础(修订版)》由会员分享，可在线阅读，更多相关《通信网理论基础(修订版)（234页珍藏版）》请在金锄头文库上搜索。

1、第二章 网内业务分析,提纲,2.1 排队论基础 2.2 通信网的业务模型与分析 2.3 提高网效率的一些措施,2.1 排队论基础,由要求服务的顾客和提供服务的服务员双方构成的系统通常被称为排队系统。,节点,顾客,服务员,生活中的排队现象通信中的排队,研究这种系统的意义在于它的广泛性: 信息流与信道； 计算机的指令与总线 数据与中央处理单元 故障与维修等,资源的有限性和需求的随机性是排队现象存在的基础。,由于顾客到达和服务完毕的时间都是不确定的，绝大多数排队系统工作于随机状态。 这种随机性造成有时顾客排队时间过长，有时服务员却闲着；前者是服务质量的损失，后者是服务资源的浪费。 一个高效益的排队系

2、统应能为顾客提供满意服务的同时，尽量提高资源的利用率。这既与排队系统的统计参数有关，又与所选择的工作方式有关。,排队论的概念,排队论：即利用概率论和随机过程理论，研究随机服务系统内服务机构与顾客需求之间的关系，以便合理地设计和控制排队系统。,排队论所研究的问题有: (1)等待时间的分布,平均等待时间; (2)系统时间(也称逗留时间)的分布,平均系统时间及系统时间的方差(时延抖动);(3)在系统中的顾客数(也称系统占有数)的分布及均值; (4)等待顾客数的分布及其均值;(5)服务器忙着(或空闲)的概率; (6)忙期长度的分布及其均值; (7)在忙期被服务的顾客数的分布以及它的均值。,任何排队系统

3、都有3个参量m、l、m，称为排队模型三要素： 服务员数目m 顾客到达率 服务员服务速率,2.1.1 基本概念,顾客,服务者,服务员数目m m称为窗口数或服务员数目，表征系统的资源量，它表示系统中有多少服务设备可同时向顾客提供服务在计算机通信网中，m常指分组交换节点的输出信道数量等当m=1，可称为单窗口排队系统；当m1，就称为多窗口排队系统,排队模型三要素,10,顾客到达率 单位时间内平均到达排队系统的顾客数量 单位时间内平均到达分组交换节点的分组数量 反映了顾客到达系统的快慢程度， 越大，说明系统的负载越重,节点,顾客,服务者,排队模型三要素,11,顾客到达率 ti:任意相邻两顾客到达的时间间

4、隔，是一个随机变量：ti的统计平均值，表示顾客到达的平均时间间隔,排队模型三要素,如1分钟（60秒）到达顾客数为4人，则平均顾客到达的时间间隔就是(1/4)分钟，即15秒。,12,顾客到达率,排队模型三要素,13,服务员服务速率 单位时间内由一个服务员进行服务所离开排队系统的平均顾客数 对于m1系统， 就是系统的服务速率 对于m 1系统，系统的服务速率为m:任意相邻两顾客离开的时间间隔，是一个随机变量，即第i个顾客的服务时间：单个服务员对顾客的平均服务时间，也就是一个顾客在系统内接受服务的平均时间如1分钟（60秒）由1个服务员服务离开顾客数为4人，则平均一个顾客服务的时间为(1/4)分钟，即1

5、5秒。,排队模型三要素,Wi:第i个顾客等待时间(下降沿与上升沿之差) Ci:第i个顾客到达或离去时间 ti：第i+1与第i个顾客到达时间间隔,ti=(Ci+1-Ci)到达，上升沿之差 i:第i个顾客与第i+1个顾客离去的时间间隔，即第i个顾客的服务时间， i=(Ci-Ci-1)离去，下降沿之差,窗口数m、顾客到达率l和服务率m虽是排队系统的3个基本参数，要充分描述排队系统并分析其运行状态还是不够的，因为排队系统的性能主要取决于顾客到达时间间隔ti与服务时间ti的统计分布和排队规则。 对于一般的统计分布，迄今还不易得到解析结果。通常最常用的分布是指数分布，它能导致排队过程成为马尔可夫（Mark

6、ov）过程，许多问题易于得到解析结果，而这种分布也是与实际排队问题中的一大类相近。,常见排队系统的一般假设 平稳性：在时间间隔t内，到达k个顾客的概率只与t的长度有关，而与这间隔的起始时刻无关。无后效性：顾客到达时刻互相独立，即顾客各自独立地随机到达 在互不重叠的时间段内，顾客到达的概率相互独立，即不同t内顾客到达的概率无关疏稀性：在无限小时间间隔t内，到达2个或2个以上顾客的概率为零，且在有限时间内到达的顾客数是有限的 即：在t内只有一个顾客到达或没有顾客到达,满足以上三个条件的随机流称为简单流. 简单流的到达间隔是负指数分布的 且在一段时间内到达的顾客数是泊松分布.,证明简单流的到达间隔是

7、负指数分布:,设为到达间隔为t,把t分成N等份,每份的长度 根据无后效性和稀疏性，在前面N个 内无顾客到达，再一个 内有一个顾客到达的概率为（其中，a(t)为概率密度）： ：,tt内到达1人的概率 1-tt内到达无人到达的概率tt内离去1人的概率 1-tt内无人离去的概率,证明简单流的到达间隔是负指数分布:,所以在上述三个假设下的简单流的顾客到达间隔是负指数分布，其概率密度为：,再证明当到达间隔是指数分布时,在时间间隔T内的到达数是普松分布:把时间间隔T分成N等份,在这N个小区间内, k个顾客可在N个 中任意k个 中 到达:,T:顾客到达时间间隔，0T,概率分布函数,表示在时间t内有顾客到达的

8、概率,在时间t内没有顾客到达(k=0)的概率即为,如果将T看成是数轴上的随机点的坐标，那么，分布函数FT (t)在t处的函数值就表示T落在区间(-,t上的概率,因为概率密度 积分即为分布函数，所以也可以由下式得到分布函数：表示T落在区间(-,t上的概率是1-e-t,所以，对于最简单流有：,顾客到达时间间隔分布 在T期间内有k个顾客到达的概率符合泊松（Poission）分布，即,顾客在T时间间隔内到达k个的概率,泊松分布参数，单位时间内顾客到达数,在T时间内顾客到达的个数,对于最简单流有：,在一段时间内,电话的呼叫是简单流,因为 顾客的到达数与时间起点无关;顾客的到达 时刻相互独立;在很短的时间

9、间隔内到达两 个以上顾客的概率可认为是0.,服务时间分布,把上述假设用于服务过程，有类似结果 即假设服务相继两个顾客所需要的时间也是互不相关、平稳和稀疏的，则： 服务时间t服从负指数分布，其概率密度为在T期间内有k个顾客被服务后离去的概率服从（Poission）分布，即,排队系统表示符号： ABm(N,n),A 顾客到达时间间隔分布， 分布a(t) B 服务时间分布， 分布b() m窗口数 N顾客源，潜在顾客数，省略为 n截止队长，省略为，不拒绝,A和B可以分别填入M、Er、Hr、D和G等，其中G表示任意分布,M分布,输入过程对应的是顾客到达间隔时间的分布函数，服务过程对应的是服务时间的分布函

10、数，如果为上述指数分布，称为M分布指数分布所导致的排队过程具有马尔可夫（Markov）性，所以可称为M分布。（马尔柯夫最基本的性质是无后效性，顾客之间的到达是随机的）,M指数分布,MMm(n)顾客到达时间间隔和服务时间都服从指数分布,m个服务窗口，截止队长为n,Er分布,Er分布是r阶厄朗分布，适用于成批处理的排队问题，如顾客到达积累成r个时作为一批，再进入排队系统，或处理r个任务后作为一批送出时。或每秒平均到达批，则前后两批之间的间隔时间t的概率密度函数为：,当r=1，就是前面的指数分布：,D分布,即在t=1/时为，其他时候为0，并且从-到+积分，结果为1.每隔1/秒来一个顾客（如分组交换）

11、或每个顾客服务时间固定都可以用D分布描述 如包交换系统中，包长是常量，服务时间是固定值，则用D分布是恰当的。,Er分布中，当r时，为单元脉冲函数,说明时间间隔t是固定,的 值：常称为D分布或确定性分布：,成批处理 r批人数，有r人一起进入排队系统，或处理后r个一批送出 批到达率 r-顾客到达率 t 批间隔， a(t)批间隔t的概率密度函数（r=1，即为指数分布（EM） 当r ,a(t)=(t-1/), 确定型分布, 等间隔进入,称D分布,Er阶厄朗分布（Erlang）,Er、D分布,HR分布,当到达的顾客有R类，各类的平均到达率不相同，分别为1，2，, R，各类顾客所占的比例分别为1， 2，,

12、 R，当这些顾客混合排队时，就可得到如下分布：,且有,R=1，则HRM,排队系统的工作方式,排队系统的运行性能不仅与上述的统计分布有关，还与系统预先规定的工作方式有关。排队规则是指服务机构是否允许排队服务规则是指在排队等待情形下服务的顺序是什么。,排队系统的工作方式,按服务规则划分有： 先到先服务：按顾客到达先后，顺序服务，这是常见情况，无其他说明时，常按这种方式分析。 后到先服务：这是不常见情况，也可能出现，如仓库中同品种的货物，出库时常是后进先出。 优先制服务。对各类顾客分别事先赋予不同的优先级，优先级愈高，愈提前被服务。通信网中也较为常见。 还有随机服务等。,n为顾客数，m为窗口数。 顾

13、客到达时，如果所有服务窗口m均被占满 等待制系统（不拒绝方式）允许排队，且队长没有限制，但应满足稳定性要求，即排队强度：截止型，即时拒绝方式立即遭到拒绝，即服务机构不允许顾客排队等待（m=n,电话通信网常采用） 即除了m个正在服务的人外，系统不允许有其他人排队截止型，延迟拒绝方式允许排队，但队长有限制。（mn,带缓冲存储的数据通信就属于这一类） 即除了m个正在服务的人外，还允许n-m个人排队,排队系统的工作方式-排队规则,排队系统的主要性能指标 （1 ）排队长度k （2）等待时间w （3）服务时间t （4）系统时间s （5）系统效率h （6）稳定性,排队系统的主要性能指标 （1）排队长度k 简

14、称队长，是某时刻观察系统内滞留的顾客数，包括正在被服务的顾客。 k是非负的离散随机变量，需用概率来描述，通常有以下3种观察方式： pk: 随机地取t时刻来观察队长为k的概率。 rk: 顾客到达时刻所观察到的人数（不包括刚刚到达的顾客）为k的概率。 dk: 顾客被服务完毕将离开时所看到人数为k的概率。,排队长度k 一般pk、rk、dk三者是不同的；对于顾客到达规律具有前述的马尔可夫性的系统，则pk=rk 。 此外，当每瞬间到达人数或离去人数只能是一人时，则rk=dk。 满足疏稀性时，只要顾客到达是泊松流，就有pk=rk=dk。 上述参数都是指队长为k的概率k的统计平均值 称为平均队长。,排队系统

15、的主要性能指标,排队系统的主要性能指标,（2）等待时间w 顾客到达至开始被服务的这段时间，是连续随机变量，其统计平均值 称为平均等待时间。越小越好在通信网中， 是信息在网内的平均时延的主要部分，其他时延如传输时间、处理时间等一般均为常量，而且一般比较小。,排队系统的主要性能指标,（3）服务时间t 顾客被服务的时间，即顾客从开始服务至离开系统的时间间隔，其统计平均值 称为平均服务时间。为单个窗口平均服务的顾客数（平均服务速率）,排队系统的主要性能指标,（4）系统时间s 顾客从到达系统至离开系统的这段时间，又称为系统内停留时间，其统计平均值 称为平均系统时间。,系统时间=等待时间+服务时间,排队系

16、统的主要性能指标,（4）系统时间s：列德尔（Little）公式,称为列德尔（Little）公式（适用于任何排队系统）,一个平均到达率为的排队系统，在平均意义上有：,Little,即：在排队系统中的平均顾客数=顾客的平均到达率平均逗留时间:,主要性能指标,（5）系统效率h 定义为平均窗口占用率。某时刻t有rt个窗口被占用，若共有m个窗口，则rt/m就是占用率。显然，rt/m是一个随机变量，它的统计平均值就是系统效率，即h愈大，服务资源的利用率愈高。,主要性能指标,（6）稳定性 对于不拒绝系统，当到达率与服务率之比大于窗口数时，平均顾客到达数将大于平均顾客离去数，顾客的队长将愈来愈长，平均等待时间趋于无限大，系统陷于混乱，将不能稳定工作。 令排队系统的强度r为：对于截止型系统，因为队长被人为地限制，即使rm，系统仍能稳定地工作。,